Algorithms
Algorithms
Check for balanced parentheses
Use a stack to check for valid { ( [ ] } )
Push any opening { ( [ on the stack.
When you have the corresponding ] } )
Pop off the stack == { ( [
Parentheses are balanced
Java implementation
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.Map;
public final class BalancedParenthesis {
private static final Map<Character, Character> brackets = new HashMap<>();
static {
brackets.put('[', ']');
brackets.put('{', '}');
brackets.put('(', ')');
}
private static boolean isBalanced(String parenList) {
Deque<Character> stack = new ArrayDeque<>();
for (Character eachParen : parenList.toCharArray()) {
if (brackets.containsKey(eachParen)) {
stack.push(eachParen);
} else if (!eachParen.equals(brackets.get(stack.pop()))) {
return false;
}
}
return true;
}
public static void main(String[] args) {
System.out.println(isBalanced("{}([])"));
System.out.println(isBalanced("([}])"));
System.out.println(isBalanced("([])"));
System.out.println(isBalanced("()[]{}[][]"));
}
}
Python implemenation
paren_list = {'[': ']', '{': '}', '(': ')'}
def is_balanced(parens):
stack = []
for each in parens:
if each in paren_list:
stack.append(each)
elif each != paren_list.get(stack.pop()):
return False
return True
def main():
print is_balanced("{}([])")
print is_balanced("([}])")
print is_balanced("{}([])")
print is_balanced("([])")
if __name__ == '__main__':
main()
Check for duplicate char in string
Use the int value for a char to “mark” it in a boolean array.
If already set (to true), flag as duplicate, return false.
package com.chocksaway.interview;
public class DuplicateCharacter {
private static final int ASCII_SIZE = 128;
private static boolean characterUnique(String str) {
// 128 char ascii table
if (str.length() > ASCII_SIZE) {
return false;
}
boolean[] ascii_char_set = new boolean[ASCII_SIZE];
for (int i = 0; i < str.length(); i++) {
int val = str.charAt(i);
if (ascii_char_set[val]) {
return false;
}
ascii_char_set[val] = true;
}
return true;
}
public static void main(String[] args) {
String[] words = {"miles", "chocksaway", "apple", "avenue", "circus", "lane"};
for (String word : words) {
System.out.printf(word + ": %s\n", characterUnique(word));
}
}
}