Recently I tried to use JavaScript to solved some algorithm challenges in LeetCode. And I solved pretty much all the challenges in LeetCode that marked as “Hard”. You can checkout my code in this Github repo.. And in my experience, my submissions are usually faster than submissions with Ruby and lots of Python submissions. Considering that my first goal is to express the algorithm nicely, and I am avoiding to do tricky performance tuning, I feel this is a quiet acceptable result.
This blog is going to share some features in JavaScript that I found handy and useful when solving these challenges, and the parts that bother me. But before that, I think I should explain a little bit about why I want to do this. Even it is used widely in back-end nowadays, few people may use JavaScript to implement complex algorithms in production.
The major reason of implementing algorithms in JavaScript is that implementing an algorithm elegantly and clearly requires you to be familiar with features and concepts of the language you are using. And during this process, I actually feel more confident and delightful writing algorithms with JavaScript. I did found some good features that make my life easier! Sadly I don’t utilize them at the very beginning. Those code makes me feel awful now >_<.
And the other reason is that information could be gathered during execution of algorithms. WIth these information, the process of algorithms could be later visualize in web page. With some good presentation, the visualization can be super helpful and fun to watch. Actually, there are a few projects going through this road map.
Now let’s start to talk about the handy tricks and things that bother me.
Array
The first credit I want to give it to Array. Array is very useful in many ways. If you want a stack, you can do it with Array.prototype.pop(), Array.prototype.push() and Array.length. Want a queue? Array.prototype.push() and Araay.prototype.shift() can handle this.
And the fact that Array is actually associated map rather than an actual consecutive buffer sometime helps. You don’t bother to check if the index is out of range before accessing. Array just silently returns undefined. But you also need to be very concise about this otherwise it will be a bug that drags you all the way to very late night debugging.
Plain Object
JavaScript’s plain object has many limitation comparing to Python’s Dict or C++’s map. Its key can only be string. So when you write object[233] = 1 what actually happened is object["233"] = 1. Despite of that, in lots of situation plain object is just what you want. If you want a hash table, plain object could be it in most situation.
When you are doing dynamic programming with memoizating (which is my favorite way to implement a dynamic programming solutions when the memory footprint is not a problem, since it makes the solution looks nice and clean), plain object could be the memo since JavaScript does not have a direct way to allocate a given size tabular memory. It is like,
1 2 3 4 5 6 | var f = {}; function fib(n) { if (n < 2) return n; if (f[n] !== undefined) return f[n]; return f[n] = f(n - 1) + f(n - 2); } |
The default value of missing key in plain object is undefined, which tells us the result of the current argument n has not been memoizated.
Plain object can memoizate more complicate functions. For example, if the memoizating function has two parameters, plain object could store them like
1 2 3 4 5 6 | var memo = {}; function f(i, j) { if (memo[[i, j]] !== undefined) return memo[[i,j]]; // ..... // ..... } |
Note that it should be memo[[i, j]] instead of memo[i, j]. memo[i, j] is a valid express but what it means is memo[j] since the evaluation of i, j is just j according the comma operation. And [i,j] could be convert into a string like "[22,33]" which is an one-to-one map of arguments.
Or it could be like,
1 2 3 4 5 6 7 8 | var memo = {}; for all potential i do memo[i] = {}; function f(i, j) { if (m[i][j] !== undefined) return m[i][j]; // ..... // ..... } |
memo[i][j] approach has better performance in my experience. But I don’t know the implementation details of V8, so this may not be very accurate. Actually, I can not find any very definite documents about how Array or plain object, so this is all of guessing. Maybe I should dig into this topic more deeply in the future.
And ES6’s Map can use any type of value (objects or primitive values) as key. So it also could be a good choice for memoizating. I don/t use it in my solution so far, since I am kind of afraid it is implemented as a BST rather than a hash table. Anyway, I will investigate it and do some updates.
Closure
Another nice thing that JavaScript has is its closure. Closure is very useful when you want to implement your solution without populating any scope outside the function you are implementing. Take Edit Distance as an example. You are implementing minDistance. With closure, you can define another function f inside of minDistance, access and modify variables that is available in minDistance. This is not just about keeping the global namespace clean. It also makes it very easy to ensure minDistance does not have any side-effect since now it will not modify and access any variable outside its scope.
var minDistance = function(word1, word2) {
var n = word1.length; var m = word2.length;
var t = {};
function f(i, j) {
// you can access t, n, m, word1 and word2 here.
}
return f(0, 0);
};
Functional Programming and Arrow Function
Modern JavaScript supports many concepts in functional programming. There are Array.prototype.forEach(), Array.prototype.reduce() and so on. And the introducing of arrow function in ES6 makes them more handy and usable. If I want to iterate an array in order, forEach is always my first choice, since it saves me the time of typing assignments like var element = elements[i] and also keeps the scope clean.
var and let
The problem that bothers me the most is JavaScript’s var, which declares variables in the function scope. I am very uncomfortable with it and keeping writing codes like
for (var i = 0; i < n; i++) {
// ....
}
for (var i = n; i >= 1; i--) {
// ....
}
This is awful! I keep doing these only because I am not super sure if all the loops are needed when I wrote them. And I don’t like the feel that I need to modify the code in two places when I am applying one idea simply because they have variable with same name, even though these variables actually do not have to be same. So I keep using var everywhere to avoid this. Shame on me!
Luckily, ES6 introduced let as a way to declare variale in block-level scope. And it also works well with for statement. Sadly I know this too late and don’t use any let in my code. Shame on me! In fact, since all most all the var in my code are actually means let, I think I could write a simple tool to help me to update my code with let.
The Silent NaN
And one thing that may drive you into late late night debugging is the Silent NaN. In JavaScript, when you do undefined + 1, there will be no error raised and JavaScript just silently return a NaN. And you can operate with this NaN long enough. You can store it into a Array or object, or doing number operations with in. Until something serious bad happened, everything just silently runs. And when the error raises to you, it is usually to late to give you direct clue of where the problem is.
I know it is because of JavaScript’s highly dynamic design. But something I also want some guards to ensure I don’t do stupid things. I feel TypeScript and flow may be helpful. I will give them a shot in the following challenge implementation.
Implementation of Data Struct
The other thing that bothers me is that I can not found I definite document of how data structs in JavaScript are implemented in V8. There is detailed documents of semantic of these data structs like MDN. And this is important when you are implementing algorithms since how the data structs in JavaScript are implemented will affect your run-time complexity analysis. I do hope there is a document like this, so that I can refer to. But if it is not, I will look into V8’s code to figure it out in the future.
Conclusion
After finishing 30+ challenges in JavaScript, I feel it is actually quite delightful to solve algorithm challenges with JavaScript. Due to its highly-dynamic nature, it is easier to find a way to express my idea elegantly. In the meanwhile, thanks to the JS community, the performance is still acceptable.