Entrepreneurials‎ > ‎Jobs‎ > ‎Interview‎ > ‎

### Interview Training

 Largest Sum Subarray (link)```Initialize: max_so_far = 0 max_ending_here = 0 Loop for each element of the array (a) max_ending_here = max_ending_here + a[i] (b) if(max_ending_here < 0) max_ending_here = 0 (c) if(max_so_far < max_ending_here) max_so_far = max_ending_here return max_so_far```Explanation: Simple idea of the Kadane's algorithm is to look for all positive contiguous segments of the array (max_ending_here is used for this). And keep track of maximum sum contiguous segment among all positive segments (max_so_far is used for this). Each time we get a positive sum compare it with max_so_far and update max_so_far if it is greater than max_so_farin each iteration (i), find the maximum sub-array ending at element i. which means whether including element i or not. before that whenever we got a negative sum discard all that found up to thenThe Longest Increasing Subsequence(my code link): find the length of the longest subsequence of a given sequence such that all elements of the subsequence are in increasing order.For example: Given sequence sequence {10,22,9,33,,21,,50,41,60}Subsequences are: {10}, {10,22}, {10,9,33}, {33,21,60}, {50,60}, etc.Solutiondynamic programming:A[i] // sequenceLIS[i] // Length of longest increasing subsequence which includes element A[i] as its last element.```LIS(i) = 1 + Max j=1 to i-1 {LIS(j)} if A[i]>A[j] for 1 A[ j ])             LIS[i] = max(LIS[i], LIS[ j ] )      LIS[i]= LIS[i] + 1return max(LIS)Explanation:The longest subsequence ending in element i is equal to checking if element i added to each of LSI's before it can be improved by it through concatenation```Example: A[] = {3, 4, 1, 5} i=1 , LIS(1) = 1 i=2 , LIS(2) = 1+ Max(LIS(1)) = 1 +1 =2 (4>3) i=3 , LIS(3) = 1 (1>3, 1>4) i=4 , LIS(4) = 1+ Max(LIS(1),LIS(2), LIS(3)) = 1 + Max(1,2,1) = 3```Hamming distancedef hammingDistance ( x ,     y ):     assert len ( x ) == len ( y )     n = 0     for i in xrange ( 0 ,     len ( x )):           if x [ i ] != y [ i ]:                 n += 1      return nEdit distanceGiven two strings S1 and S2 and operations (insert/delete/replace). Find minimum number of edits to convert S1 into S2.to get from ε,ε to G,Gd[1,1] = min(D[0,1]+1], D[1,0] +1, D[0,0] + 1indicatorFunction_{G==G}) from{ε,G} to {G,G} one operation is needed to convert S1 to S2 (Insert), so + 1from{G,ε} to {G,G} one operation is needed to convert S1 to S2 (Delete), so + 1from{ε,ε} to {G,G} zero operations are needed because they are already equal. if they were not equal one operation was needed. S1 was itself, and S2's character would be just replaced to that of S2's Partition a set into two subsets such that the difference of subset sums is minimum```Input: arr[] = {1, 6, 11, 5} Output: 1 Explanation: Subset1 = {1, 5, 6}, sum of Subset1 = 12 Subset2 = {11}, sum of Subset2 = 11 ```a subset is defined an assignment of 0's and 1's to set elements. 2^nits complement is just the negate of the binary value{3} -> ε,3{3,4} ->  ε|3,4    3|4 {a,b,c} ->   ε|a,b,c     a|b,c    c|a,b   b|a,c  Partition Problem: deciding whether S = {x1, ..., xn} of positive integers can be partitioned into two subsets S1 and S2 such that the ΣS1 = ΣS2.p = ΣS/2 x n       p = row represents sum value, column represents true means p(i, j) is True if either p(i, j − 1) is True or if p(i − xj, j − 1) is True       ::: of all items w/o xj is splittable to become i  OR of all items w/o xj is splittable to become i - xj  p(i, j) is False otherwise 0-1 Knapsack: fill a knapsack of capacity W, with items of weight w[n] each worth v[n] value such that maximum value is collected.`// Returns the maximum value that can be put in a knapsack of capacity W``int` `knapSack(``int` `W, ``int` `wt[], ``int` `val[], ``int` `n)``{``   ``// Base Case``   ``if` `(n == 0 || W == 0)``       ``return` `0;` `   ``// If weight of the nth item is more than Knapsack capacity W, then``   ``// this item cannot be included in the optimal solution``   ``if` `(wt[n-1] > W)``       ``return` `knapSack(W, wt, val, n-1);` `   ``// Return the maximum of two cases: ``   ``// (1) nth item included ``   ``// (2) not included``   ``else` `return` `max( val[n-1] + knapSack(W-wt[n-1], wt, val, n-1),``                    ``knapSack(W, wt, val, n-1)``                  ``);``}`on a sorted then pivoted array at an unknown location find an item:```1) Find middle point mid = (l + h)/2 2) If key is present at middle point, return mid. 3) Else If arr[l..mid] is sorted a) If key to be searched lies in range from arr[l] to arr[mid], recur for arr[l..mid]. b) Else recur for arr[mid+1..r] 4) Else (arr[mid+1..r] must be sorted) a) If key to be searched lies in range from arr[mid+1] to arr[r], recur for arr[mid+1..r]. b) Else recur for arr[l..mid] ```not neede, but to find the pivot`int` `findPivot(``int` `arr[], ``int` `low, ``int` `high)``{``   ``// base cases``   ``if` `(high < low)  ``return` `-1;``   ``if` `(high == low) ``return` `low;` `   ``int` `mid = (low + high)/2;   ``/*low + (high - low)/2;*/``   ``if` `(mid < high && arr[mid] > arr[mid + 1])``       ``return` `mid;``   ``if` `(mid > low && arr[mid] < arr[mid - 1])``       ``return` `(mid-1);``   ``if` `(arr[low] >= arr[mid])``       ``return` `findPivot(arr, low, mid-1);``   ``return` `findPivot(arr, mid + 1, high);``}` in an unsorted array, find the k-smallest element:call max-heap k timesORnot to do complete quicksort, but stop at the point where pivot itself is k’th smallest element. Also, not to recur for both left and right sides of pivot, but recur for one of them according to the position of pivot.Maximum Path Sum in a Binary Treein a recursive post-order traversal:1. Node only2. Max path through Left Child + Node3. Max path through Right Child + Node4. Max path through Left Child + Node + Max path through Right Child
Subpages (1):