Algorithm Time: Secret Number

or: Technical Interview Take Two

I had an interview this week (yay!) and worked on two different algorithms. With the second one, I felt that I rushed things due to my nerves, and while I got a working solution, it didn't sit right with me. I felt I could do better, especially since I ended up with a time complexity of O(n²). I was sure I could get it lower.

Here's the scenario: I'm thinking of a secret number that is n digits long. You can guess what number I'm thinking of, and I'll tell you how many digits in your guess were exact matches to my number, and how many were partial matches. An exact match means that the number and position were both correct. A partial match means that that number appears somewhere in my secret number, but not where you put it.

So for example, if my secret number is "1243" and you guessed "1235", there would be 2 exact matches (1 and 2) and one partial match (the 3).

The challenge is to write a function that takes in the secret number and the guess as parameters, and prints the number of exact and partial matches. You can assume the guess will always be the same length as the secret, and you can assume the strings won't ever be empty.

Take 1

Below is the code I worked up during the interview, or as close as I could recreate it from memory.

function guesser(secret, guess) {
  let partial = 0;
  let exact = 0;
  let sArr = secret.split("");
  let gArr = guess.split("");

  for (let i = 0; i < sArr.length; i++) {
    if (gArr[i] === sArr[i]) {
      exact++;
      gArr.splice(i, 1);
      sArr.splice(i, 1);
      i--;
    }
  }

  for (let i = 0; i < sArr.length; i++) {
    if (sArr.includes(gArr[i])) {
      partial++;
      sArr.splice(sArr.indexOf(gArr[i]), 1);
      gArr.splice(i, 1);
      i--;
    }
  }

  console.log("exact: ", exact, "partial: ", partial);
}

Let's run through the basics. sArr and gArr are arrays of the characters in secret and guess respectively. This was done to make the data easier to work with.

The first loop runs through the secret array and compares each character to the character at the same index in the guess array. If they are the same, we tick up our exact match counter, and remove the character from each array so we don't repeat it later. We also need to decrement the index counter (i) by one to make up for the fact that we just shortened the array and prevent our loop from getting out of sync.

The second loop runs through the guess array. For each character, it checks whether or not that character is found in the secret array. If it is, same deal as before, we increment the partial match counter, remove the characters from the arrays, and decrement i.

This solution works, but it's not the fastest. At a first glance I was inclined to call it O(n) but my interviewer pointed out that you have to take the .splice and .includes methods into account. Those methods work by looping through an array to find what you've asked for. An absolute best case scenario, where what you're looking for is always the first element, may end up being O(n), but most of the time that's not going to happen. So in actuality, this solution has a time complexity of O(n²). Space Complexity is O(n), because of the arrays.

Take 2

I was pretty sure I could use a hash to simplify the solution, so I pursued that angle. Here is what I ended up with:

function guesser(secret, guess) {
  let partial = 0;
  let exact = 0;
  let sHash = {};
  let gHash = {};

  for (let i = 0; i < secret.length; i++) {
    if (secret[i] === guess[i]) {
      exact += 1;
    } else {
      sHash[secret[i]] ? sHash[secret[i]]++ : (sHash[secret[i]] = 1);
      gHash[guess[i]] ? gHash[guess[i]]++ : (gHash[guess[i]] = 1);
    }
  }

  for (char in gHash) {
    if (sHash[char]) {
      partial++;
      sHash[char]--;
    }
  }

  console.log("exact: ", exact, "partial: ", partial);
}

Right away, there's no need to split the strings into arrays. Instead of creating an array of characters that we remove from as we go, we will store any characters that were not an exact match in some new hashes, with a count.

Then for the second loop, we check each character left in guess and see if it appears in the hash of secret's leftover characters. When we find a match, we increment the partial match counter and we decrement the count for that character in the secret hash. That way we avoid duplicate matches. In fact, we don't even need to set up any logic to check whether the count is above zero. Since 0 is "falsy" in JavaScript, simply calling on s[char] in a conditional will tell us if the number has dropped to zero.

Comparing the Two

Now to compare these two solutions. Space Complexity stays the same, at O(n). If there's a way to reduce it, I haven't done enough puzzling to find it.

Time complexity, though, is another matter entirely. Using this hash method, I have cut out the use of both .splice and .includes. A call to a hash (at least a very simple one like this) takes constant time, so we've dropped our total time complexity down to O(n)!

Comments

[spitz6860]

I believe your new solution fails when secret = '0011', guess = '1100' because for (char in gHash) iterates through object keys, which means your function only returns 2 partials, instead of 4.
You can find the exact question here leetcode.com/problems/bulls-and-cows/ along with test cases and solutions.