Below follow highly unstructured notes on algs/data structures I've taken while Leetcoding
For thinking about problems:
-fundamentally, there are two data structures: linked lists, and arrays. all other DS are just composing these in cool ways. You know the tradeoffs of these two structures, so just apply reasoning about them recursively to the structure composed of them.
For coding problems:
-READ THE INSTRUCTIONS DUMMY!
-don't assume you know the operations
-eg, list.addAtIndex(val, len(list)) adds at the tail! even though len(list) isn't a valid index, it's valid for the operation! this is clearly explained
-EVERY TIME think about these cases:
-empty lists
-null value
-calling "general" method for "specialized case", probably delegate
-eg, addAtIndex(val, 0) vs addAtHead(val) -- if you already handle the special considerations in addAtHead, why write them again in addAtIndex?
-off by one! PAY ATTENTION!
-items passed in for operation are identical/point to the same thing
-basically ALWAYS do the dumb obvious thing first and get it working, THEN improve on it. trying to optimize INSTANTLY unless you FOR SURE know the solution is pretty stupid and you'll get tied in knots.
-Think about what you KNOW in the problem...don't instantly try to map other solutions onto it until you've thought about what information is available
-if input set is restricted to ints between -N and N where N is not enormous, consider using an array with 2N + 1 items
-when checking solutions, start with base case and go from there..."null, empty list, 1 item, 2 items"
-More generally, enumerate all possible cases:
-EG, array of ints could be:
-empty
-unsorted
-strictly increasing
-strictly decreasing
-non decreasing
-non increasing
-all equal
-all negative
-all positive
-all zero
-when dealing with ints, know the set...positive ints? non-negative? consider how this impacts if not x in python
-DO NOT try manipulating the size of the DS while iterating over it, eg while p1 < arr.size: del arr[p1]
DS:
Linked lists:
Attributes:
-sequential access time O(N), no random access, no efficient indexing
-better than conventional array for insertion/removal because not stored contiguously, O(1) if we have node reference
Types of linked lists:
singly Linked:
hard to get last value...n time
doubly linked:
2x as much mem for pointers
XOR linking:
special technique where pointer is prev xor next, so need at least one other pointer to use, but half the pointer mem
drawbacks: debuggers can't follow refs, more complex, garbage collection doesn't work with non-literal pointers, typing issues
multiply linked:
as many pointers as you want, chanining items together in any ordering scheme
example:
order by date, order by name, rank, reverse of those etc
circular linked list:
last item has pointer to first instead of null reference, same for doubly linked--first points to last as well
sometimes use "dummy" or sentinel nodes
hash linking:
two arrays, item stored in one, same index item in other has pointer
big why?
Techniques:
-Hash table for "visited"
-Two pointers:
-To find cycles, either hash table for visited nodes, or two "runners" with one twice as fast
-Lots of recursion (merging lists, problems with multiple pointers, they become like trees, use BFS/DFS)
-"weaving" nodes together to copy (1 -> 2) -> (1 -> 1C -> 2 -> 2C)
-Find items N apart, use pointers N apart
Linked list problem notes, for the stupid:
-keep a head pointer
-if you wanna make it slightly harder, use more mem, but save time, keep a tail pointer
-keep a "current" pointer if traversing through lists and comparing items
-keep a "prev" pointer also if intending to insert/delete
-pay attention to stopping conditions!
-is the current.next pointer null?
-is prev null? doesn't that tell us something?
-in problems with linked lists, pay attention to in-place vs creating something new
-if you're searching for something (min/max) repeatedly, have you removed an element each time? otherwise you'll get a circular issue
-any time you see "merge" think R E C U R S I O N you dummy!
-it is essential to update head when adding a new node at the beginning of the list.
-if you have tail, it is essential to update tail when adding to the end of the list
-find cycles with two pointers
-floyd's tortoise and hare -- find intersection first, then proceed one step at a time until cycle point is found
-to find items N steps away from end, two pointers N steps apart
-make SURE you're not messing with cur, always always use a tmp. you can hide that you're messing with cur under other var names. probably set a tmp right away and then immediately cur = cur.next
Arrays:
Attributes:
-O(1) access time for any element we have index for
-O(N) for inserting elements
-EXCEPT AT THE END!
-Stored contiguously
Techniques:
-Two pointers around some pivot (maybe between negative and non-negative integers?)
-queues for shifting items if you don't know how many you'll need to shift
-Can use empty space at the end of the array instead of using extra space -- need to shift items by n and there's n + 1 space at the end etc
-Treat values as indexes...if list is size n and items are guaranteed to be [i,n], you can use negate the values to mark them
Problem Notes:
-DO NOT try manipulating the size of the DS while iterating over it, eg while p1 < arr.size: del arr[p1]
Binary trees:
Attributes:
-basically linked lists with two next pointers
-O(log n) for getting or inserting an element (if sorted and balanced)
Techniques:
-R E C U R S I O N is used A LOT
-treat each subtree as a new tree
-traversals:
-Unlike lists, you have a decision about how to traverse
-if iterating, likely will use second data structure?
-DFS
-It's a stack, push children on in order below for pre/in/post, pop them off to visit
- preorder = visit(root) -> visit(left) -> visit(right)
- in order = visit(left) -> visit(root) -> visit(right)
- postorder = visit(left) -> visit(right) -> visit(root)
-BFS
-It's a queue!
Queues/Stacks
Attributes:
-Queue = FIFO
-for python use deque, appendleft/pop
-Stack = LIFO
-for python regular list, append/pop
Problems:
-If you see "minimum number of steps", generally it's BFS with a queue
-If "number of steps to next item with x property" consider a stack and traversing backwards
ALGO:
-For recurision, if two recursive calls per item O(2^N)
-Memoization = top-down, DP = bottom-up
-DFS = Stack, BFS = Queue