Algorithms and Data Structures Explained and Implemented in JavaScript
github.com
github.com
The implementation choices leave some things to be desired. The Queue and Stack implementations are Linked Lists instead of array backed, the hash table is closed instead of (the only barely more complicated) open Robin hood hash table scheme, the union-find/disjoint-set implementation doesn't have path compression or rank unions.
Overall very good, but it could be Great (tm) with just a little bit of work.
Am I wrong? I thought array-based queues resulted in O(n) queue/dequeue. Now for stacks, which are last-in first-out, it makes sense to use an array.
Not necessarily. A circular buffer[1] can be used as a queue with O(1) queue/dequeue. C++ implementations (gcc?), IIRC, uses an interesting array-of-arrays approach; it also has O(1) queue/dequeue. I'm not sure why the array-of-arrays approach is better than a circular buffer, though.
Array based designs can result is less allocations, and maybe less overhead. For example, if you have a circular buffer with space for 16 items, it only needs to allocate space if you need more room, whereas a linked list queue would allocate for each and every item placed into it. Linked lists also require space for the pointer to the next link, for each link in the list. (And, if you keep them, back pointers, though these aren't necessary for just a queue.) Arrays might have some unused slack space, however.
On the other hand, an array of arrays (no recursion) doesn’t change the big-O complexity cost, just the constant multiplier. That should definitely improve performance of the uncommon operation (the copy), but hypothetically might slow down the actual queuing operations (and drastically reduce throughout)
But maybe you meant the array of arrays to be recursive? That seems like it would alter the big-O (from n+m to log(n)+m). But typically m>>n, so the net result is the same.
The array vs. linked list thing is sort of just knowledge you pick up, I suppose? Linked lists have their place, just fairly rarely. For a more in depth listing of the pros and cons, https://stackoverflow.com/questions/393556/when-to-use-a-lin... is a good discussion. I consider use cases for linked lists to be rather niche (if someone comes in and mentions the kernel - that is niche). a & b are both basically on embedded systems (real time or low memory), c is rare outside of, well, queues and stacks, which are better in arrays anyway, and d is reasonable but with a bad example (a heap-based priority queue is better - and your heap should be array backed). They're flexible and easy but rarely the best solution.
The union-find thing should be fairly standard. I mean, the optimizations are on the wiki page for union find. Pretty sure Sedgewick and online course cover those optimizations too. Adding those optimizations is equivalent from transforming a naive binary search tree into AVL or a Red-Black tree, which is a pretty huge improvement.
The hashtable stuff I learned mostly from lurking here on HN. ;)
I always found it misleading for example, to use an existing language implementation of a particular data structure (in this case a JS array) to represent a queue, and then simply provide methods that mock enqueue / dequeue but don't provide the same performance guarantees. All you're doing is mimicking the queue API but actually performing O(N) shift/unshift, which defeats the point of even having the data structure.
Not saying you can't do it properly with an Array, but I can't count the number of times I've seen not only blogs, but published educational materials advocate for using an existing Array-like structure as a starting point for a queue, and totally ignore the fact that that structure was not designed to remove from the front.
Just my personal opinion, but I think a linked list more clearly illustrates how to properly implement stacks/queues in a higher level language since you're forced to handle the pointers (nodes) yourself.
Having said all that: The algorithms I've had to tackle at work tend to be fairly trivial or total one-offs involving scheduling events in human time.
How much algorithmic work do you other JS folks end up doing?
I recently built a questionnaire/form editor/builder which relies heavily on tree structures. I ended up writing a lot of tree walking code. It was the first time I've ever needed to implement interview-like questions in an actual project.
I make heavy use of functional programming in Javascript, which lends itself to really clean implementations of algorithms like tree walking, e.g.: https://hastebin.com/qapawepavi.js
> How much algorithmic work do you other JS folks end up doing?
I find JS to be the ideal language to implement an algorithm, despite its quirks. Why?
1. Because JS has syntax similar to most other class based languages, or can be used in ways that match functional languages, even if the syntax is different.
2. It is the lingua-franca of the web, so it is easy for others to also understand, use as a reference implementation (into other languages), or literally visualize it in the browser.
3. Along the lines of visualization, browser's have some of the best and state-of-the-art live debugging tools. So often it is easier to implement and test in JS (despite lack of types) than other languages.
4. For better or for worse, a pure JS implementation (no NPM or other packages) has very little standard library tooling, so you are forced to write some pretty low level logic that you might not otherwise write in real low level languages simply because they have good built-in standard libraries.
We also took the time to write some algorithm and explainer articles, but they are largely focused at the high-level conceptual layer, and explaining for kids:
- GIT explained for kids http://gun.js.org/explainers/school/class.html
- Stream sorting interactive explainer http://gun.js.org/explainers/basketball/basketball.html
- Cartoon cryptography http://gun.js.org/explainers/data/security.html
Most all the work we do is algorithmic, not app focused. But that is unusual for JS devs.
https://www.cs.usfca.edu/~galles/visualization/Algorithms.ht...
And I'm a good bit into the javascript client which even uses proxies :) https://github.com/westoncb/JS-Watcher
(Mostly I've been using a Java client which is much more advanced, but I had an idea to do a visualized sandbox for a 'code tutor' kind of app in javascript/Electron, so I started the js client.)
Edit: I should also point out that it's meant to easily hook up to any algorithm you write, so it's as much for debugging as instructional algorithm visualization.
[1] https://www.packtpub.com/web-development/learning-javascript...
Every library I looked at had implementations revolving around nodes that stored chars (you know, for auto-complete scenarios) but nowhere in the definition of a Trie is it bound to such an implementation (so I thought).
It shouldn’t be too hard to roll your own here, it’s just a set of tree traversal functions.
I've implemented at least 5 different generic Tries since this one. The idea is almost always the same, but different tradeoffs can require different implementations. While I don't recommend that you use this version, the contents of [1] should give you all the inspiration you need to roll your own.
[1] https://github.com/superlopuh/SuperTrie/blob/master/SuperTri...
https://gist.github.com/robertfairley/11ba23640578650671dbde...
There's a python library called networkx, but it is so heavily object-oriented (multi-inheritance) as to make it impossible to get any benefit from reading the code.
Nicely done
There are people posting verbatim interview questions, which is a breach of interview NDA.