Algos & DS

Question 1

Typically, a recursive algorithm consists of two main components:

Answer 1

Base case: This is the simplest possible input for the problem - a case where we can no longer break down the problem into simpler sub-problems. The base case is usually some form of empty input, such as an empty list, string, or 0.

Recursive step: Needs a base case necessary for stopping the recursion & recursive call, where the fn calls itself and some updated value. Can return a value but doesn’t have too.
Usually this involves breaking down the inputs in some way (e.g. removing a character from a substring, removing an element from a list) and re-combining the outputs from the recursive calls in some way (e.g. adding, appending to a list).

When to use: any time you can find a base case, but really good for trees and graphs

Not good for: maybe good for interviewing but not practical for real life due to increased cpu usage and can crash memory if errors occur

Question 2

Linked List/Doubly Linked List

Answer 2

Collection of nodes that hold some element(s) and either points to the next node (singly linked) or points to both the previous and next node (doubly linked).

When to use: when you need to efficiently insert or delete items from a list, and when you need the size of the list to be flexible

Not good for: look ups, indexing (arrays better) or searching (hash tables and trees better), caching since elements are not stored in adjacent memory

Question 3

Hash Table/Map/Dictionary

Answer 3

Hash table is at its core an associative array of key, val pairs where the key is created using some sort of hashing fn to transform the key into an index. The more unique the hash fn the less likely you are to experience collisions.
In the event of a collision we can have an array that holds multiple key,val pairs in any given hashtable index.

When to use: Should be the FIRST option when interviewing. Operates in constant time and at worst case O(n). Use whenever you need constant-time lookup, insertion, or deletion of items by key.

Not good for: storing sorted data, and searching by value instead of by key is still O(N).

Question 4

Binary Search

Answer 4

Best used for sorted arrays, where you basically cut the array in half each operation giving you an Logn complexity.

When to use: when finding an element within a sorted list. key is in taking advantage of sorted data to divide the search space in half at every step

Not good for: any unsorted array