Skip to main content

Meta Algorithm

System Design Course/Platform

1. Do I really understand the problem?

  • What exactly does the input consist of?
  • What exactly are the desired results or output?
  • Can I construct an input example small enough to solve by hand? What happens when I try to solve it?
  • How large is a typical instance of my problem? Will I be working on 10 items? 1,000 items? 1,000,000 items?
  • Am I trying to solve a numerical problem? A graph algorithm problem? A geometric problem? A string problem? A set problem? Which formulation seems easiest?

2. Can I find a simple algorithm or heuristic for my problem?

  • Will brute force solve my problem correctly by searching through all subsets or arrangements and picking the best one?
    • If so, why am I sure that this algorithm always gives the correct answer?
    • How do I measure the quality of a solution once I construct it?
    • Does this simple, slow solution run in polynomial or exponential time? Is my problem small enough that this brute-force solution will suffice?
    • Am I certain that my problem is sufficiently well defined to actually have a correct solution?
  • Can I solve my problem by repeatedly trying some simple rule, like picking the biggest item first? The smallest item first? A random item first?
    • If so, on what types of inputs does this heuristic work well? Do these correspond to the data that might arise in my application?
    • On what types of inputs does this heuristic work badly? If no such examples can be found, can I show that it always works well?
    • How fast does my heuristic come up with an answer? Does it have a simple implementation?

3 Are there special cases of the problem that I know how to solve?

  • Can I solve the problem efficiently when I ignore some of the input parameters?
  • Does the problem become easier to solve when I set some of the input parameters to trivial values, such as 0 or 1?
  • Can I simplify the problem to the point where I can solve it efficiently?
  • Why can’t this special-case algorithm be generalized to a wider class of inputs?

4. Which of the standard algorithm design paradigms are most relevant to my problem?

  • Is there a set of items that can be sorted by size or some key? Does this sorted order make it easier to find the answer?
  • Is there a way to split the problem in two smaller problems, perhaps by doing a binary search? How about partitioning the elements into big and small, or left and right? Does this suggest a divide-and-conquer algorithm?
  • Do the input objects or desired solution have a natural left-to-right order, such as characters in a string, elements of a permutation, or leaves of a tree? Can I use dynamic programming to exploit this order?
  • Are there certain operations being done repeatedly, such as searching, or finding the largest/smallest element? Can I use a data structure to speed up these queries? What about a dictionary/hash table or a heap/priority queue?
  • Can I use random sampling to select which object to pick next? What about constructing many random configurations and picking the best one? Can I use some kind of directed randomness like simulated annealing to zoom in on the best solution?
  • Can I formulate my problem as a linear program? How about an integer program?
  • Does my problem seem something like satisfiability, the traveling salesman problem, or some other NP-complete problem? Might the problem be NP-complete and thus not have an efficient algorithm

Check up the categories depending on the problem definition:

  • Is it array related (missing/duplicate elements, operation on string...) ---> Arrays
  • Do I need to test every configuration of search space (exhaustive search)? ---> Backtracking
  • Can I start from one node and scan the search space (parent-child relation)? ---> DFS and BFS
  • Is the input partially (or fully) ordered and are we searching for a specific element (place to insert element)? ---> Binary Search
  • Are we searching for optimal configuration in a left-to-right/small-to-large input? ---> Dynamic Programming
  • Can we just discard some configuration based on the problem statement or prove by contradiction that some configuration cannot be part of the optimal solution? ---> Greedy
  • Is there a natural relation between elements of the input, can we model it as graph and use some of the known algorithms? ---> Graph
  • Is the input linked list? ---> Linked List
  • Are we searching for min or max element or do we have some elements with priority over the others? ---> Heap
  • Is the input given as interval (start and end pair)? ---> Intervals
  • Is there a special focus on math operations or random number generation? ---> Math
  • Are we only interested in subarray/substring of the input and can we easily detect if the part of input satisfies specific property? ---> Sliding Window
  • Are you searching text, using prefix or suffix? ---> Trie
  • Can we somehow use two pointers to decrease the search space and make decisions based on their value in (partially/fully) sorted input? ---> Two Pointers

Our interview questions are organized by difficulty level and tagged with the companies that frequently ask them in interviews. We recommend starting with a specific category and going through all the questions in that category, testing your skills on related problems as you progress (links to related problems are provided for each question in the course). However, if you prefer to search by company or difficulty, we've also provided some useful links to help you navigate the platform: