4 ms·

> Me: on which kind of CPU? Why not let me compare my code to yours in a benchmark? While I agree that this is the right answer, questions regarding "Big-O" ar

> Me: on which kind of CPU? Why not let me compare my code to yours in a benchmark? While I agree that this is the right answer, questions regarding "Big-O" are trying to find out whether or not you can evaluate the complexity of an algorithm. If you can, you have some hope of writing different useful benchmarks that could be compared, where sometimes you can see orders of magnitude of improvement. If you can't, you might be just blindly tweaking the code to get 1-5% improvement from compiler flags, assembly optimizations, etc. In practice this recruiter might be bad at their job by binding themselves so rigidly to the script.

jerf 9y ago
"While I agree that this is the right answer, questions regarding "Big-O" are trying to find out whether or not you can evaluate the complexity of an algorithm." Most algorithms for counting bits will be O(1) for a given int, so O(number of ints) for a list of ints. Algorithms that aren't O(1) for a given int [1] will still be essentially O(1) since the upper bound would be so tight. So I don't think that was a Big-O question. [1]: "count = 0; while i != 0 { count += i % 2; i >> 2 }". Technically this is O(leftmost set bit), but on a fixed-bit int could be considered O(1) with a suitable constant. Note that algorithm isn't entirely pointless; it works on bigints too, so in something like Python where ints and bigints are not distinguished by type you could use it as a fallback for "generic int" (which may include user-defined classes). (Though of course there are ways to speed it up.)
SilasX 9y ago
Well, I've been in this scenario before, and have resorted to that. I was this guy [1]. (Interview question in link, I had written a solution.) The interviewer stubbornly insisted that the run time was n^2 because it had an inner loop. (Never mind that the inner wasn't looping over pairs with the bigger loop, but just the bits within that element.) I went through a number of heuristics to convince him otherwise: what if you doubled the list, how would that analytically affect the run time? What if the elements were bigger? (as you can find from the reddit thread) Disturbingly, I asked him what he would need to see to convince him that the code I wrote was O(n), and he said, "no inner loop", which reveals a profound misunderstanding of both the issue at hand, and how to resolve disagreement. At that point, I resorted to saying, well, let's run the code with increasing input size and see how it scales (which would give valuable information about its actual scaling behavior). Then he refused, left the room, and told the director to veto me from the rest of that day's interviews. [1] https://news.ycombinator.com/item?id=6070001 https://news.ycombinator.com/item?id=6070001
- wyldfire 9y ago
  > Then he refused, left the room, and told the director to veto me from the rest of that day's interviews. "Bullet dodged" -- he did you a huge favor.

jerf 9y ago

"While I agree that this is the right answer, questions regarding "Big-O" are trying to find out whether or not you can evaluate the complexity of an algorithm." Most algorithms for counting bits will be O(1) for a given int, so O(number of ints) for a list of ints. Algorithms that aren't O(1) for a given int [1] will still be essentially O(1) since the upper bound would be so tight. So I don't think that was a Big-O question. [1]: "count = 0; while i != 0 { count += i % 2; i >> 2 }". Technically this is O(leftmost set bit), but on a fixed-bit int could be considered O(1) with a suitable constant. Note that algorithm isn't entirely pointless; it works on bigints too, so in something like Python where ints and bigints are not distinguished by type you could use it as a fallback for "generic int" (which may include user-defined classes). (Though of course there are ways to speed it up.)

SilasX 9y ago

Well, I've been in this scenario before, and have resorted to that. I was this guy [1]. (Interview question in link, I had written a solution.) The interviewer stubbornly insisted that the run time was n^2 because it had an inner loop. (Never mind that the inner wasn't looping over pairs with the bigger loop, but just the bits within that element.) I went through a number of heuristics to convince him otherwise: what if you doubled the list, how would that analytically affect the run time? What if the elements were bigger? (as you can find from the reddit thread) Disturbingly, I asked him what he would need to see to convince him that the code I wrote was O(n), and he said, "no inner loop", which reveals a profound misunderstanding of both the issue at hand, and how to resolve disagreement. At that point, I resorted to saying, well, let's run the code with increasing input size and see how it scales (which would give valuable information about its actual scaling behavior). Then he refused, left the room, and told the director to veto me from the rest of that day's interviews. [1] https://news.ycombinator.com/item?id=6070001 https://news.ycombinator.com/item?id=6070001

wyldfire 9y ago
> Then he refused, left the room, and told the director to veto me from the rest of that day's interviews. "Bullet dodged" -- he did you a huge favor.