Google Interview Question Software Engineers
Country: United States
Interview Type: Phone Interview
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) {
}
}
}
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.
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>
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..
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("[{()()}]"));
}
}
/**
* 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("[{()()}]"));
}
}
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("[{()()}]"));
}
}
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
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[]) {
}
}
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;
}
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;
}
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();
}
(stack of stacks solution)
- dr.house December 14, 2017Use 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.