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_far

in 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 then



The 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.

Solution
dynamic programming:

A[i] // sequence
LIS[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<j<i =   1 if no such j exists.


for i = 1 to n
    for j = 1 to i    
        if(A[i] > A[ j ])
             LIS[i] = max(LIS[i], LIS[ j ] )
      LIS[i]= LIS[i] + 1
return 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 distance
def 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 n



Edit distance
Given 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,G
d[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 + 1
from{G,ε} to {G,G} one operation is needed to convert S1 to S2 (Delete), so + 1
from{ε,ε} 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^n
its 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(ij) is True if either p(ij − 1) is True or if p(i − xjj − 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(ij) 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 times
  • OR
  • not 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 Tree
in a recursive post-order traversal:
1. Node only
2. Max path through Left Child + Node
3. Max path through Right Child + Node
4. Max path through Left Child + Node + Max path through Right Child































Subpages (1): Java Interview
Comments