Google Interview Question
Backend DevelopersCountry: United States
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"));
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
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";
}
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')
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')
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);
}
The above implementation is without O(1) space.
Below implementation is with O(1) space
- Amit Bansal March 31, 2018