Square phone interview

3 Rounds phone interview...

#1. Given array A[], find A[j] - A[i] which is max and j < i
A: DP

#2. String reverse
#3. Implement a hash table

#4 Prefix calcuator

prefix calculator

(+ (/ 4 2) 3)

5

giving a string, compute the expression using prefix notation

feel free to make simplifying assumptions about the expression or helper methods available to you

we'll relax some of these assumptions as we go

Palantir Phone Interview

/**
 * Write a function that is given an array of integers. It should return true if
 * and only if there are two integers in the array a[i] and a[j] with the same
 * value such that the difference between i and j is at most k.
 */

boolean containsDuplicateWithinK(int[] arr, int k) {
    // 1. build Map<Integer, Integer>  (key, value) = (number, pos)
    Map<Integer, Integer> map = new HashMap<Integer, Integer>();
    // 2. Iterate through arr, for each elem, we need to compute the max diff
    int cur = 0;
    for (int ele : arr) {
       if (map.constainsKey(ele)) {
          int diff = cur - map.get(ele);
          if (diff <= k) {
            return true;
          }
       }
       map.set(ele, cur);          
       cur++;
    }
    return false;
}

/**
 * Write a function that is given an array of integers. It should return true if
 * and only if there are two integers in the array with the same value.
 */

boolean containsDuplicate(int[] arr) {
    // 1. build Set
    Set<Integer> set = new HashSet<Integer>();
    // 2. scan the arr, check every element in HashTable or not, if not, push to table
    for (int ele : arr) {
      if (set.contains(ele)) {
        return true;
      }
      set.push(ele);
    }
    // 3. if we reach here, return false
    return false;
}


/**
 * The Fibonacci sequence is defined as
 * F_0 = 0
 * F_1 = 1
 * For each n > 1, F_n = F_(n-1) + F_(n-2)
 *
 * Write a function inverseFibonacci that is given a number fib. If fib is a
 * Fibonacci number, the function should return the index of that Fibonacci
 * number (e.g. if fib is F_8, then the function should return 8). Otherwise,
 * the function should return -1.
 */

int inverseFibonacci(long fib) {
    // Write code here
    int index = 2;
    long value_0 = 0, value_1 = 1;
    long value = value_0 + value_1;
    // 1. Handle corner case first
    if (fib == 0) {
      return 0;
    } else if (fib == 1) {
      return 1;
    } else {
        // fib > 1, we can start index from 2
        while (value < fib) {
            value = value_0 + value_1;
            value_0 = value_1;
            value_1 = value;
            index++;
        }
        // when function comes to here, value is either > or == to fib
          return (value == fib) ? index : -1;    
    }
}

Quora phone interview

都是white board coding, 也就是說只要interviewer沒找出bug 你就pass 了
1. 給一個Reverse polish notation數學運算式, 所有的operand都是整數, operator只有+, -, *, / 。 算出結果
    都已經給reverse polish了, 也不需要做parse ，只要用stack穩穩的算result即可

2. 給一個binary tree (不是binary search tree),  每個node存int, 會有duplicate, 給出第二大 distinct值 (此處簡稱DSM, Distinct Second Maximum) . Eg. 如果tree 裡面是 3, 3, 1, 2, 2, 2  output會是2 ,因為3重複了

    遞迴即可. ex:   DSM(P) = DSM {P, MAX(L), DSM(L), MAX(R), DSM(R)}. done.

        P
      /    \
    L     R

Twitter phone interview (damn I screw up)

Given a class named Stream which represents a math statement, there are only two elements in Stream:

1. operand: only integer

2. operator: only "+" and "*"

the stream has three methods:

boolean hasNext();  // return true if the Stream has operand or operator left, false if cursor reaches end

int getNum(); // return the next operand, increase cursor in stream

char getOp(); // return the next operator, increase cursor in stream

You need to write a method:

int getValue();

which compute the correct value of the given Stream. Remember "*" has higher priority than "+". You can only use constant space.

Its guaranteed that the Stream is always well-formatted, which means, there wont be Stream like 1 ++ 2 or 12 * 3 +* 4. You dont't need to worry about parsing, just use the above three methods. 

算是四則運算的簡化版。不過我居然沒在interview時寫出來，真是太弱了。之後從頭想了一下花了半小時寫玩並在eclipse上簡單驗證:

public class Stream {

    public String[] equation;
    public int index;
    public int length;
    
    public Stream(String eq) {
        this.equation = eq.split(" ");
        this.index = 0;
        this.length = equation.length;
    }
    
    public int getNum() {
        if (index < length) {
            
            return Integer.valueOf(equation[index++]);
        }
        return -9999999;
    }

    public String getOP() {
        if (index < length) {
            return equation[index++];
        }
        return null;
    }
    
    public boolean hasNext() {
        return index < length;
    }
    
    
    public int getValue() {
        this.index = 0;
        int value = 0;
        int num = getNum();
        
        while (hasNext()) {
            String op = getOP();
            if (op.equals("+")) {
                value = value + num;
                num = getNum();
            } else {    
                // op == "*"
                num = num * getNum();
            }  
        }
        value = value + num; 
        return value;
    }
    
    public static void main(String[] args) {
        Stream stream = new Stream("4 * 5 * 2 + 3");
        System.out.print("value = " + stream.getValue());
    }
}