9 ms·
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
by kevan 9y ago
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.
- lighthazard 9y agoHaving a hard time understanding why those candidates were even called in. No pre-screen coding practice? No pre-screen phone call?
- trendia 9y agoThere are a lot of people who have more credentials than skill, which isn't easily detected by looking at a resume.
- kevan 9y agoI 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.
- brookside 9y agoWhat is the runtime complexity for inserting an item into a list or array?
- xxs 9y agoO(n) - regardless linked structure or array backed.
- arethuza 9y agoHow is inserting an item at the head of a linked list O(n)?
- Joe-Z 9y agoIt's an average. Sometimes you insert at 0, sometimes at 1, sometimes at 2, ... sometimes at n. On average it's O(n).
- poikniok 9y agoWho said you insert at different locations?
- abalashov 9y agoNobody. 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.
- chaosite 9y agoIn this case it's the worst-case performance.
- sherincall 9y agoEasy: 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 http://thedailywtf.com/articles/The-Speedup-Loop
- pflats 9y agoO(1) is a subset of O(n).
- GhostVII 9y agoO(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).
- avip 9y agothere'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.
- beagle3 9y ago"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.
- avip 9y agoEven ignoring "implementation details", insertion at head/tail would be O(1). Why would you traverse the list to insert an item?
- beagle3 9y agoBut 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).
- avip 9y agoThere'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.
- dean177 9y agoDepends what you mean by insert, list and array.
- mtviewdave 9y agoThere 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.
- sage76 9y agoWhat 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.
- beagle3 9y agoCan you link to it / describe it?
- sage76 9y agoThis 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.
- Clubber 9y agoWhen 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.