4 ms·

> Good for obscure leetcode problems (...) God, I hate how pointless leetcode has become, and how it's used in interviews. Smug assholes using obscure data str

> Good for obscure leetcode problems (...) God, I hate how pointless leetcode has become, and how it's used in interviews. Smug assholes using obscure data structures and algorithms trivia that no one ever used at all in any professional setting, and which the interviewer only learned about because he spent a week searching for a coding problem, to decide whether you are competent at putting a button on a window.

josephg 2y ago
> that no one ever used at all in any professional setting, (…), to decide whether you are competent at putting a button on a window. Some software jobs involve more than putting a button on a window.
- crest 2y ago
  Maybe they should keep interviewing for jobs that require nothing more complex, important, or dangerous than that.
kccqzy 2y ago
It's also about your communication skills and ability to use existing knowledge even when it isn't the most suitable. A while ago in an interview I was asked a problem for which the correct solution is in fact an order statistic tree, but not knowing that, I solved the problem using more standard data structures with worse complexity, and pointed out their limitation. I still passed that interview.
deciplex 2y ago
I mean, fwiw sometimes "obscure data structures" really do cleanly, efficiently, and performatively solve a problem that would have been a nightmare to address with simpler, more well known structures. That said, for most of us, it's rare enough to be memorable - but it does happen. I think you're right that requiring such knowledge off the top of one's head and in the context of a one-hour interview is almost always unreasonable, though. What I'd really want to know is how well a person can do the research to arrive at performant solutions involving, as you say, obscure data structures. In an interview context though, I think you basically just have to ask them - would be nice if you could get a sense of it through doing, though.
zug_zug 2y ago
I mean tbh, a list structure with logN indexed access, insert, and removal seems like a really useful structure. I just wish it was built into languages as one implementation of the list type
- usrusr 2y ago
  And with predictably good cache locality on iteration. Given the ever increasing gap between the fast and the slow end off our volatile memory hierarchies, I'm surprised that we don't see more of an identifiable trend of using algorithms/structures traditionally associated with spinning disks in nonpersistent memory.
  - humzashahid98 2y ago
    B+ Trees (which store data at leaves) rather than B-Trees are what you want for good iteration performance usually. An ordered B-Tree iteration would jump between different arrays in the tree often, but a B+ Tree would only have you jump to another array once you’re done iterating over all the elements in the current array. The following article says the same. https://www.scylladb.com/2021/11/23/the-taming-of-the-b-trees/#:~:text=There%20are%20two%20different%20ways,keys%20from%20its%20left%20subtree https://www.scylladb.com/2021/11/23/the-taming-of-the-b-tree....
- SkiFire13 2y ago
  FYI this is not that uncommon in functional languages and persistent data structure libraries.
- cb321 2y ago
  A lot of PLangs have this outside their stdlibs. For example, in Python: https://pypi.org/project/blist/ https://pypi.org/project/blist/ Some C & Nim variants are elsethread (https://news.ycombinator.com/item?id=40441832 https://news.ycombinator.com/item?id=40441832 & https://news.ycombinator.com/user?id=cb321 https://news.ycombinator.com/user?id=cb321 , respectively). -- There seems to be a lot of disagreement about how big stdlibs should be. Personally, I think a large Python one was a selling point (batteries included) as well as the way C++ STL and similar Java ones won over many back in the 1990s. However, in today's modern networked-by-assumption world, stdlib maintainers seem to feel overwhelmed pretty easily and eager to "slough off" as much as they can to the ecosystem. It's likely a sub-discussion of an even more broadly contentious "how narrow/wide should dependency trees" be. What seems to be missing, IMO, are agreed upon "metrics" beyond "saleability of the PL/ecosystem". As guidance for granularity metric relevance, it should be observed that most PL's have some kind of module/separate compilation units. A good answer would be able to work at (and across) many & various levels of the containment hierarchy - at least 3..4 of (procedure, type|module, package, developer, organization). Maybe someone has a set of such metrics in their back pocket, but if so they don't get a lot of exposure in PL chit-chat circles like this one. My guess would be there just isn't enough agreement, but it's probably been fodder for like 100s of software engineering PhD theses. Lol. ( As well as even broader human organization discussions like https://en.wikipedia.org/wiki/Conway's_law https://en.wikipedia.org/wiki/Conway's_law )

josephg 2y ago

> that no one ever used at all in any professional setting, (…), to decide whether you are competent at putting a button on a window. Some software jobs involve more than putting a button on a window.

crest 2y ago
Maybe they should keep interviewing for jobs that require nothing more complex, important, or dangerous than that.

kccqzy 2y ago

It's also about your communication skills and ability to use existing knowledge even when it isn't the most suitable. A while ago in an interview I was asked a problem for which the correct solution is in fact an order statistic tree, but not knowing that, I solved the problem using more standard data structures with worse complexity, and pointed out their limitation. I still passed that interview.

deciplex 2y ago

I mean, fwiw sometimes "obscure data structures" really do cleanly, efficiently, and performatively solve a problem that would have been a nightmare to address with simpler, more well known structures. That said, for most of us, it's rare enough to be memorable - but it does happen. I think you're right that requiring such knowledge off the top of one's head and in the context of a one-hour interview is almost always unreasonable, though. What I'd really want to know is how well a person can do the research to arrive at performant solutions involving, as you say, obscure data structures. In an interview context though, I think you basically just have to ask them - would be nice if you could get a sense of it through doing, though.

zug_zug 2y ago

I mean tbh, a list structure with logN indexed access, insert, and removal seems like a really useful structure. I just wish it was built into languages as one implementation of the list type

usrusr 2y ago
And with predictably good cache locality on iteration. Given the ever increasing gap between the fast and the slow end off our volatile memory hierarchies, I'm surprised that we don't see more of an identifiable trend of using algorithms/structures traditionally associated with spinning disks in nonpersistent memory.
- humzashahid98 2y ago
  B+ Trees (which store data at leaves) rather than B-Trees are what you want for good iteration performance usually. An ordered B-Tree iteration would jump between different arrays in the tree often, but a B+ Tree would only have you jump to another array once you’re done iterating over all the elements in the current array. The following article says the same. https://www.scylladb.com/2021/11/23/the-taming-of-the-b-trees/#:~:text=There%20are%20two%20different%20ways,keys%20from%20its%20left%20subtree https://www.scylladb.com/2021/11/23/the-taming-of-the-b-tree....
SkiFire13 2y ago
FYI this is not that uncommon in functional languages and persistent data structure libraries.
cb321 2y ago
A lot of PLangs have this outside their stdlibs. For example, in Python: https://pypi.org/project/blist/ https://pypi.org/project/blist/ Some C & Nim variants are elsethread (https://news.ycombinator.com/item?id=40441832 https://news.ycombinator.com/item?id=40441832 & https://news.ycombinator.com/user?id=cb321 https://news.ycombinator.com/user?id=cb321 , respectively). -- There seems to be a lot of disagreement about how big stdlibs should be. Personally, I think a large Python one was a selling point (batteries included) as well as the way C++ STL and similar Java ones won over many back in the 1990s. However, in today's modern networked-by-assumption world, stdlib maintainers seem to feel overwhelmed pretty easily and eager to "slough off" as much as they can to the ecosystem. It's likely a sub-discussion of an even more broadly contentious "how narrow/wide should dependency trees" be. What seems to be missing, IMO, are agreed upon "metrics" beyond "saleability of the PL/ecosystem". As guidance for granularity metric relevance, it should be observed that most PL's have some kind of module/separate compilation units. A good answer would be able to work at (and across) many & various levels of the containment hierarchy - at least 3..4 of (procedure, type|module, package, developer, organization). Maybe someone has a set of such metrics in their back pocket, but if so they don't get a lot of exposure in PL chit-chat circles like this one. My guess would be there just isn't enough agreement, but it's probably been fodder for like 100s of software engineering PhD theses. Lol. ( As well as even broader human organization discussions like https://en.wikipedia.org/wiki/Conway's_law https://en.wikipedia.org/wiki/Conway's_law )