Solving the Google practice code question

Applying for a Coop position in Google without any hope that they will get back to me. It was a rainy morning when I saw a new email notification, and it’s from Google, I was numb for a while and couldn’t believe in my eyes.

After the excitement, comes the anxiety, the requirements are to answer 2 coding sample questions in 90 minutes and I know it will be hard… I didn’t take a look at it until I finished all the final exams (it came at the right time, eh?).  So today, I read the email and see that they provide the practice question aside from the coding sample questions. That’s great, at least I could have some scene of what I’m doing. Sadly, there’s only one practice question available, I don’t think it’s enough for me to be prepared….

What is the practice question of Google interview?

We are given a string S consisting of N characters and an integer K. The string represents a software license key which we would like to format. The string is composed of alphanumerical characters and/or dashes. The dashes split the alphanumerical characters within the string into groups (i.e. if there are M dashes, the string is split into M+1 groups). The dashes in the given string are possibly misplaced.
We want each group of characters to be of length K (except for possibly the first group, which could be shorter, but still must contain at least one character). To satisfy this requirement, we will reinsert the dashes. Additionally, all the lower case letters in the string must be converted to upper case.
For example, in the license key “2-4A0r7-4k
” there are two dashes which split it into three groups of lengths 1, 5 and 2, respectively. If we want each group to be of length 4, then we would have to reinsert the dashes. Thus, for K = 4, the correctly formatted string is “24A0-R74K”.
Write a function:
function solution(S, K);
that, given a non-empty string S consisting of N characters, representing a license key to format, and an integer K, returns the license key formatted according to the description above.

For example, given S = “2-4A0r7-4k
” and K = 4, the function should return “24A0-R74K”, and for K = 3, the function should return “24-A0R-74K” as the first group could be shorter.Given S = “r” and K = 1, the function should return “R”.

Write an efficient algorithm for the following assumptions:
N and K are integers within the range [1..300,000];
string S consists only of alphanumerical characters (a−z and/or A−Z and/or 0−9) and/or dashes (-);
string S contains at least one alphanumerical character.

You can choose the programming language that you want among:  C, C++, C#, Go, Java, JavaScript or Python. For me, I chose JavaScript since this is the one that I feel comfortable the most.

To be honest, it was hard for me, I didn’t get used to this kind of question, and I’m not that good to solve it quickly. I was required to finish it in 30 minutes, I complete at the last second only for the naive solution not the optimal one.

Analyzing the solution

First, I decided to solve the easiest problem.

• If the string S contains only 1 character, return that character in uppercase.
• If the string S doesn’t contain any character, return invalid.
• If the string S doesn’t consists only of alphanumerical characters (a−z and/or A−Z and/or 0−9) and/or dashes (-), return invalid.

Second, I must take all of dashes out of the string S. And I could transform the string to uppercase at this point also

Third, loop through the string and add “-” where it should be, depend on variable K

Lastly, return the finished String.

Naive Solutions

I started to code with a naive solutions, just to make it works with using the helps from built-in methods and doesn’t care about performance.

Since I’m not familiar with using Regex, I used a helper method for checking string valid. 

function isAlphaNumeric(char) {
  var code = char.charCodeAt();
  if (
    !(code > 47 && code < 58) &&
    !(code > 64 && code < 91) &&
    !(code > 96 && code < 123) &&
    !(code === 45 || code === 47)
  ) {
    return false;
  }
  return true;
}
// This code will check if the character is number or alphabel or / or -

Here come the solution:

function solution(S, K) {
  // write your code in JavaScript (Node.js 8.9.4)
  if (S.length < 1) return false;
  if (S.length == 1) return S.toUpperCase();

  for (let c = 0; c < S.length; c++) {
    if (!isAlphaNumeric(S[c])) return "";
  }

  let newStr = S.split("-")
    .join("")
    .toUpperCase()
    .split("");

  let count = 0;
  for (let i = newStr.length - 1; i >= 0; i--) {
    count++;
    if (i !== 0 && count === K) {
      newStr.splice(i, 0, "-");
      count = 0;
    }
  }

  return newStr.join("");
}

This code uses a lot of built-in methods which I think it has a big time complexity. Then I tried to improve my code without using too many built-in method.

Another Solution:

function test(S, K) {
  if (S.length < 1) return "invalid";
  if (S.length === 1) return S.toUpperCase();
  if (K < 0) return "invalid";
  for (let k in S) {
    if (!isAlphaNumeric(S[k])) return "invalid";
  }
  let key = 0;
  let strObj = {};
  for (let c of S) {
    if (c != "/" && c != "-") {
      strObj[key] = c.toUpperCase();
      key++;
    }
  }
  let newStr = "";
  let counter = key - 1;

  for (let k in strObj) {
    newStr += strObj[k];
    if (counter !== 0 && counter % K === 0) {
      newStr += "-";
    }
    counter--;
  }
  return newStr;
}

In this case,  I looped through the string and checked if a single character is not “-” or “/” I would add it to an object.

After having the object of characters setup, I make an empty string, loop through the object and then add every single character to the string. Concurrently, I made a counter that equals to the number of character and check for the right place that I should add the “-” to the string.

Though it works, I’m not sure this algorithm is good enough since I’ve just started learning about algorithm by an online course.

If you’re reading this post and know there is a better way, feel free to write something in comment section.