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

- tucker December 20, 2017 | Flag Reply
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

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

- milota@mindgrip.com December 18, 2017 | Flag Reply
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;
    }
}

- Anonymous December 18, 2017 | Flag Reply
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;
    }
}

- Madhu Sampangi Prakash December 18, 2017 | Flag Reply
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;
    }
}

- MADHU SAMPANGI PRAKASH December 18, 2017 | Flag Reply
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);
    }

}

- siva December 20, 2017 | Flag Reply
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);
    }
}

- siva December 20, 2017 | Flag Reply
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

- tucker.leavitt December 20, 2017 | Flag Reply
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() {
	// 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;
}

- Smodi2007 May 11, 2018 | Flag Reply
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);
    }

- Robb May 30, 2018 | Flag Reply
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);

}

- Robb May 30, 2018 | Flag Reply
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);
    }
}

- siva December 20, 2017 | 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