Google Interview Question for Software Engineers


Country: United States
Interview Type: Phone Interview




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

(stack of stacks solution)

Use a stack but limit it's size to a permissible limit, say 4mb, or 4.19 million characters. Once the stack grows beyond this limit, serialize the entire stack onto disk and start a new stack in memory. If the current stack becomes empty, load the last serialized stack from disk into memory and keep working.

There is an edge case where stacks are written and read from disks after almost every operation. The problem is very similar to thrashing in virtual memory.

- dr.house December 14, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 4 vote

Read character by character from the file and use stack to push and pop parenthesis based on its order in the file. If an open parenthesis comes, add it to the stack, if its closed parenthesis comes, remove its open parenthesis from the stack. If a close parenthesis comes without the existence of an open parenthesis, it will be added to the stack, and it will be invalid example.

import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertTrue;

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.Collection;
import java.util.HashMap;
import java.util.Set;
import java.util.Stack;

import org.junit.Test;

/**
 * @author Abouads, Badawy
 *
 */
public class ParenthesisChecker {
	// Mapping Parenthesis
	HashMap<Character, Character> mappedSpecialCharacters = new HashMap<>();
	Set<Character> opens = null; // Open Parenthesis
	Collection<Character> closes = null; // Close Parenthesis
	Stack<Character> stringParenthesis = null;// Parenthesis inside string

	/**
	 * initialization
	 */
	public ParenthesisChecker() {
		// TODO Auto-generated constructor stub
		mappedSpecialCharacters.put('{', '}');
		mappedSpecialCharacters.put('(', ')');
		mappedSpecialCharacters.put('[', ']');
		opens = mappedSpecialCharacters.keySet();
		closes = mappedSpecialCharacters.values();
	}

	/**
	 * 
	 * @param filePath
	 * @return
	 * @throws IOException
	 */
	public boolean checkParenthesisInFile(final String filePath) throws IOException {
		stringParenthesis = new Stack<>();
		FileReader fileReader = null;
		boolean result = false;
		BufferedReader bufferedReader = null;
		try {
			fileReader = new FileReader(filePath);
			bufferedReader = new BufferedReader(fileReader);
			int r = 0;
			while ((r = bufferedReader.read()) != -1) {
				result = checkParenthesis((char) r); // Read character by character and check it
			}
		} catch (FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} catch (IOException ex) {
			ex.printStackTrace();
		} finally {
			fileReader.close();
			bufferedReader.close();
		}
		return result;
	}

	public boolean checkParenthesis(final char ch) throws NullPointerException {
		boolean passed = true;
		if (ch != ' ') {
			if (opens.contains(ch)) {
				stringParenthesis.push(ch);
			} else if (closes.contains(ch)) {
				if (!stringParenthesis.isEmpty() && ch == mappedSpecialCharacters.get(stringParenthesis.peek())) {
					stringParenthesis.pop();
				} else {
					stringParenthesis.push(ch);
					passed = false;
				}
			}
		}
		return passed && stringParenthesis.isEmpty();
	}

	/**
	 * Test code
	 */
	@Test
	public void testParenthesis() {
		try {
			assertFalse(checkParenthesisInFile("D://incorrectLargefile.txt"));
			assertTrue(checkParenthesisInFile("D://correctLargefile.txt"));
		} catch (IOException ex) {

		}
	}
}

- Badawy December 14, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

We can use a memory-mapped file for the stack.
Also, we can count repeating open brackets instead of adding each into the stack. E.g. for "((({[[" we can have the stack looking like this: "(3{[2". If the file contains a lot of repeating brackets, this should help a lot.

If it's more likely for the file to be wrong, we can do the first pass without a stack. Just counting open and close brackets of each type. If the first pass doesn't fail, we another pass, using a stack.

- Alex December 14, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

For cases like "({[}])" counts will be correct, but the sequence is invalid.

- Alex December 15, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@abouads I think if the only contains only parenthesis, it may not be possible to use stack as in worst case scenario half of the file is on stack, I am not sure if it is allowed

- tryingtolearn December 14, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

It depends on what we want to do. If we are just checking to see that there are no dangling pairs, then we can count the number of each brace, bracket, paren, etc from the open set. Then do the same for the closing set. Once we have their values, we can compare if the open and closing sets are equal. If they are not equal then it's bad data and we move on to the next phase. (Whatever that phase is)
Reading and writing from file wears down HDDs and SSDs. I would avoid it and try to stick with memory operations. Though, this all depends on the size of the file. But if it's too large to fit in memory, then I'd look to chunking or batch processing it in memory somehow and use read/writes as last resort. This depends on how often we are looking at the file too. If it happens often, then I would try and avoid it. If it happens every blue moon, then I might get lazy and just read write it. <shrugs>

- Maxim Stewart December 15, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Sorry if this is a duplicate but I clicked submit and all content disappeared but nothing seemed to get posted. I hope this isn't repeated but I see no indication or my post so think I'll be OK. Anyway, on to the post:

It depends on what we want to do. If we are just checking to see that there are no dangling pairs, then we can count the number of each brace, bracket, paren, etc from the open set. Then do the same for the closing set. Once we have their values, we can compare if the open and closing sets are equal. If they are not equal then it's bad data and we move on to the next phase. (Whatever that phase is)
Reading and writing from file wears down HDDs and SSDs. I would avoid it and try to stick with memory operations. Though, this all depends on the size of the file. But if it's too large to fit in memory, then I'd look to chunking or batch processing it in memory somehow and use read/writes as last resort..

- Maxim Stewart December 15, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think this is a map-reduce problem. you can simply count or build some sort of reduced stack in reducer process

- smurugu December 15, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.Stack;

/**
* Created by zviad on 12/11/17.
*/
public class Brackets {

public int solution(String S) {
Stack<Character> bracketStack = new Stack<>();
int br1 = 0, br2 = 0, br3 = 0;
for (int i = 0; i < S.length(); i++) {
if (S.charAt(i) == '{' || S.charAt(i) == '(' || S.charAt(i) == '[') {
bracketStack.push(S.charAt(i));
} else {
if (S.charAt(i) == ')') {
if (bracketStack.size() == 0 || '(' != bracketStack.pop()) {
return 0;
}
}
if (S.charAt(i) == ']') {
if (bracketStack.size() == 0 || '[' != bracketStack.pop()) {
return 0;
}
}
if (S.charAt(i) == '}') {
if (bracketStack.size() == 0 || '{' != bracketStack.pop()) {
return 0;
}
}
}
}
if(bracketStack.size()>0){
return 0;
}else {
return 1;
}
}


public static void main(String[] argv) {
Brackets brackets = new Brackets();
System.out.println(brackets.solution("[{()()}]"));

}

}

- Anonymous December 15, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/**
* Created by zviad on 12/11/17.
*/
public class Brackets {

public int solution(String S) {
Stack<Character> bracketStack = new Stack<>();
int br1 = 0, br2 = 0, br3 = 0;
for (int i = 0; i < S.length(); i++) {
if (S.charAt(i) == '{' || S.charAt(i) == '(' || S.charAt(i) == '[') {
bracketStack.push(S.charAt(i));
} else {
if (S.charAt(i) == ')') {
if (bracketStack.size() == 0 || '(' != bracketStack.pop()) {
return 0;
}
}
if (S.charAt(i) == ']') {
if (bracketStack.size() == 0 || '[' != bracketStack.pop()) {
return 0;
}
}
if (S.charAt(i) == '}') {
if (bracketStack.size() == 0 || '{' != bracketStack.pop()) {
return 0;
}
}
}
}
if(bracketStack.size()>0){
return 0;
}else {
return 1;
}
}


public static void main(String[] argv) {
Brackets brackets = new Brackets();
System.out.println(brackets.solution("[{()()}]"));

}

}

- {{{ and }}} December 15, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.Stack;

/**
* Created by zviad on 12/11/17.
*/
public class Brackets {

public int solution(String S) {
Stack<Character> bracketStack = new Stack<>();
int br1 = 0, br2 = 0, br3 = 0;
for (int i = 0; i < S.length(); i++) {
if (S.charAt(i) == '{' || S.charAt(i) == '(' || S.charAt(i) == '[') {
bracketStack.push(S.charAt(i));
} else {
if (S.charAt(i) == ')') {
if (bracketStack.size() == 0 || '(' != bracketStack.pop()) {
return 0;
}
}
if (S.charAt(i) == ']') {
if (bracketStack.size() == 0 || '[' != bracketStack.pop()) {
return 0;
}
}
if (S.charAt(i) == '}') {
if (bracketStack.size() == 0 || '{' != bracketStack.pop()) {
return 0;
}
}
}
}
if(bracketStack.size()>0){
return 0;
}else {
return 1;
}
}


public static void main(String[] argv) {
Brackets brackets = new Brackets();
System.out.println(brackets.solution("[{()()}]"));

}

}

- zvnemsadze December 15, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Purely an algorithmic approach:
2 stacks: one for forward->back, one for reverse order.
Open two read-only versions of the file.
Move one file pointer to the last character.
Moving in both directions, inward, perform the described algorithm, an once the file pointers converge, check for balance in the remaining stack contents.

--my take

- hiten December 15, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I have a solution for this. We can use only files without loading input file into the memory or modifying it. See below example, I used the existing file without any changes, and I created a temp file for insertion/deletion process.
Algorithm is working as the following:
- If an open parenthesis comes, insert it to the file
- if a close parenthesis comes; check it with the latest one in the temp file. If they are match, delete its open from the temp file, otherwise, the file will be invalid and break.
- After completing this, temp file will be checked. If it has any open or close parenthesis, then this file is invalid file, otherwise, it will be valid file.

I hope the code to come in a good format.

package com.careercup;

import static org.junit.Assert.*;
import java.io.File;
import java.io.IOException;
import java.io.RandomAccessFile;
import java.util.Collection;
import java.util.HashMap;
import java.util.Set;
import org.junit.Test;

/**
 * @author Abouads, Badawy
 *
 */
public class CheckParenthesesInFile {
	/**
	 * Arrays for Parentheses
	 */
	HashMap<Character, Character> mappedSpecialCharacters = new HashMap<>();
	Collection<Character> opens = null; // Open Parenthesis
	Set<Character> closes = null; // Close Parenthesis

	/**
	 * Initialization of Parentheses arrays
	 */

	public CheckParenthesesInFile() {
		mappedSpecialCharacters.put('}', '{');
		mappedSpecialCharacters.put(')', '(');
		mappedSpecialCharacters.put(']', '[');
		closes = mappedSpecialCharacters.keySet();
		opens = mappedSpecialCharacters.values();

	}

	public boolean check(String filePath) throws IOException {
		File file = new File(filePath);
		RandomAccessFile current = new RandomAccessFile(file, "r");
		// System.out.println(file.);
		File tempFile = new File(file.getParent() + "//output.temp");
		tempFile.deleteOnExit();
		RandomAccessFile temp = new RandomAccessFile(tempFile, "rw");

		long mainFilePointer = 0;
		long tempFilePointer = 0;
		boolean isValid = true;
		while ((mainFilePointer = current.read()) != -1) {
			char currentCharacter = (char) mainFilePointer;
			if (opens.contains(currentCharacter)) {
				temp.seek(tempFilePointer);
				temp.write(currentCharacter);
				tempFilePointer++;
			} else if (closes.contains(currentCharacter)) {
				tempFilePointer--;
				if (tempFilePointer >= 0) {
					temp.seek(tempFilePointer);
					char lastChar = (char) temp.read();
					if (mappedSpecialCharacters.get(currentCharacter) == lastChar) {
						temp.seek(tempFilePointer);
						temp.write(' ');
					} else {
						isValid = false;
						break;
					}
				} else {
					isValid = false;
					break;
				}

			}
		}
		current.close();
		return isThereParenthesesInFile(temp) && isValid;
	}

	/**
	 * Check if the file has any open Parentheses or any close Parentheses
	 * 
	 * @param tempFile
	 * @return
	 * @throws IOException
	 */
	private boolean isThereParenthesesInFile(final RandomAccessFile file) throws IOException {
		file.seek(0);
		int read = 0;
		boolean isValid = true;
		while ((read = file.read()) != -1) {
			char ch = (char) read;
			if (opens.contains(ch) || closes.contains(ch)) {
				isValid = false;
				break;
			}
		}
		file.close();
		return isValid;
	}

	@Test
	public void testParenthesis() {
		try {
			// check valid files
			assertTrue(check("validateFiles/correctLargefile1.txt")); // file contains [{()()}]
			assertTrue(check("validateFiles//correctLargefile2.txt")); // file contains [{(32)(44)565}23232][]{}()
			assertTrue(check("validateFiles//correctLargefile3.txt")); // file contains this java class inside it, with valid comments in testParenthesis method
			assertTrue(check("validateFiles//correctLargefile4.txt")); // file contains (){}[]{ { { } } } [()[]]
			
			// invalid files
			assertFalse(check("validateFiles//incorrectLargefile1.txt"));// file contains [{()()}[
			assertFalse(check("validateFiles//incorrectLargefile2.txt"));// file contains [{()()}][{(}()}]
			assertFalse(check("validateFiles//incorrectLargefile3.txt")); // file contains this java class inside it, with invalid comments in testParenthesis method
		} catch (IOException ex) {
			ex.printStackTrace();
		}
	}
	public static void main(String args[]) {
		
	}
}

- Badawy December 18, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

We need to know previous order of opening parentheses, and stack is a good solution for this. What we can do is we can create a serializable stack which can read from disk if items empty and writes to disk if current items exceeds the memory. This is a single machine solution but can handle infinite size of input. With serializable stack we can abstract scalability from our business logic. Solution to our problem is below:

Assumption to have (or implement if requested) three generic classes. Compressor, StreamReaderWriter and Serializable stack.

SerializableStack has following methods, top(), size(), push(), pop(). It receives dependency Compressor and StreamReaderWriter. It reads from given stream instance if current buffer is empty or writes to given stream instance if current buffer exceeds our given memory limit. This stack has list of integers and each integer holds more than one character information. This integers have meaning by support of compressor instance, it tells how many bits assigned per character and what is also encoded/decoded char/integer.

Compressor has following methods, compress(), decompress(), getBitSize(), getMask(). What compressor does, it inflates/deflates given input, for our specific case compressor makes following; compression key(binary): value(char) (ie, 00: {, 01: (, 10: [) and decompression key(char): value(binary) (ie, {: 00, (:01, [:10).

StreamReaderWriter, has << and >> operator overloads. This is abstracted, the reason is if we want to read/write from another location then local disk, we can easily override this instance and make our code work. As an example if we want to perform on diskless machines to abstract disk reliability problems.

For more testability and future expansion we can pass Compressor, FileReaderWriter and SerializableStack instances as parameter to our validParanthesis function. We can implement them from interface, this will help us to mock and test the logic with unit tests.

bool validParanthesis(stringstream &sin) {
        Compressor comp({'{', '[', '('}); // char set to compress/decompress
        StreamReaderWriter srw("tmpFile");
        SerializableStack s(comp, srw, 1024); // compressor, stream reader/writer, memory limit
        char c;
        
        while(sin >> c) {
            if(c == '{' || c == '[' || c == '(') {
                s.push(c);
            } else if(c == '}' || c == ']' || c == ')' ) {
                if(s.size() == 0 || (c == '}' && s.top() != '{') || (c == ']' && s.top() != '[') || (c == ')' && s.top() != '('))
                    return false;
                s.pop();
            }
        }
        
        return s.size() == 0;
    }

- yasinh January 29, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Also we can abstract the code from parentheses as well, this way our code can work on different combinations of parenthesis (ie, only (), or [], or multiple {}[]())

bool validParanthesis(stringstream &sin, const unordered_map<char, char> &openParanthesis) {
        Compressor comp({'{', '[', '('}); // char set to compress/decompress
        StreamReaderWriter srw("tmpFile");
        SerializableStack s(comp, srw, 1024); // compressor, stream reader/writer, memory limit
        char c;
        unordered_map<char, char> closeParanthesis;

        for(auto p: openParanthesis) {
            closeParanthesis[p.second] = p.first;
        }
        
        while(sin >> c) {
            if(openParanthesis.count(c)) {
                s.push(c);
            } else if(closeParanthesis.count(c)) {
                if(s.size() == 0 || s.top() != closeParanthesis[c])
                    return false;
                s.pop();
            }
        }
        
        return s.size() == 0;
    }

- yasinh January 29, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

A cleaner implementation:

private boolean isValidParenthesesInLargeFile(String filePath) throws IOException {
        FileReader fileReader = null;
        BufferedReader bufferedReader = null;

        HashMap<Character, Character> cache = new HashMap<>();
        cache.put('(', ')');
        cache.put('{', '}');
        cache.put('[', ']');

        Stack<Character> stack = new Stack<>();

        fileReader = new FileReader(filePath);
        bufferedReader = new BufferedReader(fileReader);

        int r;
        while ((r = bufferedReader.read()) != -1) {
            char ch = (char) r;
            if (cache.containsKey(ch)) {
                stack.push(ch);
            }
            else if (cache.containsValue(ch)) {
                char tmp = stack.pop();
                if (ch != cache.get(tmp)) {
                    return false;
                }
            }
        }

        return cache.isEmpty();
    }

- Hugh May 29, 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