5 ms·

At my last job interview I had to implement popcount and explain how to optimise it (amongst other things). I was able to jot down a naïve implementation and t

by klmr 6y ago

At my last job interview I had to implement popcount and explain how to optimise it (amongst other things). I was able to jot down a naïve implementation and the obvious optimisation based on a lookup tables. I only vaguely remembered the Bit Twiddling treatment of the subject but, with a bit of nudging from the interviewer, I managed to implement and explain the variant that runs in O(set bits) (“Brian Kernighan's way”). I got the job. Now, it’s fashionable to deride this this kind of code interview as unrealistic and unhelpful. But in my first week on the job, by sheer coincidence, I had to use the function. Obviously there are existing, efficient implementations, including intrinsics. But knowing how to derive an efficient implementation certainly didn’t harm. My job has since evolved into different responsibilities but low-level algorithmic knowledge is still important. I’m not sure testing for it in job interviews is generally a good idea, and designing good job interviews is certainly a big topic. But in my particular case it happened to be a relevant, fair test of my abilities.

wiredfool 6y ago
I’ve had that question twice in google phone screen interviews, and iirc, the best answer has changed from the hash table thing to just use the hardware instruction.
- praptak 6y ago
  I don't believe companies want to hire for knowing that popcnt exists. The interviewer should follow up with the hypothetical situation when either the language or the CPU doesn't have the instruction. Nobody should ask this anyway, this has become the fizzbuzz type of question.
  - wiredfool 6y ago
    Yeah, it's a stupid question, which is why I was surprised that Google asked it to me twice, separated by a couple of years. What's funny is that 15 years later, I actually had a use for popcnt, put it together with something that seemed expensive at the time, and wound up with a C program that exhaustively searched a problem space in .12 sec. On a single core, in a vm, on a laptop. So much for me trying GPU programming on that one. (as in , feckit, there aren't that many possibilities, we'll just count them all)
  - ericbarrett 6y ago
    Long before leetcode, I used to ask an "algorithm" question in interviews. I don't remember it exactly, but IIRC it was about determining quickly if a number was 2^n-1 for any n. (Don't shoot me, this was a decade ago.) There were three broad ways candidates answered it: 1) Hack out a for-loop-style bit count. This was good, because even though it wouldn't be optimized, it demonstrated they could understand the problem and at least conceptualize a solution. 2) Give the "leetcode" best-answer (it was some bitwise math trick). I'd then ask if they'd seen the problem before, and the answer was always yes. This was a mark in their favor—but no better than (1)—and also a signal I needed to ask them a follow-up question that actually made them think. 3) Code a bit, but not quite arrive at a solution. I'd then probe them about their thought process. Not an automatic fail, sometimes our brains just don't walk down the corridors we want them to at a given time, especially during an interview. (One candidate couldn't hold the marker steady because his hands were shaking too much! Poor guy.) 4) Give up and say they had no idea. Obviously the worst case for the interviewee. The purpose was not to check a candidate's recall and test-taking abilities, but rather to watch them reason through a novel problem, appropriately limited in scope for the interview timeframe. Case (2) served as a great short-circuit to block test-preppers lacking actual experience.
vsareto 6y ago
I mean, it wouldn't hurt to know how to do all of this, plus all the data structures & algorithms stuff, plus all major and minor details about your language and environment of choice, plus anything else that someone deems important, but realistically most of us need a job before you can learn all of that. Even if you do learn it all, people tend to lose knowledge they don't use, so it may have an expiration date depending on how good your brain is. New technologies and advancements can also introduce more knowledge that becomes required to know for interviews. The pool of knowledge for interview questions might continue to grow until you'd have to study for a year or more to have a high chance of passing it.
- nayuki 6y ago
  DSA = data structures & algorithms
  - deleted 6y ago
    [deleted]
  - deleted 6y ago
    [deleted]
- klmr 6y ago
  > but realistically most of us need a job before you can learn all of that The interview was for a senior position. > Even if you do learn it all, people tend to lose knowledge they don't use Let me emphasise that my interview was not a knowledge test (and at any rate I don’t study for interviews). I wasn’t expected to know by heart how to implement popcount. The interviewer was trying to see me work. Successfully, I might add. — Another question I got concerned something I had no knowledge of, and I had to derive a solution myself. In fact, I failed to do so, but that didn’t prevent me from getting the job since the interviewer was satisfied with what they observed about my thought process.

by klmr 6y ago

wiredfool 6y ago

I’ve had that question twice in google phone screen interviews, and iirc, the best answer has changed from the hash table thing to just use the hardware instruction.

praptak 6y ago
I don't believe companies want to hire for knowing that popcnt exists. The interviewer should follow up with the hypothetical situation when either the language or the CPU doesn't have the instruction. Nobody should ask this anyway, this has become the fizzbuzz type of question.
- wiredfool 6y ago
  Yeah, it's a stupid question, which is why I was surprised that Google asked it to me twice, separated by a couple of years. What's funny is that 15 years later, I actually had a use for popcnt, put it together with something that seemed expensive at the time, and wound up with a C program that exhaustively searched a problem space in .12 sec. On a single core, in a vm, on a laptop. So much for me trying GPU programming on that one. (as in , feckit, there aren't that many possibilities, we'll just count them all)
- ericbarrett 6y ago
  Long before leetcode, I used to ask an "algorithm" question in interviews. I don't remember it exactly, but IIRC it was about determining quickly if a number was 2^n-1 for any n. (Don't shoot me, this was a decade ago.) There were three broad ways candidates answered it: 1) Hack out a for-loop-style bit count. This was good, because even though it wouldn't be optimized, it demonstrated they could understand the problem and at least conceptualize a solution. 2) Give the "leetcode" best-answer (it was some bitwise math trick). I'd then ask if they'd seen the problem before, and the answer was always yes. This was a mark in their favor—but no better than (1)—and also a signal I needed to ask them a follow-up question that actually made them think. 3) Code a bit, but not quite arrive at a solution. I'd then probe them about their thought process. Not an automatic fail, sometimes our brains just don't walk down the corridors we want them to at a given time, especially during an interview. (One candidate couldn't hold the marker steady because his hands were shaking too much! Poor guy.) 4) Give up and say they had no idea. Obviously the worst case for the interviewee. The purpose was not to check a candidate's recall and test-taking abilities, but rather to watch them reason through a novel problem, appropriately limited in scope for the interview timeframe. Case (2) served as a great short-circuit to block test-preppers lacking actual experience.

vsareto 6y ago

I mean, it wouldn't hurt to know how to do all of this, plus all the data structures & algorithms stuff, plus all major and minor details about your language and environment of choice, plus anything else that someone deems important, but realistically most of us need a job before you can learn all of that. Even if you do learn it all, people tend to lose knowledge they don't use, so it may have an expiration date depending on how good your brain is. New technologies and advancements can also introduce more knowledge that becomes required to know for interviews. The pool of knowledge for interview questions might continue to grow until you'd have to study for a year or more to have a high chance of passing it.

nayuki 6y ago
DSA = data structures & algorithms
- deleted 6y ago
  [deleted]
- deleted 6y ago
  [deleted]
klmr 6y ago
> but realistically most of us need a job before you can learn all of that The interview was for a senior position. > Even if you do learn it all, people tend to lose knowledge they don't use Let me emphasise that my interview was not a knowledge test (and at any rate I don’t study for interviews). I wasn’t expected to know by heart how to implement popcount. The interviewer was trying to see me work. Successfully, I might add. — Another question I got concerned something I had no knowledge of, and I had to derive a solution myself. In fact, I failed to do so, but that didn’t prevent me from getting the job since the interviewer was satisfied with what they observed about my thought process.