[Algorithms] 1 - Review (1)

This is a review post for preparing coding interviews.

1. Recursion

Definition

Recursion is when you define something in terms of itself. Simply, it is a function that refers to itself inside of the function.

Things to keep in mind

What is Stack Overflow?

• Stack Overflow is a common problem we get when it comes to implementing a recursion. Simply means the stack in RAM runs out of space because too many functions got called.

Recursive vs Iterative

• Anything that can be implemented with recursion can also be done iteratively.

• Recursion has advantage over iterative functions in terms of readability

When to use?

• Recursion is useful when we have a task that has repeated subtasks to do.

• Consider using recursion when it comes to Tree problems and Divide and Conquer problems.

2. BFS & DFS

Definition

Depth First Search (DFS)

• Search all the way down as long as the node has children.

• Then come back up until reaches the node that does have any child node.

• Use stack.

• PRO: Good at telling if the path exists.

• CON: Might be slower.

Breath First Search (BFS)

• Search nodes from left to right, or right to left.

• Use queue.

• PRO: Shortest path to closer nodes.

• CON: More memory required.

Things to keep in mind

When to use DFS

• If you know a solution is not far from the root of the tree.

• If the tree is very wide. (BFS will need too much memory)

• Determining whether a path exists between two nodes.

• If the solutions are frequent but located deep in the tree.

When to use BFS

• If the tree is very deep and solutions are rare. (DFS will take too long)

• Finding the shortest path.

• If you know a solution is not far from the root of the tree.

3. Sorting

Big-O Complexity Cheat Sheet

Definitions

1) Quick Sort - O(nlogn)

• Divide and Conquer algorithm.

• Space complexity: O(logn)

• Worst time complexity: O(n^2)

• Advantages over merge sort

  • Sometimes give you the better time complexity.
  • Less space complexity.

2) Merge Sort - O(nlogn)

• Divide and Conquer algorithm.

• One of the most efficient way to sort an array.

• Space complexity: O(n)

• Worst time complexity: O(nlogn)

• Advantages over Quick Sort:

  • Guarantees you the time complexity of O(nlogn).

3) Insertion Sort - O(n^2)

• Find the element that is smaller than the current element, then swap it. Keep the current element as the biggest number so far.

• Good thing about this algorithm is that you do not need to perform swap every time you find out the smaller element than the current element. Also, space complexity is constant.

When to use:

• Insertion sort has a fast best-case running time and is a good sorting algorithm to use if the input list is already mostly sorted

4) Selection Sort - O(n^2)

• Find the smallest number from the list, and swap it with the first element. Then find the next smallest element and swap it with the second element, and so forth.

• When to use:

  • Selection sort can be good at checking if everything is already sorted.
  • It is also good to use when memory space is limited. (Space complexity is O(1))