Rosuav

//The share price for a company over a week's trading is as follows:
//[128, 97, 121, 123, 98, 97, 105]. If you had to buy shares in the company
//on one day, and sell the shares on one of the following days, write an
//algorithm to work out what the maximum profit you could make would be.
function best_profit(prices) {
	if (!prices.length) return 0;
	//Algorithm: Step through potential selling days. If the price
	//is lower than our current buying day, switch to a new buying
	//day. If the price diff between buying and selling days is
	//greater than our current best, it's our new best.

Rosuav

//Utility function to display a binary tree to the console
//More helpful than console.log(tree) due to circular parent refs
//Usage: print_tree(some_tree)
function print_tree(tree, depth) {
	if (!depth) {
		console.log("" + tree.key);
		depth = 0;
	}
	depth += 1;
	if (tree.left) {

Rosuav

var HashMap = function() {
    this.length = 0;
    this._slots = [];
    this._capacity = 8;
    this._secret = (Math.random() * 65536) | 0;
};
HashMap.MAX_LOAD_RATIO = 0.9;
HashMap.SIZE_RATIO = 3;

HashMap._hashString = function(string) {

Rosuav

# Python implementations of the same functionality as in
# https://gist.github.com/Rosuav/9c43bd978e2a794470436e9c3e3769c4
# Note that these functions can be used with strings containing any
# Unicode characters, and will be reliable. (Assumes Python 3.3 or newer.)

# Python provides a handy variant of mapping that will automatically
# create entries as we need them. It's called collections.defaultdict,
# and would save us a bit of work. But in the interests of algorithmic
# clarity, I have avoided its use here.

Rosuav

//NOTE: These functions are NOT reliable if there are astral characters
//in the input! Use with UCS-2 strings only.

//Python implementations of the same algorithms for comparison:
// https://gist.github.com/Rosuav/d02bf71f8bb5354327ee8a8e5fb54e3f

//Write an algorithm to check whether any permutation of a string is a
//palindrome (a string which reads the same forwards and backwards).
//Note that this does not use the HashMap class due to a lack of useful
//features such as iteration. The core algorithm would work the same way

Rosuav

// Imagine you have an array of numbers. Write an algorithm to remove
// all numbers less than five from the array.

// Option 1: Mutate the array
function remove_lt_5(arr) {
	for (var i = arr.length-1; i >= 0; --i) {
		if (arr[i] < 5) arr.remove(i);
	}
	return arr;
}

Rosuav

//2^5 == 32 == 100000
//2^5-1 == 31 == 11111
//Powers of two (2^n) are 1 followed by n zeroes.
//Mersenne numbers (2^n-1) are n ones.

//Negate an integer using Two's Complement
function negate(int) {
    return ~int + 1;
}

Rosuav

findNthElement halves the size of the array at each step, so it's a classic
example of an O(log n) algorithm.

findElements calls findNthElement, so its complexity must be at best O(log n);
we can generally assume that toFind will be smaller than array (you won't be
asking for duplicate elements with this), so it gets dropped from the Big O,
and we describe findElements as O(log n).

isOdd does one floating-point division and one comparison, no matter what
number is provided. It's O(1), constant time.

Rosuav

//Iterative versions of https://gist.github.com/Rosuav/5736378d02c6cd459470582ce301b4b4

//Exercise 1: Take an integer as input, and return a boolean indicating whether
//the value is even or odd.
//Editorial comment: This isn't even iterative, just fomulaic. Exercise 4 could
//be done similarly. Avoiding iteration AND recursion generally gives the best
//performance, when it's possible (but usually it won't be).
function is_even(int) {
    return (int % 2) == 0;
}

Rosuav

//Exercise 1: Take an integer as input, and return a boolean indicating whether
//the value is even or odd.
function is_even(int) {
    if (int < 0) return is_even(-int);
    if (int < 2) return !int;
    return is_even(int - 2);
}

//Exercise 2: Take an array as input which contains an unknown set of numbers,
//and output an array which doubles the values of each item in that array. Test