How never to have a code limit

So you come home, check your email, and here it is. A letter from the company of your dreams. They want to interview with you. But first you got to solve a coding assessment. You have two problems to solve, and you also have a time pressure.You only have 1 hour to solve both of them.

You may solve the first problem somehow, and you have half an hour remaining.But the second problem seems to be really complex.You look at it and you start panicking.

What you gonna do? Would you be able to solve this problem in just 30 minutes that you have remaining?There is might be only one solution left.

Calling the Fairy Code Mother!

  • You called for me? What's the problem?

  • I'm running out of time. I don't know what to do. The problem is too complex.

-Come on, just look at the constraints.

  • What's up with constraints?

-Oh, you don't know? They didn't share the secret with you! But okay, I'm gonna help you. I'm good today.

All you're gonna do is to remember one number. 10^9.

It's not random. This is an approximate amount of operations your computer is able to do per second.

Of course, it has a constant associated with it.

It's not exactly 10^9,

but approximately it is. C * 10^9.

  • Is it related to the fact that processor frequency is measured in Gigahertz?

-Right.

-I have 20 minutes left. And what I'm supposed to do with this useful information?

-1 second is usually a limit, coding platforms set for their submissions.

-So I'm able to do 10^9 in my submissions?

-Yes. If you are over a second, this is time limit for you. You need to try harder.

But sometimes you can cheat.

You look at the input and you see 10^4.

So your solution is most likely to succeed even if it's not optimal.

  • Yeah.

  • Right.

  • The array length is 310^4. My algorithm complexity is O(n). And I'm expected to do 310^4 operations.

So multiplied it all together is 9 * 10^8.

It's almost 10^9!

Would it work?

-Yeah... Your almost 10^9 solution might work.

Fairy Code Mother! My sucky solution went through!

-Don't thank me.

The problem they were speaking about: https://leetcode.com/problems/range-sum-query-mutable/description/