Heaps, Backtracking, Dynamic Programming, Graphs

Heaps -1

• Heap
• Data structure which can give getMin/extractMin & insert in logN TC
• It is a Complete Binary Tree
• Height is always logN
• Nodes in last level will be ~ N/2
• Min or Max Property
• Value of the node must be greater(max heap)/smaller(min heap) than both LST & RST
• Store heap in an array
• Space saving by removing left/right pointers
• Move from Parent/child in O(1) 
• last index can be found in O(1)
• Convert Array to min Heap
• Approach1: Sort the array O(N log N)
• Approach 2: Insert into heap 1 by 1 ->TC: O(N)
• Approach 3: Insert elements from bottom up : TC: O(N)
• Heap in Java is Priority Queue

• Magician and Chocolates: Given N bags, each bag contains Bi chocolates. There is a kid and a magician. In a unit of time, the kid can choose any bag i, and eat Bi chocolates from it, then the magician will fill the ith bag with floor(Bi/2) chocolates. Find the maximum number of chocolates that the kid can eat in A units of time.

• Solution: Max Heap, poll max element & add half back to heap

• Amz, MS, Paypal
• Connect Ropes: You are given an array A of integers that represent the lengths of ropes. You need to connect these ropes into one rope. The cost of joining two ropes equals the sum of their lengths.
  Find and return the minimum cost to connect these ropes into one rope.
• Optimal Strategy: Always pick 2 rows of min possible size using heap, and add the sum to the heap
• TC: O(N logN) for sorting + O(N^2) for insertion
• Product of 3: Given an integer array A of size N. You have to find the product of the three largest integers in array A from range 1 to i, where i goes from 1 to N.

  Return an array B where B[i] is the product of the largest 3 integers in range 1 to i in array A. If i < 3, then the integer at index i in B should be -1.

• Strategy: Heap[3] with min on top. Heapify when new val is > heap[0]

• Maximum array sum after B negations: Given an array of integers A and an integer B. You must modify the array exactly B number of times. In a single modification, we can replace any one array element A[i] by -A[i].

  You need to perform these modifications in such a way that after exactly B modifications, sum of the array must be maximum.

• B Closest Points to Origin: We have a list A of points (x, y) on the plane. Find the B closest points to the origin (0, 0). Here, the distance between two points on a plane is the Euclidean distance. You may return the answer in any order. The answer is guaranteed to be unique (except for the order that it is in.)

  NOTE: Euclidean distance between two points P1(x1, y1) and P2(x2, y2) is sqrt( (x1-x2)2 + (y1-y2)2 ).

• Misha and Candies: Misha loves eating candies. She has been given N boxes of Candies.

  She decides that every time she will choose a box having the minimum number of candies, eat half of the candies and put the remaining candies in the other box that has the minimum number of candies.
  Misha does not like a box if it has the number of candies greater than B so she won't eat from that box. Can you find how many candies she will eat?

  NOTE 1: If a box has an odd number of candies then Misha will eat the floor(odd / 2).

  NOTE 2: The same box will not be chosen again.

• B-th Smallest Prime Fraction: Given a sorted array of integers A which contains 1 and some number of primes.

  Then, for every p < q in the list, we consider the fraction p / q.

  What is the B-th smallest fraction considered?

  Return your answer as an array of integers, where answer[0] = p and answer[1] = q.

• Kth Smallest Element in a Sorted Matrix: Given a sorted matrix of integers A of size N x M and an integer B.

  Each of the rows and columns of matrix A is sorted in ascending order, find the Bth smallest element in the matrix.

  NOTE: Return The Bth smallest element in the sorted order, not the Bth distinct element.

Heaps-2

• Heaps & Priority Queues
• K smaller elements
• Sorting: TC: NlogN  SC: depends on sorting algorithm O(N) or O(logN)
  
• Min Heap Approach:
• create min heap
• keep extracting min K times
• TC: O(N) + O(K logN)
• SC: O(1)  O(N) incase we should not change input array
• Max Heap
• Create max heap of first K elements ->O(K) operations
  
• Iterate over remaining N-K elements
    if (A[i]<heap.top()){
       extract Max  -> O(logK)
      insert(A[i]  -> O(logK)
  }
• TC: O(K) + O(N-K)* logK)
• SC: O(K)
• 
  
•  Given an Array, with nearly/K sorted array. Every element is almost K positions away from its sorted position.(actual index - sorted index)<=k
  
• Create heap of size K+1
• for each of the other element, 
• extract min from heap
• insert next element & heapify
• TC: O(K) + O(N-K)
• Heap Sort: Given an array, sort it inplace
  
• Bubblesort, insertion sort, selection sort TC: O(N^2) & SC:O(1)
  
• Create max Heap
• Extract Max and add to end of array. Repeat for every element.
  
• TC: O(N) + O(N logN) SC: O(1)
• Draw backs;
• Heap creationO(N) is overhead compared to Mergesort/quicksort
• when the input size is high, then it will add to perf
• Given a stream of integers, find the median with every insertion
• Brute force: O(N * N logN)
  
• sort on every insertion
• if count is odd -> return mid else return avg of mid elements
  
• Insertion Sort: O(N^2)
• Optimized approach
• Divide elements into 2 groups
• if number of elements are even -> return avg(max from left group, min from right group)
• if number of elements are odd and left has extra element -> return max(left)
  else return min(right)
• How to divide elements
• if new num> median then move to right else left
• if elements in left are more then move max to Right and vice versa
• TC: N logN  SC:

Greedy Algorithms - Problems which require sort the input based on certain property and select the input from min to max to solve the problem.

• Reduce overall cost
  
• Fractional Knapsack: Given N items along with total weight of item & cost associated with item. Given a bag of capacity W, Pick some items such that the value in the bag is maximized.
  
• Constraint: Either select all or select none -> 0/1 Knapsack
  
• Steps
• Sort all items based on per unit cost
• iterate, pick the best and keep updating the bags capacity
• Paypal: Given N jobs to be formed. For every job, start time and end time is given. Constraint it to perform only one job at any time.  Find the max no of jobs that we can perform. 
• Soln:
• Every time - select job with least end time from the list
  
• count=1;
  lastEndTime=E[0];
  for(i: 1:n-1){
      if (S[i]>= lastEndTime){
            count++;
            lastEndTime=E[i];
            
• TC: O(N logN) + O(N) ~ O(NlogN)

Heaps Followup

• Given N distinct integers. Find the number of ways to form a max heap
• Observations
• root node is fixed(max element)
• Structure for N is also fixed(complete binary tree)
• No relation between left & right sub-trees
• We simply need to compute the total number of ways to divide the remaining N-1 elements between LST & RST
• Goal: #elements in LST
• L+R=N-1
• L>=R
• Height of tree=floor(logN)
• Total number of elements in all the levels except the last level
• 2^0 + 2^1 + 2^2+2^3....+ 2^H-1  -> Geometric progression
• 2^H - 1
• #elements in last level is N - (2^H - 1)
• Elements in Left sub tree = min(2^(H-1) , N-(2^H - 1))
• #Elements in the LST
  
•  No of max heaps = N-1 C L * number of max heaps(L) * number of max heaps(R)
•  Code
• int noOfMaxHeaps(int N){
      if (N<=2) return 1;
     int H =  logN;
     int x = 2^H - 1;
  int L =     (x-1)/2 + min((x+1)/2, N-x);
  int R = (N-1)-L;
  int ans = N-1 C L * No of max heaps (L) * No of Max heaps(R);
   return ans;
  }
• Given a Binary Tree, flatten it(change to Linked List representing preorder traversal)
  
• Code
• Node flatten(root){
     if (root==null) return null;
     Node l = flatten(root.left);
     Node r = flatten(root.right);
     root.left=null;
    if (l<>null) {
       root.right=l;
       while (l.right != null) l=l.right;
       l.right=r;
      } else {
      root.right=r;
      return root;
   }

Backtracking - 1

• Trying out all possibilities(same as brute force)
  
• Q: Print all N digit numbers using 1 & 2
•  void generate(n, index, currlist){
    if (n==index) print currlist;
  
  currlist[index]=1;
  generate(n,index+1,currlist);
  currlist[index]=2;
  generate(n,index+1,currlist);
  }
• TC: O(N * 2^N)  
• time complexity of single call is O(N) as we are printing list
• 2^N function calls
  
• Depth is N
• recursive calls is 2^N (similar to fiboncci series where every function invokes recursion twice)
• Q: Print all N digit numbers using 1, 2, 3, 4, 5
• O(N 5^N)
• Q: Given an array, Generate all subsets
• getAllSubsets(currlist[],index, A[], list<list<int>> ans){
     if (index==A.size()){
        ans.add(currlist);
        return;
     }
      currlist.add(A.index);
      getAllSubsets(currlist,index+1,A,ans);
      currlist.pop();  //delete the last added element
      getAllSubsets(currlist,index+1,A,ans);
  }
• TC: O(N 2^N)
• SC: Recur stack+curr list = O(N) + O(N) ~ o(N) excluding output
  
• Q: Count subsets with count K
• Q: Given an array, print all permutations of an array. (no duplicates in input)

Backtracking-2

• Q: RAT in a maze: Given a maze(2D matrix) and initial location of mouse(x,y). Return true if there exists a path from mouse to the cheese.
  mat[i][j]=0 then non-blocked
  
• boolean mazeSolve(matrix, n,m,x,y){
  if (x==n-1) && (y==m-1)  return 1; //cheese it always last cell of maze
  if (x<0) or (y<0) or (x>=N) or y>=M) return 0;
  if (matrix((x,y)==1 or matrix((x,y)==2 return false;
  matrix(x,y)=2;
  ret mazeSolve((matrix, n,m,x+1,y) OR ( mazeSolve((matrix, n,m,x,y+1))
  OR mazeSolve((matrix, n,m,x-1,y) OR ( mazeSolve((matrix, n,m,x,y-1));
• TC: O(N^2), SC:
  
•  Q: RAT in a maze(Collect all cheese). Given a start point, end point, blocked cells, cells filled with cheese, Count the number of paths from start to end such that rat can eat all the cheese available in the maze with out stepping on same cell twice(or more than once) in a single path.
    Cheese - 0, blocked - 1, empty - 2, start si,sj, end ei, ej
  
• int countPaths(mat,N,M,si,sj,ei,ej,cheeseTotal,cheesecurr){
      if (si<0) or (sj<0) or (si>=N) or sj>=M) return 0;
      if (mat[si][sj]==1) return 0;
      if (si==ei && sj==ej) {if cheesetotal==cheesecurr)  return 1; else return 0;
     int temp=mat[si][sj];
     mat[si][sj]=-1;
     int ans=countPaths(mat,N,M,si-1,sj,ei,ej,cheeseTotal,cheesecurr)+
                  countPaths(mat,N,M,si+1,sj,ei,ej,cheeseTotal,cheesecurr)+
                  countPaths(mat,N,M,si,sj-1,ei,ej,cheeseTotal,cheesecurr)+
                  countPaths(mat,N,M,si,sj+1,ei,ej,cheeseTotal,cheesecurr)
     mat[si][sj]=temp;
    return ans;
  }

Dynamic Programming

• Making use of something that you already Calculated - eg: using prefixsum
• Fibnocci series - recursion program
• number of function calls is max of 2^N
• Unique functions calls are only N
• int dp[N+1] = {-1}
  int fib(N){
      if(dp[N]==-1){
             if (N<1)  dp[N]=N;
         } else {
             dp[N] = dp[N-1]+dp[n-2]
      }
    }
    ret dp[N]
  }
• All function calls are repeated atmost 2 times. So time complexity is O(N)
• This is Top-Down DP or DP with memorization
• int fib(N){
     a=0, b=1;
     for(i=2; i<N;i++){
           c=a+b;
           a=b; b=c;
        }
  }
• 
  
• What does DP require -> go for Dynamic Programming
• Optional sub-structures -> recursion
• Overlapping sub-problems -> Repetition of function calls
• Something that is calculated once, should not be repeated again. Instead store in memory structure and reusing is called Dynamic Programming.
  
• Number of ways to reach Nth step from 0th step. Given that from any ith step you can either go to i+1 or i+2 step
  
• Soln1: Similar to backtracking -> where a person has 2 possible ways from a given step
• Soln2: Same as Fibonacci series  
• Path[A-Z]=Path[b-z] + path[c-z]
• Path[N]=Path[N-1] + path[N-2]
• 
  
• int dp[N+1] = {-1}
  int fib(N){
      if(dp[N]==-1){
             if (N<=1)  dp[N]=N;
         } else {
             dp[N] = dp[N-1]+dp[n-2] 
      }
    }
    ret dp[N]
  }
• House Robber: Given an array of +ve numbers, return the max sum with out including any adjacent numbers
• Approach1: max(sum of odd indexes, sum of even indexes)
• wrong when one odd and one even have high sums
• Approach2:
• Every house one decide to rob or not to rob. If decided to rob then you have N-2 choices else N-1 choices
• money from first N houses = max (A[N-1]+money(N-2), money(N-1)
• Money(N) returns the max amount that can be robbed in first N houses
• Similar to fibonocci series with slight change
•  dp[N] = max(dp[N-1], a[n-1]+dp[n-2]) 
• Bottom up/iterative
• dp[i] = max(a[i-1] + dp[(i-2) , dp[i-1])

 Dynamic Programming -2

• Ways to decode: Each alphabet is marked with a interger starting from 1.(A-1, B2.. Z-26). Given the string of digits count the number of ways of decoding.
• Consider ith digit as single digit
• if it is possible to couple with i-1 digit then consider as 2 digit number
• ways(i) -> ways of decoding the string from index 0 to i
• ways(i-1)+ways(i-2)
  i=3 => ways(2) + ways(1)
  i=2 => ways(1) + ways(0)
  i=1 => ways(0) + ways(-1) //-1 is valid
• Base Case: if (i==0) { //index 0 to 0. len=1
                            return a[i]>0?1:0
                            }
                     if (i==1) { //index 0 to 1. len=2
                           ans=0
                           if (possible to consider both as single digits)     ans++
                           
                            if (possible to consider both as single digits)    ans++
                     } 
                  return ans;
• Ways to Party: N number of people in hall. Person can enjoy in 2 ways - Being alone OR getting Paired with someone. Return number of ways in which Party can be enjoyed.
•  Ways(N) = Ways(N-1) + (N-1) * Ways(N-2)
• Base Case: 
• if (i==1) return 1;
  if (i==2) return 2;
• Given a 6 face dice, count the number of ways to get a required sum N, if you can throw the dice as many times as you want
• sum(ways(n-1)+ways(n-2)+ways(n-3)+ways(n-4)...+ways(1))
  
• Base Condition
• if (

Dynamic Programming-3

• Given a 2D matrix N*M, count number of unique paths to reach N-1,M-1 from (0,0). From any cell one can move right or down
• Number of paths from (0,0) to (i,j) is
   paths(0 to (i,j)) =  paths(0 to (i-1,j)) + paths(0 to (i,j-1))
   paths(i,j) =  paths(i-1,j) + paths(i,j-1)
• recurrsion
• Base case
• if ((i<0) or (j<0)) return 0;
  
  if ((i==0) or (j==0)) return 1;
  
  paths(i-1,j) + paths(i,j-1) 
• Total nodes in tree - O(2^N)
• Total Unique fun callsO(N*N)
  
  
Interative 
• dp[i][j]=dp[i-1][j]+dp[i][j-1]
  
• Given a 2D grid with some values. Return the min path sum from start (0,0) to end (N-1, M-1)
• minPaths(i,j) =  min(minPaths(i-1,j) , minPaths(i,j-1))+A[i][j];
  
  
• Dungeon Princess:  +ve numbers improve your health and -ve numbers detoriate. If the health becomes <=0 then you are dead. What is the min amount of health you should start the iteration so that when you reach princess you are in living condition.
• x+A[i][j] >= min(dp[i+1][j], dp[i][j+1])
• dp[i][j] is the min amount of energy required before stepping into (i,j) for reaching the princess alive
• 
  

Dynamic Programming-4

• LCS(Longest Common Subsequence)
• Given 2 strings, find the length of LCF between the strings.
• int lcs(sa,la,sb,lb){
    if (dp[la][lb]==-1{
    if (la==0 || lb==0) (dp[la][lb]=0; return 0;}
  else {
      if (dp[i][j]==sb[lb-1]) return 1+ lcs(sa,la-1,sb,lb-1);
      esle dp[i][j]= max(lcs(sa,la-1,sb,lb),lcs(sa,la,sb,lb-1) )
  }
  return dp[la][lb];
•  TC : 2^n which is reduced by Dynamic programming approach to O(NM)
• Iterative/Bottom Up
• dp[la+1][lb+1]
  if (sa[i-1] == sb[j-1])
  
  dp[i][j] = 1+ dp[i-1][j-1] ;
  
  else dp[i][j] = max (dp[i][j-1], dp[i-1][j]);
• Edit Distance
• Given 2 strings sa & sb. Conver sa to sb in min possible paths. Three operations can be performed on sa, insert with cost i, delete with cost d, update with cost u.
  
• mincost(la, lb){
      if (sa[la-1]==sb[lb-1])  return  mincost(la-1,lb-1);
      else {
        min( costD + mincost(la-1,lb), costI+ mincost(la,lb-1), costE+mincost(la-1,lb-1));
• Given two strings A & B. Count the number of unique ways, in which we can get stringB as a subsequence of String A.
• int cont(la, lb){
      if (lb==0) return 1;
      if (la==0) return 0;
       if (sa[la-1]!=sb[lb-1]) return count(la-1,lb);
       else return count(la-1,lb-1) + count(la-1,lb);
• Memoization
• Iterative solution
  

Dynamic Programming 5

•  Wild card matching - Return true if wild card string sb matches to string sa.
  
• if (la==0) && (lb==0) return true;
  if (lb==0) return false;
  if (la==0)
       if (sb[i] =='?' or [a..z] return false;
      if (sb[lb-1] =='*') return isMatch(la,lb-1); else return false;
  
  if (sb[lb-1] in (a-z))
      if (sb[lb-1] == sa[la-1]) return isMatch(la-1, lb-1);
  
  if (sb[lb-1] in '?') return isMatch(la-1, lb-1);
  
  if (sb[lb-1] in '*') return isMatch(la-1, lb) || isMatch(lb, la-1);
• TC & SC is O(MN) after memorization
• Longest Palendromic subseqence
• Approach1
• return LCS(s, reverse(s));
• TC & SC is O(N^2)
• Approach2
• int lps(String S, int i, int j){
    if (i>j) return 0;
    if (i==j) return 1;
      if S[i]==S[j] return 2 + lps(i+1, j-1);
  else
      return max(lps(i+1, j), lps(i, j-1));
• #function calls in recursive tree is O(n^2)
  #unique fn calls O(n^2)
• dp[i][j] is length of LPS in sub string from index i to j
• Iterative approach
• 
  

Dynamic Programming 6

•  KnapSack
• Given N items each with a weight & a value. Find the max value that can be obtained by picking items such that total weight of all items being picked is <=K.
• int knapsack(w[], v[], N, K){
     if (N<0 || k<0) return 0;
    if (w[N-1] <=k)
       int ans= max(knapsack(w[], v[], N-1, K-w[N-1])+v[N-1], knapsack(w[], v[], N-1, K));
  else ans = knapsack(w[], v[], N-1, K);
  return ans;
  }
• Iterative approach
• dp[n+1[k+1]
  if (i==0) dp[0][j]=0;
  if(j==0) dp[i][0] =0
   dp[i][j]=max(dp[i-1][j], dp[i-1][j-(w-1)]+v[i-1]);
• Unbounded Knapsack
• One specific item can be picked as many times as we want.
• dp[i][j]=max(dp[i-1][j], dp[i][j-(w-1)]+v[i-1]);
   

Dynamic Programming 7

• Word Break
• Given a Dictionary(List of valid words) & a word(without spaces). Check if it is possible to breakdown the complete string into valid words from the dictionary.
• WordBreak(s, e){    //return true if it is possible to break substring from s to e
  dict ={};
  Boolean WordBreak(s,e,Str){
    if (s==str.length()) return true;
  
       for (i: s..e){
           if (isValidWord(String (s:i))  && WordBreak(i+1, e, str)) {
              return true;
           }
  return false;
  }
• Memorization
• DP[i] store true if it is possible to break the string from i to last index
• 
  
• Palindrome partitioning
• Given a string, return min number of partitions required such that every partition is a Palendrome.
•  
• Matrix chain multiplication
•  Given N matrix in a sequence such that it is possible to multiply. Return min number of multiplications required to multiply all the matrix
• minMul(s,e) = minMul(s,i) * minMul(i+1,e) + r[s]*c[i]*c[e];

Advanced DSA : Problem solving session on DP

• Repeating Subsequence
• Given a string, find if there is any subsequence that repeats itself
• 
   
• Max rectangle in a binary matrix
• Interchanging string
• Russion doll envelopes
   

Graphs-1

• Graph is a network/collection of which has nodes & edges
• examples
• Cloud computing (networks & computers)
• Website(pages & links)
• Social Media(user & connections)
• GPS(Google Maps)
• Project Management Tool(Maven + Java)
• Facebook - friend relation is undirected graph
• Scaler -classroom is directed graph
• Classification
• Directed vs undirected graph
• Weighted vs UnWeighted graphs
• Cyclic Graph - Reach back to node with out repeating any edge
• Connected component - Every vertex should be reachable from every other vertex
• Adjacency Matrix[V, E]
  
• Number of edges in non-directional graph is
• Vc2 = v * (v-1)/2 ~ O(V^2)
• For directed graph max= Vc2 * 2 = v* (v-1)
• list<lists>
• list<pair<u,v>>
• Path in Directed Graph: Given an directed graph having A nodes labelled from 1 to A containing M edges given by matrix B of size M x 2 such that there is a edge directed from node B[i][0] to node B[i][1]. Find whether a path exists from node 1 to node A. Return 1 if path exists else return 0. 
• First Depth First Search: You are given N towns (1 to N). All towns are connected via unique directed path as mentioned in the input. Given 2 towns find whether you can reach the first town from the second without repeating any edge. Input contains an integer array A of size N and 2 integers B and C ( 1 <= B, C <= N ). There exist a directed edge from A[i] to i+1 for every 1 <= i < N. Also, it's guaranteed that A[i] <= i for every 1 <= i < N. 
• Number of islands: Given a matrix of integers A of size N x M consisting of 0 and 1. A group of connected 1's forms an island. From a cell (i, j) such that A[i][j] = 1 you can visit any cell that shares a corner with (i, j) and value in that cell is 1. Return the number of islands. 
  
• 
  

Graphs-2 

•  BFS(Breadth First Search)
  
• TC: O(v+e) where v is vertices and e is edges
• DFS(Depth First Search)
  
• Select one neighbour of the source
• explore path completely
• backtrack and explore other paths
• TC: O(v+e)
• Given an N*M matrix, with a source and destination. Find the shortest path from given source to given destination.
• For shortest path always use BFS
• Q: Given a 2D matrix, with cells marked as R(Residence) & H(Hospital). For every residence, find the distance to nearest hospital.
• Rotten Oranges: Given a matrix of integers A of size N x M consisting of 0, 1 or 2. The value 0 representing an empty cell. The value 1 representing a fresh orange. The value 2 representing a rotten orange.

  Every minute, any fresh orange that is adjacent (Left, Right, Top, or Bottom) to a rotten orange becomes rotten. Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1 instead.

• Coloring a Cycle Graph: Given the number of vertices A in a Cyclic Graph. Your task is to determine the minimum number of colors required to color the graph so that no two Adjacent vertices have the same color.
• Check Bipartite Graph: Given a undirected graph having A nodes. A matrix B of size M x 2 is given which represents the edges such that there is an edge between B[i][0] and B[i][1]. Find whether the given graph is bipartite or not. A graph is bipartite if we can split it's set of nodes into two independent subsets A and B such that every edge in the graph has one node in A and another node in B 
• Construct Roads:  A country consist of N cities connected by N - 1 roads. King of that country want to construct maximum number of roads such that the new country formed remains bipartite country. Bipartite country is a country, whose cities can be partitioned into 2 sets in such a way, that for each road (u, v) that belongs to the country, u and v belong to different sets. Also, there should be no multiple roads between two cities and no self loops. Return the maximum number of roads king can construct. Since the answer could be large return answer % 10⁹ + 7.
  NOTE: All cities can be visited from any city.
• Cycle in Undirected Graph: Given an undirected graph having A nodes labelled from 1 to A with M edges given in a form of matrix B of size M x 2 where (B[i][0], B[i][1]) represents two nodes B[i][0] and B[i][1] connected by an edge.Find whether the graph contains a cycle or not, return 1 if cycle is present else return 0.
• Valid Path: There is a rectangle with left bottom as (0, 0) and right up as (x, y). There are N circles such that their centers are inside the rectangle. Radius of each circle is R. Now we need to find out if it is possible that we can move from (0, 0) to (x, y) without touching any circle. Note : We can move from any cell to any of its 8 adjecent neighbours and we cannot move outside the boundary of the rectangle at any point of time.
  
• Distance of nearest cell: Given a matrix of integers A of size N x M consisting of 0 or 1. For each cell of the matrix find the distance of nearest 1 in the matrix. Distance between two cells (x1, y1) and (x2, y2) is defined as |x1 - x2| + |y1 - y2|. Find and return a matrix B of size N x M which defines for each cell in A distance of nearest 1 in the matrix A.

  NOTE: There is atleast one 1 is present in the matrix.

Graphs-3

• Given an undirected graph, check if there exists a cycle or not
• Topological sort: Linear ordering of the nodes such that if there is a path from i to j, then i is on the left of j in the linear ordering.
  
• Given an N dependent jobs. Find out the order in which we can perform these jobs.
• This is possible only with Directed acyclic graph(DAG)
• Topological sort
• Linear ordering of the nodes such that if there is a path from node I to J, then I is on the left hand side of J in the linear ordering.
• ways
• using indegree -> # of incoming edges
•  how to find indegree
• using indegree
• using outdegree(stacks)
• Cycle in Directed Graph: Given an directed graph having A nodes. A matrix B of size M x 2 is given which represents the M edges such that there is a edge directed from node B[i][0] to node B[i][1]. Find whether the graph contains a cycle or not, return 1 if cycle is present else return 0.
• Reversing Edges: Given a directed graph with A nodes and M edges. Find the minimum number of edges that needs to be reversed in order to reach node A from node 1.
  
• Clone Graph: Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

Graphs-4

•  Given a unweighted graph, find the min distance from a source node to all other nodes.
• BFS traversal from source node
  
• TC: O(V+E)  & SC: O(V)
  
• Dijikstra's Algorithm: Given a weighted undirected graph having A nodes and M weighted edges, and a source node C. You have to find an integer array D of size A such that:
  => D[i] : Shortest distance form the C node to node i.
  => If node i is not reachable from C then -1.

  Note: There are no self-loops in the graph. No multiple edges between two pair of vertices. The graph may or may not be connected. Nodes are numbered from 0 to A-1.
  

• Floyd Warshal Algorithm(All possible shortest path algorithm)
• Find min distance to reach any node from any node
• Initial direct distances( Adjacency matrix) is given- consider it as D0 matrix
  
• Consider every node as intermediate node and change the matrix
• consider node1 as intermediate node and construct D1 matrix(means travel to other nodes via node1)
  
• eg: D[2][3] = D[2][1]+ D[1][3]  // go to node 1 from 2 & from node1 to 3
• 
  

Graphs-5

• Floyd Warshal Algorithm: All possible shortest path algorithm)
  
• D-> initial adjacency matrix
  for(k=0;k<N;k++){
    for(i=0;i<N;i++){
     if(i==k) continue;
     if (D[i][k] == INT-MAX) continue;
      for(j=0;j<N;j++){
         if (j==k) continue;
         if (i==j) continue;
         if (D[k][j] == INT-MAX) continue;
        D[i][j]= min(D[i][j], D[i][k]+ D[k][j]);
     }
• TC: O(V^3) & SC: O(1)
  
• Given a N*N matrix with K distinct knights(horse). If a knight is reachable from other knight, they can be swapped. Find the number of ways to arrange the knights.
• Connected component logic using BFS
• 
  
• Minimum Spanning Tree(undirected graph)
  
• Given an connected graph, remove some edges so that only n-1 edges are remaining and graph is still connected. The structure that we get is spanning tree.
• Spanning tree with min edge sum is Minimum spanning tree
• Properties
• Graph will be disconnected if any one edge is removed
• Cycle will be formed if any new edge is added
• Find MST in a weighted graph
• Prims Algorithm
• remove self-loops
• Remove multi-edges with high cost
• Start from node 1,  consider the outgoing edge with low cost
• Check the outgoing edges from the (MST) graph formed from above step and select the minimum one to form another MST
  
• Reject/drop the outgoing edges with high cost and keep only one
• Kruskal's algorithm

Graphs-6

• Prims Algorithm
• self-loops
• multi-edges
• Pair <int, Pair<node,node>>
  minHeap h;  //heap of pair  element type
  set S;
  set(Pair<Node,Node>)
  createMST(u){
    S.add(u);
    for (all v connected to u){
      h.add<new Pair<w, new Pair<u,v>>);
     }
  while (!h.isEmpty()){
      x=h.getMin();
      v=x.second.second;
  
      if (!s.contains(v)){
        S.add(v);
        mst.add(x.second);
    for(all b connected to v){
      if(!s.contains(b)){
          h.add(new pair(w, new pair(v,b);
        }
  }
  }

Graphs-6 Followup

• Disjoint set union
• Intersection of 2 sets is NULL set
• Union By Rank(height)
• Change the parent of tree with smaller height to point to bigger tree parent node
• max height -> logN
  
• Path Compression
• Along with finding parent of given node, connect each node to parent
• Given a graph check if it is connected
• perform union by rank/height
  for all i, parent(i) should be same to a connected graph
• Detect cycle in a graph using Disjoint set union
• Sort by weights OR add to min heap
  
• For all edges, perform union by 

Graphs-6 Followup

• Min head of type <wt, <node>,<node>
• set(S) -> vertices already added to MST
  createMST(u){
     s. add(u);
     for all v connected to u
         h.add(new pair(w, pair<u,v>))
         while (h not empty){
             x=h.getMin();
             v=x.second.second;
             if (!s contains(v)) {
                  s.add(v);
                  mst.add(x.second);
                  for(all w connected to  v){
                      if (!s.contains(w)){
                          h.add(new pair(w, new pair(u,v));
                    
  
• Krushal's algo 
• Consider every set to be a Tree with one element only
• The leader of set will be root of the tree
• The root node will have self-edge(this identified the root of the tree)
• Every node of the tree has edge to Parent
• 
  
• 
  

Graphs - Followup

• Bipartite Graph
• Graph that can be divided into 2 disjoint sets  such that no edges goes within set. Every edge goes from vertex from set1 to vertex in set2.
• Graph coloring
• Min num of colors in which you can color all the nodes such that no two adjacent nodes have the same color
• Chromatic number 
• min number of colors required. 
•  Odd number cycle requires 3 colors and even cycle requires 2 colors
  
• Given a tree with N nodes, find max number of edges that can be added to the tree such that it remains bipartite
•  x in first set, y in 2nd set
• Ans is X*Y-(N-1)
• Important topics to know
• Topological sort
• BFS/DFS
• Djikstras
• Kauskhal/Prims
• 
  

DBMS - 1

• File system disadvantages
  
• searching is slow due to sequential search
• Security as the file is stored as it is
  
• Concurrency
• When are they used
• When no updates to the information
• File is small
• low throughput(requests per sec)
• DBMS advantages
• Backups
• Concurrency
• Security
• Storage
• Integrity
• views
• Other databases(no sql dbs)
• graph based (Neo4j)
• columnar db(Casandra) -> for analytics
  
• time based(influx)
  
• document based(mongo)
• key value(redis)
• Scaler production system uses mysql. They use Mongodb for interaction between prod DB and chat system
• SQL vs NOSQL Databases
• too many writes -> NoSQL
• too many joins -> SQL
• too many reads -> sql
• Keys
• Identify records/rows
• Identify relationships

DBMS - 2

•  Schema - blue print
• tables, columns, pk, fk
• Scaler scema
• Users(userId, name, mail, phone, experience..)
• Students(id, userId, batchId, psp, attendance, streak,)
• batches(id, name)
• ER Model(Entities Relationship model)
  
• 1.20
• Entity(Nouns, visualizations) -> real thing, concept(batch, assignment, class)
• represented by Rectangle with name inside it
  
• Attributes 
• represented by owvels
• types
• simple/automic
• composite like address
• multivalued like mobile numbers(represented by two owvels/circles)
  
• derived attributes like tax/age. dotted owvel
  
• Keys
• underlined
• Relationships
• represented by diamond between two entities
  

DBMS - 3

•  Anamolies 
• Redundancy
• Normalization
• Process of removing redundancy from DB design and making DB design better.
• 1NF
• No multi valued attributes
  
• More than one phone number in column
• Solution
• Multiple columns
• It will waste memory and makes sql design complex
• Multiple rows
• too much redundancy and wastes storage
• Separate table
• 2NF
• Schema should be in 1NF
• There should be NO partial dependency ie A particular attribute can be derived from a subset of primary key attribute.(Attribute can be derived from a subset of primary key attributes) eg: if studentId, BatchId is primary key, batchName can be derived using BatchId
• 3NF
• Schema should be in 2NF
• There should be no transitive dependencies(For all Functional dependencies in a table, either left side should be candidate key or right side should be part of the key)
• eg: studentId -> batchId -> batchName(happens when all of them are in same table)
• BCNF (Boyce code normal form)
  
• Schema should be in3NF
• For any functional dependency(X->Y) X has to be primary key/candidate key
  
•  After 3NF all other Normalizations are not practical to implement. Hence, for practical scenarios 2NF/3NF is enough
• Transaction
• Set of logically linked operations which need to go as a whole
• ACID - Single Server data bases
  
• Automicity
• Consistency
• Isolation
• Durability
• CAP - Distributed server DB

DBMS - 4

• Sparce index
• Index where we don't have every entry
• Clustered index
• Ordered values
• non-Unique
• Indexes are stored as B+ tree(Balanced binary search tree)
• B Tree
• All leaves are at last level
• Has a value call t  (t value)
• Every node can have t+1 value
• When not to use index
• Writes will be slower
• storage cost

DBMS-5

•