2

I may have fricked up my interview.

Per the interviewer's instructions, I wrote a program that ended up taking O(n^3) time. The interviewer then asked if I could improve my algorithm to O(nlogn) time. I did not see a way to do so and answered as much. THEN, I mentioned how if this were a professional setting, I wouldn't be concerned with optimization unless the algorithm was so poorly optimized as to cause the program to violate time constraints.

The interviewer, fortunately, kind of engaged me in discussion regarding that point and seemed to understand where I'm "coming from," so to speak.

Was it a mistake to discuss the necessity of optimization, or not? Might it have worked in my favor?

Improve this question
11
  • I don't see anything out of ordinary or any immediate "no-hire" flags in your description of the interview. Diving into topic brought up by interviewee is a reasonable strategy as there is a good chance that it is the topic interviewee is passionate about and conversation would give more ideas about their working/communication style compared to "just write some code".
    – Alexei Levenkov
    Oct 13, 2021 at 22:25
  • He wanted to know if you knew your computer science. Choosing the right algorithm is important when you go to very large datasets. An n-logn algorithm typically solve a data set by splitting the input data in half, solve each half recursively, and merge the two results back. Look at mergesort.
    – Thorbjørn Ravn Andersen
    Oct 13, 2021 at 22:31
  • @ThorbjørnRavnAndersen: TBH, if that were the case, I'd probably just Google an algorithm (or, better yet, the code to implement said algorithm)
    – user32190
    Oct 13, 2021 at 22:50
  • 3
    O(n^3) is something that gets you into trouble even with a powerful computer. O(n^3) will violate time constraints. With O(n^2) you can bet that you'll get enough complaints from some customers that you have to fix it.
    – gnasher729
    Oct 13, 2021 at 23:43
  • 5
    Well, I have seen colleagues worrying days about how to optimize their algorithm and when I asked what it was used for, it turned out that due to real world physical constraints in the warehouse where they would use the program and the algorithm, n would never be larger than 3. It's hard to find an algorithm bad enough to mess that up and it's certainly not worth worrying about O notations then. "Algorithm" does not neccessarily mean lots of data. It just mean it's easier to have a formula than to make single cases.
    – nvoigt ♦
    Oct 14, 2021 at 12:26

4 Answers 4

Reset to default
11

Was it a mistake to discuss the necessity of optimization, or not?

It wasn't a mistake.

Might it have worked in my favor?

It might well have.

I think your answer is exactly what I would want to hear if I were the hiring manager. IMHO, too many candidates talk about computer science and theory, while too few take a real-life business viewpoint.

Well done.

Improve this answer
12
  • 2
    Exactly. If it meets the spec then it's good enough. After that, more time spent optimizing is time wasted which could have been applied to other business needs.
    – brhans
    Oct 13, 2021 at 23:46
  • 1
    I would consider the situations where an interviewee wrote a program and didn't know there was a solution that would scale better, and wrote a program and deliberately chose one that didn't scale well different, and I would like to know which one this was. The reasoning "good enough" needs background information.
    – Thorbjørn Ravn Andersen
    Oct 14, 2021 at 8:31
  • A typical distinction in a real world scenario would be whether you need to do that computation just once or whether you (or even some customer) needs to do it over and over again. In the first case any time spend on optimization after you got the result is essentially wasted.
    – quarague
    Oct 14, 2021 at 10:01
  • 1
    @ThorbjørnRavnAndersen: I follow the philosophy of: "First get it done, then get it done FAST." First priority is to write a program that works. If the program is too slow, then optimize as necessary.
    – user32190
    Oct 15, 2021 at 17:14
  • 1
    @ThorbjørnRavnAndersen Sure. I have about 8-10 years of experience working in mobile application development, some of which was as an intern. I never concerned myself with making optimizations unless there was something obviously wrong, and - in any case - my clients were perfectly happy with the final result. My philosophy comes from a college professor. Many profs at my university have industry experience.
    – user32190
    Oct 16, 2021 at 16:56
7

When I was still interviewing, I would often ask similar questions. I state a problem, asks you to describe an algorithm, and if the running time isn't optimal, first ask you whether you can see a way to improve then, followed by some discussion about complexities.

"I wouldn't be concerned with optimization unless it violates time constraints" is missing the point. Multiple ways.

First, it's not answering the question. It's an interview. I want to know what you know about time complexities and scaling. You're deflecting the question.

Second, it gives the impression you're not concerned about looking ahead. You give the impression you just want an assignment with clearly defined constraints, and anything with fits is good. But if I have to pick between someone who writes code which needs to be revisited next year when the project grows by 25% versus someone who writes code which works till the project has grown by 250% before it needs to revisited, I pick the latter one.

Third, there's a difference between a bad algorithm (O (n^3) vs O (n log n)) and code which isn't optimized. A cubed algorithm will scale poorly, no matter how it's optimized.

Fourth, if you are only concerned about performance once time constraints have been violated, you're too late. That's the moment the company will start losing money.

Now, if you were interviewing with me, and you would have made such a remark, but went on and answered the question, I wouldn't hold it against you. But don't go on about it -- the interview is only so long, and I do need to know what you know about time complexities, and how well you can judge them.

Improve this answer
4
  • 5
    This is spot on. The remark was okay, but it's no substitute for actually answering the question.
    – Gregory Currie
    Oct 14, 2021 at 15:01
  • 3
    Exactly. You don't lose points for saying this. You don't lose points for not getting the optimal solution on the first try. But I'm giving you this test to see your CS skills, I want you to try and find a better answer. Depending on the level of the job and the skills you show in getting there the O(n^3) may or may not be good enough to pass.
    – Gabe Sechan
    Oct 14, 2021 at 17:16
  • +1 for this. Way too often on SE Workplace people go the route of "that must have been a trick question to see if you refuse it". I've never seen or heard of that in reality; assume the question they asked is the one they wanted answered.
    – Daniel R. Collins
    Oct 14, 2021 at 21:47
  • ""I wouldn't be concerned with optimization unless it violates time constraints" is missing the point. Multiple ways." I told the interviewer that I didn't know how to optimize the algorithm. If I ever had the knowledge I needed to optimize that algorithm, that knowledge is now gone. I did the Software Engineering track in college, so I didn't really touch data structures & algorithms after my first year (although I still know some basics)
    – user32190
    Oct 15, 2021 at 17:18
1

I, too, see nothing damning in your response. You wrote an algorithm that presumably worked. You were asked if you knew how to improve it and you honestly said, "no." You then said that you would only strive to improve the performance of the algorithm if you actually observed that it needed to be improved. ("If it ain't broke, don't fix it.") All of these answers are entirely defensible.

Improve this answer
0

In general, its great idea, only I would suggest another approach next time.

Instead, ask what kind of n you should expect right at the beginning. If asked why, give the talk. But you are likely to be told "any/unknown" anyway.

Then remember the interview is more focused on how do you think rather than if you can solve the task (well, mostly). Given the situation, I would say something along the lines of "I can't think of anything better at the moment, were it real situation, I would first check for n ranges and business needs and if needed, probe the internet and/or consult my colleagues"

The talk:

I wouldn't talk about time-constraints directly, that sounds like you aim for the bare-minimum effort; instead talk about real usage - like whether the code is part of UI vs nightly ran backend job. Show you understand business impact - if n is low and will stay so, it may not be worth implementing something more complex. If it is low now, but expected to rise in the future, talk about prioritization, technical debt, even premature optimization (e.g. I can spend two days on something, that may become a problem in 6 months or on something that brings value now).

Note:

The interviewer then asked if I could improve my algorithm to O(nlogn) time.

In my experience, the interviewers tend to ask "Can you think of any way to improve your solution" anyway, but in this case it is likely the interviewer knew it can be done in O(n log n).

Improve this answer

You must log in to answer this question.