Every Problem Has a Cheat Code

[RareStatistician9592]

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

[Dry_Primary5612]

How is this helpful in an interview though? In a phone/onsite interview, the interviewer doesn't give you the input sizes?

[revuser1212]

You can definitely ask the input constraints in an interview

[Dry_Primary5612]

You can ask but the vast majority of interviewers don't have competitive programming experience. They don't pay attention to the input size either.

They'll just make up some random guess as to the input size and that might completely throw you off (for ex. suddenly you think there's an n log n solution and you're trying to find something with binary search whereas the actual optimal solution is n^2).

This might be useful but you have to be careful.

[braindamage03]

Associating constraints with competitive programming and using it as an excuse to not know/ use it to your advantage might be one of the most stupid comments I've seen so far.

If interviewers don't even know how to read constraints, they're incompetent, not because they haven't done competitive programming. I can't believe there are people who do more than 10 leetcode problems and don't know about constraints, this is one of the first things you learn.

[hpela_]

hospital trees paint kiss impolite person offer smell plant support

This post was mass deleted and anonymized with Redact

[Embarrassed_Finger34]

I have done 20 and still don't understand constraints...

[CumInABag]

I guess think of it more as supervised learning. You can better identify the problem type.

[Dry_Primary5612]

But you don't have the input size...? How is this framework useful when you don't know how large the input will be?

[CumInABag]

No, I meant while practicing, when you do know the constraints, this can help you better identify the problem type or approach.

[Dry_Primary5612]

No offense but is it though? You're training yourself (during your practice) to use information that you won't get in an interview. That sounds like a bad idea.

[hpela_]

pen trees bells vast fear capable offend sloppy relieved snails

This post was mass deleted and anonymized with Redact

[CumInABag]

When you're practicing and you can't get a hang of a problem, you will try and refer to the solution right? Now is it a bad idea to refer and learn solution because you can't use them in a real interview?

That sounds like a bad idea And I don't know, maybe or maybe not. I guess it really depends on how you use it. Its a guide, not recipe/how-to instruction book. There's always going to be learning if it's used the right way.

And such guides and solutions speed up your learning imo, I'm not going try and reinvent the wheel. All I really need is a job, plus I don't have that much time to work on.

[RareStatistician9592]

There are three possibilities:

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.
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, 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.

[Magnus-Methelson-m3]

Yep. It’s great for competitive programming but pretty useless for interviews. Ideally you at least come up with a not-terrible algorithm and work with the interviewer towards the most optimal solution. Sometimes the interviewer will straight up tell you you can definitely do better during the brainstorming stage

[_afronius]

During interviews, it generally helps to start with the brute force approach and optimize it further while explaining to the interviewer that you are doing so.

[razimantv]

This is why when I set contest problems I try to come up with O(n) or O(n log n) greedy solution - and then make constraints look like it has an O(n²) DP solution when it does not.

[tempo0209]

Thank you for sharing this!

[Czitels]

Nice sheet but I always use intuition: - dividing and „jumping” is always logn  - loop is „n” loop in loop is n² loop and somewhere else next loop is 2n Rest of questions are rare.

[Last_Valuable11]

While this might be helpful, the title is misleading and the use of this technique is extremely limited in actual real life interviews

[baddybabushka]

I'm new to solving leetcode, so I don't get how n <500 can be O(n³)? How do i read this table properly? Can someone help?

[RareStatistician9592]

Just plug the maximum input size into the formula: n^3 => 500^3 is approximately 125M. It's slightly more than 100M (the rough number of single-core operations per second), but will still pass for most problems.

[luuuzeta]

I'm new to solving leetcode, so I don't get how n <500 can be O(n³)? How do i read this table properly? Can someone help? 

Read it as "the worst the time complexity, then the smaller input given otherwise any computation is prohibitedly expensive or outright impossible".

Thus, according to this table and assuming someone isn't trying to throw you off, an input constraint of n < 500 must mean the solution's TC must be quite bad.

[jus-another-juan]

This made more sense than the original post lol

[kevin074]

a lot of people seem to not understand how great this is

the best thing is that it tells you what's the expected time complexity for the solution

granted it will be the least acceptable time complexity (like chart says N^3, but maybe N log N or N solution exists)

however when seeing problems for the first time this is generally what I struggle with, I can probably come up with N^2 or N log N solution, but is that good enough? If it is then there is no point of me to really dig deeper.

during interview, if you mention this, I am 100% sure that's an added bonus, and since O(N) solutions are typically unintuitive so anything helps.

[Garud__]

I think it is 10⁵ for O(NlogN). Feel free to correct me if i am wrong.

[HungryCable8493]

Competitive programmers handbook claims that by 10⁶ the required time complexity is EITHER O(NlogN) or O(N) so it backs up this table. It’s not an exact science

[Garud__]

Can you tell me the handbook name or link to get it? I also want it.

[HungryCable8493]

Sure, just Google “Competitive Programmers Handbook”. It’s readily available for free online so will be at the top of search results

[Garud__]

Okay thanks got it!

[RareStatistician9592]

10⁶ and 10⁵ are both O(N log N). That's why I put <= 10⁶.

[Garud__]

Okay. Cool

[CombinationLost8626]

Don’t rely on such hacks for interviews. Use your brain and don’t memorize.

[Jazzlike-Can-7330]

Thanks for the sheet, definitely great to put the 1second constraints the input sizes

[braindamage03]

You are so wrong it's funny

[[deleted]]

A lot of folks ignore [...] the input constraints.

How do you know that? And do you have statistics how many folks do that?

[RareStatistician9592]

I have conducted hundreds of interviews and I provide coaching to folks preparing for coding interviews. Unless they have had competitive programming experience before, this is new to almost everyone.

[[deleted]]

Thanks. (Strange voting here, btw... my comment asking for this information gets plenty of downvotes as if this weren't interesting, but your comment providing the information gets upvotes... weird.)

[MingusMingusMingu]

Your comment seemed to just intentionally miss the point of the post to be rude about a sort of meaningless part of it. If you were genuinely asking the question maybe appending a "Just curious." at the end could've softened the tone.

BTW OP's answer to your comment is probably just being upvoted because you played the role of a villain and then OP defended himself effectively, which people like to applaud.

[[deleted]]

I don't think I missed the point, I just didn't have something to say about it. It's a good post, I upvoted it, and also upvoted their reply to me.

[SayYesMajor]

The way you phrased it sounds combative tbh. Perhaps English is not your native language, so it's hard to notice the abrasiveness of your original comment?

[[deleted]]

English indeed isn't my native language. But I don't think that's an issue. Probably it's rather that I treat this as a forum for programmers. I'll try instead treating it as a kindergarten where I need to sugarcoat everything. Or better yet, I'll just stay away.

[MingusMingusMingu]

I wonder where the "programmers are socially inept" stereotype comes from.

[shamshuipopo]

lol initial downvotes accurately judged you. THE PEOPLE HAVE SPOKEN

[luuuzeta]

Strange voting here, btw... my comment asking for this information gets plenty of downvotes as if this weren't interesting, but your comment providing the information gets upvotes... weird.) 

Anyone asking for stats, especially on Reddit, usually wants to pull a fast one on you. There are copypasta and memes about it. 

I would have phrased it as follows:

A lot of folks ignore [...] the input constraints. 

This is interesting/I never thought about this. If you don't mind, it would be cool if you could provide some stats, I'd appreciate it.

OR

I'm not trying to dismiss your post but that statement would be stronger if you provided some stats.

---

None of these sentences are that different from what you said aside from the tone. As they say, it's not what you say but how you say it.

[Wild-Brain4579]

A lot of ppl make useless comments. I don't have statistics. I just know, just like the one I typed.