Using a Set For Faster Searching

Recently, I was working on a code challenge at CodeFights which specified that the solution had to run in O(n) time. The brute force solution was a nested for loop, but this would run in O(n^2) time. Here’s the code challenge:

Note: Write a solution with O(n) time complexity and O(1) additional space complexity, since this is what you would be asked to do during a real interview.

Given an array a that contains only numbers in the range from 1 to a.length, find the first duplicate number for which the second occurrence has the minimal index. In other words, if there are more than 1 duplicated numbers, return the number for which the second occurrence has a smaller index than the second occurrence of the other number does. If there are no such elements, return -1.


For a = [2, 3, 3, 1, 5, 2], the output should be
firstDuplicate(a) = 3.

There are 2 duplicates: numbers 2 and 3. The second occurrence of 3 has a smaller index than than second occurrence of 2 does, so the answer is 3.

For a = [2, 4, 3, 5, 1], the output should be
firstDuplicate(a) = -1.


[time limit] 4000ms (js)
[input] array.integer a

Guaranteed constraints:
1 ≤ a.length ≤ 105,
1 ≤ a[i] ≤ a.length.

[output] integer

The element in a that occurs in the array more than once and has the minimal index for its second occurrence. If there are no such elements, return -1.

My first attempt to solve it worked but unfortunately was not quite fast enough and did not pass the last two tests. I created a new array to hold numbers that were already checked. In a for loop, in each iteration, the new array would be checked to see if the current number was included. If it was, then function would return the number. Take a look…

function firstDuplicate(a) {
    let visitedNumbers = [],
    for (i = 0; i < a.length; i++) {
        if (visitedNumbers.includes(a[i])) {
            return a[i];
    return -1;

If the visitedNumbers array includes the current indexed number in the given array, then that number will be returned. If not, then the number is added to the visitedNumbers array and the next number in the given array is checked. If all the numbers are checked and none of them are duplicated, the function will return -1. Like I said earlier, this works, however it was not passing the last two tests, which I assume had very large inputs. After digging around a bit, I stumbled across something that I had not used before.

According to our friends at Mozilla, a Set is an object that “lets you store unique values of any type, whether primitive values or object references”. Ok, so how does that help us? Well according to this site, the Set method ‘has’ is 16% faster than the Array method ‘includes’. For small inputs, this won’t matter. But imagine a huge input; 16 percent would be very noticeable. Let’s see a Set in action.

function firstDuplicate(a) {
    let visitedNumbers = new Set(),
    for (i = 0; i < a.length; i++) {
        if (visitedNumbers.has(a[i])) {
            return a[i];
    return -1;

Now all test pass! Yay! Apparently this question is asked at Google. That makes me feel good about myself. The moral of the story: Sets are cool and fast. I’ll be using them more in the future. Until next time. Cheers:)

Vacation Time

I’ve been on vacation the last two weeks, which included a whole lot of moving around and not much time to think about programming. I don’t think I checked my email for 5 days straight. Honestly, it felt pretty good. Technology is wonderful, but there is a beautiful world beyond the bits and bytes that consume much of our attention.

It’s nice to get a breather every now and then. Coming back refreshed and still realizing you haven’t forgotten much is very nice. I’m still in Montreal until Monday, but wanted to write a little something to keep my blog up. If you haven’t been to Montreal, go now – in the summer! It’s a completely different city during the winter months, which can be quite brutal. I’ll be bringing back the technical part of the blog next week. Until then – happy summer:)

Recursion – It’s Not a Hallucination

Does recursion scare the crap out you? Well, it should! You should stop reading this now, draw the blinds, get in bed and put the covers over your head. Just kidding! Recursion is pretty cool once you get the hang of it. I’m going to try to break it down for you so you won’t have to run and hide every time it’s mentioned.

From Wikipedia:

Recursion in computer science is a method where the solution to a problem depends on solutions to smaller instances of the same problem (as opposed to iteration). The approach can be applied to many types of problems, and recursion is one of the central ideas of computer science.

Okay, so basically it is a problem that can be broken down into smaller versions of itself. This happens when a function gets called repeatedly by itself until it reaches the stopping point, which is called the base case. So a recursive function is a function that calls itself. Every time the function calls itself, it is looking for the base case. If the base case is not found, the function calls itself again. If you think about it too long, it might make you feel like you’re hallucinating. And down the rabbit hole we go…

Think of it like a for loop, except that the function is sort of flying blind until it reaches the base case.

Enough talk, let’s see an example.

function multiplyUpToFive() {
  // (1 * 2 * 3 * 4) * 5 or
  return multiplyUpToFour() * 5;

function multiplyUpToFour() {
  // (1 * 2 * 3) * 4 or
  return multiplyUpToThree() * 4;
// and down to multiplyUpToOne()

What we’re doing here is breaking down the problem into smaller problems. That wasn’t a recursive function, but it acts the same way a recursive function does. I’ll rectify this further on. Now for our recursive function, by taking function called multiplyUpTo(n), you can say that the definition of the function is equal to taking the product of

  • the products up to n – 1
  • times n
  • Let’s see…

    function multiplyUpTo(n) {
      return multiplyUpTo(n - 1) * n;
    // let's call this with an argument of 4 and see what happens
    multiplyUpTo(3)  // gets called
    multiplyUpTo(2)  // gets called
    multiplyUpTo(1)  // gets called
    multiplyUpTo(0)  // gets called
    multiplyUpTo(-1) // gets called
    // shiiiiiit. Looks like we might be stuck in a recursive loop forever!!!

    That function would have ran infinitely because we didn’t add a base case. Think of the base case as the roof of the function. Without it the function will keep going out into space – to infinity and beyond! There’s literally nothing to stop it. Okay, enough analogies. Let’s fix our multiplier function.

    function multiplyUpTo(n) {
      // Our base case is 1, so we'll check if n equals 1
      if (n == 1) {
        return 1;
      return multiplyUpTo(n - 1) * n;
    // Now if we call our function with 4 as the argument, this is what will happen
    // n does not equal 1, so it's called again
    multiplyUpTo(3) * 4
    // Again n does not equal 1
    multiplyUpTo(2) * 3
    multiplyUpTo(1) * 2
    // We reached our base case which is 1 and our function will not repeat forever 

    Now our function knows where it is in the universe and has found its purpose in life.

    Okay, the function has purpose. Now what?

    // Once the function reaches the base case, it will now solve all of the
    // problems it left behind
    multiplyUpTo(1) * 2 // 1 * 2 = 2
    multiplyUpTo(2) * 3 // 2 * 3 = 6
    multiplyUpTo(3) * 4 // 6 * 4 = 24
    // Once the function has an answer to all of itselves (I think I made that up),
    // then it returns the product the original function call. Woah dude.

    If we’re feeling good about our JavaScript we can even use a ternary statement to really make our function compact.

    function multiplyUpTo(n) {
      return n == 1 ? 1 : multiplyUpTo(n - 1) * n;

    I like it! Thinking recursively makes you think recursively makes you think recursively. See what I did there. Yeah, I’m a dork. Hopefully this helped you understand the world of recursion. It’s quite fun to write algorithms this way. Although it might be scary at first, don’t worry: The worst that can happen is you float away into the infinite:)

    How to Clone a Website Using Chrome’s Dev Tools Part III

    Alrighty then! We’re going down the home stretch. Let’s take a look at our remaining errors.

    Screen Shot 2017-07-07 at 4.01.48 PM

    Much better!

    And this is what our clone looks like…

    Screen Shot 2017-07-07 at 4.04.47 PM

    This is what Carbon Five’s site actually looks like…

    Screen Shot 2017-07-10 at 10.37.59 AM

    Right off the bat, we can see that our fonts are not the same and we need the Carbon Five logo. Looking at the errors above tells us the same story. Let’s dig in and tackle each one of these errors. The first error is for a JS file called ‘v2.js’. After searching our index.html file, we’ll find the JS file being referenced in the footer as:

    <script charset="utf-8" type="text/javascript" src="//"></script>

    All we have to do is prepend the src link with ‘http:’. After refreshing our index.html file in Chrome, the error is gone. Easy peasy:) Next on our error list is for ‘file:///fonts/c5-logo.woff’. If we search our index.html file, we’ll find two lines of code referencing the styles for the font/logo. So that means we’ll search the app.css file. We’ll find this block of styles:

    /* c5 icon font styles */
    @font-face {
      font-family: 'c5-logo';
      src:url('/fonts/c5-logo.eot?#iefix') format('embedded-opentype'),
        url('/fonts/c5-logo.woff') format('woff'),
        url('/fonts/c5-logo.ttf') format('truetype'),
        url('/fonts/c5-logo.svg#c5-logo') format('svg');
      font-weight: normal;
      font-style: normal;

    Let’s go check the sources in our console at carbonfive. When we click the images folder, there are two files – c5-logo.woff & pentel.woff. The ‘woff’ extension stands for Web Open Font Format. This file type for fonts is compressed so websites using these file formats should load faster. We can append ‘/fonts/c5-logo.woff’ to ‘’ in Chrome and the file will download to our computer. All we have to do is make a ‘fonts’ folder in Atom and drag our recently downloaded file over and drop in. When we refresh the browser we’re still getting the error. So we probably have to change the way it’s being referenced.

    Let’s prepend all of the urls from the c5 icon font styles above with ‘..’. This will bring us up two the root directory and then we’ll be able to access our fonts folder. Let’s refresh Chrome and see if we’re down a couple more errors. We are! We only have three errors to go:)

    Screen Shot 2017-07-10 at 11.12.44 AM

    Two of the errors look very similar to the ones we just took care of. Let’s try the same steps. First, append with ‘/fonts/pentel.woff’ and open in Chrome. That should download the file. Next drag it over to Atom and place in the fonts folder. Now let’s do a search in our app.css file for ‘pentel’. We should find this block of code:

    @font-face {
      font-family: 'pentel';
      src:url('/fonts/pentel.eot?#iefix') format('embedded-opentype'),
        url('/fonts/pentel.woff') format('woff'),
        url('/fonts/pentel.ttf') format('truetype'),
        url('/fonts/pentel.svg#pentel') format('svg');
      font-weight: normal;
      font-style: normal;

    Looks very familiar! I think you’ll know what to do next. If you said ‘prepend the urls with two periods’, you are correct! After refreshing the browser we’re left with one error! Sweet!

    **Just a note – the ‘pentel’ font is an Adobe font, which you’ll need a typekit password for. This is not a free font. It will work locally, but if you publish to github pages or something similar it will break.**

    The last error has something to do with a Google API and from the look of the link, it’s specific to Carbon Five. This means only their devs have access to the API. In that case we’re done! Feel free to change images, fonts and styles. If you see a cool feature, try to figure out how they’re doing it – you have the code in your hands! I hope this was enjoyable for you. If you’re ever on a cool website and you want to see what’s going on under the hood, command + option + i. What did the world look like before Dev Tools? I don’t want to know!

    How to Clone a Website Using Chrome’s Dev Tools Part II

    We left off with turning some errors green. You can find the site we’re working on here. Once we got the bootstrap reference link to work, all of a sudden the site started to look like something real. It still needs some work though. This is where we’re at…

    Screen Shot 2017-07-02 at 5.41.40 PM

    Getting there!

    Let’s check out the console to see what errors we still have…

    Screen Shot 2017-07-07 at 3.16.27 PM

    Welp. Still a lotta red! Let’s dig back in and tackle some of these errors. Starting with the first error:

    Failed to load resource: net::ERR_FILE_NOT_FOUND – conversion.js

    So this error is telling us we’re missing a conversion.js file. Going back to our index.html file (or the view page source at carbonfive), we can find that the js file has something to do with Google Analytics. We don’t need analytics for our purposes, so we’re just going to delete that whole script from the head. If you’re following along, the script starts just after the script for app.js and ends just before the closing head tag. Delete it all!

    Now when we refresh our local index file in the browser, that error is gone. Our next error is for file:///images/square.png. Looking at this link, right off the bat, there are too many forward slashes after ‘file’. Also, we don’t have this file! If we go into Chrome’s Dev Tools (command + option + j), and go to ‘sources’ we can see the images folder and the images within. If we click and drag an image into its own tab in Chrome, we can see that its hosted on carbonfive. All we have to do is prepend the reference links for all images with ‘; and we should be good to go. Find the square.png img tag in your index.html file and add it. That should take care of that error.

    Looking at most of the other errors, we can find them to be the same in nature. We just have to complete the previous step for all images referenced in the our index.html and app.css files. If you’re using Atom as your text editor, you can click just before the forward slash on the image you want to change. Then hold down the command key do the same to every image you want to change. Now we can change them all at the same time!

    After refreshing our local html page in Chrome, there are significantly less errors! Sweet!

    Screen Shot 2017-07-07 at 4.01.48 PM

    Much better!

    Screen Shot 2017-07-07 at 4.04.47 PM

    We just kicked those errors asses. The site is really coming along now. Let’s meet back here next week for the third and final installment. Until then, CHEERS:)

    How to Clone a Website Using Chrome’s Dev Tools Part I

    Ever want to copy a website? Well, it’s pretty easy – especially with Chrome’s Dev Tools! I find it pretty useful to go into someone else’s code to see how they’re doing what they’re doing. Then you can implement new cool features for sites you’re working on. I’m not going into complicated websites with API’s and the like; just a simple static site.

    I’m going to be using Carbon Five’s website as reference. First head on over there, then right click on the page and select ‘view page source’. This will show us all the html for the page. Now just select all (command + ‘a’) and copy. In your text editor of choice (I’m using Atom), create an index.html file and paste the html there. You’ll see a bunch of files that are referenced in the ‘head’ of the document. We’ll have to copy the non-CDN local files into our text editor.

    We’re going to open each file from the page source and copy file into our text editor.

    Screen Shot 2017-07-02 at 3.41.31 PM

    Create folders for each type of file, ie. javascripts, stylesheets, images, etc. We’re going to do what we did above when copying and pasting all of the HTML. Starting from the ‘javascripts/showup.js’ file in the head of the view source page document, click on each file, select all, copy (noticing a trend?) and paste into a newly created file in Atom. Name the file the same as the file you’re copying from. From here, let’s see where we stand by opening the index.html file in Chrome. Go ahead, I’ll wait…

    Screen Shot 2017-07-02 at 5.24.47 PM

    It should look something like this

    Woah! All of a sudden we’re in 1995 and Nirvana’s on the radio! We’re getting the bare bones HTML here. Let’s take a look in the console to see what’s going on under the hood. Command + option + ‘j’ will get us there. Notice all of the errors.

    Screen Shot 2017-07-02 at 5.30.38 PM

    That’s a lotta red

    There are a ton of files that can’t be found. There are definitely some files we haven’t looked at yet, but let’s focus on the ones we have. Our file directory must be different than Carbon Five’s. All we have to do is reference them a bit differently than we are.

    Let’s look at the non-CDN files in the ‘head’ of our index.html page. They all start with a forward slash, but if we’re referencing from the index.html file, we’ll have to prepend them with a single period to jump up to the root directory. Start from the ‘showup.js’ file start adding.

    <script type="text/javascript" src="/javascripts/showup.js"></script> // This
    // Turns into 
    <script type="text/javascript" src="./javascripts/showup.js"></script>

    When you’re done (remember to save), refresh your index.html file in Chrome. You’ll notice a few things happened. The page has some styling now – not great, but it’s something. Next, we have less errors in the console. Sweet! Let’s keep going and turn these errors green.

    In the console, notice how the cdn files which can’t be found start with two forward slashes. Since they are referencing outside websites as opposed to local files, we’ll have to prepend them with ‘https:’, and they should be good to go. Back in our index.html file, let’s do just that. Once you’re done, notice how the links turn blue. We now have good links. Go back to your browser and refresh.

    Screen Shot 2017-07-02 at 5.41.40 PM

    Getting there!

    Now we’re talking! Since we’re now referencing the bootstrap cdn files correctly, we have our navbar looking good and the page layout is looking much better. Next time, we’ll add images and conquer any other errors we come across. Until then, CHEERS:)

    I’ve Got 99 Problems – but Deploying My Rails/Angular App to Heroku is No Longer One of Them:) PART 1

    I’ve been trying to deploy my app Medidate to heroku for a while. I sort of let it go a couple of months ago, but I’m using the app on my portfolio site, so I wanted it to work. It works fine when deployed locally, but Heroku does not likey. I’ve deployed straight up Rails apps with no problem. Angular definitely made it a lot harder. This sort of thing can make a developer go crazy, perhaps contemplating throwing their laptop through the closest window. Of course I would never do that! But other less even keel people might:) I am using Rails 5, AngularJS 1.6, and Bower for dependencies.

    I was actually able to deploy to Heroku, however, nothing was working. What I mean by working – none of my styles or javascript files were showing up. I just had a white page with a few non-styled links in the navbar. I assumed it was an issue with the Asset Pipeline in Rails and how it was compiling in Heroku. A friend had a similar issue (from what I hear, many people have trouble deploying Rails/Angular apps), and he said a great gem to try out was ‘ngannotate-rails’. This gem basically fixes any dependency injections issues in Angular files when minified. This helped a lot of other devs – not me though.

    I needed to precompile my assets for Heroku. I found this little line of code to do that:

    RAILS_ENV=production rake assets:precompile

    That did not run and was aborted. The reason?

    ExecJS::RuntimeError: SyntaxError: Unexpected character ‘`’

    Hmmm. Since it’s a JS error and the character is a backtick, I thought it might have something to do with ES6 syntax, which I used a bunch in my code. After Googling around it looked like my assumption was correct. The answer? I needed more gems of course! Sprockets and babel-transpiler would take care of translating any new JS6 syntax that the Rails precompiler (Uglifier) was having trouble understanding. Unfortunately, that didn’t do the trick and I started to change my files error by error by converting any ES6 syntax to the old style. It’s all a learning process right. Ugh.

    I used some great advice via Stack Overflow on how to track down bugs when compiling – run the rails console, then type:

    JS_PATH = "app/assets/javascripts/**/*.js"; 
    Dir[JS_PATH].each do |file_name|
      puts "\n#{file_name}"
      puts Uglifier.compile(

    This will show you which files are causing the errors. After going through one file, I thought I might be missing something in regards to babel. Luckily I was! I had to add the .es6 extension to my problem js files. After I did this, everything was good. But not for long:( Stay tuned next week for the continuation. Flashbacks of watching an episode of Scooby Doo and seeing ‘to be continued’. I hated that!