7 ms·

> There are a whole bunch of popular interview questions As a very personal strong opinion, this makes me groan. I'm not concerned If someone happens to know

> There are a whole bunch of popular interview questions As a very personal strong opinion, this makes me groan. I'm not concerned If someone happens to know some esoteric trick that they could Google search (Unless of course you're applying for a position at a company that manufactures very low level devices like microcontrollers or embedded systems and questions like this are _actually relevant_). I'd rather know whether or not they are a pleasant person, are a team player, whether they have leadership aspirations, and take responsibility.

jenwkejnwjkef 6y ago
Nobody wants to see the XOR solutions. These questions are really basic and only filter out the non-programmers. Any decent programmer should be able to solve all of these without a problem.
- dragontamer 6y ago
  I wouldn't say "nobody" wants to see the XOR-trick solution. Its just that those who DO care about it is asking about the general solution: Reed-Solomon codes, or maybe a more modern (harder to understand) variant: like LDPC or Tornado codes. Anyone who needs to recover *ONE* symbol from a data-stream with noise actually needs to recover two, three... four... symbols in the general case. One symbol of erasure recovery is the weakest-of-the-weakest of error correction codes. Its even weaker than the single-error-correction / double-error detection Hamming Code (discovered back in 1950s). XOR-trick is your "basic parity bit", and is the stuff taught to undergrads to wet your appetite for error correction codes (well... erasure correction in this case. Since XOR isn't strong enough to actually correct an error. Only an erasure).
  - shiftingleft 6y ago
    I don't see how the problem corresponds to erasure coding. Typically in erasure coding you know the locations of the erasures. Here, you don't know the location. Maybe you can elaborate on how it relates to erasure coding?
    - dragontamer 6y ago
      Since you asked this question in two different locations, I'll give a 2nd answer here. One way to construct a Reed Solomon code is to create a Vandemonde Matrix. 1 a^1 a^2 a^3 a^4 a^5 ... 1 a^2 a^4 a^6 a^8 a^10 ... 1 a^3 a^6 a^9 a^12 a^15 ... ... All of the "1" values are from a^0. As long as a^1, a^2, a^3... are distinct, then this matrix is invertible (aka: all rows / columns are linearly independent). In a GF(2^8) field, there are 2^8-1 distinct values (the values 0x01 through 0xFF), making a 255x255 matrix. The polynomial "x" (aka: 0x02) is often chosen to be the value of "a", but it can be any primitive element that loops around all 255 non-zero numbers and still work. This Vandemonde Matrix has a very simple construction, but it is non-systematic (the data is "mangled" in encoded form, so we need to invert the matrix to decode). However, this non-systematic form is easier to see some patterns. Now lets take the 1st column: 1 1 1 1 1 ... Hmmm... look familiar? What happens when we multiply the data vector with this column?? It becomes a bit more obvious: 1 1 1 [d0 d1 d2 d3...] * 1 1 1 1 1 1 Remember, in Reed-Solomon, you perform operations over GF(2^blah). So all multiplications are GF-multiplications. But these are all multiplications by 1, so we can just ignore the complications of GF-multiplication entirely. (Even in GF(): a multiplication by 1 is just the identity). To finish the matrix-multiply, we add everything together. But we do GF-addition (not regular addition). A GF-addition is also known as XOR. So the ultimate answer is: d0 XOR d1 XOR d2 ... Which so happens to be the first parity bit of the non-systematic Reed Solomon code. As such, we've proven the relationship between the "XOR trick" and Reed Solomon (Vandemonde construction). ------------ The hamming-distance between codes is 1. We can correct floor(1/2) errors (aka 0 errors) and 1 erasure. As such, this "all 1s matrix" is a 1-erasure punctured Reed Solomon code.
      - shiftingleft 6y ago
        Thanks a lot for the detailed answer! I'm familiar with some subset of coding and number theory, so you can assume at least some more knowledge (Galois Fields, or basics of RS codes for example). Small nitpick: The Vandermonde matrix actually isn't square. It's a (k × n) matrix, (where typically k ≠ n). Therefore, it can't be invertible. I see that many codes contain a parity bit (for example the extended Golay code), however I don't see how the operation of recovering "the missing number" could be implemented in terms of a code and its encoding/decoding algorithms. I've found this on stackoverflow: https://stackoverflow.com/a/3492967/3868157 https://stackoverflow.com/a/3492967/3868157 It describes a way to recover the missing number by constructing a Vandermonde matrix using the given numbers. This would correspond to constructing a generator matrix of a specific RS code [1]. However, after this I'm not so sure about the relation between encoding/decoding and recovering the missing number. In the end they also factor a polynomial (that could be something analogous to the error locator polynomial?). [1]: although I'm not sure if it's strictly an RS code
- RHSeeger 6y ago
  Something in the middle might be useful though. Discussing XOR and it's properties (the first part of the article) with the assumption the interviewee doesn't know them... and then working through what it means you can do with it (the second part) could be a useful exercise. "Given these properties, what can you do with it". To some extent, it still means the person that knows the tricks will do better.. but much less so.
whimsicalism 6y ago
> pleasant person, are a team player, whether they have leadership aspirations, and take responsibility. I know the above is a popular opinion, but I've worked as a SWE at a company A that had a "technical interview" process and Company B that didn't have a formalized one. I would much, much prefer to work at company A (pay differences aside) because of the type of person who passes these interviews. It can be quite difficult to determine someone's capability at interview-time. But company B had lots of competency "false positives" (in my view) whereas company A had very few. That's the value of a technical interview. That said, of course the XOR solution would never be the only one accepted, but it would probably get you brownie points here.
- RHSeeger 6y ago
  > company B had lots of competency "false positives" The thing to note is that, in exchange for this, Company A (probably) had a lot false negatives. So it comes down to whether you'd rather missing out on someone that would have been beneficial for the company (false negative) or have to deal with accidentally hiring someone that is not a good choice (false positive). The best choice to make depends a lot on the situation.
dragontamer 6y ago
> I'm not concerned If someone happens to know some esoteric trick that they could Google search (Unless of course you're applying for a position at a company that manufactures very low level devices like microcontrollers or embedded systems and questions like this are _actually relevant_). Erasure correction is a very useful trick for data-engineers. I don't think this is a microcontroller trick, as much as a data-resliliency trick. The XOR-trick is how you implement RAID5 most efficiently. A proper discussion / interview would probably describe the XOR trick, and then see if the engineer is smart enough to understand the difference between erasure and errors. -------------- With a blog post describing the XOR trick ahead of us: now I ask you (the audience): what is the difference between an erasure and an error? Why can this XOR-trick protect against an erasure, but NOT an error? And how does this relate to RAID5's known failure cases? But at that point, I'm interviewing for someone who has passed a data communications class.
- abhishekjha 6y ago
  I guess I will fail your interview as well.
  - dragontamer 6y ago
    Lol. Well, that's why I ended with: > But at that point, I'm interviewing for someone who has passed a data communications class. This is basic data-communications stuff. But there's a reason why data-communications isn't exactly a commonly taught subject: its niche and not really generally applicable IMO. My main point is that the XOR-trick is a decent data-communications question. But I don't know how generally applicable it is to other programming fields.
- shiftingleft 6y ago
  I think in erasure coding you typically know the locations of the erasures: If a disk fails, you know which one failed. However, I don't see how you would know the locations in this problem? Maybe you can elaborate on how this problem relates to erasure coding?
  - 6y ago
woofie11 6y ago
I think it kind of depends on the type of programmer one wants to hire. There are different roles, solving different types of problems. There are places for people with technical brilliance, there are places for people with social brilliance, with both, and with neither. That's healthy. You want a diverse economy with different types of positions for different types of folks, and vice-versa. If I ask a half-dozen questions like the xor trick, I'll have a filter for one type of technical background. Whether you know each of them is pretty random, but whether you know none of them or most of them is not.
- whimsicalism 6y ago
  > there are places for people with social brilliance, with both, and with neither. That's healthy There are lots of socially brilliant people out there, it's what many of us spend at least 20 years of our lives practicing. Why would being a brilliant socializer command the same salary that a brilliant engineer does?
  - bonoboTP 6y ago
    Because commanding a salary and appearing valuable is itself a social skill.
  - RHSeeger 6y ago
    Being able to interact well with others is part of being a valuable employee. You can be the best engineer in the company, but if nobody wants to work with you, it's going to negatively impact the value you bring to the company.
  - woofie11 6y ago
    Because, as you move up the management chain, understanding how people work and how groups of people work becomes more important than technical brilliance. The job of a manager is to create a healthy working environment where people work effectively, and are well-aligned to a common goal. That's hard. You don't just practice that by living. That's made easier by having people lower down who are helping and not hurting.
vzidex 6y ago
> I'm not concerned If someone happens to know some esoteric trick that they could Google search (Unless of course you're applying for a position at a company that manufactures very low level devices like microcontrollers or embedded systems and questions like this are _actually relevant_). The "XOR trick" actually nearly sank me on an interview once, I'm assuming because the interviewer shared your opinion. One of the questions they asked me to solve was the "n - 1 numbers in a list" question the article talks about - I promptly came up with the XOR solution because I have more background in low-level work than the high-level finance role I was interviewing for. Turns out, they had never seen it before, didn't really understand how/why it worked, and they took a lot of convincing to accept it as correct. I think I only still got the job was by then proceeding to also solve the problem the "normal" way.
bonoboTP 6y ago
Maybe you feel like you are being inclusive and warmhearted for praising soft skill vs 'teh codez skillz', but please also consider that tech and programming jobs is like the last refuge for people with high technical aptitude and perhaps less social soft skills regarding the meta political and expectation games, eg people somewhere on the autism spectrum. Perhaps such interviews are overused but if the interview is purely soft, and about "sell yourself to me", you will also be biased towards some people. I mean of course it's important to be able to work together in a pleasant way, but when someone's main strengths are in the technical aspects, they may like to be able to showcase that too. And yes of course in the age of high level frameworks and glued CRUD pruducts, some programming jobs are more social than technical. But not necessarily all. And I'm seeing lots of this sentiment nowadays on social media, that all "allegedly" merit based nerdy "gatekeeping" is merely about white male privilege and hence not inclusive.
- whatshisface 6y ago
  Nobody complains about puzzles in tech interviews. People care about uncreative "did you read this book about interview questions" questions. If you want to test tech knowledge in tech interviews, ask a question that isn't in any book. That takes a lot more skill as an interviewer to pull off, but if you're a hiring manager, surely you can find someone on your team qualified to design a puzzle.
  - bidirectional 6y ago
    Google's policy is to extensively discuss interview questions internally, and blacklist any that are leaked. They are still complained about near-constantly on any tangentially related HN thread.
    - deleted 6y ago
      [deleted]
    - bonoboTP 6y ago
      The attitude is often quite strange. Like on Twitter I saw a few days ago that many were riled up about the fact that a prof would ask how to solve Ax=b (linear algebra) for a deep learning / computer vision PhD position. People were calling this unnecessary gatekeeping... I'm like that's just a warm-up question to get comfortable... But apparently the loud online hive mind opinion is that all that should count is soft skills and that everyone is equally able. People are even calling out professors on Twitter (who then engage, for some reason) for saying they are looking for "outstanding" PhD candidates. Because this is apparently too exclusionary language, everyone is equally outstanding or something...

jenwkejnwjkef 6y ago

Nobody wants to see the XOR solutions. These questions are really basic and only filter out the non-programmers. Any decent programmer should be able to solve all of these without a problem.

dragontamer 6y ago
I wouldn't say "nobody" wants to see the XOR-trick solution. Its just that those who DO care about it is asking about the general solution: Reed-Solomon codes, or maybe a more modern (harder to understand) variant: like LDPC or Tornado codes. Anyone who needs to recover *ONE* symbol from a data-stream with noise actually needs to recover two, three... four... symbols in the general case. One symbol of erasure recovery is the weakest-of-the-weakest of error correction codes. Its even weaker than the single-error-correction / double-error detection Hamming Code (discovered back in 1950s). XOR-trick is your "basic parity bit", and is the stuff taught to undergrads to wet your appetite for error correction codes (well... erasure correction in this case. Since XOR isn't strong enough to actually correct an error. Only an erasure).
- shiftingleft 6y ago
  I don't see how the problem corresponds to erasure coding. Typically in erasure coding you know the locations of the erasures. Here, you don't know the location. Maybe you can elaborate on how it relates to erasure coding?
  - dragontamer 6y ago
    Since you asked this question in two different locations, I'll give a 2nd answer here. One way to construct a Reed Solomon code is to create a Vandemonde Matrix. 1 a^1 a^2 a^3 a^4 a^5 ... 1 a^2 a^4 a^6 a^8 a^10 ... 1 a^3 a^6 a^9 a^12 a^15 ... ... All of the "1" values are from a^0. As long as a^1, a^2, a^3... are distinct, then this matrix is invertible (aka: all rows / columns are linearly independent). In a GF(2^8) field, there are 2^8-1 distinct values (the values 0x01 through 0xFF), making a 255x255 matrix. The polynomial "x" (aka: 0x02) is often chosen to be the value of "a", but it can be any primitive element that loops around all 255 non-zero numbers and still work. This Vandemonde Matrix has a very simple construction, but it is non-systematic (the data is "mangled" in encoded form, so we need to invert the matrix to decode). However, this non-systematic form is easier to see some patterns. Now lets take the 1st column: 1 1 1 1 1 ... Hmmm... look familiar? What happens when we multiply the data vector with this column?? It becomes a bit more obvious: 1 1 1 [d0 d1 d2 d3...] * 1 1 1 1 1 1 Remember, in Reed-Solomon, you perform operations over GF(2^blah). So all multiplications are GF-multiplications. But these are all multiplications by 1, so we can just ignore the complications of GF-multiplication entirely. (Even in GF(): a multiplication by 1 is just the identity). To finish the matrix-multiply, we add everything together. But we do GF-addition (not regular addition). A GF-addition is also known as XOR. So the ultimate answer is: d0 XOR d1 XOR d2 ... Which so happens to be the first parity bit of the non-systematic Reed Solomon code. As such, we've proven the relationship between the "XOR trick" and Reed Solomon (Vandemonde construction). ------------ The hamming-distance between codes is 1. We can correct floor(1/2) errors (aka 0 errors) and 1 erasure. As such, this "all 1s matrix" is a 1-erasure punctured Reed Solomon code.
    - shiftingleft 6y ago
      Thanks a lot for the detailed answer! I'm familiar with some subset of coding and number theory, so you can assume at least some more knowledge (Galois Fields, or basics of RS codes for example). Small nitpick: The Vandermonde matrix actually isn't square. It's a (k × n) matrix, (where typically k ≠ n). Therefore, it can't be invertible. I see that many codes contain a parity bit (for example the extended Golay code), however I don't see how the operation of recovering "the missing number" could be implemented in terms of a code and its encoding/decoding algorithms. I've found this on stackoverflow: https://stackoverflow.com/a/3492967/3868157 https://stackoverflow.com/a/3492967/3868157 It describes a way to recover the missing number by constructing a Vandermonde matrix using the given numbers. This would correspond to constructing a generator matrix of a specific RS code [1]. However, after this I'm not so sure about the relation between encoding/decoding and recovering the missing number. In the end they also factor a polynomial (that could be something analogous to the error locator polynomial?). [1]: although I'm not sure if it's strictly an RS code
RHSeeger 6y ago
Something in the middle might be useful though. Discussing XOR and it's properties (the first part of the article) with the assumption the interviewee doesn't know them... and then working through what it means you can do with it (the second part) could be a useful exercise. "Given these properties, what can you do with it". To some extent, it still means the person that knows the tricks will do better.. but much less so.

whimsicalism 6y ago

> pleasant person, are a team player, whether they have leadership aspirations, and take responsibility. I know the above is a popular opinion, but I've worked as a SWE at a company A that had a "technical interview" process and Company B that didn't have a formalized one. I would much, much prefer to work at company A (pay differences aside) because of the type of person who passes these interviews. It can be quite difficult to determine someone's capability at interview-time. But company B had lots of competency "false positives" (in my view) whereas company A had very few. That's the value of a technical interview. That said, of course the XOR solution would never be the only one accepted, but it would probably get you brownie points here.

RHSeeger 6y ago
> company B had lots of competency "false positives" The thing to note is that, in exchange for this, Company A (probably) had a lot false negatives. So it comes down to whether you'd rather missing out on someone that would have been beneficial for the company (false negative) or have to deal with accidentally hiring someone that is not a good choice (false positive). The best choice to make depends a lot on the situation.

dragontamer 6y ago

> I'm not concerned If someone happens to know some esoteric trick that they could Google search (Unless of course you're applying for a position at a company that manufactures very low level devices like microcontrollers or embedded systems and questions like this are _actually relevant_). Erasure correction is a very useful trick for data-engineers. I don't think this is a microcontroller trick, as much as a data-resliliency trick. The XOR-trick is how you implement RAID5 most efficiently. A proper discussion / interview would probably describe the XOR trick, and then see if the engineer is smart enough to understand the difference between erasure and errors. -------------- With a blog post describing the XOR trick ahead of us: now I ask you (the audience): what is the difference between an erasure and an error? Why can this XOR-trick protect against an erasure, but NOT an error? And how does this relate to RAID5's known failure cases? But at that point, I'm interviewing for someone who has passed a data communications class.

abhishekjha 6y ago
I guess I will fail your interview as well.
- dragontamer 6y ago
  Lol. Well, that's why I ended with: > But at that point, I'm interviewing for someone who has passed a data communications class. This is basic data-communications stuff. But there's a reason why data-communications isn't exactly a commonly taught subject: its niche and not really generally applicable IMO. My main point is that the XOR-trick is a decent data-communications question. But I don't know how generally applicable it is to other programming fields.
shiftingleft 6y ago
I think in erasure coding you typically know the locations of the erasures: If a disk fails, you know which one failed. However, I don't see how you would know the locations in this problem? Maybe you can elaborate on how this problem relates to erasure coding?
- 6y ago

woofie11 6y ago

I think it kind of depends on the type of programmer one wants to hire. There are different roles, solving different types of problems. There are places for people with technical brilliance, there are places for people with social brilliance, with both, and with neither. That's healthy. You want a diverse economy with different types of positions for different types of folks, and vice-versa. If I ask a half-dozen questions like the xor trick, I'll have a filter for one type of technical background. Whether you know each of them is pretty random, but whether you know none of them or most of them is not.

whimsicalism 6y ago
> there are places for people with social brilliance, with both, and with neither. That's healthy There are lots of socially brilliant people out there, it's what many of us spend at least 20 years of our lives practicing. Why would being a brilliant socializer command the same salary that a brilliant engineer does?
- bonoboTP 6y ago
  Because commanding a salary and appearing valuable is itself a social skill.
- RHSeeger 6y ago
  Being able to interact well with others is part of being a valuable employee. You can be the best engineer in the company, but if nobody wants to work with you, it's going to negatively impact the value you bring to the company.
- woofie11 6y ago
  Because, as you move up the management chain, understanding how people work and how groups of people work becomes more important than technical brilliance. The job of a manager is to create a healthy working environment where people work effectively, and are well-aligned to a common goal. That's hard. You don't just practice that by living. That's made easier by having people lower down who are helping and not hurting.

vzidex 6y ago

> I'm not concerned If someone happens to know some esoteric trick that they could Google search (Unless of course you're applying for a position at a company that manufactures very low level devices like microcontrollers or embedded systems and questions like this are _actually relevant_). The "XOR trick" actually nearly sank me on an interview once, I'm assuming because the interviewer shared your opinion. One of the questions they asked me to solve was the "n - 1 numbers in a list" question the article talks about - I promptly came up with the XOR solution because I have more background in low-level work than the high-level finance role I was interviewing for. Turns out, they had never seen it before, didn't really understand how/why it worked, and they took a lot of convincing to accept it as correct. I think I only still got the job was by then proceeding to also solve the problem the "normal" way.

bonoboTP 6y ago

Maybe you feel like you are being inclusive and warmhearted for praising soft skill vs 'teh codez skillz', but please also consider that tech and programming jobs is like the last refuge for people with high technical aptitude and perhaps less social soft skills regarding the meta political and expectation games, eg people somewhere on the autism spectrum. Perhaps such interviews are overused but if the interview is purely soft, and about "sell yourself to me", you will also be biased towards some people. I mean of course it's important to be able to work together in a pleasant way, but when someone's main strengths are in the technical aspects, they may like to be able to showcase that too. And yes of course in the age of high level frameworks and glued CRUD pruducts, some programming jobs are more social than technical. But not necessarily all. And I'm seeing lots of this sentiment nowadays on social media, that all "allegedly" merit based nerdy "gatekeeping" is merely about white male privilege and hence not inclusive.

whatshisface 6y ago
Nobody complains about puzzles in tech interviews. People care about uncreative "did you read this book about interview questions" questions. If you want to test tech knowledge in tech interviews, ask a question that isn't in any book. That takes a lot more skill as an interviewer to pull off, but if you're a hiring manager, surely you can find someone on your team qualified to design a puzzle.
- bidirectional 6y ago
  Google's policy is to extensively discuss interview questions internally, and blacklist any that are leaked. They are still complained about near-constantly on any tangentially related HN thread.
  - deleted 6y ago
    [deleted]
  - bonoboTP 6y ago
    The attitude is often quite strange. Like on Twitter I saw a few days ago that many were riled up about the fact that a prof would ask how to solve Ax=b (linear algebra) for a deep learning / computer vision PhD position. People were calling this unnecessary gatekeeping... I'm like that's just a warm-up question to get comfortable... But apparently the loud online hive mind opinion is that all that should count is soft skills and that everyone is equally able. People are even calling out professors on Twitter (who then engage, for some reason) for saying they are looking for "outstanding" PhD candidates. Because this is apparently too exclusionary language, everyone is equally outstanding or something...