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));
        }
    }

}