VietMX Staff asked 4 years ago
The file cannot fit in the memory. How would you process the file and how would you store the intermediate results. Walk me through the entire algorithm.
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.
To deal with large files 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.
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.
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) {
}
}
}