To: my FB phone screen interviewer today re the constant time vs linear time disc

Microsoft / Eng
whozat?

Go to company page Microsoft Eng

whozat?
Sep 27, 2018 41 Comments

If you're reading this - the complexity of my solution is O(1) as I initially mentioned.

I missed a couple of test cases, you missed the complexity analysis. Does that make us kind of even? Recommend me for the on-site maybe? Please, pretty please? 😅😅
I swear I'm a pretty good engineer, I have not seen the problem before and it was real code.

https://en.m.wikipedia.org/wiki/Time_complexity

Despite the name "constant time", the running time does not have to be independent of the problem size, but an upper bound for the running time has to be bounded independently of the problem size. For example, the task "exchange the values of a and b if necessary so that a≤b" is called constant time even though the time may depend on whether or not it is already true that a ≤ b. However, there is some constant t such that the time required is always at most t.

comments

Want to comment? LOG IN or SIGN UP
TOP 41 Comments