bastille.spec.js

/*
To run locally...
$> npm install mocha -g
$> mocha bastille.spec.js
*/

"use strict";
var assert = require("assert");
var Bastille = function (){

  this.items = [];

  this.saveUrl = function(userToken, url){
    for (let item of this.items) {
      if (item.url === url)
        return false;
    }

    const item = {
      userToken: userToken,
      url: url
    };
    this.items.push(item);
    return true;
  };

  this.getUrls = function(){
    let urls = [];
    for(let i = 0; i < this.items.length; i++){
      const url = this.items[i].url;
      urls.push(url);
    }
    return urls;
  };

  this.removeUrl = function(userToken, url){
    for(let i = 0; i < this.items.length; i++){
      const item = this.items[i];
      if (item.userToken === userToken && item.url === url){
        this.items.splice(i, 1);
        return true;
      }
    }
    return false;
  };

  this.getUsersByDomain = function(domain){
    let userTokens = [];

    // TODO: Performance? Consider changing the way items are stored. On insert group by user token.

    for(let i = 0; i < this.items.length; i++){
      const item = this.items[i];
      // TODO: Use extractDomain...
      if (item.url.includes(domain))
        userTokens.push(item.userToken);
    }
    return userTokens;
  };

  /* example graph.
  this.root = {
    url: "http://www.root-node.com0",
    nodes: [
      {
        url: "http://...",
        createdBy: "userxxx"
      },
      {
        url: "http://...",
        createdBy: "userxxx"
      },
      {
        url: "http://...",
        createdBy: "userxxx"
        nodes: [
          {...},
          {...}
        ]
      }
    ]
  };

  this.findStartNode(node, url){
    // if (node.url === url)
      // return node;
    // else
      // for each child in nodes
        // return this.findStartNode(child, url);
  }

  this.getNodesWithinExactDistance(node, userToken, distance){
    let nodes = [];
    if (node.createdBy !=== userToken && distance === 0)
      return node;
    // else
      // for each child in nodes
        // nodes.push(this.getNodesWithinExactDistance(child, userToken, distance-1))
    return nodes;
  }

  this.getRecommendedUrls(userToken, url){
    const targetDistance = 3;
    const start = this.findStartNode(this.root, url);
    const targetNodes = this.getNodesWithinExactDistance(start, targetDistance);
    let urls = [];
    // for each node in targetNodes
      // urls.push(node.url)
    // return urls;
  }
  */

};

describe("Bastille Agency", function() {
  describe("CRUD without the U", function() {

    it("Should save one url.", function() {
      const bastille = new Bastille();
      const token = "user1";
      const url = "http://www.gmail.com";
      const result = bastille.saveUrl(token, url);
      assert.equal(true, result);
    });

    it("Should not save url more than once.", function() {
      const bastille = new Bastille();
      const token = "user1";
      const url = "http://www.gmail.com";
      bastille.saveUrl(token, url);
      const result = bastille.saveUrl(token, url);
      assert.equal(false, result);
    });

    it("Should get two urls.", function() {
      const bastille = new Bastille();
      bastille.saveUrl("user1", "http://www.gmail.com");
      bastille.saveUrl("user1", "http://www.hotmail.com");
      const urls = bastille.getUrls();
      assert.equal(2, urls.length);
    });

    it("Should delete url.", function() {
      const bastille = new Bastille();
      const token = "user1";
      const url = "http://www.gmail.com";
      bastille.saveUrl(token, url);
      const result = bastille.removeUrl(token, url);
      assert.equal(true, result);
    });

    it("Should not delete url when none exist.", function() {
      const bastille = new Bastille();
      const token = "user1";
      const url = "http://www.gmail2.com";
      const result = bastille.removeUrl(token, url);
      assert.equal(false, result);
    });

    it("Should not delete url that does not exist.", function() {
      const bastille = new Bastille();
      const token = "user1";
      const url = "http://www.gmail.com";
      bastille.saveUrl(token, url);
      const result = bastille.removeUrl(token, "http://www.invalid.com");
      assert.equal(false, result);
    });

    it("Should find one user for gmail.com.", function() {
      const bastille = new Bastille();
      bastille.saveUrl("user1", "http://www.gmail.com");
      bastille.saveUrl("user2", "http://www.hotmail.com");
      const userTokens = bastille.getUsersByDomain("gmail.com");
      assert.equal(1, userTokens.length);
    });

    it("Should find zeo user for previously deleted domain.", function() {
      const bastille = new Bastille();
      const token = "user1";
      const url = "http://www.gmail.com";
      bastille.saveUrl(token, url);
      bastille.removeUrl(token, url);
      const userTokens = bastille.getUsersByDomain("gmail.com");
      assert.equal(0, userTokens.length);
    });

  });
});

@kahneraja - thanks for your time in taking our assessment - glad you enjoyed it! Overall, I thought you did well, here's my feedback:

• Your solutions to problem #1 would work, but I would have preferred to see something like an associative array, where you could use a hashtable like implementation. With that, your get/save/remove operations can become a lot simpler where each value in your associative array could be an array of URLs.
• Enjoyed the tests!
• Your solution to #2 would work, but as you intimated, it's not the most performant as your dataset becomes larger. It would have been great if you went with your initial instincts of finding a more performant solution - perhaps creating a separate datastructure that mapped domains to users. That would have necessitated a change to your solution for #1, but would give you a much more performant #2.
• Your solution to #3 looked pretty good, nice use of recursion! A couple smaller comments:
  a) You didn't need getStartNode() - the problem already made the assumption that this function existed in getNode()
  b) I noticed how you added createdBy to the datastructure to do the filtering part. I would have preferred to see you use the datastructure presented to you. Also, In theory, you may have had many users save the same URL, so just checking createdBy wouldnt be sufficient - you need to make sure the user in question didnt save that URL. An easy way to do that is to filter using the getUrls() function you already implemented in #1.
  c) I was a little confused by your use of nodes in getNodesWithinExactDistance. It would have probably been easier to call the function recursively on node.A(), node.B(), and node.C().
  d) You need to check if the node is null (which would happen if the edge doesnt exist).

Ah! Interesting :)

I did start with an associative array but ended up taking a different approach and then run out of time. Totally agreed tho. hashtable approach is better. It's only been a few hours and I can't remember why exactly I took a diff approach. Might have been a perf experiment I parked along the way. Would love to spend time on improving performance.

Ah right. Yep. There are many gaps in my "find distance" pseudo code but in general I think the recursive strategy spells itself. Lots of interesting ways to improve that one too.

There was a data structure provided? Oops. Missed that. @karnie6 thanks for checking it out tho!

@kahneraja - thanks for the reply! Yeah, the node object in #3 had methods supplied in the problem that you could use.