Most important concepts for Coding Interviews Flashcards
1
Q
1 and 2
A
- Logarithm
- Graphs traversal:
- Tree traversal
- Matrix traversal
- BFS, DFS
- Traversal of a cyclic graph by saving the visited nodes in a temporal data structure
2
Q
3 and 4
A
- Binary search: it’s easy to learn and the time complexity is logarithmic
- 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
3
Q
5 and 6
A
- 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 - Inverting a binary tree algorithm:
- It’s an easy problem
- It consists of traversing the tree and swapping every value
4
Q
7 and 8
A
- Reversing a linked list algorithm:
- It helps to solve other manipulations problems regarding linked lists - 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
5
Q
9 and 10
A
- 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 - Dynamic programming:
- A lot of hard problems can be solved with it
- Requires a lot of practice to master it
6
Q
11
A
- 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