Posts

Why binary search is the fastest search

 dadf

The Giving Trie

Image
 Alternative Titles: A Trie Grows in Palo Alto The Trie of Life The Best Time to Make a Trie is Twenty Years Ago, the Second Best Time is Now The Trie of the Knowledge of 1 and 0 If a Trie Fails and No One Sees the Error, Does The Code Compile? What is a Trie? Source: Wikipedia A trie (generally pronounced like "tree") is a searchable tree that has individual letters for nodes.  So in the example above, we have the following keys associated with their values: "to": 7 "tea": 3 "ted": 4 "ten": 12 "A": 15 "i": 11 "in": 16 "inn": 25 Keys are only complete when you run into a value - so just "t" or "te" by themselves do not constitute keys for this trie. Tries are sort of a niche data structure, but they do have some advantages: the lookup time for a trie will only ever be at most the length of the longest key.  In comparison to a binary search tree - which can at most have only 2 s...

Kadane's Algorithm

Imagine it is 1977.  You do not have a degree in computer science.  You have not spent months grinding leetcode.  You are given a algorithm problem that a decorated mathematician has already created what looks like an optimal solution. And then in less than a minute you come up with a better answer. You are  Jay Kadane , and the problem that you have solved is the maximum subarray problem. The maximum subarray problem gives you an array of numbers and asks you to pick out the subarray with the largest sum.  The problem is trivial if all the numbers are positive: [ 1 , 5 , 1 , 3 , 2 ] <- the largest subarray is obviously the entire array But what if you've got some negative numbers thrown in there? [ 1 , 5 , -1, 3 , - 2 ] <- sure, you don't want the negatives. But isn't taking the -1 worth the +3? A brute-force solution materializes pretty easily: just create every subarray and find the biggest sum: [ 1 ] = 1 [ 1 , 5 ] = 6 [ 1 , 5 , - 1 ] = 5 ...

Loose Equality, the Null Operator, and Other Oddities

 Here's a fun bit of code to run: console . log ( '0.5' == 0.5 ) //evaluates to true console . log ( '0.5' === 0.5 ) //evaluates to false The first equality statement is what's known in JavaScript as "abstract equality comparison", which people usually refer to as "loose equality."  Loose equality compares objects only after doing a type conversion - so even though '0.5' is a string and 0.5 is a number, JavaScript sort of jams them together and says "sure, good enough."  It's weird, but convenient sometimes when dealing with data that's really (in an abstract sense) numbers but could come through the pipes as either a number or a string. People have written surprisingly long algorithms to precisely define what  abstract equality  and  strict equality (aka, normal equality)  mean in JavaScript and other languages that adhere to the ECMAScript standards.  But for our regular usage, things that are to people the same ...

Heartbeats

Are you working in Ruby and need to do some asynchronous work? Like, you're waiting for an input but also want your program to, say, be doing other calculations on the side, or to stop waiting if your user is too slow? One of the first programs I made this year was an emulation of the game Set , which a certain element of speed to it - players try to make sets before each other (or before the computer does, in this version).  Here was my solution for allowing the terminal to continue displaying available cards while *also* waiting for the player to input a set while *also* putting a clock on the player's actions and letting the computer jump in with its move when time was up:           begin status = Timeout ::timeout(rand_time) do # status = Timeout::timeout(rand_time) do DisplayBoard .run(board) puts "Choose your cards: " guess = gets . chomp if guess ...

Advice for Hosting a Front-End on Heroku

Image
 ...don't.  Use  surge  instead.  Seriously, surge is the absolutely easiest front-end publishing method I've ever seen*.  Here's how to use it: 1. Download surge by opening up your terminal, typing "npm install --global surge" and pressing enter. 2.  Navigate to the directory with all your front-end code and run "npm build".  This will create a build sub-folder within your directory. 3. Navigate into that directory ("cd build") and.... Type "surge" and enter. That's it.  If you just keep pressing enter your site will go to the web. Several cool things about this: A. There's a nice, neat division between your production code and your code that you filled full of bugs trying to get one simple, easy new button into.  You can work all you want on your laptop with your buggy code and not mess up your running-just-fine website.  Then when you do figure out your bugs, you can simply run npm build again and publish again to surge to ...

How to Uses Hashes, Maps, and Sets in JavaScript

Image
One of the first thing new JavaScript programmers learn is hashes.  Hashes are useful for saving data, nesting data, and in general having a faster Big-O lookup time than arrays*. *Do you know the reason that hashes have O(1) lookup time?  IT'S BECAUSE A HASH IS A FUNCTION !  You take in your hash keys, do a bunch of fancy math, and out pops a singular result for each key input.  It still sort of blows my mind that a hash is essentially the sort of thing we studied in Algebra 1, only you can input strings, numbers, whatever you want into a hash and it'll still spit out an answer.  Of course, all those strings and s and whatnot are of course binary numbers, so it makes a fair amount of sense when you think about it. If you had Aleph-One amount of memory, you could make a hash table for these functions. Hashes are useful for all sorts of things as well - the sorts of things you might encounter in code challenges in particular, like counting up how many of a thing ...