zerolfu

md

Importance: Arrays > Lists > Hash > Trees
*Arrays
1. find the sum of contiguous subarray within a one-dimensional array of numbers which has the largest sum 
  http://www.geeksforgeeks.org/largest-sum-contiguous-subarray/

2. find a triplet in an array that sum-to a given value http://www.geeksforgeeks.org/find-a-triplet-that-sum-to-a-given-value/

3. Find minimum number of coins that make a given value http://www.geeksforgeeks.org/find-minimum-number-of-coins-that-make-a-change/

*List
1. Given a linked list, reverse alternate nodes and append at the end http://www.geeksforgeeks.org/given-linked-list-reverse-alternate-nodes-append-end/

2. Delete x nodes after y nodes http://www.geeksforgeeks.org/delete-n-nodes-after-m-nodes-of-a-linked-list/

3. Detect loop in a linked list http://www.geeksforgeeks.org/write-a-c-function-to-detect-loop-in-a-linked-list/

_________________________________________________________________________________________________________________

Concepts to know
*Trees
1. Binary tree vs Binary Search Tree
2. In a binary search tree: complexities of insertion, deletion, get height and how https://en.wikipedia.org/wiki/Binary_search_tree#Insertion
  Quick answer: insertion & deletion & get height: all O(logN) where N is the total number of nodes in the tree

*Hashmap/Hash
1. quick scan https://en.wikipedia.org/wiki/Hash_table, read section 1.1 and 3 (both important)
2. Common collision handling techinique: use an array of linkedlists, if two objects are indexed into the same position in the array by the hash function
  dump both into the linkedlist. Tradeoff: getting an value from the hash is no longer O(1), instead O(N)
3. Complexities(time): Get: O(1), insert/delete O(1). As a tradeoff, hash sacrifices space for time efficiency, because not all hash locations are filled.