Google Interview Question
SDE1sCountry: United States
// 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
} //------------------------------------------------------------------
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;
}
}
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;
}
}
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;
}
}
# 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
#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() {
// your code goes here
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;
}
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);
}
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);
}
- tucker December 20, 2017