4 ms·

As an engineer who works on security software, here's what I've empirically used on the job: 1. Tree/graph traversal (certificate validation and a couple other

As an engineer who works on security software, here's what I've empirically used on the job: 1. Tree/graph traversal (certificate validation and a couple other random places) 2. Using, not implementing, hash tables 3. Generators/iterators/streams: minimizing the number of unnecessary list traversals or allocations made when you have to shovel data around 4. Circular buffers: specifically in low latency, high throughput applications 5. Some exotic string search algorithms in a very specific, highly performance sensitive inner loop 6. Database query performance tuning 7. Every now and then something vaguely reminiscent of dynamic programming comes up, but it's never an actual dynamic programming problem, it's just a "cache results of expensive operations" problem. For my job you need something exotic once in a blue moon, and when that happens you Google for someone else's research. You're not making up algorithms on your own. If you want to test that someone can handle algorithm-heavy situations like case #5, you should be testing their paper reading and ability to implement that paper, not their ability to solve an algorithms puzzle. Also relevant to my job: if you find yourself implementing cryptographic algorithms, you're almost certainly doing it wrong. You shouldn't be implementing cryptographic algorithms. When I need them, my job is to vet and correctly use an expert implementation.

harha 6y ago
This absolutely! The interview process is totally broken, as it tests mainly how much someone is willing to prepare for the interview, which might actually show more how little they focus on doing more productive things in their current job, at university or by starting interesting projects. It also scares away people who might actually be better at the job but not as good or interested in interviews - at least this was my experience at Google compared to the usually more interesting people I worked with at university. It’s just more difficult to test beforehand how someone might actually solve a problem in a good way as you describe. If applicable it’s possible to look at prior work, if you have any other good ways I’d be very interested. Edit: this is actually a good thread to get some ideas on improving interviews.
- munchbunny 6y ago
  I still do algorithms interviews, sort of. The one-hour interview format is an external constraint, so within that constraint I will do ~40 minutes of coding and ~15 minutes of discussing past projects. I ask a question where the algorithm itself is at most some list iterations or tree traversals, but the real difficulty is thinking through the data and figuring out the right generalizations and transformations to apply. It seems to control decently well for people who have practiced for interviews, because they do the usual dance of asking some clarification questions, mocking the functions, and narrating their code, but many of them hit a wall five minutes in. It's not because their algorithm doesn't work. They're using the right algorithm. The problem is that they haven't thought through "ok what do you do with the data now that you've traversed the tree?" In my experience, for my job, that's usually the actual hard question. For example, if you're checking a JWT, are you validating it in a way that is hard to subvert? Are you taking any time to think about pathological data inputs? The counterpoint would be "what about a candidate who has solid coding skills but stumbles on the problem space because they're unfamiliar with it?" In my sample size of approximately n=10 since I started interviewing candidates this way (admittedly a small sample, but it's the sample I have), I have yet to see someone who writes code well who neglects thinking through the characteristics of the data up front. That said, it's a real issue. Data is usually contextual, so you're at an advantage if you have experience in the corresponding problem domain, which is not something I'm measuring for in the coding exercise. While I try to pick topics that should be universal, I inevitably get surprised, so I offer three different topics based on the candidate's resume, and I give the candidate a choice. The biggest weakness I've seen in my interview process (within the scope of what you can do with only one hour) is that it doesn't control for nervousness or people who just don't operate well under time pressure. Unfortunately that's an unavoidable consequence of the mandated form factor, so I have to try my best to help relax the candidate and then rely on my gut for how much nervousness or pressure affected the interviewee.
  - harha 6y ago
    This all makes sense, thanks for the details. I think the key element is how you calibrate towards the candidate, bringing common sense into the process. This is something Google tried to cancel out to increase fairness, which failed in my experience. Maybe another issue is setting the bar too high during the interview to improve the metric on retention, sometimes it might just not be the match that the interview appeared to have. I usually try to work with people on something small to get a feeling for how well we work together before committing to larger projects, but at some point I’ll need to start hiring, so I’m very interested in this topic.
jiggawatts 6y ago
I'm a very "generic" programmer that dabbles in an incredible variety of problems, from Windows GUIs to health monitor probes running on a BSD network appliance. You just summed up pretty much everything I've ever needed to know as well. IMHO the #1 thing that most developers are missing is database query writing skills. There is a shocking amount of terribly inefficient SQL out there that is wasting everyone's time and money.
proverbialbunny 6y ago
Thumbs up on circular buffers. Those are totally underrated.
michaelg7x 6y ago
We often see the "don't roll your own crypto", and of course, in a production setting that's obligatory advice. I think that it's a valuable exercise for anyone to implement some of the algorithms and protocols, just to understand the complexity within. I did that for a minimal TLS1.2 implementation, just because, and it was a valuable exercise. Do you see any value in changing the slant you put on "don't try this at home"?
- munchbunny 6y ago
  I think there has always been an implied exception for doing things for their pedagogical value. In the case of my previous comment, I think it’s pretty clear that I’m talking about production code. As far as rolling your own crypto goes, I think the advice should be “only try it at home and don’t ever use it in production even for yourself”.

harha 6y ago

This absolutely! The interview process is totally broken, as it tests mainly how much someone is willing to prepare for the interview, which might actually show more how little they focus on doing more productive things in their current job, at university or by starting interesting projects. It also scares away people who might actually be better at the job but not as good or interested in interviews - at least this was my experience at Google compared to the usually more interesting people I worked with at university. It’s just more difficult to test beforehand how someone might actually solve a problem in a good way as you describe. If applicable it’s possible to look at prior work, if you have any other good ways I’d be very interested. Edit: this is actually a good thread to get some ideas on improving interviews.

munchbunny 6y ago
I still do algorithms interviews, sort of. The one-hour interview format is an external constraint, so within that constraint I will do ~40 minutes of coding and ~15 minutes of discussing past projects. I ask a question where the algorithm itself is at most some list iterations or tree traversals, but the real difficulty is thinking through the data and figuring out the right generalizations and transformations to apply. It seems to control decently well for people who have practiced for interviews, because they do the usual dance of asking some clarification questions, mocking the functions, and narrating their code, but many of them hit a wall five minutes in. It's not because their algorithm doesn't work. They're using the right algorithm. The problem is that they haven't thought through "ok what do you do with the data now that you've traversed the tree?" In my experience, for my job, that's usually the actual hard question. For example, if you're checking a JWT, are you validating it in a way that is hard to subvert? Are you taking any time to think about pathological data inputs? The counterpoint would be "what about a candidate who has solid coding skills but stumbles on the problem space because they're unfamiliar with it?" In my sample size of approximately n=10 since I started interviewing candidates this way (admittedly a small sample, but it's the sample I have), I have yet to see someone who writes code well who neglects thinking through the characteristics of the data up front. That said, it's a real issue. Data is usually contextual, so you're at an advantage if you have experience in the corresponding problem domain, which is not something I'm measuring for in the coding exercise. While I try to pick topics that should be universal, I inevitably get surprised, so I offer three different topics based on the candidate's resume, and I give the candidate a choice. The biggest weakness I've seen in my interview process (within the scope of what you can do with only one hour) is that it doesn't control for nervousness or people who just don't operate well under time pressure. Unfortunately that's an unavoidable consequence of the mandated form factor, so I have to try my best to help relax the candidate and then rely on my gut for how much nervousness or pressure affected the interviewee.
- harha 6y ago
  This all makes sense, thanks for the details. I think the key element is how you calibrate towards the candidate, bringing common sense into the process. This is something Google tried to cancel out to increase fairness, which failed in my experience. Maybe another issue is setting the bar too high during the interview to improve the metric on retention, sometimes it might just not be the match that the interview appeared to have. I usually try to work with people on something small to get a feeling for how well we work together before committing to larger projects, but at some point I’ll need to start hiring, so I’m very interested in this topic.

jiggawatts 6y ago

I'm a very "generic" programmer that dabbles in an incredible variety of problems, from Windows GUIs to health monitor probes running on a BSD network appliance. You just summed up pretty much everything I've ever needed to know as well. IMHO the #1 thing that most developers are missing is database query writing skills. There is a shocking amount of terribly inefficient SQL out there that is wasting everyone's time and money.

proverbialbunny 6y ago

Thumbs up on circular buffers. Those are totally underrated.

michaelg7x 6y ago

We often see the "don't roll your own crypto", and of course, in a production setting that's obligatory advice. I think that it's a valuable exercise for anyone to implement some of the algorithms and protocols, just to understand the complexity within. I did that for a minimal TLS1.2 implementation, just because, and it was a valuable exercise. Do you see any value in changing the slant you put on "don't try this at home"?

munchbunny 6y ago
I think there has always been an implied exception for doing things for their pedagogical value. In the case of my previous comment, I think it’s pretty clear that I’m talking about production code. As far as rolling your own crypto goes, I think the advice should be “only try it at home and don’t ever use it in production even for yourself”.