LeetCode Patterns Flashcards: Tries, Design Problems, LRU Cache, Time Complexity

A trie, also called a prefix tree, is a tree data structure where each node represents a character and paths from the root represent strings or prefixes. Each node has up to 26 children for lowercase English letters. A boolean flag marks nodes where a complete word ends. Tries support insertion, search, and prefix matching all in O of m time where m is the word length, independent of how many words are stored. They solve autocomplete, spell checking, word search in grids, finding all words with a common prefix, and the word break problem.

A Least Recently Used cache stores key-value pairs with a capacity limit, evicting the least recently accessed item when full. It requires O of one time for both get and put operations. The key insight is combining a hash map for O of one key lookups with a doubly linked list for O of one removal and insertion. The hash map maps keys to linked list nodes. The linked list orders nodes by recency with the most recent at the head. On get, move the accessed node to the head. On put, add a new node at the head and evict the tail node if capacity is exceeded. Both operations are constant time.

For recursive algorithms, count the number of recursive calls and the work done per call. If each call makes two recursive calls and does O of one work, the total is O of two to the power of n. Draw the recursion tree: the total work is the sum across all levels. For divide-and-conquer, the Master Theorem provides formulas based on the recurrence relation: if T of n equals a times T of n over b plus O of n to the d, the complexity depends on how log base b of a compares to d.

O of n log n grows much slower than O of n squared. For 10,000 elements, n log n is roughly 133,000 operations while n squared is 100 million, a 750 times difference. For one million elements, n log n is about 20 million while n squared is one trillion, a 50,000 times difference. This is why sorting-based solutions at O of n log n are dramatically faster than nested-loop solutions at O of n squared for large inputs.

From fastest to slowest: O of one is constant time regardless of input size, like hash table lookup. O of log n is logarithmic, like binary search. O of n is linear, like a single array pass. O of n log n is linearithmic, like efficient sorting. O of n squared is quadratic, like nested loops over the same array. O of two to the power of n is exponential, like generating all subsets. O of n factorial is factorial, like generating all permutations. Interviewers expect you to state and justify the time and space complexity of your solution.