Blog Details

Google Initial Phone Screen with Recruiter

1. Questions

  • What’s the best/worst running time of Merge Sort? O(nlogn), O(nlogn)
  • What’s the best/worst running time of Quick Sort? O(n), O(n^2)
  • What’s the worst running time for a look up in a HashTable? O(n) two reasons: if too many elements were hashed into the same key: looking inside this key may take O(n) time; Once a hash table has passed its load balance, it has to rehash. But the average is O(1).
  • Could you name an implementation of HashTable? Word spelling check; Java LRU Cache?
  • Which of the following Python data structure is not mutable: tuple, list, dictionary? Dictionary.
  • For an unweighted graph, which algorithm should be used to find shortest path: breadth-first search or Dijkstra’s algorithm? Dijkstra’s algorithm.
  • Could you estimate 2^24? 16 million
  • In Java, could you name two Map implementations? HashMap, TreeMap, LinkedHashMap, HashTable, Properties, Provider, ConcurrentHashMap, EnumMap.