Google Interview Question for Backend Developers


Country: United States




Comment hidden because of low score. Click to expand.
0
of 0 vote

I present my solution to this problem below. I assume that backslash+b represents backspace and backslash+c represents the caps lock. The hardest part about this problem is a shit ton of edge cases. I use python's pop() function to modify the list in place since the problem states to solve it in O(1) SC.

Other than that, the main idea is to keep track of two pointers, current and next. If it is backspace, carefully remove the escape characters and the previous character to be deleted. If it is caps lock, carefully remove the escape characters and modify the next+1 pointer to be uppercase.

Solution:

def isValid(inputString):
  # There can't be a single backslash character as the string
  if len(inputString) == 1 and inputString[0] == '\\':
    return False
  # Backspace can't occur at beginning of a string
  if len(inputString) >= 2 and inputString[0] == '\\' and inputString[1] == 'b':
    return False
  # You can't have just a caps lock character in your string
  if len(inputString) == 2 and inputString[0] == '\\' and inputString[1] == 'c':
    return False
  # Can't have just a caps lock string at the end
  if len(inputString) >= 2 and inputString[-2] == '\\' and inputString[-1] == 'c':
    return False

  for i in range(len(inputString)-3):
    temp = inputString[i:i+4]
    # Caps lock can't be immediately followed by backspace
    if temp[0:2] == r'\c' and temp[2:4] == r'\b':
      return False

  return True


def compareStrings(specialString, secondString):
  specialString = list(specialString)
  if not isValid(specialString):
    print('*** Invalid input string. Characters are not properly escaped! ***')
    return False

  curr = 0
  next = 1
  while curr < len(specialString) - 1:
    if specialString[curr] == '\\' and specialString[next] == 'c':
      specialString[next+1] = specialString[next+1].upper()
      specialString.pop(next)
      specialString.pop(curr)

    if specialString[curr] == '\\' and specialString[next] == 'b':
      specialString.pop(next)
      specialString.pop(curr)
      curr = curr - 1
      specialString.pop(curr)
    else:
      curr = curr + 1
    next = curr + 1
  return ''.join(specialString) == secondString

print(compareStrings('abc\\b', 'ab')) # True
print(compareStrings('abc\\bxy\cz', 'abxyZ')) # True
print(compareStrings('a\\ba', 'a')) # True
print(compareStrings('a\\b\cb', 'B')) # True
print(compareStrings('abc\ca', 'abcA')) # True
print(compareStrings('a\\b', '')) # True
print(compareStrings('\cz', 'Z')) # True

- prudent_programmer March 03, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

If it's ok to destroy the input, we can do one pass backward, counting backspaces and replacing the chars which will be removed by 0, another pass forward, tracking state of the CapsLock and replacing chars with upper case when needed, and the final pass, comparing non-zeroed non-slashed chars.

If it's not ok to destroy the input, my idea is to find the next characters which will not be removed and compare them. Space is O(1), but time is O(N^2):

#include <iostream>
#include <string>

using namespace std;

int GetNext(string const &s, int idx, bool &caps)
{
    for (int i = idx + 1; i < s.size(); ++i) {
        if (s[i] == '\\') {
            if (s[i + 1] == 'c') {
                caps = !caps;
            }
            ++i;
        } else {
            int chars_count = 0;
            int bs_count = 0;
            bool char_will_be_removed = false;
            for (int j = i; j < s.size() && !char_will_be_removed; ++j) {
                if (s[j] == '\\') {
                    if (s[j + 1] == 'b') {
                        if (++bs_count >= chars_count) {
                            char_will_be_removed = true;
                        }
                    }
                    ++j;
                } else {
                    ++chars_count;
                }
            }
            if (!char_will_be_removed) {
                return i;
            }
        }
    }
    return -1;
}

bool Compare(string const &s1, string const &s2)
{
    bool caps1 = false;
    bool caps2 = false;
    int i = -1;
    int j = -1;
    while (true) {
        i = GetNext(s1, i, caps1);
        j = GetNext(s2, j, caps2);
        if ((i == -1) && (j == -1)) {
            return true;
        }
        if ((i == -1) || (j == -1)) {
            return false;
        }
        char c1 = caps1 ? toupper(s1[i]) : s1[i];
        char c2 = caps2 ? toupper(s2[j]) : s2[j];
        if (c1 != c2) {
            return false;
        }
    }
}

int main()
{
    cout << Compare("Abc\\b\\bt", "\\caef\\b\\c\\bt") << "\n";
}

- Alex March 04, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Javascript Implementation -

function match(str, pattern){
  let BACKSLASH = false;
  let CAPSLOCK = false; 
  let stack = [];
  
  str.split('').forEach((char, index) => {
    if(char === "\\"){
      BACKSLASH = !BACKSLASH; 
    }else{
      if(BACKSLASH && char === 'b'){
        stack.pop();
        BACKSLASH = !BACKSLASH;
      }
      else if(BACKSLASH && char === 'c'){
        CAPSLOCK = !CAPSLOCK;
        BACKSLASH = !BACKSLASH;
      }
      else{
        stack.push(CAPSLOCK ? char.toUpperCase() : char);
      }  
    }
  });
  return stack.join('') === pattern;
}



console.log(match("abc\\b", "ab"));
console.log(match("abc\\ca", "abcA"));
console.log(match("abc\\bde\\cfd", "abdeFD"));
console.log(match("\\ba", "a"));
console.log(match("abc\\cde\\cfd", "abcDEfd"));
console.log(match("a\\ba", "a"));
console.log(match("a\\b\\cb", "B"));
console.log(match("a\\b", ""));
console.log(match("\\cz", "Z"));
console.log(match("Abc\\b\\bt", "At"));
console.log(match("\\caef\\b\\c\\bt", "At"));

- Amit Bansal March 31, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The above implementation is without O(1) space.

Below implementation is with O(1) space

function match(str, pattern){
  let CAPSLOCK = false; 
  
  let matchRec = (str, left, right) => {
    if(left > right){
      return str;
    }else{
      let char = str[left];
      if(char === "\\" && str[left+1] === 'b'){ //Backslash case
        str = str.substring(0, left - 1) + str.substring(left+2); 
        left--;
      }else if(char === "\\" && str[left+1] === 'c'){
        CAPSLOCK = !CAPSLOCK;
        str = str.substring(0, left) + str.substring(left+2); 
      }else{
        if(CAPSLOCK){
          str = str.substring(0, left) + str.charAt(left).toUpperCase() + str.substring(left+1);    
        }
        left++;
      }
      return matchRec(str, left, str.length - 1);
    }
  };
  console.log("str '" +str + "' and pattern '" + pattern +"' matches ==> " );
  str = matchRec(str, 0, str.length - 1);
  return str === pattern;
}

console.log(match("abc\\b", "ab"));
console.log(match("abc\\ca", "abcA"));
console.log(match("abc\\bde\\cfd", "abdeFD"));
console.log(match("\\ba", "a"));
console.log(match("abc\\cde\\cfd", "abcDEfd"));
console.log(match("a\\ba", "a"));
console.log(match("a\\b\\cb", "B"));
console.log(match("a\\b", ""));
console.log(match("\\cz", "Z"));
console.log(match("Abc\\b\\bt", "At"));
console.log(match("\\caef\\b\\c\\bt", "At"));
console.log(match("\\ca", "A"));

- Amit Bansal March 31, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def compare_strings_with_escape_characters(s1: str, s2: str) -> bool:
bs, cl = ['\\', 'b'], ['\\', 'c']
s1, s2 = list(s1), list(s2)
if s1[:2] == bs: s1 = s1[2:]
if s1[-2:] == cl: s1 = s1[:-2]
for i in range(len(s1) - 3):
if s1[i:i+2] == cl:
s1.pop(i)
s1.pop(i)
s1[i] = s1[i].upper()
if s1[i+1:i+3] == bs:
s1.pop(i)
s1.pop(i)
s1.pop(i)
return s1 == s2


if __name__ == '__main__':
assert compare_strings_with_escape_characters(r'fooo\bBA\cr', 'fooBAR')
assert compare_strings_with_escape_characters(r'\bfoo', 'foo')
assert compare_strings_with_escape_characters(r'foo\c', 'foo')

- python April 10, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def compare_strings_with_escape_characters(s1: str, s2: str) -> bool:
    bs, cl = ['\\', 'b'], ['\\', 'c']
    s1, s2 = list(s1), list(s2)
    if s1[:2] == bs: s1 = s1[2:]
    if s1[-2:] == cl: s1 = s1[:-2]
    for i in range(len(s1) - 3):
        if s1[i:i+2] == cl:
            s1.pop(i)
            s1.pop(i)
            s1[i] = s1[i].upper()
        if s1[i+1:i+3] == bs:
            s1.pop(i)
            s1.pop(i)
            s1.pop(i)
    return s1 == s2


if __name__ == '__main__':
    assert compare_strings_with_escape_characters(r'fooo\bBA\cr', 'fooBAR')
    assert compare_strings_with_escape_characters(r'\bfoo', 'foo')
    assert compare_strings_with_escape_characters(r'foo\c', 'foo')

- python April 10, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

private static boolean isStringsSimilar(String longStr, String shortStr)
{
int longStrIndex = longStr.length()-1;
int shortStrIndex = shortStr.length()-1;


while(longStrIndex >=0 && shortStrIndex >=0)
{
if(longStrIndex > 0 && longStr.charAt(longStrIndex) == 'b'
&& longStr.charAt(longStrIndex - 1) == new Character('\\'))
{
longStrIndex = longStrIndex -3;
continue;
}
else if(longStrIndex > 1 && longStr.charAt(longStrIndex -1) == 'c'
&& longStr.charAt(longStrIndex -2) == new Character('\\'))
{
if(Character.toUpperCase(longStr.charAt(longStrIndex)) != shortStr.charAt(shortStrIndex))
{
return false;
}

longStrIndex = longStrIndex -3;
}
else
{
if(longStr.charAt(longStrIndex) != shortStr.charAt(shortStrIndex))
{
return false;
}
longStrIndex--;
}
shortStrIndex--;
}

return (longStrIndex < 0 && shortStrIndex < 0);
}

- mayankjaiho8 May 30, 2018 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More