As an interviewer, sometimes I feel a little silly having to ask a candidate super basic things like what the runtime complexity is for inserting an item into a list or array. But then a third of candidates that I interview fail pretty badly. At his last fortune 500 job one of my coworkers started every interview with fizzbuzz and had about a 50% pass rate on it. Maybe that's a problem with candidate sourcing, but there's a lot of people out there that can't code.

There is a core truth that there are "programmers" out there who cannot program, and the only way to filter them out is to have them implement some algorithm live.

But I think a lot of the grief around whiteboard interviews comes from all the additional crap that's grown up around that, including:

1. That ideally a candidate should code up solutions on a whiteboard, while standing. That it's unnecessary, or even bad, to try to replicate a working situation by having the candidate seated at a computer.

2. That there's a correlation between difficulty of question and quality of developer. So a candidate who can implement both fizzbuzz and quicksort at whiteboard from memory would be a better developer at your company than one that can do fizzbuzz, but not quicksort.

3. That the ideal programming question has some sort of "trick". So the ideal flow when a candidate is answering a question starts with the candidate implementing a naive solution. After which the interviewer says "it's possible to do better". Then the candidate ponders for, ideally 30-60 seconds, whereupon they realize the trick and code up the optimal solution.

My ideal interview process recognizes the need for a developer to demonstrate the ability to code while at the same time recognizing the above interview style for the cargo cult exercise that it is.

What are these companies that ask fizzbuzz? Every company I have applied to lately, asks me impossibly tough questions on hackerrank, which have to be done in like 30 minutes each. That would mean perfect syntax, and perfect coverage of test cases with no knowledge of what test cases are failing, or else I am rejected.

EDIT : Add to that, perfect time complexity.

I had a question recently, which was so tough, that forget the allotted time, I have asked my friends about how to solve it and they seem to have no clue either.

Can you link to it / describe it?

This is all I remember now :

An array represents a binary tree like this :

        1
       / \
      2   3
       \ /
       4 5
      /
     6

is represented as : 1 2 3 * 4 5 * 6

so apart from the last level, any missing child nodes are represented as *. You need to find the set of unconnected nodes whose sum is maximum. Child-parent relationship means they are connected.

What is the runtime complexity for inserting an item into a list or array?

O(n) - regardless linked structure or array backed.

How is inserting an item at the head of a linked list O(n)?

Easy:

    insert(list, node):
        node.next = list.head;
        list.head = node;
        sleep(list.count++);

Remove the `sleep` in second version, and quote significant speedup. See also http://thedailywtf.com/articles/The-Speedup-Loop

It's an average. Sometimes you insert at 0, sometimes at 1, sometimes at 2, ... sometimes at n. On average it's O(n).

In this case it's the worst-case performance.

Who said you insert at different locations?

Nobody. But who said you insert at the head? And who said the whole thing is list-backed? Insert is just insert--not a lot to work with there.

Performance complexity is spoken to general cases and averages unless indicated otherwise.

"insert" does not stipulate prepend or append. The latter two operations are O(1) both for linked and array backed [amortized O(1) for array backed and actually faster due to high constant costs of allocating/releasing/iterating linked structures]

O(n) means it takes less than or equal to linear time to preform the operation. So if an operation is O(1), it is also O(n).

O(1) is a subset of O(n).

Depends what you mean by insert, list and array.

there's no "time complexity" associated with inserting an item to an abstract linked list. The answer varies with implementation. Any answer <= O(n) could be correct.

"Linked list" usually refers to a very specific structure (regardless of language, or whether it is implemented as pointers or arrays or whatever) - one in which to find the middle element you have to traverse at least half the list.

Singly linked list or doubly linked lists are still considered linked lists. Skip lists, even though they technically are lists of linked items, are not generally considered a "linked list" data structure.

Even ignoring "implementation details", insertion at head/tail would be O(1). Why would you traverse the list to insert an item?

But average case or worst case are in the middle (for a doubly linked list) or the end (a singly linked list without a tail pointer).

There's no "worse case" for insertion if the api just says list.insert(item).

The half-trollish point being that nothing is "obvious". Indeed, list insertion is O(1) in popular programming languages s.a python or JS.

When I was doing Delphi, the first technical question was, "what is the difference between a function and a procedure?" That was a quick and easy way to figure out who had written a program in Delphi before. Anything more complex than that or FizzBuzz doesn't add any value.

Case in point: I interviewed a guy who nailed even the most obscure stuff, but he couldn't finish a project. He was great at small, complex problems, but he couldn't ship. We needed someone who can ship.

Having a hard time understanding why those candidates were even called in. No pre-screen coding practice? No pre-screen phone call?

I don't know what their exact process was, but I'd guess there was just a non-tech phone screen before the onsite. It's a tricky balance, some people get insulted if you ask them to complete a pre-screen coding exercise. "I have 15 years of experience, stop wasting my time!" On the other hand, I've interviewed a few people with that much experience, supposedly code-writing lead engineers, that couldn't write the code to insert an item into a sorted array.

There are a lot of people who have more credentials than skill, which isn't easily detected by looking at a resume.

Even more concrete example, something like:

Q: Explain the difference between they're, their, and there.

Q: Principle or Principal?