elisabethgross for Coderbyte

Posted on Dec 2, 2019 • Edited on Jan 8, 2020

A coding interview question asked at Google

#career #codenewbie #javascript #challenge

Hey everyone! Hope you enjoyed solving last week’s challenge. In case you haven’t seen it, I’ll link last week’s article so you can go check it out.

The article
The challenge on Coderbyte

Here's a popular way to solve last week's challenge:

Two index approach:

A more optimized solution (one that is possible because the strings of numbers are sorted) involves initializing two indexes at the start of both strings. Check to see if the element at the index in the first string is equal to, less than, or greater than the element at the index in the second string. If they are equal, push the value to the result array. Because the strings are sorted, if the element in the first string is less than the element in the second string, you can be sure the first element doesn’t exist in the second string. Therefore, you can increment the first index to look at the next value. If the element in the first string is greater than the element in the second string, you can be sure that the value in the second string doesn’t exist in the first string and can increment the second index to look at the next value. This might be clearer to see in code!

 function intersection (arr) {
  const inBothArrays = []
  const [arr1, arr2] = arr.map((str) => str.split(', ').map((e) => parseInt(e)))

  let index1 = 0
  let index2 = 0

  while (index1 < arr1.length && index2 < arr2.length) {
    const elem1 = arr1[index1]
    const elem2 = arr2[index2]

    if (elem1 === elem2) {
      inBothArrays.push(elem1)
      index1++
      index2++
    } else if (elem1 > elem2) {
      index2++
    } else if (elem1 < elem2) {
      index1++
    }
  }

  return inBothArrays.join(',')
}

So for the example:

Calling intersection([“3, 4, 7, 11, 15”, “1, 3, 5, 8, 11”]); your function should return “3,11”.

Here is an illustration that might make this a little clearer.

Remember, this solution only works because the arrays are sorted. The time complexity of this solution is O(n+m).

This week's challenge:

For this week, we'll be solving a coding problem that was given in an actual Google phone screen interview. Remember to head over to Coderbyte to submit your code!

Write a function that takes an array containing two strings where each string represents keypresses separated by commas. For this problem, a keypress can be either a printable character or a backspace (represented by -B). Your function should determine if the two strings of keypresses are equivalent.

You can produce a printable string from such a string of keypresses by having backspaces erase one preceding character. Consider two strings of keypresses equivalent if they produce the same printable string. For example:

checkEquivalentKeypresses(["a,b,c,d", "a,b,c,c,-B,d"]) // true
checkEquivalentKeypresses(["-B,-B,-B,c,c", "c,c"]) // true
checkEquivalentKeypresses(["", "a,-B,-B,a,-B,a,b,c,c,c,d"]) // false

Have fun and you got this!!

Our newsletter 📫

We’re going to be sending out a small, feature reveal snippet every time we release something big, so our community is the first to know when we break out something new. Give us your email here and we'll add you to our "first to know" list :)

Latest comments (40)

KT • Mar 28 '22 • Edited

I came up with this simple solution :D

pentacular • Jul 10 '20

The insight here should be that this is a variation upon Merge Sort.

Jingo • Feb 2 '20

Here is my solution

Ricardo Pedroso • Jan 23 '20

Hi there, this is the solution I came up with :)

Luiz Guilherme • Dec 10 '19

SaiKumar Immadi • Dec 9 '19

Stack solution using JavaScript array methods push and pop. O(n).

const checkEquivalentKeypresses = array => {
  const array1 = array[0].split(",");
  const array2 = array[1].split(",");

  const firstString = [];
  const secondString = [];

  array1.forEach(char => {
    if (char === "-B") {
      firstString.pop();
    } else {
      firstString.push(char);
    }
  });

  array2.forEach(char => {
    if (char === "-B") {
      secondString.pop();
    } else {
      secondString.push(char);
    }
  });

  return firstString.join() === secondString.join();
};

Scott Yeatts • Dec 8 '19 • Edited

Not the "code golf" solution, but I think is more readable and avoids nested looping (plus I think the ternaries are more readable once they get a little long using multiple lines).

"Clever" solutions are fun... maintainable ones save time :D

If you wanted to split this out to handle multiple cases or non-compliant arrays (say with spaces or non-string content) I would add additional functions to handle those cases, but not as the spec exists now.

Localization for non-English languages could be handled by adding a language code param to the function or a constant.

function EquivalentKeypresses(strArr) { 

  // code goes here  
  const comparatorString = strArr[1].split(',')
    .reduce((agg, current) => {
      return current === '-B'
        ? agg.substring(0, agg.length - 1)
        : agg + current; 
    }, '');

  return strArr[0].localeCompare(comparatorString, 'en', {ignorePunctuation: true}) === 0;
}

// keep this function call here 
console.log(EquivalentKeypresses(readline()));

Scott Yeatts • Dec 8 '19 • Edited

Changed, only cause when I submitted on coderbyte, the test cases showed that "-B" cases were possible in the first string (IE: comparing vs an edited string as opposed to a base-string, so... egg on my face haha)

(And I edited again... because code review matters, and there's code to be removed...)

Here's the modified solution:

function compare(str) {
  return str.split(',')
    .reduce((agg, current) => {
      return current === '-B'
        ? agg.substring(0, agg.length - 1)
        : agg + current; 
    }, '');
}

function EquivalentKeypresses(strArr) { 

  // code goes here 
  return compare(strArr[0]).localeCompare(compare(strArr[1]),'en',{ignorePunctuation: true}) === 0;
}

// keep this function call here 
console.log(EquivalentKeypresses(readline()));

DownloadPizza • Dec 5 '19 • Edited

A rust solution without using a stack and any number of strings:
play.rust-lang.org/?version=stable...

DownloadPizza • Dec 5 '19

Ill proably make one that fails as soon as there is a difference between the arrays, maybe it will be done tomorrow

DownloadPizza • Dec 6 '19

Done, also feels way less hacky and doesn't spin strings around:
play.rust-lang.org/?version=stable...

Erick Hagstrom • Dec 4 '19 • Edited

I'm learning clojure, which isn't supported by Coderbyte :-(

Here's my clojure solution:

(ns challenge20191202.core
  (:gen-class)
  (:require [clojure.string :as str]))

(defn check-equivalent-keypresses [v]
  (defn parse-string [s]
    (vec (str/split s #",")))

  (defn apply-keypresses [v s]
    (if (= s "-B")
      (vec (drop-last v))
      (conj v s)))

  (let [[s1 s2] v
        v1 (str/split s1 #",")
        v2 (str/split s2 #",")]
    (= (reduce apply-keypresses '[] v1)
       (reduce apply-keypresses '[] v2))))

elisabethgross • Dec 4 '19 • Edited

One of the benefits of having a close relationship with our community is hearing what you all want and building it! Like this comment if you'd be interested in Coderbyte supporting clojure!

rascanoo • Dec 4 '19 • Edited

Using Regex:

const check = arr => {
  let regex = /[a-z]-B/g

  let [x, y] = arr.map(elm => {
    elm = elm.replace(/,/g, '');

    while (regex.test(elm)) {
      elm = elm.replace(regex, '');
    }

    return elm.replace(/-B/g, '');
  });

  return x === y;
}

console.log(check(["a,b,c,d", "a,b,c,c,-B,d"])); // true
console.log(check(["-B,-B,-B,c,c", "c,c"])); // true
console.log(check(["", "a,-B,-B,a,-B,a,b,c,c,c,d"])); // false
console.log(check(["a,a,a,-B,-B,c", "a,c"])); //true