google/fb面经

1. 给个数组seq， 和一个total，找 if there is a contiguous sequence in seq
which sums to total.

注意，这里的contiguous意思是位置上的邻接，而不是consecutive

2. use trie to implment word search suggestion.
3. given a prefix expression, convert it to postfix expression(+12 -> 12+)
4. given a array of integers, find the minimum in a sliding window of size 4. eg. Input: [2,1,3,4,6,3,8,9,10,12,56]  Output: [1,1,3,3,3,3,8,9]
5. given an integer target, calculate the minimum number of integer square summation equal to that target



Answer:

1.
O(n) solution for unsorted array.

An example
arr=[-1 4 1 0 -2 -3 7],
sum = 2

step 1: accumulate the sums
arr -> acc = [0 -1 3 4 4 2 -1 6]. Insert 0 at the front

step 2: traverse the acc with hash table.
 the hash table uses the sum up to each index i + the target sum as the key,
and index i as the mapping value,
the "acc" array contain the sum up to each index j
if acc[j] is already the key in the hash table with mapping value i, you know the
subarray [i+1,j] is summed up to the target sum

2.

void convertPreFixToPostFix(char[] expr)
{
   if(expr.length>=3)
   {
         boolean operandNotFound=true;
   Stack stack=new Stack();
   int i=0;
   while(i<expr.length)
   {
   if(expr[i] is operator)
   {
      stack.push(expr[i]);
   }
   else
   {
       Print expr[i];
    if(operandNotFound)
    {
     operandNotFound=false;
     print expr[++i];
    }
    Print stack.pop();
   }
   i++;
   }
   
   }

}

5. here