Hacker News Reader

"What is the big O time of heap sort?" vs "Would you mind writing a function that returns true if any two numbers in the list sum to zero? For example, it would return false for [2,3,5] and true for [-3,5,3]"

Are completely different questions. The first is useless: It tests if someone remembers how a heap sort works, and whether or not they use the term "worst case" in the answer.

The second one is much better. Some could sort the list, (nlogn time, constant memory) then walk through it. They could use a hash table (idealy n time, assuming no collisions, but more memory). You also get to see if their solution handles the 0 case. If they answer it very quickly, you can move on to the three sum problem. If they recognize the question from university or something you can do a different one.

If someone doesn't know the big-O time of iterating through a list of integers once for every integer, then I seriously doubt their dedication to the field of software. This is not some pie in the sky doubt, it is of legitimate concern whether someone knows how to properly approach a problem of this nature with the right data structures, code, and communication.

Good interviewers put the interviewee at complete ease before they bring out the technical questions. From an economics point of view, it is better to hire the person that is in all other ways identical, yet interviews poorly, since they are less likely to want to leave.

Very good illustration, I must say. I strongly disagreed with the GP's rant about knowing O-notation, but I realized he might have faced the first type of questions a lot (e.g tell me the O-complexity of X algorithm).

My experience with Amazon was actually the opposite, but I might have been lucky. All the interviewers were very friendly and started from simple questions and went on to more complex ones. Never a "do you know concept a from language Y". In fact, one of them worked with me through the solution to a pretty tricky problem, and when we were done, he actually took a picture of my solution on the whiteboard! So yeah, it was fun :)

Were you given an offer by Amazon?

That was my experience at Amazon as well. Most of the interviewers were very good and the questions were a reasonable judge of skill IMO.

I didn't get an offer (understandably so) but I thought the interview was good.

That mirrors my experience with Amazon too. Although it was 3.5hrs of full-on whiteboard coding, I really enjoyed the process and felt like I learned a lot. 3 of the 4 interviewers were excellent.

I generally agree, most logic questions are useless, but Big-O notation I use every day. Programmers who don't understand the performance difference between Array#include? and Set#include? in ruby are dangerous!

I'm curious to know where you use the notation in daily programming. In code comments? Discussions with other developers? Other documentation?

I use the spirt of Big-O almost daily, but do the actual calculations rarely, and basically never use the notation. With some experience, you quickly get an intuitive feel for execution time, which is good enough in most cases.

Actually using something like a math notation to solve a programming problem is asking for too much. What are those general problems which can't be solved by standard libraries, frameworks and IDE's these days?

And even if you are facing problems that mandate you to roll out your stuff how much of that requires these math tricks.

Given all this, if you truly want to hire a math geek to get some magic done. I guess you are looking at a very small pool of people to hire from and it should hardly be a problem to hire one.

Big-O notation is hardly "math geek" stuff. I'd not call this comment ridiculous, because I might have misunderstood it, but catch me in my cups and ask me for my true opinion and maybe I'd say that.

Big-O notation is pretty basic, and very useful. Combined with a memorized table of powers of two (you don't need all of them - I know up to 2^20, and this has proven sufficient - just enough so you can guess log N for a given value) you have a good chance at being able to make quick calculations about time and space requirements for things. Which, since we don't have infinitely fast computers with infinite amounts of memory, often comes in handy.

I'm not talking about Big-O. I'm talking about the general theme of these interviews.

Besides that I still don't understand this. I don't even know the last time anybody around me ever had a problem or a show stopper problem anything to do with Big-O or an algorithm.

Its always how the programmer can take pressure, how he can contribute to making the project happen, getting things done, how he can collaborate with fellow team mates, how he responds under times of crisis, how good he is with tools, what are his everyday practices, does he write unit tests, does he do code reviews, does he document the API's he writes, how does he package his code, how update he is with software world(tools, framework and techniques) etc etc.

Lets be frank, Its always these things that are relevant today in practical everyday software projects today. Unfortunately people hardly ask questions on these and then complain of bad software practices among people these days.

> I don't even know the last time anybody around me ever had a problem or a show stopper problem anything to do with Big-O or an algorithm.

Either your team does horrifically easy work, or no one has told you about their abstract work. I am sorry, but even writing CRUD apps I have to think about the informatics of the system to make it work reasonably well.

If I'm reading up on a new technology it's useful to understand what they mean when they say 'operations are O(1)'.

Additionally, when writing an API for use by other developers its useful to say, this operation runs in constant time, that one in logarithmic time.

Redis, for example, mentions the computational complexity of all operations in its docs. Additionally, everyone should know that most decent sorting algorithms are O(n log n), and understand the implications of that.

The last time I talked about Big-O notation was three days ago, when talking about whether or not inserting/deleting from a list should be done online or queued up:

  Zarel: and for insertions, aren't they O(nm) for n insertions into a list of size m either way?
  Cathy: inserting n elements into a list of size m when done with queueing requires at most m iterations
  Cathy: when not done using a queue, it requires at most n*m iterations
  Cathy: a factor of n is the difference
  Cathy: of course, n might be pretty small, depending on how many insertions happen in the debounce wnidow
  Cathy: n might be 10-15
  Zarel: how do you insert n elements into a list of size m in m iterations?
  Cathy: iterate over the list of m elements
  Cathy: well, i guess you'd need to sort the list of n elements first
  Zarel: oh, I see, I forgot about sorting the list
  Zarel: so it'd be O(n+m)
  Zarel: which is admittedly much faster for our purposes
  Zarel: well, considering n is likely to be approximately 5, "much" might be an exaggeration
  Cathy: in any case, i agree that inserting/deletion approach is the right way to do this
  Zarel: incidentally if we wanted we could apply certain optimizations to improve an insertion from O(n)
  Zarel: for instance, binary search
  Cathy: it's not immediately obvious whether that is faster than the sorted queued
  Zarel: actually, that's not a bad idea regardless
  Cathy: but it's certainly faster than the naive single insertion
  Zarel: I mean, O(n log m) is significantly faster than O(n+m)
  Zarel: when n is ~5 and m is ~1500
  Cathy: true, and it actually makes it clear that using a queue is unnecessary

I don't know of a better way to discuss optimizing an inner loop than to use big O notation.

All one really needs to know about Big-O is that nested data lists can be exponentially harder to process. If you understand that then you understand the need for it and when the time arises for you to create these type of structures you'll calculate the time needed to process them accordingly using said method. In turn helping you predict future performance and avoiding bottlenecks.

In your example, I see Big-O as a side effect of using the right data structure for the job. If you need a data structure to hold items that should not be duplicated or ordered then a set (or hash which is likely what the ruby set is based on) is what you want to use because it is not only faster but conveys meaning to the maintenance programmer. If you need order maintained then move up to an ordered set. If you need to keep distinct duplicates then some sort of list is going to be needed (Array, Linked, etc...).

I guess what I'm trying to say is that Big-O between a Set and Array do not matter if you can't use a set to begin with. If the problem fits a set then using a set is right regardless of the performance implications.

I do agree with your overall premise of laziness though. Most programmers default to a list likely because it is the first thing ever taught, and for some reason rarely think beyond it. For me, part of the fun of solving coding problems is finding the best fit data structure :)

> and a lot of the more academic questions

It is on purpose. A <bigcompany> recruiter confessed. He said they are specifically targeting recent grads. So plenty of questions are of that type.

I guess they want to indoctrinate and take advantage of them while they are "fresh".

> did like the question I was asked about how I'd design an elevator system and then asked how my solution would scale. That's not too far off from what I'd be doing, albeit in an abstract form.

That would piss me off though too. "So does Amazon write algorithms for its elevators?". Why not just simplify a problem they solve. "So you have key value storage and you want to make it distributed". Why even talk about elevators?

Actually, yes...they do. I work in a building with an elevator control system designed by an internal engineer.

More importantly, the elevator control system uses mathematical expertise that is normally used solving variants of the multi-commodity flow problem, used extensively in the Supply Chain.

> Actually, yes...they do. I work in a building with an elevator control system designed by an internal engineer.

Well then that makes a good interview question then!

Heh, that's pretty cool. How does it compare to the average elevator?

When load is not particularly high, it works well (seemingly efficient for passengers and in energy consumption). When load gets high (think ~noon), it tends to perform pretty badly in terms of latency.

Sib has it about right. It is an NP complete problem, and I'm pretty sure the solution is using a Heuristic, but it does seem to be pretty suboptimal during lunch time. Then again, maybe it just seems worse because you wait longer as a tradeoff to having a faster ride to your floor.

> are still concerned about big-O notation

Time complexity is important, and hiring someone who doesn't think so is dangerous. That said, it's important to ask about an algorithm you've already discussed. Asking "what's the big-O of <generic algorithm>" also tests for whether you remember the specifics of that algorithm, which isn't terribly useful.

There are jobs where algorithms matter. Where someone picking the wrong data structure or algorithm can completely fuck up the problem, or where the company's secret sauce is doing something much faster than their competitors are doing it.

Yea this is where I'm at with it. If I walk into an interview and the first question is what is the difference between an abstract class and an interface my interest in the interview is probably going to decrease exponentially. How about asking me about my design approach to a specific problem, what frameworks have I try when presented with a specific problem and my thoughts on it, or what I'm currently learning. I get why they do it but at a certain level it's almost a sign of disrespect to be asked to fizzbuzz if you can verify I've been working at reputable companies for the last x yrs. Let's have a more nuanced discussion about technology so that you can confirm that I didn't just cram certification questions over the weekend and I can get a gauge on the type of problems I may have to tackle on the job.

You assume people working at programming jobs for years on end have a clue... that's not always true. I've worked with people who couldn't do fizzbuzz, or describe the difference between an interface and an abstract class, or any other basic programming stuff.

If they throw you an easy pitch, knock it out of the park and they'll ask you something more difficult afterward.

This is precisely right: I ask people questions like the difference between an interface and an abstract class as a gauge, because I've had so many people answer them really badly.

The question wouldn't normally come out of the blue, though, but as a follow-up from part of a design exercise where they would have just used one or the other in their design, and as part of finding out whether they could justify their choice.