algorithm design problem catalog

note: the problems on this page are majorly (/ intend to be) grouped by the nature of their problem statement and not their solution's mode of approach. related: algorithmic operations catalog

From LeetCode

• Count the number of points within a region on a 2D plane (quadtree)
• range sum query 2D - mutable, range sum query 2D - immutable
• number of ships in a rectangle
• minimize the total price of the trips
• design a leaderboard
• decode string
• word break 1, word break 2
• MRU queue, LRU Cache, LFU Cache, design in-memory file system. What is the difference between LRU and LFU?
• invalid transactions (look into how OOP might complicate implementation? a solution to I.T: https://www.youtube.com/watch?v=N0Hgr7vTXOw)
• course schedule 1 asks if it is possible to complete a given 'curriculum' of courses when some courses are dependent on other courses; course schedule 2 determines some particular order in which the courses should be taken; (dependency graph; topological sorting; optimal job scheduling; unix tsort; railway timetables.)
• number of islands and max area of island computes the number and size (respectively) of separate segments within a matrix of binary-state elements. When the shape of the segment is a constraint, the problem is more difficult: maximal square, maximal rectangle. Even more difficult is efficiently (O(k log mn)) obtaining the intermediate number of separate segments when the "matrix of binary-state elements" is populated one "land-state" at a time, where k in O(k log mn) is the number of times: Number of Islands 2.
• 2 sum selects any 2 integers (from an integer array) that sum to a target integer. How about we select 3? 3 sum. How about we select any n that sum to target? (If we can't select, can we at least test?) subset sum equals k. How about we select any contiguous 2? any contiguous 3? any contiguous n? (If we can't select, can we do better than test and actually count all the number of ways that a solution is true?) i.e., How about we obtain all the number of ways that a contiguous n sums to the target? subarray sum equals k. What if we obtain the maximum target that any contiguous n sums to? maximum subarray sum. What if the operation is not a sum but a product? maximum subarray product.
• Subsets (Private), Subsets 2 (Private)
• Minimum Size Subarray Sum (Private)
• split linked list in parts
• non-overlapping intervals
• maximum number of events that can be attended
• merge intervals
• insert interval
• minimum number of taps to open to water a garden
• minimum operations to make the array increasing
• minimum replacements to sort the array
• maximum length of pair chain
• Maximize Score After N Operations (Private)
• Minimum Penalty For a Shop (Private)
• Unique Paths 1 (Private), Unique Paths 2 (Private)
• Extra Characters in a String (Private)
• Frog Jump (Private), Jump Game 1 (Private), Jump Game 2 (Private)
• Interleaving String (Private)
• Text Justification (Private)
• Reorganize String (Private)
• Excel Sheet Column Title (Private), Excel Sheet Column Number (Private)
• Repeated Substring Pattern (Private)
• Gas Station (Private)
• Candy (Private)
• Container Filled With Most Water (Private), Trapping Rain Water
• House Robber 1 (Private), House Robber 2
• Combinations (Private), Combination Sum 2 (Private), Combination Sum 3 (Private)
• Permutations 1 (Private), Permutations 2 (Private), Permutation Sequence (Private)
• N-Queens (Private), N-Queens 2 (Private)
• Spiral Matrix (Private) Spiral Matrix 2 (Private)
• Rotate Image (Private)
• Group Anagrams (Private)
• Pow(x, n) (Private)
• Sort Colors (Private)
• Insertion Sort List (Private)
• Bitwise AND of Numbers Range (Private)
• Happy Number (Private)
• Word Search (Private)
• Remove Duplicates from Sorted Array 2 (Private)
• Search in Rotated Sorted Array 2 (Private)
• Remove Duplicates from Sorted List (Private), Remove Duplicates from Sorted List 2 (Private)
• Largest Rectangle in Histogram (Private)
• Partition List (Private)
• Reverse Linked List 2 (Private)
• Restore IP Addresses (Private)
• Unique Binary Search Trees 2 (Private)
• Clone a graph (Private)
• Binary Tree Inorder Traversal (Private)
• Invert Binary Tree
• Unique Binary Search Trees
• Validate Binary Search Tree
• Recover Binary Search Tree
• Same Tree
• Symmetric Tree
• Binary Tree Level Order Traversal
• Binary Tree Zigzag Level Order Traversal
• Maximum Depth of Binary Tree
• Construct Binary Tree from Preorder and Inorder Traversal
• Construct Binary Tree from Inorder and Postorder Traversal
• Binary Tree Level Order Traversal 2
• Convert Sorted Array to Binary Search Tree
• Convert Sorted List to Binary Search Tree
• Balanced Binary Tree
• Minimum Depth of Binary Tree
• Flatten Binary Tree to Linked List
• Binary Tree Maximum Path Sum
• Binary Tree Preorder Traversal
• Binary Tree Postorder Traversal
• Binary Tree Right Side View
• First Missing Positive
• Multiply Strings
• Add Two Numbers
• Longest Substring Without Repeating Characters
• Median of Two Sorted Arrays
• Longest Palindromic Substring
• Palindrome Number
• Regular Expression Matching
• Longest Common Prefix
• Letter Combinations of a Phone Number
• Remove Nth Node From End of List
• Valid Parentheses
• Merge Two Sorted Lists
• Generate Parentheses
• Merge k Sorted Lists
• Swap Nodes in Pairs
• Reverse Nodes in k-Group
• Remove Duplicates from Sorted Array
• Next Permutation
• Longest Valid Parentheses
• Search in Rotated Sorted Array
• Find First and Last Position of Element in Sorted Array
• Search Insert Position
• Valid Sudoku
• Sudoku Solver
• Count and Say
• Rotate List
• Minimum Path Sum
• Valid Number
• Plus One
• Add Binary
• St(x)
• Climbing Stairs
• Simplify Path
• Edit Distance
• Set Matrix Zeroes
• Search a 2D Matrix (Search a sorted 2D Matrix for a target)
• Minimum Window Substring
• Interleaving String
• Path Sum 1, Path Sum 2
• Distinct Subsequences
• Populating Next Right Pointers in Each Node 1, Populating Next Right Pointers in Each Node 2
• Pascal's Triangle 1, Pascal's Triangle 2
• Triangle
• Best Time to Buy and Sell Stock 1, Best Time to Buy and Sell Stock 2, Best Time to Buy and Sell Stock 3
• Word Ladder 1, Word Ladder 2
• Longest Consecutive Sequence
• Sum Root to Leaf Numbers
• Surrounded Regions
• Palindrome Partitioning 1, Palindrome Partitioning 2
• Single Number 1, Single Number 2
• Copy List with Random Pointer
• Linked List Cycle 1, Linked List Cycle 2
• Reorder List
• Sort List
• Max Points on a Line
• Evaluate Reverse Polish Notation
• Find Minimum in Rotated Sorted Array 1, Find Minimum in Rotated Sorted Array 2
• Min Stack
• Intersection of Two Linked Lists
• Maximum Gap
• Majority Element
• Dungeon Game
• Largest Number
• Repeated DNA Sequences
• Best Time to Buy and Sell Stock 4
• Rotate Array
• Reverse Bits
• Number of 1 Bits
• Remove Linked List Elements
• Count Primes
• Isomorphic Strings
• Reverse Linked List
• Implement Trie (Prefix Tree)
• Design Add and Search Words Data Structure
• Word Search 2
• Shortest Palindrome
• Kth Largest Element in an Array
• Contains Duplicate
• The Skyline Problem
• Count Complete Tree Nodes
• Rectangle Area
• Basic Calculator
• Implement Stack using Queues
• Basic Calculator 2
• Summary Ranges
• Majority Element 2
• Kth Smallest Element in a BST

From EPI

1. Primitive types

   • compute the parity of a word (Private)
   • swap bits (Private)
   • reverse bits (Private)
   • find a closest integer with the same weight (Private)
   • compute x * y without arithmetical operators (Private)
   • compute x/y (Private)
   • compute xy (Private)
   • reverse digits (Private)
   • check if a decimal integer is a palindrome (Private)
   • generate uniform random numbers (Private)
   • rectangle intersection (Private)

2. Arrays adp related to arrays (Private)

3. Strings adp related to strings (Private)

   • Interconvert strings and integers (Private)
   • Base conversion (Private)
   • Compute the spreadsheet column encoding (Private)
   • Replace and remove (Private)
   • Test palindromicity (Private)
   • Reverse all the words in a sentence (Private)
   • Compute all mnemonics for a phone number (Private)
   • The look-and-say problem (Private)
   • Convert from Roman to decimal (Private)
   • Compute all valid IP addresses (Private)
   • Write a string sinusoidally (Private)
   • Implement run-length encoding (Private)
   • Find the first occurrence of a substring (Private)

4. Linked Lists adp related to linked lists (Private)

   • sort a LL
   • insertion sort a LL
   • reverse a LL
   • reverse a sequence in a linked list
   • merge two sorted LLs
   • merge two sorted lists (Private) ✔
   • reverse a single sublist (Private)
   • test for cyclicity (Private) ✔
   • test for overlapping lists—lists are cycle-free (Private)
   • test for overlapping lists—lists may have cycles (Private)
   • delete a node from a singly linked list (Private)
   • remove the kth last element from a list (Private) ✔
   • remove duplicates from a sorted list (Private) ✔
   • implement cyclic right shift for singly linked lists (Private) ✔
   • implement even-odd merge (Private)
   • test whether a singly linked list is palindromic (Private) ✔
   • implement list pivoting (Private) ✔
   • add list-based integer (Private) ✔

5. Stacks and Queues adp related to stacks and queues (Private)

   • implement a stack with max API (Private)
   • evaluate RPN expressions (Private)
   • test a string for well-formedness (Private)
   • normalize pathnames (Private)
   • Compute buildings with a sunset view (Private)
   • Compute binary tree nodes in order of increasing depth (Private)
   • Implement a circular queue (Private)
   • Implement a queue using stacks (Private)
   • Implement a queue with max API (Private)

6. Binary Trees adp related to binary trees (Private)

7. Heaps adp related to heaps (Private)

   • Merge sorted files (Private)
   • Sort an increasing-decreasing array (Private)
   • Sort an almost-sorted array (Private)
   • Compute the k closest stars (Private)
   • Compute the median of online data (Private)
   • Compute the k largest elements in a max-heap (Private)

8. Searching adp related to searching (Private)

   • Search a sorted array for first occurrence of k (Private)
   • Search a sorted array for entry equal to its index (Private)
   • Search a cyclically sorted array (Private)
   • Compute the integer square root (Private)
   • Compute the real square root (Private)
   • Search in a 2D sorted array (Private)
   • Find the min and max simultaneously (Private)
   • Find the kth largest element (Private)
   • Find the missing IP address (Private)
   • Find the duplicate and missing elements (Private)

9. Hash Tables adp related to hash tables (Private)

   • Test for palindromic permutations (Private)
   • Is an anonymous letter constructive? (Private)
   • Implement an ISBN cache (Private)
   • Compute the LCA, optimizing for close ancestors (Private)
   • Find the nearest repeated entries in an array (Private)
   • Find the smallest subarray covering all values (Private)
   • Find smallest subarray sequentially covering all values (Private)
   • Find the longest subarray with distinct entries (Private)
   • Find the length of a longest contained interval (Private)
   • Compute all string decompositions (Private)
   • Test the Collatz conjecture (Private)
   • Implement a hash function for chess (Private)

10. Sorting adp related to sorting (Private)

    • Compute the intersection of two sorted arrays (Private)
    • Merge two sorted arrays (Private)
    • Remove first-name duplicates (Private)
    • Smallest nonconstructible value (Private)
    • Render a calendar (Private)
    • Merging intervals (Private)
    • Compute the union of intervals (Private)
    • Partitioning and sorting an array with many repeated entries (Private)
    • Team photo day—1 (Private)
    • Implement a fast sorting algorithm for lists (Private)
    • Compute a salary threshold (Private)

11. Binary Search Trees adp related to binary search trees (Private)

12. Recursion adp related to recursion (Private)

    • The Towers of Hanoi problem (Private)
    • Generate all nonattacking placements of n-Queens (Private)
    • Generate permutations (Private)
    • Generate the power set (Private)
    • Generate all subsets of size k (Private)
    • Generate strings of matched parens (Private)
    • Generate palindromic decompositions (Private)
    • Generate binary trees (Private)
    • Implement a Sudoku solver (Private)
    • Compute a Gray code (Private)

13. Dynamic Programming adp related to dynamic programming (Private)

14. Greedy Algorithms and Invariants adp related to greedy

    • Compute an optimum assignment of tasks (Private)
    • Schedule to minimize waiting time (Private)
    • The interval covering problem (Private)
    • The 3-sum problem (Private)
    • Find the majority element (Private)
    • The gasup problem (Private)
    • Compute the maximum water trapped by a pair of vertical lines (Private)
    • Compute the largest rectangle under the skyline (Private)

15. Graphs adp related to graphs (Private)

• Parallel Computing
  • Implement caching for a multithreaded dictionary (Private)
  • Analyze two unsynchronized interleaved threads (Private)
  • Implement synchronization for two interleaving threads (Private)
  • Implement a thread pool (Private)
  • Deadlock (Private)
  • The readers-writers problem (Private)
  • The readers-writers problem with write preference (Private)
  • Implement a Timer class (Private)
  • Test the Collatz conjecture in parallel (Private)
• Language Questions
  • Garbage Collection (Private)
  • Closure (Private)
  • Shallow and deep copy (Private)
  • Iterators and Generators (Private)
  • decorator (Private)
  • List vs tuple (Private)
  • args and kwargs (Private)
  • Python code (Private)
  • Exception Handling (Private)
  • Scoping (Private)
  • Function arguments (Private)
• Common Tools
  • Merging in a version control system (Private)
  • Hooks (Private)
  • Is scripting more efficient? (Private)
  • Polymorphism with a scripting language (Private)
  • Dependency analysis (Private)
  • ANT vs. Maven (Private)
  • SQLvs.NoSQL (Private)
  • Normalization (Private)
  • SQL design (Private)
  • IP, TCP, and HTTP (Private)
  • HTTPS (Private)
  • DNS (Private)
• Honors
  • Compute the greatest common divisor (Private)
  • Find the first missing positive entry (Private)
  • Buy and sell a stock k times (Private)
  • Compute the maximum product of all entries but one (Private)
  • Compute the longest contiguous increasing subarray (Private)
  • Rotate an array (Private)
  • Identify positions attacked by rooks (Private)
  • Justify text (Private)
  • Implement list zipping (Private)
  • Copy a postings list (Private)
  • Compute the longest substring with matching parens (Private)
  • Compute the maximum of a sliding window (Private)
  • Implement a postorder traversal without recursion (Private)
  • Compute fair bonuses (Private)
  • Search a sorted array of unknown length (Private)
  • Search in two sorted arrays (Private)
  • Find the fcth largest element—large n, small k (Private)
  • Find an element that appears only once (Private)
  • Find the line through the most points - (Private)
  • Convert a sorted doubly linked list into a BST (Private)
  • Convert a BST to a sorted doubly linked list (Private)
  • Merge two BSTs (Private)
  • Implement regular expression matching (Private)
  • Synthesize an expression (Private)
  • Count inversions (Private)
  • Draw the skyline (Private)
  • Measure with defective jugs (Private)
  • Compute the maximum subarray sum in a circular array - (Private)
  • Determine the critical height & (Private)
  • Find the maximum 2D subarray (Private)
  • Implement Huffman coding (Private)
  • Trapping Rain Water (Private)
  • The heavy hitter problem (Private)
  • Find the longest subarray whose sum < fc (Private)
  • Road network (Private)
  • Test if arbitrage is possible (Private)

---

Backlinks

• catalogs