Most important concepts for Coding Interviews

Question 1

1 and 2

Answer 1

1. Logarithm
2. Graphs traversal:
   - Tree traversal
   - Matrix traversal
   - BFS, DFS
   - Traversal of a cyclic graph by saving the visited nodes in a temporal data structure

Question 2

3 and 4

Answer 2

3. Binary search: it’s easy to learn and the time complexity is logarithmic
4. Sliding windows technique
   - Consists of two pointers, one at the left and other at the right, that traverse a string or array
   - Those indices are manipulated at the same time

Question 3

5 and 6

Answer 3

5. Recursion:
   - It teaches logic and how functions work
   - Some problems are easier to solve, and the solutions are easier to read than an iterative approach
6. Inverting a binary tree algorithm:
   - It’s an easy problem
   - It consists of traversing the tree and swapping every value

Question 4

7 and 8

Answer 4

7. Reversing a linked list algorithm:
   - It helps to solve other manipulations problems regarding linked lists
8. Suffix tree:
   - It’s an advanced data structure but very optimal for certain String problems
   - For example when you want to find a bunch of strings inside a bigger String

Question 5

9 and 10

Answer 5

9. Heap:
   - Binary heaps, max heaps, and min heaps
   - They have a logarithmic time operation when you have to repeatedly find max/min value in max/min heaps
   - Constructing a max/min heap can be very empowering because you can understand how it works, and how it can be represented very simply and elegantly with an array
10. Dynamic programming:
    - A lot of hard problems can be solved with it
    - Requires a lot of practice to master it

Question 6

11

Answer 6

11. Sorting algorithms:
    - All the sorting algorithms are important to understand
    - Quick and merge sort are very popular fast algorithms. Need to understand why they run on ‘N(log N)’ time and why they are much better than bubble sort
    - Quick Select is a variation of Quick Sort. It consists of finding the smallest / largest value at a requested index