## Google Interview Question for SDE1s

Country: United States

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

# Determines whether two strings s1 and s2 are equal,
# given that the strings may contain backspace characters
# does so with O(1) additional space and exactly one pass
# over the inputs.

BACKSPACE = '\b'

def str_cmp_backspace(s1, s2):
cursor = 0; # cursor: position of current non-backspace characters to compare between strings.
pointer1 = 0; pointer2 = 0; # pointer: current position in backspaced string.
# Each string needs its own pointer

N1 = len(s1); N2 = len(s2);
cannon_len1 = N1; cannon_len2 = N2; #cannon_len:
# length of the cannonical string, with backsapces expanded

num_diff = 0
while True:
if s1[pointer1] == BACKSPACE or s2[pointer2] == BACKSPACE:
# decrement the cursor and undo the previous compare
cursor -= 1;
if s1[cursor] != s2[cursor]:
num_diff -= 1
# decrement the cannonical lengths appropriately
cannon_len1 -= 2 if s1[pointer1] == BACKSPACE else 0
cannon_len2 -= 2 if s2[pointer2] == BACKSPACE else 0
else:

if s1[pointer1]  != s2[pointer2]:
num_diff += 1
cursor += 1

# increment the pointers, making sure we don't run off then end
pointer1 += 1; pointer2 += 1;
if pointer1 == N1 and pointer2 == N2:
break
if pointer1 == N1: pointer1 -= 1
if pointer2 == N2: pointer2 -= 1

return num_diff == 0 and cannon_len1 == cannon_len2

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

// Back_String_Comp.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>
#include <string>
using namespace std;

class Back_string_Itter
{
public:
Back_string_Itter(string &s)
{
data = &s;
index = s.size() - 1;
} //------------------------------------------------------------------

char pop()
{
if (index == -1)
{
return 0;
}
int back = 0;

while (true)
{
while ((*data)[index] == '<') // count back spaces
{
back++;
index--;
if (index == -1)
{
return 0;
}
}

do // drop letters
{
back--;
if (back == -1)
{
index--;
return (*data)[index + 1];
}

index--;
if (index == -1)
{
return 0;
}

} while ((*data)[index] != '<');
}
} //------------------------------------------------------------------

private:
string *data;
int index;

}; //------------------------------------------------------------------

bool comp(string &a, string &b)
{
Back_string_Itter i(a);
Back_string_Itter j(b);

while (true)
{
char x = i.pop();
char y = j.pop();

if (x != y)
{
return false;
}

if (x == 0 || y == 0)
{
if (x == y)
{
return true;
}
return false;
}
}
return false; // make the compiler happy
} //------------------------------------------------------------------

/*
int _tmain(int argc, _TCHAR* argv[])
{
string s = "EDC<B<<Z";
Back_string_Itter b(s);

while (true)
{
char c = b.pop();

while (c != 0)
{
cout << c;
c = b.pop();
}
}

return 0;
}*/ //------------------------------------------------------------------

int _tmain(int argc, _TCHAR* argv[])
{
cout << comp(string("EDC<B<<Z"), string("EZ")) << "\n";  // t
cout << comp(string("ED<C<B<<Z"), string("EZ")) << "\n"; // f
cout << comp(string("ABC"), string("EZ")) << "\n"; // f
cout << comp(string("ABC"), string("ABC")) << "\n"; // t
cout << comp(string("ABC"), string("<ABC")) << "\n"; // t
cout << comp(string("<ABC"), string("<ABC")) << "\n"; // t
cout << comp(string("<ABC"), string("ABC")) << "\n"; // t
cout << comp(string("Q<ABC"), string("ABC")) << "\n"; // t
cout << comp(string("Q<ABC"), string("ABC<")) << "\n"; // f

} //------------------------------------------------------------------

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

package com.google.test;

import java.util.Scanner;
import java.util.Stack;

public class BackSpace
{

public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);
String s1 = scan.nextLine();
String s2 = scan.nextLine();
char[] charArray1 = s1.toCharArray();
char[] charArray2 = s2.toCharArray();
Stack<Character> stack1 = new Stack<Character>();
Stack<Character> stack2 = new Stack<Character>();
char backspaceChar= '<';
for(int i =0;i<charArray1.length;i++)
{
if(charArray1[i] == backspaceChar)
{
if(!stack1.isEmpty()) stack1.pop();
}
else
{
stack1.push(charArray1[i]);
}

}
for(int i =0;i<charArray2.length;i++)
{
if(charArray2[i] == backspaceChar )
{
if(!stack2.isEmpty()) stack2.pop();
}
else
{
stack2.push(charArray2[i]);
}
}
System.out.println(compareStack(stack1,stack2));
scan.close();
}
public static boolean compareStack(Stack<Character> stack1,Stack<Character> stack2)
{
boolean result = true;
if(stack1.size() == stack2.size())
{
while(!stack1.isEmpty())
{
if(!stack1.pop().equals(stack2.pop()))
{
result = false;
break;
}
}
}
else
{
result = false;
}
return result;
}
}

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

package com.google.test;

import java.util.Scanner;
import java.util.Stack;

public class BackSpace
{

public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);
String s1 = scan.nextLine();
String s2 = scan.nextLine();
char[] charArray1 = s1.toCharArray();
char[] charArray2 = s2.toCharArray();
Stack<Character> stack1 = new Stack<Character>();
Stack<Character> stack2 = new Stack<Character>();
char backspaceChar= '<';
for(int i =0;i<charArray1.length;i++)
{
if(charArray1[i] == backspaceChar)
{
if(!stack1.isEmpty()) stack1.pop();
}
else
{
stack1.push(charArray1[i]);
}

}
for(int i =0;i<charArray2.length;i++)
{
if(charArray2[i] == backspaceChar )
{
if(!stack2.isEmpty()) stack2.pop();
}
else
{
stack2.push(charArray2[i]);
}
}
System.out.println(compareStack(stack1,stack2));
scan.close();
}
public static boolean compareStack(Stack<Character> stack1,Stack<Character> stack2)
{
boolean result = true;
if(stack1.size() == stack2.size())
{
while(!stack1.isEmpty())
{
if(!stack1.pop().equals(stack2.pop()))
{
result = false;
break;
}
}
}
else
{
result = false;
}
return result;
}
}

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

package com.google.test;

import java.util.Scanner;
import java.util.Stack;

public class BackSpace
{

public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);
String s1 = scan.nextLine();
String s2 = scan.nextLine();
char[] charArray1 = s1.toCharArray();
char[] charArray2 = s2.toCharArray();
Stack<Character> stack1 = new Stack<Character>();
Stack<Character> stack2 = new Stack<Character>();
char backspaceChar= '<';
for(int i =0;i<charArray1.length;i++)
{
if(charArray1[i] == backspaceChar)
{
if(!stack1.isEmpty()) stack1.pop();
}
else
{
stack1.push(charArray1[i]);
}

}
for(int i =0;i<charArray2.length;i++)
{
if(charArray2[i] == backspaceChar )
{
if(!stack2.isEmpty()) stack2.pop();
}
else
{
stack2.push(charArray2[i]);
}
}
System.out.println(compareStack(stack1,stack2));
scan.close();
}
public static boolean compareStack(Stack<Character> stack1,Stack<Character> stack2)
{
boolean result = true;
if(stack1.size() == stack2.size())
{
while(!stack1.isEmpty())
{
if(!stack1.pop().equals(stack2.pop()))
{
result = false;
break;
}
}
}
else
{
result = false;
}
return result;
}
}

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

public class AktanaTest {
public static void main(String[] args) {
String str1 = "a\bb c\\d\be\bf";
String str2 = "g\bh\bi\bj";

System.out.println(str1.split("\b").length ==  str2.split("\b").length);
}

}

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

public class AktanaTest {
public static void main(String[] args) {
String str1 = "a\bb c\\d\be\bf";
String str2 = "g\bh\bi\bj";

System.out.println(str1.split("\b").length ==  str2.split("\b").length);
}
}

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

# Determines whether two strings s1 and s2 are equal,
# given that the strings may contain backspace characters
# does so with O(1) additional space and exactly one pass
# over the inputs.

BACKSPACE = '\b'

def str_cmp_backspace(s1, s2):
cursor = 0; # cursor: position of current non-backspace characters to compare
pointer1 = 0; pointer2 = 0; # pointer: current position in backspaced string.
# Each string needs its own pointer

N1 = len(s1); N2 = len(s2);
cannon_len1 = N1; cannon_len2 = N2; #cannon_len:
# length of the cannonical string, with backsapces expanded

num_diff = 0
while True:
if s1[pointer1] == BACKSPACE or s2[pointer2] == BACKSPACE:
# decrement the cursor and undo the previous compare
cursor -= 1;
if s1[cursor] != s2[cursor]:
num_diff -= 1
# decrement the cannonical lengths appropriately
cannon_len1 -= 2 if s1[pointer1] == BACKSPACE else 0
cannon_len2 -= 2 if s2[pointer2] == BACKSPACE else 0
else:

if s1[pointer1]  != s2[pointer2]:
num_diff += 1
cursor += 1

# increment the pointers, making sure we don't run off then end
pointer1 += 1; pointer2 += 1;
if pointer1 == N1 and pointer2 == N2:
break
if pointer1 == N1: pointer1 -= 1
if pointer2 == N2: pointer2 -= 1

return num_diff == 0 and cannon_len1 == cannon_len2

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

#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;

bool comparestrwithX( char* str1, char* str2);

bool comparestrwithX( char* str1, char* str2) {

char curr1, curr2;
int delc1 = 0, delc2 = 0;
int len1, len2;
int i, j;

len1 = strlen(str1); len2 = strlen(str2);
i = len1 - 1; 	j = len2 - 1;

//main logic
while(i >= 0 && j >= 0) {

//calc current char for first str
while(1)
{
if(str1[i] != 'X')
{
curr1 = str1[i];
i--;
if(delc1 == 0)
break;
else
delc1--;
}
else
{
delc1++;
i--;

}
}

//calc current char for sec str
while(1)
{
if(str2[j] != 'X')
{
curr2 = str2[j];
j--;
if(delc2 == 0)
break;
else
delc2--;
}
else
{
delc2++;
j--;
}
}

//comparing
if(curr1 != curr2)
return false;

//do nothing if they are same and loop for next character.

}

if (i != j)  //ie one str has more char than other
return false;
else
return true;

}

int main() {
char A[20]= "abaab";
char B[20]= "ababbXXab";

bool ans;

ans = comparestrwithX(A, B);

if (ans)
printf("Yes they are same");
else
printf("No they are not same");

return 0;
}

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

public static int getIgnoredKeys(String subString) {
char BACKSPACE = '\b';
int BACK_CNT = 0;
for (int i = subString.length() - 1 ; i > 0; i--) {
if (subString.charAt(i) == BACKSPACE) {
BACK_CNT++;
} else {
break;
}
}
return BACK_CNT*2;
}
public static boolean isEqual(String a, String b) {
int aCursor = a.length();
int bCursor = b.length();
char BACKSPACE = '\b';
while (aCursor >= 0 || bCursor >= 0) {
char aLast = (a.length() > 0 && (aCursor - 1 >= 0)) ? a.charAt(aCursor - 1) : Character.MIN_VALUE;
char bLast = (b.length() > 0 && (bCursor - 1 >= 0)) ? b.charAt(bCursor - 1) : Character.MIN_VALUE;
if (aLast != bLast) {
if (aLast == BACKSPACE) {
aCursor = aCursor - getIgnoredKeys(a.substring(0, aCursor));
} else if (bLast == BACKSPACE) {
bCursor = bCursor - getIgnoredKeys(b.substring(0, bCursor));
} else {
return false;
}
} else if (aLast == Character.MIN_VALUE){
return true; // Both strings have reached their end
} else {
aCursor--;
bCursor--;
}
}

return (aCursor == 0 && bCursor == 0);
}

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

private static int getIgnoredKeys(String subString) {
char BACKSPACE = '\b';
int BACK_CNT = 0;
for (int i = subString.length() - 1 ; i > 0; i--) {
if (subString.charAt(i) == BACKSPACE) {
BACK_CNT++;
} else {
break;
}
}
return BACK_CNT*2;
}
public static boolean isEqual(String a, String b) {
int aCursor = a.length();
int bCursor = b.length();
char BACKSPACE = '\b';
while (aCursor >= 0 || bCursor >= 0) {
char aLast = (a.length() > 0 && (aCursor - 1 >= 0)) ? a.charAt(aCursor - 1) : Character.MIN_VALUE;
char bLast = (b.length() > 0 && (bCursor - 1 >= 0)) ? b.charAt(bCursor - 1) : Character.MIN_VALUE;
if (aLast != bLast) {
if (aLast == BACKSPACE) {
aCursor = aCursor - getIgnoredKeys(a.substring(0, aCursor));
} else if (bLast == BACKSPACE) {
bCursor = bCursor - getIgnoredKeys(b.substring(0, bCursor));
} else {
return false;
}
} else if (aLast == Character.MIN_VALUE){
return true; // Both strings have reached their end
} else {
aCursor--;
bCursor--;
}
}

return (aCursor == 0 && bCursor == 0);

}

Comment hidden because of low score. Click to expand.
-1
of 1 vote

public class Test {
public static void main(String[] args) {
String str1 = "a\bb c\\d\be\bf";
String str2 = "g\bh\bi\bj";

System.out.println(str1.split("\b").length ==  str2.split("\b").length);
}
}

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.

### 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.