5
\$\begingroup\$

This question was asked during an interview as a software developer:

Task:

You work on a team whose job is to understand the most sought after toys for the holiday season. A teammate of yours has built a webcrawler that extracts a list of quotes about toys from different articles. You need to take these quotes and identify which toys are mentioned most frequently. Write an algorithm that identifies the top N toys out of a list of quotes and list of toys.

Your algorithm should output the top N toys mentioned most frequently in the quotes.

Input:

The input to the function/method consists of five arguments:

  • numToys, an integer representing the number of toys
  • topToys, an integer representing the number of top toys your algorithm needs to return;
  • toys, a list of strings representing the toys,
  • numQuotes, an integer representing the number of quotes about toys;
  • quotes, a list of strings that consists of space-sperated words representing articles about toys

Output:

Return a list of strings of the most popular N toys in order of most to least frequently mentioned

Note:

The comparison of strings is case-insensitive. If the value of topToys is more than the number of toys, return the names of only the toys mentioned in the quotes. If toys are mentioned an equal number of times in quotes, sort alphabetically.

Example:

Input:
numToys = 6
topToys = 2
toys ["elmo", "elsa", "legos", "drone", "tablet", "warcraft"]
numQuotes = 6
quotes = ["Emo is the hottest of the season! Elmo will be on every kid's wishlist!",
"The new Elmo dolls are super high quality", 
"Expect the Elsa dolls to be very popular this year",
"Elsa and Elmo are the toys I'll be buying for my kids",
"For parents of older kids, look into buying them a drone",
"Warcraft is slowly rising in popularity ahead of the holiday season"];

Output:
["elmo", "elsa"] 

My Approach: At first I wanted to use TDD. But it was too time consuming and I felt I was running out of time. Therefore I tried to break down the task into small, simple, and reuseable functions in my head. I got confused when it came to splitting the quotes and and the words within a quote. Also, I didn't understand why the function got so many parameters - most of them aren't needed IMO or would using them would make my function more efficient?

My solution:

// DEFINE ANY FUNCTION NEEDED
function sanitize (w) {
    return w.toLowerCase();
}
function sanitizeSentence(sentence = "") {
    return sanitize(sentence.replace(/[^a-zA-Z ]/g, ""));
}
function sanitizeArr(arr = []) {
    return arr.map(a => sanitize(a));
}
function getUniqueWordsOf(quote) {
    return quote.split(" ").reduce((uniqueWords, word) => {
        if (!uniqueWords.includes(word)) {
            uniqueWords.push(word);
        }
        return uniqueWords;
    }, []);
}

// returns a key value object, 
// with key the toy name and value the number of toys
function getToysFromQuotes(quotes, toys = []) {
  const sanitizedToys = sanitizeArr(toys);
  const uniqueToys = {};
  quotes.forEach(quote => {
    const uniqueWords = getUniqueWordsOf(quote);
    uniqueWords.reduce((uniqueToys, word) => {        
        if (toys.includes(word)) {
            if (uniqueToys[word]) {
                uniqueToys[word] = uniqueToys[word] + 1;                
            } else {
                uniqueToys[word] = 1;
            }         
        }
        return uniqueToys;
    }, uniqueToys);
  });
  return uniqueToys;
}
function orderToys (toyObj) {
    const sortable = [];
    for (const toy in toyObj) {
        sortable.push([toy, toyObj[toy]]);
    }
    return sortable.sort((a, b) => b[1] - a[1])
        .map(x => x[0]);
}
// FUNCTION SIGNATURE BEGINS, THIS FUNCTION IS REQUIRED
function popularNToys(numToys, topToys, toys, numQuotes, quotes) {
    // WRITE YOUR CODE HERE
    const quotesArr = quotes.map(sentence => sanitizeSentence(sentence));
    const sanitizedToys = sanitizeArr(toys);
    const mentionedToys = getToysFromQuotes(quotesArr, toys);
    const orderedToys = orderToys(mentionedToys);

    return (orderedToys.length <= topToys)
      ? orderedToys
      : orderedToys.slice(0, topToys);
}
// FUNCTION SIGNATURE ENDS

Test cases:

Test 1

var numToys = 6;
var topToys = 2;
var toys = ["elmo", "elsa", "legos", "drone", "tablet", "warcraft"];
var numQuotes = 6;
var quotes = ["Emo is the hottest of the season! Elmo will be on every kid's wishlist!",
"The new Elmo dolls are super high quality", 
"Expect the Elsa dolls to be very popular this year",
"Elsa and Elmo are the toys I'll be buying for my kids",
"For parents of older kids, look into buying them a drone",
"Warcraft is slowly rising in popularity ahead of the holiday season"];

Expected result:
["elmo", "elsa"]

Test 2

var numToys = 5;
var topToys = 2;
var toys = ["anacell", "betacellular", "cetracular", "deltacellular", "eurocell"];
var numQuotes = 3;
var quotes = [
  "Best services provided by anacell",
  "betacellular has great services",
  "anacell provides much better services than all other",
];

Expected result:
["anacell", "betacellular"]

Test 3

var numToys = 5;
var topToys = 2;
var toys = ["anacell", "betacellular", "cetracular", "deltacellular", "eurocell"];
var numQuotes = 3;
var quotes = [
  "I love anacell Best services Best services provided by anacell",
  "betacellular has great services",
  "deltacellular provides much better services than betacellular",
  "cetracular is worse than eurocell",
  "betacellular is better than deltacellular",
];

Expected result:
["betacellular", "deltacellular"]
\$\endgroup\$
  • \$\begingroup\$ The expected result of 3rd test does not match problem "If toys are mentioned an equal number of times in quotes, sort alphabetically" The toys . "deltacellular", and "anacell" each have 2 matches, "anacell" is ahead of "deltacellular" alphabetically so should the expected result not be ["betacellular", "anacell"], \$\endgroup\$ – Blindman67 Dec 16 '19 at 12:56
  • \$\begingroup\$ If you include numQuotes to limit the number of quotes to search then for the 3rd test the toys "betacellular" and "anacell" both occur twice thus the expected result should be ["anacell", "betacellular"] \$\endgroup\$ – Blindman67 Dec 16 '19 at 13:41
3
\$\begingroup\$

Design

Generally speaking, putting logic into functions is good. But abstractions have a price. They can serve to hide what otherwise may be explicit functionality. Only abstract when there is pressing motivation to do so, and when writing abstractions, make the contract clear and purposeful.

Consider the sanitize function:

function sanitize (w) {
    return w.toLowerCase();
}

For the above function, just calling toLowerCase() in the calling scope is much more explicit, so a wrapper on a builtin like this harms readability and offers few of the benefits of abstraction (encapsulation, reduction of complexity, etc).

Your intent may have been that you're planning ahead for sanitization to grow more complex, require frequent changes or be called in many locations. Great--but these functions still seem premature. Coding the "helpee" function(s) correctly would eliminate the need for more than a single call and we can inline the logic.

The same applies to the following functions as well to an extent:

function sanitizeSentence(sentence = "") {
    return sanitize(sentence.replace(/[^a-zA-Z ]/g, ""));
}
function sanitizeArr(arr = []) {
    return arr.map(a => sanitize(a));
}

I'm not sure what the point of the default parameters is here--it appears that the issue is concern for the caller forgetting to provide a parameter. But crashing on calling undefined.map is an appropriate response to this. Providing [] for malformed calls might hide bugs and is actually less friendly to the client of the function than a good, old-fashioned crash.

sanitizeArr is also too insubstantial to be its own function. The caller can simply say arr.map(e => e.toLowerCase()) and be done with it.

sanitizeSentence hard codes the logic in the regex and has a non-obvious contract. It's unclear throughout all of these functions exactly what sanitization entails without looking at the bodies of the functions. This is an indication that something has gone wrong with the design.

getToysFromQuotes and orderToys are single-use and overly specific and while they do help de-clutter the calling code (popularNToys does turn out pretty clean, taken alone), properly coding the caller should make them easy to toss out. For example,

const sanitizedToys = sanitizeArr(toys);

creates a variable that is unused inside getToysFromQuotes. It's mentally taxing to trace execution through all of these helper functions.

You're correct: there's no need for the redundant length parameters. These would only be necessary in a language like C where arrays aren't objects and have no length property. I'd alert the interviewer that these would be likely to introduce bugs and have no business being in function headers in JS. Test 3 does use one of these parameters to trim the quotes array, but this is unusual. Typically, the caller would call the function with whatever subset of the array that they want to call it with rather than overloading the function with unrelated data preparation concerns.


Efficiency

Although premature optimization is the root of all evil, the line

if (!uniqueWords.includes(word)) 

is slow, requiring a linear search across the entire list inside a hot loop. Frequency counting is a computationally-demanding task and the plot you were given suggests that this code will need to scale to large datasets. Rely on hash structures like Set, Map and plain old JS objects for this purpose. Only use includes when the heap allocation cost of an object is greater than the linear search time.

Even if we process each quote individually, there are cleaner ways to create the frequency count map than reduce inside a forEach, both of which break scope to mutate an object in getToysFromQuotes.


Style

  • Your variable names are generally clear and descriptive, the occasional w notwithstanding.
  • Use consistent indentation; this code switches between 2 and 4 spaces. The snippet editor's autoformatting does a pretty stellar job of formatting JS (although I like Stroustrup-style if/else blocks).
  • Use vertical whitespace to separate function definitions and other blocks. Attach parameter lists to function names:

    function orderToys (toyObj) {
        const sortable = [];
        for (const toy in toyObj) {
            sortable.push([toy, toyObj[toy]]);
        }
        return sortable.sort((a, b) => b[1] - a[1])
            .map(x => x[0]);
    }
    

    is clearer as

    function orderToys(toyObj) {
        const sortable = [];
    
        for (const toy in toyObj) {
            sortable.push([toy, toyObj[toy]]);
        }
    
        return sortable
            .sort((a, b) => b[1] - a[1])
            .map(x => x[0]);
    }
    

    Even here, there's a builtin for the loop (Object.entries). I'm not crazy about "obj" and "arr" being in var names unless they are truly generic--toyCounts is better because it implicitly indicates we have a key-value pair structure. We can destructure the parameters to give them clearer names as well. I also prefer arrow functions when possible which are cleaner and have more restrictive scoping:

    const orderToys = toyCounts => Object.entries(toyCounts)
      .sort(([, aCount], [, bCount]) => bCount - aCount)
      .map(([toy, ]) => toy);
    ;
    

    Now we're back to a short, specific, single-use function that we can consider inlining in the caller.

  • quotes.map(sentence => sanitizeSentence(sentence)); is clearer and has less overhead as quotes.map(sanitizeSentence);.

    Similarly, arr.map(a => sanitize(a)) goes to arr.map(sanitize).

  • Conditional code like:

    return (orderedToys.length <= topToys)
      ? orderedToys
      : orderedToys.slice(0, topToys);
    

    is unnecessary because slice is smart enough not to run past the length of the array:

    return orderedToys.slice(0, topToys);
    
  • uniqueToys[word] = uniqueToys[word] + 1; can be uniqueToys[word]++.

  • Prefer function chaining to eliminate single-use intermediate variables. The code

    const quotesArr = quotes.map(sentence => sanitizeSentence(sentence));
    const sanitizedToys = sanitizeArr(toys);
    const mentionedToys = getToysFromQuotes(quotesArr, toys);
    const orderedToys = orderToys(mentionedToys);
    

    can't be chained because of the nature of the helper functions. See my rewrite for a chained version that is idiomatically composed using array builtins.

  • As alluded to earlier, avoid overusing forEach and reduce. In particular, arr.reduce((a, e) => ..., []) is almost always an antipattern that can be replaced with map + filter or flatMap. map and filter are cleaner and more semantic than reduce, which can be clunky to work with, so only use it when map and filter can't do the job.

Edge cases and testing

  • quote.split(" ") presumes that the input string doesn't have other whitespace beyond " " between words. Use regex and a quantifier to grab multiple spaces between words, quote.split(/\s+/g) or / +/g, which is more robust to unusual formatting (and there will be unusual formatting, so it's not a premature consideration).
  • The code doesn't work if there are spaces or other non-word characters in the toy names. I would imagine that this is an important edge case to think about since a lot of toy names have spaces in them. The complexity grows when you consider overlapping toy names. Since there are no specific requirements for toy names, typically interviewers will want to be prompted to establish a concrete spec with you during the interview.
  • Related to the above point, the testing suite offers poor coverage and doesn't exercise the code much. Having var toyCount = ... and different blocks is not scalable. Use a testing package like Mocha, or at least create an array of objects to hold test data and write a little harness. Then, add tests for every edge case you need to consider once a spec is defined.

A rewrite

Here's a possible rewrite:

const popularNToys = (toys, quotes, topToys=1) => {
  const pattern = new RegExp(toys.join("|"), "gi");
  const matches = quotes.flatMap(e => e.toLowerCase().match(pattern));
  
  const toyFrequencies = matches.reduce((counts, toy) => {
    counts[toy] = ++counts[toy] || 1;
    return counts;
  }, {});

  return Object.entries(toyFrequencies)
    .sort(([aToy, aCount], [bToy, bCount]) =>
      bCount - aCount || bToy.localeCompare(aToy)
    )
    .slice(0, topToys)
    .map(([toy, ]) => toy);
};

const tests = [
  {
    topToys: 2,
    toys: ["elmo", "elsa", "legos", "drone", "tablet", "warcraft"],
    quotes: [
      "Emo is the hottest of the season! Elmo will be on every kid's wishlist!",
      "The new Elmo dolls are super high quality",
      "Expect the Elsa dolls to be very popular this year",
      "Elsa and Elmo are the toys I'll be buying for my kids",
      "For parents of older kids, look into buying them a drone",
      "Warcraft is slowly rising in popularity ahead of the holiday season"
    ],
    expected: ["elmo", "elsa"]
  },
  {
    topToys: 2,
    toys: ["anacell", "betacellular", "cetracular", "deltacellular", "eurocell"],
    quotes: [
      "Best services provided by anacell",
      "betacellular has great services",
      "anacell provides much better services than all other",
    ],
    expected: ["anacell", "betacellular"]
  },
  {
    topToys: 2,
    toys: ["anacell", "betacellular", "cetracular", "deltacellular", "eurocell"],
    quotes: [
      "I love anacell Best services Best services provided by anacell",
      "betacellular has great services",
      "deltacellular provides much better services than betacellular",
      "cetracular is worse than eurocell",
      "betacellular is better than deltacellular",
    ],
    expected: ["betacellular", "deltacellular"]
  },
  {
    topToys: 15,
    toys: ["a and b", "b and c"],
    quotes: ["asdf a and b b and a b and c b and c"],
    expected: ["b and c", "a and b"]
  }
];

console.log(tests.every(test => 
  "" + popularNToys(test.toys, test.quotes, test.topToys) ===
  "" + test.expected) ? "tests passed" : "a test failed"
);

We've quartered 60 lines to 15 lines. Inlining all of the helper functions and showing each explicit step using chained array builtins makes the function body clear and solves the problem without introducing indirection.

This code isn't perfect, however, and makes assumptions about the data absent more information. If efficiency is paramount and we expect to have a large toys array, I'd question whether making toys into a giant regex with alternation as I'm doing is the fastest matching approach. There could be substantial backtracking. Using a library optimized for scanning a string to locate multiple matches would be the way to go.

This task is also easily parallelizable, so I'd consider spawning multiple worker processes to run on each core (again, premature until we're told the data will be massive, but worth mentioning in an interview; scaling is a common follow-up).

Another drawback of the above approach is that it rejects overlapping matches for toy names. If toy names aren't completely disjoint, you can use an inefficient quadratic match:

quotes = quotes.map(e => e.toLowerCase());
const matches = toys.map(toy => quotes.map(quote => 
  [...quote.matchAll(new RegExp(`\\b${toy}\\b`, "gi"))]
)).flat(3);

Regardless, whichever matching scheme you need to meet the (ambiguous) requirements for names is a matter of adjusting a couple lines of code. Should the function grow any more complex, then it'd likely be appropriate to break it up into smaller functions.

\$\endgroup\$
  • 2
    \$\begingroup\$ Great comments. Especially about my helper functions. They may be one of the reasons I git confused and my code was hard to debug. \$\endgroup\$ – thadeuszlay Dec 16 '19 at 0:49
  • \$\begingroup\$ Your rewrite does not return toys not mentioned. the problem states ...least frequently mentioned." (nor is null` a empty list if it were to exclude unmentioned toys). Also you are ignoring the numQuotes argument which reduces the search in test 3 to only 3 quotes making the expected result ["anacell", "betacellular"]. Consider the test toys ["a", "a ranger"] you have presumed that spaces can be part of the toy name, should your function not return ["a ranger"] in the quote "A ranger is the best". As it stands "a ranger" is ignored and the unmentioned "a" is returned as ["a"] \$\endgroup\$ – Blindman67 Dec 16 '19 at 14:00
  • \$\begingroup\$ On further consideration I must downvote -1 because of the inclusion of spaced names. Sorry as you have put a lot of work into this answer, but this type of initiative is a considerable problem in the industry (often called "feature creep"). Ambiguity in the design (problem) should be nutted out in the design process, not presumed by the coder. \$\endgroup\$ – Blindman67 Dec 16 '19 at 14:16
  • \$\begingroup\$ Good points and thanks for the explanation. The main points of my response all stand, though, and I think this is a major improvement over the original, which would be a lot harder to tweak as you're suggesting. I am presuming that the toy names are disjoint but it's a pretty trivial adjustment either way and sort of incidental to the review. It seems equally presumptuous to assume no spaces than to assume there are, because it's unspecified. I'll list a few options and point out the drawbacks--if you want perfect matching, you'll be taking a performance hit for that. \$\endgroup\$ – ggorlen Dec 16 '19 at 16:03
  • \$\begingroup\$ As for the extra parameter, I missed that in test 3, but caller should simply provide a list of what they want rather than pass such a variable, which is not typical in JS. I don't follow you on ...least frequently mentioned. The full context of that is from "most to least frequently mentioned", which is what I'm doing. \$\endgroup\$ – ggorlen Dec 16 '19 at 16:05
0
\$\begingroup\$

Building on ggorlen's answer, you can simplify further by just joining the quotes and mapping the toys to the length of matches.

I split out a couple functions that may or may not aid readability.

const countMatches = (s, other) => (other.match(new RegExp(s, 'gi')) || []).length;

const toyComparator = ([aToy, aCount], [bToy, bCount]) =>
      bCount - aCount || bToy.localeCompare(aToy)

const popularNToys = (toys, quotes, topToys=1) => 
  toys.map(toy => [toy, countMatches(toy, quotes.join('|'))])
    .sort(toyComparator)
    .slice(0, topToys)
    .map(([toy, count]) => toy); 


const tests = [
  {
    topToys: 2,
    toys: ["elmo", "elsa", "legos", "drone", "tablet", "warcraft"],
    quotes: [
      "Emo is the hottest of the season! Elmo will be on every kid's wishlist!",
      "The new Elmo dolls are super high quality",
      "Expect the Elsa dolls to be very popular this year",
      "Elsa and Elmo are the toys I'll be buying for my kids",
      "For parents of older kids, look into buying them a drone",
      "Warcraft is slowly rising in popularity ahead of the holiday season"
    ],
    expected: ["elmo", "elsa"]
  },
  {
    topToys: 2,
    toys: ["anacell", "betacellular", "cetracular", "deltacellular", "eurocell"],
    quotes: [
      "Best services provided by anacell",
      "betacellular has great services",
      "anacell provides much better services than all other",
    ],
    expected: ["anacell", "betacellular"]
  },
  {
    topToys: 2,
    toys: ["anacell", "betacellular", "cetracular", "deltacellular", "eurocell"],
    quotes: [
      "I love anacell Best services Best services provided by anacell",
      "betacellular has great services",
      "deltacellular provides much better services than betacellular",
      "cetracular is worse than eurocell",
      "betacellular is better than deltacellular",
    ],
    expected: ["betacellular", "deltacellular"]
  },
  {
    topToys: 15,
    toys: ["a and b", "b and c"],
    quotes: ["asdf a and b b and a b and c b and c"],
    expected: ["b and c", "a and b"]
  }
];
console.log(tests.every(test => 
  "" + popularNToys(test.toys, test.quotes, test.topToys) ===
  "" + test.expected) ? "tests passed" : "a test failed"
);

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.