8 ms·

The really frustrating part is that linked lists are actually bad practices in most instances nowadays [0]. And skiplists are better than trees for many in-memo

The really frustrating part is that linked lists are actually bad practices in most instances nowadays [0]. And skiplists are better than trees for many in-memory uses [1]. Not that you would usually implement such a thing yourself anyway. So these leetcode style interviews are actively selecting for people who practice 40 year old CS solutions that don't work well on modern hardware, and selecting against folks with real-world experience. [0] https://www.youtube.com/watch?v=YQs6IC-vgmo https://www.youtube.com/watch?v=YQs6IC-vgmo [1] https://ticki.github.io/blog/skip-lists-done-right/ https://ticki.github.io/blog/skip-lists-done-right/

chrisseaton 7y ago
But a skip list is an application of linked lists. If you can implement a skip list you can implement a linked list. If you can't implement a linked list I can't see how you'd implement a skip list. > Not that you would usually implement such a thing yourself anyway. Google has data structure libraries. They write low-level code like kernels that has no library of data structures. They implement programming languages where they need to implement data structures from scratch. Lots of need to do it.
- voodootrucker 7y ago
  Each individual level of the skip list can be an array (as described in [1]), so yes, you still have a fair bit of pointer chasing, but the article goes into good detail all the tricks you can use to reduce it. I think most binary tree implementations require pointers, so they aren't amenable to this type of optimization. I haven't implemented a skip list myself, so I could be wrong here and happy to hear about why if I am. [edit to add]: I totally get why this would be applicable at Google. The part I find silly is that most companies other than the FAANGs usually just use libraries made by the FAANGs and don't have much reason to focus on this level of comp sci in their own interview processes, yet they still read articles like this and copy Google anyway.
ben509 7y ago
> The really frustrating part is that linked lists are actually bad practices in most instances nowadays "Fancy algorithms are slow when n is small, and n is usually small." -- Robert Pike Cons-based linked lists continue to be the container workhorse of MLs. In imperative languages, arrays are preferred because allocating a chunk of memory is even simpler. > So these leetcode style interviews are actively selecting for people who practice 40 year old CS solutions that don't work well on modern hardware These claims are extremely common, so I'm not being snarky here, I want to understand your reasoning. You're doing the interview, they're gathering data, then discussing it in a meeting: What do you think is being measured? Can you describe a utility function they are applying to that measurement? > Not that you would usually implement such a thing yourself anyway. But engineering isn't like shift work. The complexity of tasks you encounter are likely Pareto distributed. Thus something like 20% of the tasks you work on will justify 80% of your pay.
- voodootrucker 7y ago
  > What do you think is being measured? In a leetcode style interview? I think they are attempting to measure aptitude at solving algorithmic-style problems on a white board. I think they are indirectly measuring ability to perform under pressure, ability to vocalize while thinking, ability to function in unnatural environments, and either time since graduation from a CS major, or time spent practicing / gaming the system on leetcode (the premium feature even lets you see which questions your employer will likely ask). I think they should be measuring things like: ability to select good frameworks for a solution, ability to reason about how such frameworks are implemented at an algorithmic level, when and where to add an index or avoid a shuffle, how to debug, ability to write readable code, ability to coach more JR devs, ability to learn from more SR devs, etc. > Can you describe a utility function they are applying to that measurement? I'm not sure I can. I see this as a very multi-dimensional problem, so I think the utility of given skills would have to be considered in regards to the existing skills within the team. Honestly, I feel like "software engineer" has been split in two: R&D is done within the FAANGs (and maybe a few universities) and the results are open-sourced. Outside the FAANGs, something more like "software development" happens: FAANG libraries are glued together. _Very_ occasionally, you get a smaller company that has a legitimate business reason to write their own library or database or whatever, and an engineer is lucky enough to convince them of that. I'm also not trying to be snarky - I've been stuck on the latter side for most of my career, because I prefer to work in smaller companies, and as such have not had as much opportunity to practice "interesting code" as I would have liked. Perhaps this is due to my market (Denver), but I've also worked with companies in the bay, and I've seen a tremendous amount of over-engineering when off the shelf parts would have worked. So I'm legitimately curious: 1. Am I interpreting your questions correctly in that you think the ds & algo whiteboard interview selects well for desired attributes? 2. Do you solve those kinds of problems on a day to day basis? 3. If so, do you work at a FAANG? I don't mean to pry, so feel free to disregard any of those questions if your are uncomfortable answering them on a public forum, or message me privately. Thanks!
Analemma_ 7y ago
For whatever it's worth, I interviewed at both Google and Amazon recently and got no linked list questions at either: trees and graphs appear to be what's "in" right now, as far as whiteboarding algo questions. Obviously there are still concerns about using whiteboarding data structure problems to assess candidates, but the issue of using practically-dead data structures has at least been acknowledged.

chrisseaton 7y ago

But a skip list is an application of linked lists. If you can implement a skip list you can implement a linked list. If you can't implement a linked list I can't see how you'd implement a skip list. > Not that you would usually implement such a thing yourself anyway. Google has data structure libraries. They write low-level code like kernels that has no library of data structures. They implement programming languages where they need to implement data structures from scratch. Lots of need to do it.

voodootrucker 7y ago
Each individual level of the skip list can be an array (as described in [1]), so yes, you still have a fair bit of pointer chasing, but the article goes into good detail all the tricks you can use to reduce it. I think most binary tree implementations require pointers, so they aren't amenable to this type of optimization. I haven't implemented a skip list myself, so I could be wrong here and happy to hear about why if I am. [edit to add]: I totally get why this would be applicable at Google. The part I find silly is that most companies other than the FAANGs usually just use libraries made by the FAANGs and don't have much reason to focus on this level of comp sci in their own interview processes, yet they still read articles like this and copy Google anyway.

ben509 7y ago

> The really frustrating part is that linked lists are actually bad practices in most instances nowadays "Fancy algorithms are slow when n is small, and n is usually small." -- Robert Pike Cons-based linked lists continue to be the container workhorse of MLs. In imperative languages, arrays are preferred because allocating a chunk of memory is even simpler. > So these leetcode style interviews are actively selecting for people who practice 40 year old CS solutions that don't work well on modern hardware These claims are extremely common, so I'm not being snarky here, I want to understand your reasoning. You're doing the interview, they're gathering data, then discussing it in a meeting: What do you think is being measured? Can you describe a utility function they are applying to that measurement? > Not that you would usually implement such a thing yourself anyway. But engineering isn't like shift work. The complexity of tasks you encounter are likely Pareto distributed. Thus something like 20% of the tasks you work on will justify 80% of your pay.

voodootrucker 7y ago
> What do you think is being measured? In a leetcode style interview? I think they are attempting to measure aptitude at solving algorithmic-style problems on a white board. I think they are indirectly measuring ability to perform under pressure, ability to vocalize while thinking, ability to function in unnatural environments, and either time since graduation from a CS major, or time spent practicing / gaming the system on leetcode (the premium feature even lets you see which questions your employer will likely ask). I think they should be measuring things like: ability to select good frameworks for a solution, ability to reason about how such frameworks are implemented at an algorithmic level, when and where to add an index or avoid a shuffle, how to debug, ability to write readable code, ability to coach more JR devs, ability to learn from more SR devs, etc. > Can you describe a utility function they are applying to that measurement? I'm not sure I can. I see this as a very multi-dimensional problem, so I think the utility of given skills would have to be considered in regards to the existing skills within the team. Honestly, I feel like "software engineer" has been split in two: R&D is done within the FAANGs (and maybe a few universities) and the results are open-sourced. Outside the FAANGs, something more like "software development" happens: FAANG libraries are glued together. _Very_ occasionally, you get a smaller company that has a legitimate business reason to write their own library or database or whatever, and an engineer is lucky enough to convince them of that. I'm also not trying to be snarky - I've been stuck on the latter side for most of my career, because I prefer to work in smaller companies, and as such have not had as much opportunity to practice "interesting code" as I would have liked. Perhaps this is due to my market (Denver), but I've also worked with companies in the bay, and I've seen a tremendous amount of over-engineering when off the shelf parts would have worked. So I'm legitimately curious: 1. Am I interpreting your questions correctly in that you think the ds & algo whiteboard interview selects well for desired attributes? 2. Do you solve those kinds of problems on a day to day basis? 3. If so, do you work at a FAANG? I don't mean to pry, so feel free to disregard any of those questions if your are uncomfortable answering them on a public forum, or message me privately. Thanks!

Analemma_ 7y ago

For whatever it's worth, I interviewed at both Google and Amazon recently and got no linked list questions at either: trees and graphs appear to be what's "in" right now, as far as whiteboarding algo questions. Obviously there are still concerns about using whiteboarding data structure problems to assess candidates, but the issue of using practically-dead data structures has at least been acknowledged.