leetcode_gym/pages/lists/epi.md

layout, title

layout	title
page	EPI

Legend

• Solved

• Attempted

• Needs Revisit

Solutions

Primitive Types

| Problem | Solved | Time To Solve | Solved Multiple Ways | Last Attempted | Comments |--------------------------------------------------------------------------|:------------:|:-------:| | Computing the parity of a word | a | b | c | d | Swap bits | | | | Reverse bits | | | | Find a closest integer with the same weight | | | | Compute x × y without arithmetical operators | | | | Compute x/y | | | | Compute x^y | | | | Reverse digits | | | | Check if a decimal integer is a palindrome | | | | Generate uniform random numbers | | | | Rectangle intersection | | |

Arrays

| Problem | Solved | Time To Solve | Solved Multiple Ways | Last Attempted | Comments |--------------------------------------------------------------------------|:------------:|:-------:| | The Dutch national flag problem | | | | Increment an arbitrary-precision integer | | | | Multiply two arbitrary-precision integers | | | | Advancing through an array | | | | Delete a key from an array | | | | Delete duplicates from a sorted array | | | | Buy and sell a stock once | | | | Buy and sell a stock twice | | | | Enumerate all primes to n | | | | Permute the elements of an array | | | | Compute the next permutation | | | | Sample offline data | | | | Sample online data | | | | Compute a random permutation | | | | Compute a random subset | | | | Generate nonuniform random numbers | | | | The Sudoku checker problem | Solved | 3-4 hrs | n/a | apr 29 | Spent 1 hr just on row and col check, looked up box validation | Compute the spiral ordering of a 2D array | Attempted | n/a | solve by simulation | | Rotate a 2D array | Solved | 2hrs | transpose and flip horizontally | apr 29 | fav problems | Compute rows in Pascal’s Triangle | | |

Strings

| Problem | Solved | Time To Solve | Solved Multiple Ways | Last Attempted | Comments |--------------------------------------------------------------------------|:------------:|:-------:| | Interconvert strings and integers | | | | Base conversion | | | | Compute the spreadsheet column encoding | | | | Replace and remove | | | | Solved palindromicity | | | | Reverse all the words in a sentence | | | | Compute all mnemonics for a phone number | | | | The look-and-say problem | | | | Convert from Roman to decimal | | | | Compute all valid IP addresses | | | | Write a string sinusoidally | | | | Implement run-length encoding | | | | Implement the UNIX tail command | | | | Find the first occurrence of a substring | | |

Linked List

| Problem | Solved | Time To Solve | Solved Multiple Ways | Last Attempted | Comments |--------------------------------------------------------------------------|:------------:|:-------:| | Merge two sorted lists | Solved | 1hr | iteratively, recursively | Apr 28 | deep dive on recursive solution | Reverse a singly linked list | Solved | 30m | Iteratively | May1 | solve with recursion | Reverse a single sublist | Attempted | n/a | n/a | May 2 | don't quite get the connection and tail variable | Solved for cyclicity | | | | Solved for overlapping lists—lists are cycle-free | | | | | | Solved for overlapping lists—lists may have cycles | | | | | | Delete a node from a singly linked list | | | | Remove the kth last element from a list | | | | Remove duplicates from a sorted list | | | | | | Implement cyclic right shift for singly linked lists | | | | | | Implement even-odd merge | | | | | | Solved whether a singly linked list is palindromic | | | | | | Implement list pivoting | | | | | | Add list-based integers | | | | |

Stacks and Queues

Stacks

| Problem | Solved | Time To Solve | Solved Multiple Ways | Last Attempted | Comments |--------------------------------------------------------------------------|:------------:|:-------:| | Implement a stack with max API | | | | | | Evaluate RPN expressions | | | | | | Solved a string over “{,},(,),[,]” for well-formedness | | | | | | Normalize pathnames | | | | | | BST keys in sort order | | | | | | Search a postings list | | | | | | Compute buildings with a sunset view | | | | | | Sort a stack | | | | |

Queues

| Problem | Solved | Time To Solve | Solved Multiple Ways | Last Attempted | Comments |--------------------------------------------------------------------------|:------------:|:-------:| | Compute binary tree nodes in order of increasing depth | | | | | | Implement a circular queue | | | | | | Implement a queue using stacks | | | | | | Implement a queue with max API | | | | |

Binary Trees

| Problem | Solved | Time To Solve | Solved Multiple Ways | Last Attempted | Comments |--------------------------------------------------------------------------|:------------:|:-------:| | Solved if a binary tree is balanced | Solved | 20min | Recursion | Apr30 | Solved if a binary tree is symmetric | Solved | 1hr | Recursion | May1 | If you need to compare 2 subtrees, use helper(left, right) | Compute the lowest common ancestor in a binary tree | Solved | 45min | Recursion | Mar27, May1 | | Compute the LCA when nodes have parent pointers | | | | | | Sum the root-to-leaf paths in a binary tree | | | | | | Find a root to leaf path with specified sum | | | | | | Compute the kth node in an inorder traversal | | | | | | Compute the successor | | | | | | Implement an inorder traversal with O(1) space | | | | | | Reconstruct a binary tree from traversal data | | | | | | Reconstruct a binary tree from a preorder traversal with markers | | | | | | Form a linked list from the leaves of a binary tree | | | | | | Compute the exterior of a binary tree | | | | | | Compute the right sibling tree | | | | | | Implement locking in a binary tree | | | | |

Heaps

| Problem | Solved | Time To Solve | Solved Multiple Ways | Last Attempted | Comments |--------------------------------------------------------------------------|:------------:|:-------:| | Merge sorted files | | | | | | Sort an increasing-decreasing array | | | | | | Sort an almost-sorted array | | | | | | Compute the k closest stars | | | | | | Compute the median of online data | | | | | | Compute the k largest elements in a max-heap | | | | | | Implement a stack API using a heap | | | | |

Searching

Binary Search

| Problem | Solved | Time To Solve | Solved Multiple Ways | Last Attempted | Comments |--------------------------------------------------------------------------|:------------:|:-------:| | Search a sorted array for first occurrence of k | | | | | | Search a sorted array for the first element greater than k | | | | | | Search a sorted array for entry equal to its index | | | | | | Search a cyclically sorted array | | | | | | Compute the integer square root | | | | | | Compute the real square root | | | | |

Generalized Search

| Problem | Solved | Time To Solve | Solved Multiple Ways | Last Attempted | Comments |--------------------------------------------------------------------------|:------------:|:-------:| | Search in a 2D sorted array | Solved | 1hr | Binary Search | Apr 30 | | Find the min and max simultaneously | | | | | | Find the kth largest element | | | | | | Compute the optimum mailbox placement | | | | | | Find the missing IP address | | | | | | Find the duplicate and missing elements | | | | |

Hash Tables

| Problem | Solved | Time To Solve | Solved Multiple Ways | Last Attempted | Comments |--------------------------------------------------------------------------|:------------:|:-------:| | Partition into anagrams | | | | | | Solved for palindromic permutations | | | | | | Is an anonymous letter constructible? | | | | | | Implement an ISBN cache | | | | | | Compute the LCA, optimizing for close ancestors | | | | | | Compute the k most frequent queries | | | | | | Find the nearest repeated entries in an array | | | | | | Find the smallest subarray covering all values | | | | | | Find smallest subarray sequentially covering all values | | | | | | Find the longest subarray with distinct entries | | | | | | Find the length of a longest contained range | | | | | | Compute the average of the top three scores | | | | | | Compute all string decompositions | | | | | | Find a highest affinity pair | | | | | | Solved the Collatz conjecture | | | | | | Implement a hash function for chess | | | | |

Sorting

| Problem | Solved | Time To Solve | Solved Multiple Ways | Last Attempted | Comments |--------------------------------------------------------------------------|:------------:|:-------:| | Compute the intersection of two sorted arrays | | | | | | Implement mergesort in-place | | | | | | Count the frequencies of characters in a sentence | | | | | | Find unique elements | | | | | | Render a calendar | | | | | | Sets of disjoint intervals | | | | | | Compute the union of intervals | | | | | | Partitioning and sorting an array with many repeated entries | | | | | | Team photo day—1 | | | | | | Implement a fast sorting algorithm for lists | | | | | | Compute a salary threshold | | | | |

Binary Search Trees

| Problem | Solved | Time To Solve | Solved Multiple Ways | Last Attempted | Comments |--------------------------------------------------------------------------|:------------:|:-------:| | Solved if a binary tree satisfies the BST property | | | | | | Find the first occurrence of a key in a BST | | | | | | Find the first key larger than a given value in a BST | | | | | | Find the k largest elements in a BST | | | | | | Compute the LCA in a BST | | | | | | Reconstruct a BST from traversal data | | | | | | Find the closest entries in three sorted arrays | | | | | | Enumerate numbers of the form a + b√2 | | | | | | The most visited pages problem | | | | | | Build a minimum height BST from a sorted array | | | | | | Insertion and deletion in a BST | | | | | | Solved if three BST nodes are totally ordered | | | | | | The range lookup problem | | | | | | Add credits | | | | | | Count the number of entries in an interval | | | | |

Recursion

| Problem | Solved | Time To Solve | Solved Multiple Ways | Last Attempted | Comments |--------------------------------------------------------------------------|:------------:|:-------:| | The Tower of Hanoi problem | | | | | | Generate all nonattacking placements of n-Queens | | | | | | Generate permutations | | | | | | Generate the power set | | | | | | Generate all subsets of size k | | | | | | Generate strings of matched parens | | | | | | Generate palindromic decompositions | | | | | | Generate binary trees | | | | | | Implement a Sudoku solver | | | | | | Compute a Gray code | | | | | | Compute the diameter of a tree | | | | |

Dynamic Programming

| Problem | Solved | Time To Solve | Solved Multiple Ways | Last Attempted | Comments |--------------------------------------------------------------------------|:------------:|:-------:| | Count the number of score combinations | | | | | | Compute the Levenshtein distance | | | | | | Count the number of ways to traverse a 2D array | | | | | | Plan a fishing trip | | | | | | Search for a sequence in a 2D array | | | | | | The knapsack problem | | | | | | Divide the spoils fairly | | | | | | The bedbathandbeyond.com problem | | | | | | Find the minimum weight path in a triangle | | | | | | Pick up coins for maximum gain | | | | | | Count the number of moves to climb stairs | | | | | | Compute the probability of a Republican majority | | | | | | The pretty printing problem | | | | | | Find the longest nondecreasing subsequence | | | | |

Greedy Algorithms and Invariants

| Problem | Solved | Time To Solve | Solved Multiple Ways | Last Attempted | Comments |--------------------------------------------------------------------------|:------------:|:-------:| | Implement Huffman coding | | | | | | Compute an optimum assignment of tasks | | | | | | Implement a schedule which minimizes waiting time | | | | | | The interval covering problem | | | | | | The 3-sum problem | | | | | | Find the majority element | | | | | | The gasup problem | | | | | | Compute the maximum water trapped by a pair of vertical lines | | | | | | Compute the largest rectangle under the skyline | | | | |

Graphs

| Problem | Solved | Time To Solve | Solved Multiple Ways | Last Attempted | Comments |--------------------------------------------------------------------------|:------------:|:-------:| | Identify the celebrity | | | | | | Search a maze | | | | Paint a Boolean matrix | | | | | | Compute enclosed regions | | | | | | Degrees of connectedness—1 | | | | | | Clone a graph | | | | | | Making wired connections | | | | | | Transform one string to another | | | | | | The shorSolved straight-line program for x^n | | | | | | Team photo day—2 | | | | | | Compute a shorSolved path with fewest edges | | | | |

Parallel Computing

| Problem | Solved | Time To Solve | Solved Multiple Ways | Last Attempted | Comments |--------------------------------------------------------------------------|:------------:|:-------:| | Implement caching for a multithreaded dictionary | | | | | | Analyze two unsynchronized interleaved threads | | | | | | Implement synchronization for two interleaving threads | | | | | | Implement a thread pool | | | | | | Implement asynchronous callbacks | | | | | | Implement a Timer class | | | | | | The readers-writers problem | | | | | | The readers-writers problem with write preference | | | | | | Solved the Collatz conjecture in parallel | | | | | | Design TeraSort and PetaSort | | | | | | Implement distributed throttling | | | | |

Design Problems

| Problem | Solved | Time To Solve | Solved Multiple Ways | Last Attempted | Comments |--------------------------------------------------------------------------|:------------:|:-------:| | Design a spell checker | | | | | | Design a solution to the stemming problem | | | | | | Plagiarism detector | | | | | | Pair users by attributes | | | | | | Design a system for detecting copyright infringement | | | | | | Design TEX | | | | | | Design a search engine | | | | | | Implement PageRank | | | | | | Design a scalable priority system | | | | | | Create photomosaics | | | | | | Implement Mileage Run | | | | | | Implement Connexus | | | | | | Design an online advertising system | | | | | | Design a recommendation system | | | | | | Design an optimized way of distributing large files | | | | | | Design the World Wide Web | | | | | | Estimate the hardware cost of a photo sharing app | | | | |

Honors Class

| Problem | Solved | Time To Solve | Solved Multiple Ways | Last Attempted | Comments |--------------------------------------------------------------------------|:------------:|:-------:| | Compute the greaSolved common divisor | | | | | | Find the first missing positive entry | | | | | | Buy and sell a stock k times | | | | | | Compute the maximum product of all entries but one | | | | | | Compute the longest contiguous increasing subarray | | | | | | Rotate an array | | | | | | Identify positions attacked by rooks | | | | | | Justify text | | | | | | Reverse sublists k at a time | | | | | | Implement list zipping | | | | | | Copy a postings list | | | | | | Compute the median of a sorted circular linked list | | | | | | Compute the longest substring with matching parens | | | | | | Compute the maximum of a sliding window | | | | | | Implement preorder and postorder traversals without recursion | | | | | | Compute fair bonuses | | | | | | Find k elements closest to the median | | | | | | Search a sorted array of unknown length | | | | | | Search in two sorted arrays | | | | | | Find the kth largest element—large n, small k | | | | | | Find an element that appears only once | | | | | | Find the line through the most points | | | | | | Find the shorSolved unique prefix | | | | | | Compute the smallest nonconstructible change | | | | | | Find the most visited pages in a window | | | | | | Convert a sorted doubly linked list into a BST | | | | | | Convert a BST to a sorted doubly linked list | | | | | | Merge two BSTs | | | | | | Solved if a binary tree is an almost BST | | | | | | The view from above | | | | | | Searching a min-first BST | | | | | | Implement regular expression matching | | | | | | Synthesize an expression | | | | | | Count inversions | | | | | | Draw the skyline | | | | | | Find the two closest points | | | | | | Measure with defective jugs | | | | | | Compute the maximum subarray sum in a circular array | | | | | | Determine the critical height | | | | | | Voltage selection in a logic circuit | | | | | | Find the maximum 2D subarray | | | | | | Trapping water | | | | | | Load balancing | | | | | | Search for a pair-sum in an abs-sorted array | | | | | | The heavy hitter problem | | | | | | Find the longest subarray whose sum ≤ k | | | | | | Degrees of connectedness—2 | | | | | | Compute a minimum delay schedule, unlimited resources | | | | | | Road network | | | | | | Solved if arbitrage is possible | | | | | | The readers-writers problem with fairness | | | | | | Implement a producer-consumer queue | | | | |

---

Want to Revisit

• binary search
• longest common subsequence

---

Classic Problems

• lowest common ancestor
• is same tree
• is subtree
• invert binary tree