DEV Community

Cover image for A coding interview question asked at Google

A coding interview question asked at Google

elisabethgross on December 02, 2019

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...
Collapse
 
llcamara profile image
LLCamara

Small code review regarding the solution: I would refrain from using the term "pointers" - both on explanation and implementation - since the solution does not use actual pointers. Suggestion: rename to pivots (or indexes) instead.

Collapse
 
byrro profile image
Renato Byrro

Agree, most appropriate term would be index. Pointer reminds me of memory allocation.

Collapse
 
elisabethgross profile image
elisabethgross

Good point! :)

Collapse
 
aminnairi profile image
Amin

Not the fastest algorithm but this is what I came up with.

"use strict";

const normalize = (xs, x) => x === "-B" ? xs.slice(0, -1) : [...xs, x];

const checkEquivalentKeypresses = ([xs, ys]) =>
    xs.split(",").reduce(normalize, []).join(",")
    ===
    ys.split(",").reduce(normalize, []).join(",")

console.log(checkEquivalentKeypresses(["a,b,c,d", "a,b,c,c,-B,d"])); // true
console.log(checkEquivalentKeypresses(["-B,-B,-B,c,c", "c,c"])); // true
console.log(checkEquivalentKeypresses(["", "a,-B,-B,a,-B,a,b,c,c,c,d"])); // false
Collapse
 
elisabethgross profile image
elisabethgross

Good work!

Collapse
 
dmadden51 profile image
David Madden

I like this solution as it is very straight forward. Defining normalize was great going in.

Collapse
 
firee80 profile image
Firee80

This solution allows n-amount of inputs and uses Set to check all items are the same.

function checkEquivalentKeypresses(...keyPressLines) {
  const keyPressArrays = keyPressLines.map(keyPressLine => keyPressLine.split(','))
  const keyPressArraysWithoutBackspace = keyPressArrays.map(array =>
    array.reduce((result, letter) => letter === '-B' ? [...result].slice(0, -1) : [...result, letter], []))
  const keyPressLinesWithoutBackspace = keyPressArraysWithoutBackspace.map(array => array.join(''))  
  return keyPressLines.length > 1 ? (new Set(keyPressLinesWithoutBackspace)).size === 1 : false  
}

console.log(checkEquivalentKeypresses(...['a,b,c,d', 'a,b,c,c,-B,d'])) // true
console.log(checkEquivalentKeypresses(...['-B,-B,-B,c,c', 'c,c'])) // true
console.log(checkEquivalentKeypresses(...['', 'a,-B,-B,a,-B,a,b,c,c,c,d'])) // false
Collapse
 
firee80 profile image
Firee80

made the function to support also other data types of input..
changed naming and simplified return statement (new Set() is not ran if result.length > 1 fails first).

function checkEquivalentKeypresses(...lines) {
  const linesSplit = lines.some(line => typeof(line) !== 'string') ? [] : lines.map(line => line.split(','))
  const linesNoBackspace = linesSplit.map(lineArray =>
    lineArray.reduce((result, key) => key === '-B' ? [...result].slice(0, -1) : [...result, key], []))
  const result = linesNoBackspace.map(array => array.join(''))
  return result.length > 1 && (new Set(result)).size === 1  
}

console.log(checkEquivalentKeypresses(...['a,b,c,d', 'a,b,c,c,-B,d'])) // true
console.log(checkEquivalentKeypresses(...['-B,-B,-B,c,c', 'c,c'])) // true
console.log(checkEquivalentKeypresses(...['', 'a,-B,-B,a,-B,a,b,c,c,c,d'])) // false
console.log(checkEquivalentKeypresses(NaN,{})) // false
console.log(checkEquivalentKeypresses('a,b,c','a,b,c,d,-B')) // true
Collapse
 
dmadden51 profile image
David Madden

Doesn't Set remove duplicates?

Thread Thread
 
firee80 profile image
Firee80 • Edited

yes.. that is why end result size should be 1
[1,1,1] => [1]
the code checks first that the initial array has more than 1 input so
[1] => [1]
would fail on the first length check

Collapse
 
elisabethgross profile image
elisabethgross

Nice!

Collapse
 
sxync profile image
SaiKumar Immadi

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();
};
Collapse
 
erickhagstrom profile image
Erick Hagstrom • 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))))
Collapse
 
elisabethgross profile image
elisabethgross • 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!

Collapse
 
ferceg profile image
ferceg

I can't think of anything else other than a stack-based solution.

Collapse
 
bilyachenkooy profile image
Olexiy

You can try to go in backward direction whule comparing char by char without strings creation. In best case you will determine that strings are different at first iteration. At worst - iterate for max(n, m) times. And in any case you will only need constant extra memory allocation

Collapse
 
tails128 profile image
Tails128 • Edited

I think a stack-based solution is the most efficient and readable method, to be fair...

If we think about the complexity it should be around O(n)
(n (to compute first) + n (to compute second) + n(to go once over both))
Which is ofc not as good as the O(log(n)), but I am not sure there's a way to cut times.

Also we can do a sneaky trick such as

if(stack1.length !== stack2.length) {
  return false;
}

But... to be 100% correct, in order to determine if this is helpful or just added time for our average case we would need to know the context a bit more in depth.

Collapse
 
elisabethgross profile image
elisabethgross

Love the stack based approach!

Collapse
 
rascanoo profile image
rascanoo • 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
Collapse
 
hyftar profile image
Simon Landry

I'm not convinced this works with every case; You're missing some edge cases such as

['a,a,a,-B,-B,c', 'a,c']
Collapse
 
rascanoo profile image
rascanoo

Hi Simon,

You are correct, well spotted. I changed the solution to reflect your case and hopefully all cases :-)
Couldn't do it with one regex though :-(

Collapse
 
gabgab2003 profile image
DownloadPizza

This is actually awesome, it shouldn't take long to make this into something that works with multiple lines

Collapse
 
scott_yeatts profile image
Scott Yeatts • 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()));
Collapse
 
scott_yeatts profile image
Scott Yeatts • 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()));
Collapse
 
tpb261 profile image
Halfwit Genius

O(s+b) is good. s for small( to search for) and b for big (to search in). But I guess, using O(s log b) is a better approach, esp if b>>s. Instead of the linear search, going with a modified binary search that indicates whether the element being searched is outside the other array's bounds would be much faster. In that case, you can get rid of the condition of the smaller array being sorted.

Collapse
 
parkskier426 profile image
parkskier426 • Edited

Some Java code that:

  • Walks backward through the shortest string, jumping passed as much as possible to build a string.
  • Uses that string while walking back through the second and comparing.
  • Tires to fail as quickly as possible.

code screenshot

Collapse
 
kanchantyagi8 profile image
KT • Edited

I came up with this simple solution :D

function checkEquivalentKeypresses(strArr) {
var x = strArr[0].split(",");
var y = strArr[1].split(",");
function backSpace(arr) {
for(var i = 0; i <= arr.length - 1; i++) {
if(arr[i] === "-B") {
delete arr[i];
delete arr[i-1];
}
}
}
backSpace(x);
backSpace(y);
if(x.join("") === y.join("")) {
return true;
} else {
return false;
}
}
checkEquivalentKeypresses(["a,b,c,d", "a,b,c,c,-B,d"])
true
checkEquivalentKeypresses(["-B,-B,-B,c,c", "c,c"]);
true
checkEquivalentKeypresses(["-B,-B,-B,c,c", "c,c,e"]);
false
checkEquivalentKeypresses(["", "a,-B,-B,a,-B,a,b,c,c,c,d"]);
false

Collapse
 
karpour profile image
karpour

Got this recommended via Google and gave it a try :)

"use strict"

function checkEquivalentKeypresses(input) {
    // Reverse arrays for easier processing
    let a = input[0].split(",").reverse();
    let b = input[1].split(",").reverse();
    // Function to return index of the next not-deleted character
    let nextChar = (arr, idx) => {
        let bc = 0; // Backspace counter
        let i = idx; // Start index
        // Loop until a regular character is found with bc=0
        // If the character at idx is a regular character, the loop is skipped
        for (; i < arr.length && !(bc == 0 && arr[i].length == 1); i++) { 
            bc += (arr[i].length > 1 ? 1 : -1); 
        }
        // If bc is 0 and the character at i is defined and not a backspace, return that i
        // Otherwise it means the end of the array is reached, return undefined
        return (bc == 0 && arr[i] != undefined && arr[i].length == 1) ? i : undefined;
    }
    let nextcharA = nextChar(a, 0); // Get first character
    let nextcharB = nextChar(b, 0); // Get first character
    // Loop as long as the characters are the same
    for (let i = 0; !(nextcharA == undefined || nextcharB == undefined) && b[nextcharB] == a[nextcharA]; i++) {
        nextcharA = nextChar(a, nextcharA + 1);
        nextcharB = nextChar(b, nextcharB + 1);
        //console.log("a: " + a[nextcharA]);
        //console.log("b: " + b[nextcharB]);
    }
    // If both strings are equivalent, they will get set to undefined at the same point

    return nextcharA == undefined && nextcharB == undefined;
}
Collapse
 
elisabethgross profile image
elisabethgross

Nice! Glad you found us :)

Collapse
 
cbarrick profile image
Chris Barrick • Edited

Just compare starting from the end of the strings. When you see "-B" (possibly consecutively), you know you can skip stuff. O(n) time and O(1) space.

The fact that backspace is two characters and the keypresses are separated by commas is gross. It would be so much nicer (and realistic) for the input be an ASCII string with literal backspace characters.

Collapse
 
gabgab2003 profile image
DownloadPizza

Important thing when just skipping:
lets say we have "a,c,-B,-B" and we start from the back: we see a -B, so we skip the next character, now there is a c and then an a so we get ca (reversed), which is wrong. You need to count the -B s that are back to back and then remove as many "chars". also agree, real chars would be far better, also returning literal "true" and "false" hurts a lot

Collapse
 
gabgab2003 profile image
DownloadPizza • Edited

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

Collapse
 
gabgab2003 profile image
DownloadPizza

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

Collapse
 
gabgab2003 profile image
DownloadPizza

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

Collapse
 
opshack profile image
Pooria A

Thank you, these articles are really useful.

Collapse
 
elisabethgross profile image
elisabethgross

Enjoy!!

Collapse
 
farxelemon profile image
Ricardo Pedroso

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

Solution

Collapse
 
pentacular profile image
pentacular

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

Collapse
 
lgmf profile image
Luiz Guilherme

Collapse
 
williamjingo profile image
Jingo

Here is my solution