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;    
    }
}