Ask HN: Have you ever had to write a data structure from scratch on your job?

https://news.ycombinator.com/item?id=12937010

by rochak • 10 years ago

5 4 10 years ago

news.ycombinator.com

I have been doing competitive coding from quite a while but failed to make use of it in my job. Most of the times, there is already a library built to perform the task required quite efficiently. Have you ever had to code a specific data structure and along with it a suitable algorithm to fulfill your purpose or do you too make use of such libraries?

nostrademons• 10 years ago

Yes, but it's pretty rare (I assume by data structure you mean like something out of an algorithms textbook, not the structs & classes that most programmers use all the time). I did a string trie for an autocompletion system once (and then found that binary search over a sorted array was faster, go figure), and a binary space partitioning tree for a game creation engine. Also stacks, queues, state machines, and augmented trees come up all the time, but they're not particularly difficult to implement.

I think that one very underrated skillset is the ability to implement a data structure or algorithm on top of an existing platform. For example, can you implement reservoir sampling and a state machine on top of SQL? If you can, there's a good chance your Hadoop analytics cluster can be replaced with a single DB instance and a work-queue system. Can you implement a graph algorithm on top of MapReduce? That's how Google's Pregel system got started. Can you implement a diff algorithm on top of the DOM? React. Three-way merge on S3? DropBox. Binpacking over Linux containers? Borg/Omega/Kubernetes.

uniclaude2• 10 years ago

I think that one very underrated skillset is the ability to implement a data structure or algorithm on top of an existing platform.

Spot on. This sort of out-of-the-box thinking is definitely one of the most important things in the career of an engineer.

uniclaude2• 10 years ago

Yes, sometimes the data structure you need is either:

- unavailable (in a permissive license in) the platform you're currently using.

- available with an unsatisfying implementation.

If you're lucky, your employer will allow you to contribute to open source during your working hours so other developers won't need to re-implement it.

Now, if the question is about whether I needed to come up with a totally novel data structure at the office, the answer is no in my case.

kafkaesq• 10 years ago

Not every day but often enough, for sure. Usually it's really nothing special, just a simple abstraction that helps prevent boilerplate accumulation and possible error sources throughout the rest of the codebase (or head off external dependencies).

For example, rather than import some all-things-to-all-people, infinitely scalable graph theory package, sometimes it's better to just spend 45 minutes writing a simple vertex-to-vertex map (to provide a piece of functionality that you know won't change).

Heck, sometimes it's even substantially quicker to roll your own data structure than go searching for a mature library that claims to provide it (and evaluate whether it's really properly maintained or won't otherwise impose technical debt on your project). What's key is knowing when to make that judgement call, of course.

Ask HN: Have you ever had to write a data structure from scratch on your job?

Related Stories