Every Problem Has a Cheat Code

Input sizes mapped to their target time complexities and possible approaches

A lot of folks ignore the most important clue in the problem statement - the input constraints.

I’ve compiled the table of input sizes above mapped to their target time complexities and possible approaches. You don’t need to memorize the table. Once you know the constraints, you can easily deduce the target time complexity—just remember the key limit of 100 million operations (10^8) per test case.

In coding challenges, there’s a practical rule of thumb: the largest test case should run in about 1 second. This 1-second limit translates to approximately 100 million single-core operations.

Why 1 second? This standard comes from competitive programming, where it’s been a benchmark for decades. It also aligns with user expectations—people are generally willing to wait about 1 second for online systems to respond.

I give a few examples and more context in my blog post.

About myself: I'm an ex-FAANG Senior Software engineer, currently on a sabbatical. Let's connect on Linkedin! https://www.linkedin.com/in/nurbolat/. I also give coding interview tips and insights in my Faangshui blog here: https://blog.faangshui.com/

Update Sep 18: adding an asnwer to the most upvoted question:

Are input constraints always given? And what to do if they are not available?

  1. Most interviews these days are conducted over some online system, such as CodeSignal or Hackerrank. Problems there almost always have input constraints. Three different interviewing systems that I've used most recently to conduct real interviews had constraints in problems statements. This of course depends on your location and the type of companies you are applying for.
  2. Online assessments are conducted online as well. Problems there almost always have input constraints.
  3. If the interview is conducted offline, or in some non-standard system (e.g. Google Docs), you have options:
    1. Ask the interviewer for constraints. Constraints are an important part of the requirements, and the interviewer should know what kind of input they would be feeding to the code.
    2. If the interviewer can't tell the constraints, ask if they have some target time complexity in mind. They won't always tell you that. If they do, you can use the right half of the table - matching complexity to approaches. If they don't, think of some frequently used time complexity O(N log N) and check if any of the O(N log N) approaches are applicable. You can go up (O(N)) or down (O(N^2)) from there. Even though this doesn't help you, it shows the interviewer that you are asking the right questions.

Feel free to reference my blog post for more details: https://blog.faangshui.com/p/every-problem-has-a-cheat-code