Coding interviews

Coding interview questions (Leetcode, top questions)

• For Two Sum, it's better to find pairs as we go, instead of putting everything into a set and then doing something. This way it's easy to forbid taking the same element twice.
• For "delete a node in a linked list", give both pointer to the head and pointer to a node that should be deleted. And a bonus question is solve a problem in O(1) time.

Categories

• Implement / warm-up
  • map, set, hashset
• Time and memory complexity
• Arrays
• Strings
• Sliding window, two pointers
• Recursion
  • backtracking
• DS
  • stack
  • queue
  • linked list
• Sorting and searching
• In-place
• Greedy
• DP
  • Fibonacci, Stairs (1 or 2 steps; 1,2,3 steps; 1-K steps, also in O(N) instead of O(N*K))
  • min-path in a grid
  • coin change
  • knapsack
  • splitting a sequence into parts
  • dp on DAG's
• Math
• Bit manipulation
• Hashing, hash table
• DS again
  • trees
  • TRIE
  • heap
• Graphs
• Divide&conquer
• Probability, randomization

Problems

• N-1 distinct numbers from 1 to N, one is missing. Find it.
  • XOR or rearranging the numbers.
• All duplicates but one. Find that single number.
• Two missing numbers from 1 to N. Find them.
• 2-sum, 3-sum.
• Get a random number from a stream. Do it in-place.
• Simulate rand(1,5) with rand(1, 7). Simulate rand(1, 7) with rand(1, 5).
• Simulate a fair coin with a spoiled coin.
• How do you swap two numbers without using the third variable?
• How do you check if two rectangles overlap with each other?
• Huge list: https://www.geeksforgeeks.org/must-do-coding-questions-for-companies-like-amazon-microsoft-adobe/