CareerCup

Looked like a simplified version of java.util.concurrent.ArrayBlockingQueue which implements java.util.concurrent.BlockingQueue will suffice. Except there is a twist of multi-put that must be atomic.

import java.util.ArrayList;
import java.util.List;
import java.util.Objects;
import java.util.concurrent.ThreadLocalRandom;

public class ArrayMultiPutBlockingBoundedQueue<E> implements MultiPutBlockingBoundedQueue<E> {

    public ArrayMultiPutBlockingBoundedQueue() {
        elements = null;
        count = 0;
    }

    @Override
    public synchronized void init(int capacity) throws Exception {
        if (isInitialized()) { // already initialized
            throw new IllegalStateException();
        }
        if (capacity <= 0) {
            throw new IllegalArgumentException();
        }

        elements = new Object[capacity];
        count = 0;
        start = 0;
        notifyAll();
    }

    @Override
    public synchronized E get() throws Exception {
        if (!isInitialized()) {
            throw new IllegalStateException();
        }

        while (isEmpty()) {
            try {
                wait();
            } catch (final InterruptedException e) {
            }
        }

        assert (!isEmpty());
        final E val = dequeue();
        notifyAll();
        return val;
    }

    @Override
    public synchronized void put(E obj) throws Exception {
        Objects.requireNonNull(obj);

        if (!isInitialized()) {
            throw new IllegalStateException();
        }

        while (isFull()) {
            try {
                wait();
            } catch (final InterruptedException e) {
            }
        }

        assert (!isFull());
        enqueue(obj);
        notifyAll();
    }

    @Override
    public synchronized void multiput(List<E> objs) throws Exception {
        if (!isInitialized()) {
            throw new IllegalStateException();
        }
        if (objs.size() > elements.length) {
            throw new IllegalArgumentException();
        }

        while (!hasCapacity(objs.size())) {
            try {
                wait();
            } catch (final InterruptedException e) {
            }
        }

        assert (hasCapacity(objs.size()));
        for (final E obj : objs) {
            Objects.requireNonNull(obj);
            enqueue(obj);
        }
        notifyAll();
    }

    private synchronized boolean isInitialized() {
        return (elements != null);
    }

    private synchronized boolean isEmpty() {
        return (count == 0);
    }

    private synchronized boolean isFull() {
        return (count == elements.length);
    }

    private synchronized boolean hasCapacity(int n) {
        return (count + n <= elements.length);
    }

    private synchronized int end() {
        return (start + count) % elements.length;
    }

    private synchronized void enqueue(E o) {
        final int idx = end();
        elements[idx] = o;
        // System.out.format("enqueue msg\"%s\" at index \"%d\"%n",
        // o.toString(), idx); // DEBUG
        count++;
    }

    private synchronized E dequeue() {
        @SuppressWarnings("unchecked")
        final E val = (E) elements[start];
        elements[start] = null;
        // System.out.format("dequeue msg\"%s\" at index \"%d\"%n",
        // val.toString(), start); // DEBUG
        start = (start + 1) % elements.length;
        count--;
        return val;
    }

    private Object[] elements;
    private int count;
    private int start;
}

Here is an ad-hoc test driver to test (note that driver will hang at the end, because consumer threads will be blocked for producers to insert more elements, but producer threads would have ended):

public class TestDriver {

    private static class Producer implements Runnable {
        public Producer(ArrayMultiPutBlockingBoundedQueue<String> queue, int id) {
            this.queue = queue;
            this.id = id;
        }

        @Override
        public void run() {
            try {
                while (counter < COUNTER_MAX) {
                    if (ThreadLocalRandom.current().nextBoolean()) {
                        counter++;
                        final String msg = "Producer[" + id + "] : Message #: " + counter;
                        System.out.format("inserting: %s %n", msg); // DEBUG
                        queue.put(msg);
                    } else {
                        final int count = ThreadLocalRandom.current().nextInt(1, 4);
                        final List<String> msgs = new ArrayList<String>(count);
                        final String msgPrefix = "Producer[" + id + "] : Message #: ";
                        for (int i = 0; i < count; i++) {
                            counter++;
                            msgs.add(msgPrefix + counter);
                        }
                        System.out.format("inserting: %sfrom %d to %d %n", msgPrefix, counter - count + 1, counter); // DEBUG
                        queue.multiput(msgs);
                    }
                }
            } catch (final Exception e) {
                e.printStackTrace();
            }
        }

        private final ArrayMultiPutBlockingBoundedQueue<String> queue;
        private final int id;
        private int counter = 0;
        private static final int COUNTER_MAX = 32;
    }

    private static class Consumer implements Runnable {
        public Consumer(ArrayMultiPutBlockingBoundedQueue<String> queue, int id) {
            this.queue = queue;
            this.id = id;
        }

        @Override
        public void run() {
            try {
                while (true) {
                    final String msg = queue.get();
                    System.out.format("Consumer[%d] extracted msg: %s %n", id, msg); // DEBUG
                }
            } catch (final Exception e) {
                e.printStackTrace();
            }
        }

        private final ArrayMultiPutBlockingBoundedQueue<String> queue;
        private final int id;
    }

    public static void main(String[] args) throws Exception {
        int num = 0;
        final int MIN_THREADS = 3;
        final int MAX_THREAD = 8;
        final int QUEUE_CAPACITY = 32;

        if (args.length >= 0) {
            try {
                num = Integer.parseInt(args[0]);
            } catch (final Exception e) {
            }
        }
        if (num < MIN_THREADS)
            num = MIN_THREADS;
        if (num > MAX_THREAD)
            num = MAX_THREAD;

        final ArrayMultiPutBlockingBoundedQueue<String> queue = new ArrayMultiPutBlockingBoundedQueue<String>();
        queue.init(QUEUE_CAPACITY);
        Thread.sleep(1000);

        for (int i = 0; i < num; i++) {
            (new Thread(new Producer(queue, i))).start();
            (new Thread(new Consumer(queue, i))).start();
        }
    }

}

public class Number {
    private enum State {
        INIT, SIGN, INTEGER, DOT, FRACTION
    }

    public static boolean isNumber(String str) {
        // RegEx: [+-]? [0-9]+ (\.[0-9]+)?

        State state = State.INIT;
        for (final char ch : str.trim().toCharArray()) {
            switch (state) {
            case INIT:
                if (ch == '+' || ch == '-') {
                    state = State.SIGN;
                } else if (ch >= '0' && ch <= '9') {
                    state = State.INTEGER;
                } else {
                    return false;
                }
                break;
            case SIGN:
                if (ch >= '0' && ch <= '9') {
                    state = State.INTEGER;
                } else {
                    return false;
                }
                break;
            case INTEGER:
                if (ch == '.') {
                    state = State.DOT;
                } else if (ch < '0' || ch > '9') {
                    return false;
                }
                break;
            case DOT:
                if (ch >= '0' && ch <= '9') {
                    state = State.FRACTION;
                } else {
                    return false;
                }
                break;
            case FRACTION:
                if (ch < '0' || ch > '9') {
                    return false;
                }
                break;
            }
        }

        return (state == State.INTEGER || state == State.FRACTION);
    }

    public static void main(String[] args) {
        final String str[] = { "1", "10", "0123", "-20", "+40", ";", "10.", "-", "-23.45" };
        for (final String s : str) {
            System.out.println("Test: \"" + s + "\" is" + ((Number.isNumber(s)) ? " " : " not ") + "a number");
        }
    }

}

import java.util.Arrays;

public class TriangleTriplets {

    public static int countTriangleTriplets(int[] array) {
        int count = 0;

        Arrays.sort(array);

        for (int i = 0; i < array.length - 2; i++) {
            int k = i + 2;
            for (int j = i + 1; j < array.length - 1; j++) {
                int maxAllowed = array[i] + array[j];
                while (k < array.length && array[k] < maxAllowed) {
                    k++;
                }
                count += k - j - 1;
                // DEBUG
                //for (int l = j + 1; l < k; l++) {
                //    System.out.println("" + array[i] + ", " + array[j] + ", " + array[l]);
                //}
            }
        }

        return count;
    }

    public static void main(String[] args) {
        System.out.println("Total trangle triplets : " + countTriangleTriplets(new int[0]));

        System.out.println("Total trangle triplets : " + countTriangleTriplets(new int[] { 1, 1, 10000 }));

        System.out.println("Total trangle triplets : "
                + countTriangleTriplets(new int[] { 10, 21, 22, 100, 101, 200, 300 }));

        System.out.println("Total trangle triplets : " + countTriangleTriplets(new int[] { 9, 8, 10, 7 }));
    }

}

public class BinarySearch {

    public static int binarySearch(final int[] array, final int value) {
        return binarySearchHelper(array, value, 0, array.length - 1);
    }

    private static int binarySearchHelper(final int[] array,
            final int value, final int left, final int right) {
        if (left > right)
            return -1; // not found

        int mid = (left + right) / 2;

        if (value == array[mid]) {
            return mid;
        } else if (value < array[mid]) {
            return binarySearchHelper(array, value, left, mid - 1);
        } else { // (value > array[mid])
            return binarySearchHelper(array, value, mid + 1, right);
        }
    }

    public static int binarySearchShifted(final int[] array, final int value) {
        return binarySearchShiftedHelper(array, value, 0, array.length - 1);
    }

    private static int binarySearchShiftedHelper(final int[] array,
            final int value, final int left, final int right) {
        if (left > right)
            return -1; // not found

        int mid = (left + right) / 2;

        if (value == array[mid]) {
            return mid;
        } else if ((array[left] <= array[mid] && (array[left] <= value && value < array[mid]))
                || (array[mid] <= array[right] && !(array[mid] < value && value <= array[right]))) {
            return binarySearchShiftedHelper(array, value, left, mid - 1);
        } else {
            return binarySearchShiftedHelper(array, value, mid + 1, right);
        }
    }

    public static void main(String[] args) {
        test(6);
        test(7);
    }

    private static void test(int count) {
        int array[] = new int[count]; // {10, 20, ... 10*COUNT}
        for (int i=0; i<count; i++) {
            array[i] = 10 * (i+1);
        }

        int VALUE_MIN = 8;
        int VALUE_MAX = 10 * count + 2;

        printArray(array);
        for (int value = VALUE_MIN; value <= VALUE_MAX; value++) {
            int index = binarySearch(array, value);
            boolean pass = ((index >= 0 && (value % 10 == 0)) || (index < 0 && (value % 10 != 0)));
            if (!pass) {
                System.out
                        .println("*** FAIL ***"
                                + " value = "
                                + value
                                + ((index >= 0) ? (" index = " + index)
                                        : " Not Found"));
            }
        }
        System.out.println();

        for (int shift = 0; shift < count; shift++) {
            for (int i = 0; i < count; i++) {
                array[i] = 10 * (((shift + i) % count) + 1);
            }

            printArray(array);
            for (int value = VALUE_MIN; value <= VALUE_MAX; value++) {
                int index = binarySearchShifted(array, value);
                boolean pass = ((index >= 0 && (value % 10 == 0)) || (index < 0 && (value % 10 != 0)));
                if (!pass) {
                    System.out.println("*** FAIL ***"
                            + " value = "
                            + value
                            + ((index >= 0) ? (" index = " + index)
                                    : " Not Found"));
                }
            }
            System.out.println();
        }
    }

    private static void printArray(int[] array) {
        System.out.print("array[] = { ");
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i]);
            System.out.print(" ");
        }
        System.out.println("}");
    }

}

import java.util.EmptyStackException;
import java.util.Stack;

public class Calculator {

    public static void main(String[] args) {
        System.out.println("Value: " + evaluateReversePolish(args));
    }

    public static double evaluateReversePolish(String expression) {
        String[] tokens = expression.split("\\s");
        return evaluateReversePolish(tokens);
    }

    public static double evaluateReversePolish(String[] tokens) {
        Stack<Double> operands = new Stack<Double>();
        for (String token : tokens) {
            char ch = token.charAt(0);
            if (ch >= '0' && ch <= '9') {
                double operand = Double.parseDouble(token);
                operands.push(operand);
            } else { // Operator
                Operator op = Operator.parse(token);
                if (op == null) {
                    throw new RuntimeException(
                            "Malformed Expression: Unknown Operator " + token);
                }

                Double op1, op2;
                try {
                    op2 = operands.pop();
                    op1 = operands.pop();
                } catch (EmptyStackException e) {
                    throw new RuntimeException(
                            "Malformed Expression: Not enough operand for operator '"
                                    + op.getValue() + "'", e);
                }
                operands.push(op.apply(op1, op2));
            }
        }

        if (operands.size() != 1) {
            throw new RuntimeException(
                    "Malformed Expression: not enough opetrators");
        } else {
            return operands.pop();
        }
    }

    public enum Operator {
        PLUS("+") {
            @Override
            public double apply(double x, double y) {
                return x + y;
            }
        },
        MINUS("-") {
            @Override
            public double apply(double x, double y) {
                return x - y;
            }
        },
        MULT("*") {
            @Override
            public double apply(double x, double y) {
                return x * y;
            }
        },
        DIVIDE("/") {
            @Override
            public double apply(double x, double y) {
                return x / y;
            }
        };

        private final String value;

        public static Operator parse(String value) {
            if (value.length() != 1)
                return null;

            char ch = value.charAt(0);
            switch (ch) {
            case '+':
                return PLUS;
            case '-':
                return MINUS;
            case '*':
                return MULT;
            case '/':
                return DIVIDE;
            default:
                return null;
            }
        }

        private Operator(final String value) {
            this.value = value;
        }

        public String getValue() {
            return this.value;
        }

        @Override
        public String toString() {
            return this.name();
        }

        public abstract double apply(double x, double y);
    }
}