CareerCup

not the best because it consumes O(mn) memory rather than only O(n).

@Justaguy

The Ideal solution is 25, not 24. And it passes through (0,0), (1,1), (2,2), (3,2).

There was a flaw in my code where I had transposed the coordinates of the value at each location. it should be map[j][i] and NOT map[i][j]. Try it again...

The DP approach PROVES it is the optimal solution.

TotalValue[i][j] = Max(TotalValue[i-1][j-1], TotalValue[i-1][j], TotalValue[i-1][j+1]) + Value[i][j]

In other words, this says, total value computed for any location in the map is equal to the maximum total value computed from the only valid predecessor total values plus the value that can be derived for this specific location. Then you just iterate over the final total values and select the largest

If the List<Integer> type being passed in is a LinkedList<Integer>, then all of your .get(int) operations are O(n) rather than O(1). Not a good approach.

Complexity analysis and memory usages within the code.

public final class ListUtils{
    private ListUtils(){
        //do nothing
    }

    //O(n + m) runtime and O(n + m) memory where n and m are the lengths of the source lists
    //Uses iterators to ensure that traversal of the Lists is of optimal speed.  If a List were a 
    //LinkedList, then the .get(int) would have a runtime complexity of O(n) by itself hence the 
    //need for iterators
    public static List<T extends Comparable> union(List<T extends Comparable> list1, List<T extends Comparable> list2){
        if(list1 == null){
            if(list2 == null){
                return null;
            }
            return list2;
        }
        if(list2 == null){
            return list1;
        }

        ArrayList<T> results = new ArrayList<T>(list1.size() + list2.size());
        Iterator<T> list1Iter = list1.iterator();
        Iterator<T> list2Iter = list2.iterator();
        T list1Obj = list1Iter.next();
        T list2Obj = list2Iter.next();
        while(list1Obj != null && list2Obj != null){
            if(list1Obj.compareTo(list2Obj) < 0){
                results.add(list1Obj);
                list1Obj = (list1Iter.hasNext()) ? list1Iter.next() : null;
            }
            else{
                results.add(list2Obj);
                list2Obj = (list2Iter.hasNext()) ? list2Iter.next() : null;
            }
        }
        while(list1Obj != null){
            results.add(list1Obj);
            list1Obj = (list1Iter.hasNext()) ? list1Iter.next() : null;
        }
        while(list2Obj != null){
            results.add(list2Obj);
            list2Obj = (list2Iter.hasNext()) ? list2Iter.next : null;
        }
        return results;
    }

    //O(min(n, m)) runtime complexity and O(min(n, m)) memory where n and m are the length of the lists
    //also uses Iterators for efficient traversal of the lists
    public static List<T extends Comparable> intersection(List<T> list1, List<T> list2){
        ArrayList<T> results = new ArrayList<T>();
        if(list1 == null || list2 == null){
            return results;
        }
        
        Iterator<T> list1Iter = list1.iterator();
        Iterator<T> list2Iter = list2.Iterator();
        T list1Obj = list1Iter.next();
        T list2Obj = list2Iter.next();
        while(list1Obj != null && list2Obj != null){
            int diff = list1Obj.compareTo(list2Obj);
            if(diff < 0){
                list1Obj = (list1Iter.hasNext()) ? list1Iter.next() : null;
            }
            else if(diff > 0){
                list2Obj = (list2Iter.hasNext()) ? list2Iter.next() : null;
            }
            else{
                results.add(list1Obj);
                list1Obj = (list1Iter.hasNext()) ? list1Iter.next() : null;
                list2Obj = (list2Iter.hasNext()) ? list2Iter.next() : null;
            }
        }
        return results;
    }

O(n * m) runtime and O(n) memory using dynamic programming:

public static int getBestPath(int[][] map){
    //handle simpler base cases
    if(map == null){
        throw new NullPointerException("\"map\" may not be null");
    }
    if(map.length == 0 || map[0].length == 0){
        return 0;
    }
    if(map.length[0] == 1){
        int sum = 0;
        for(int i = 0; i < map.length; i++){
            sum += map[i][0];
        }
        return sum;
    }

    //now compute the value of each path through the map
    //each position is the best predecessor of the 3 possible choices
    //plus the current position in the map
    //ie: working[j] = Max(subtotal[j-1], subtotal[j], subtotal[j+1]) + map[i][j]
    int[] working = new int[map.length];
    int[] subtotal = new int[map.length];
    int[] temp;
    for(int j = 0; j < subtotal.length; j++){
        subtotal[j] = map[j][0];
    }
    for(int i = 1; i < map.length; i++){
        for(int j = 0; j < map[0].length; j++){
            if(j == 0){
                working[j] = Math.max(subtotal[j], subtotal[j+1]) + map[j][i];
            }
            else if(j == map[0].length -1){
                working[j] = Math.max(subtotal[j], subtotal[j-1]) + map[j][i];
            }
            else{
                working[j] = Math.max(subtotal[j-1], Math.max(subtotal[j], subtotal[j+1])) + map[j][i];
            }
        }
        temp = subtotal;
        subtotal = working;
        working = temp;
    }
    
    //now pick the best score out of the final results
    int best = Integer.MIN_VALUE;
    for(int i : subtotal){
        if(i > best){
            best = i;
        }
    }
    return best;
}

Will it work on this?

1 1 1
1 0 1
1 0 1

O(n) with O(1) memory:

public static void numberCompression(int[] arr){
    if(arr == null){
        throw new NullPointerException();
    }
    if(arr.length == 0){
        return;
    }

    int lastNumber = arr[0];
    Integer rangeStart = lastNumber;
    StringBuilder output = new StringBuilder();

    for(int i = 1; i < arr.length; i++){
        if(rangeStart == null){
            rangeStart = arr[i];
        }
        else if(arr[i] -1 != lastNumber){
            printOutput(rangeStart, lastNumber);
            rangeStart = null;
        }
        lastNumber = arr[i];
    }
    if(rangeStart != null){
        printOutput(rangeStart, lastNumber);
    }
}

private static void printOutput(Integer rangeStart, int lastNumber){
    if(rangeStart != lastNumber){
        java.lang.System.out.println(rangeStart+" - "+lastNumber);
    }
    else{
        java.lang.System.out.println(rangeStart);
    }
}

Here's java with O(n^2) runtime complexity (not too bad since it visits each node at most 5 times) and O(n^2) memory:

public static int countIslands(int[][] map){
    if(map == null){
        throw new NullPointerException();
    }
    if(map.length == 0){
        return 0;
    }    

    boolean[][] checked = new boolean[map.length][map[0].length];
    int islandCount = 0;
    for(int i = 0; i < map.length; i++){
        for(int j = 0; j < map.length; j++){
            if(isIsland(map, checked, i, j)){
                islandCount++;
            }
        }
    }
    return islandCount;
}

private static boolean isIsland(int[][] map, boolean[][] checked, int i, int j){
    //check if this is an island
    boolean isIsland = map[i][j] == 1 && !checked[i][j];
    //now, mark this entire island as checked
    if(isIsland){
        Stack<int[]> unchecked = new Stack<int[]>();
        unchecked.push(new int[]{i, j});
        checked[i][j] = true;
        while(!unchecked.isEmpty()){
            int[] position = unchecked.pop();
            int iMax = i + 1 < map.length ? 1 : 0;
            int iMin = i > 0 ? -1 : 0;
            int jMax = j + 1 < map[0].length ? 1 : 0;
            int jMin = j > 0 ? -1 : 0;
            for(int iMod = i + iMin; iMod <= i + iMax; iMod++){
                for(int jMod = j + jMin; jMod <= j+ jMax; jMod++){
                    if(iMod == i && jMod == j){
                        continue;
                    }
                    
                    if(map[iMod][jMod] == 1 && !checked[iMod][jMod]){
                        checked[iMod][jMod] = true;
                        unchecked.add(new int[]{iMod, jMod});
                    }
                }
            }
        }
    }
    return isIsland;
}

not javascript, but O(n) runtime complexity and O(n) memory:

class TripData{
    String origin;
    String destination;

    public TripData(String origin, String destination){
        this.origin = origin;
        this.destination = destination;
    }
}

public static TripData getTripData(TripData[] tickets){
    if(tickets == null){
        throw new NullPointerException();
    }
    if(tickets.length == 0){
        return null;
    }

    //build implicit graph of the tickets
    HashMap<String, TripData> originToTripData = new HashMap<String, TripData>();
    HashMap<String, TripData> destinationToTripData = new HashMap<String, TripData>();
    for(TripData tripSegment : tickets){
        originToTripData.put(tripSegment.origin, tripSegment);
        destinationToTripData.put(tripSegment.destination, tripSegment);
    }

    //do dfs search from any point in the destination map to find the real origin
    TripData startPoint = tickets[0];
    String origin = null;
    while(startPoint != null){
        origin = startPoint.origin;
        startPoint = destinationToTripData.get(startPoint.origin);
    }
        
    //do dfs search from any point in the origin map to find the real destination
    startPoint = tickets[0];
    String destination = null;
    while(startPoint != null){
        destination = startPoint.destination;
        startPoint = originToTripData.get(startPoint.destination);
    }

    return new TripData(origin, destination);
}

O(n) complexity (I think. It's a hill climber so that's hard to really assess) with O(n) memory.

public static String processStrHillClimber(String str) {
        if (str == null) {
            throw new NullPointerException();
        }
        if (str.length() == 0) {
            return "";
        }

        ArrayList<Integer>[] charSets = buildCharSets(str);
        int[] selected = new int[26];

        boolean improved = false;
        String result = genString(charSets, selected);
        do {
            improved = false;
            for (int i = 0; i < 26; i++) {
                if (charSets[i].size() > 1) {
                    int orig = selected[i];
                    for (int j = charSets[i].size() - 1; j > -1; j--) {
                        selected[i] = j;
                        String check = genString(charSets, selected);
                        if (check.compareTo(result) < 0) {
                            result = check;
                            improved = true;
                            orig = j;
                        }
                    }
                    selected[i] = orig;
                }
            }

        }
        while (improved);
        return result;
    }

    private static String genString(ArrayList<Integer>[] charSets, int[] selected) {
        ArrayList<CharObj> charObjs = new ArrayList<CharObj>();
        for (int i = 0; i < 26; i++) {
            if (charSets[i].size() > 0) {
                charObjs.add(new CharObj(charSets[i].get(selected[i]), (char) ('a' + i)));
            }
        }

        Collections.sort(charObjs);

        StringBuilder builder = new StringBuilder();
        for (CharObj charObj : charObjs) {
            builder.append(charObj.c);
        }
        return builder.toString();
    }

    private static ArrayList<Integer>[] buildCharSets(String str) {
        ArrayList<Integer>[] charSets = new ArrayList[26];
        for (int i = 0; i < 26; i++) {
            charSets[i] = new ArrayList<Integer>();
        }
        for (int i = 0; i < str.length(); i++) {
            charSets[str.charAt(i) - 'a'].add(i);
        }
        return charSets;
    }

    private static class CharObj implements Comparable<CharObj> {

        int index;
        char c;

        CharObj(int index, char c) {
            this.index = index;
            this.c = c;
        }

        public int compareTo(CharObj obj) {
            return this.index - obj.index;
        }
    }

This is not O(1) memory. You are using recursion and that requires memory too.

Not O(1) memory. Recursion uses memory too.

O(nm) runtime complexity where n is the number of strings and m is the average size of the strings. O(nm) memory complexity too.

A quick way to determine if a string can be a palindrome is to:
1. Count the occurrences of each character in the string
2. Iterate from the 'a' to the 'z' counts. add half of the count of each character to the string. If the character has an odd count, remember it. If there were other characters with an odd count, then there isn't a palindrome so return null
3. If any odd characters, add it now
4. Iterate from the 'z' to the 'a' counts and add half the count of each character to the string
5. return the string

//If all palindromes couldn't be found, return null
public static String[] palindromify(String[] strs){
    if(strs == null){
        return null;
    }

    String[] results = new String[strs.length];
    for(int i = 0; i < strs.length; i++){
        int[] counts = genCount(strs[i]);
        StringBuilder builder = new StringBuilder();

        int middle = -1;        
        for(int j = 0; j < 26; j++){
            int count = counts[j];
            if(count % 2 == 1){
                if(middle > 0){
                    return null;
                }
                middle = j
            }
            count /= 2;
            counts[j] = count;
            for(int k = 0; k < count; k++){
                builder.append((char)('a'+j));
            }
        }

        if(middle >= 0){
            builder.append((char)('a'+middle));\
        }

        for(int j = 25; j >= 0; j--){
            int count = counts[j];
            for(int k = 0; k < count; k++){
                builder.append((char)('a'+j));
            }
        }
        results[i] = builder.toString();
    }
    return results;
}

private static int[] genCount(String str){
    int[] counts = new int[26];
    for(int i = 0; i < str.length(); i++){
        counts[str.charAt(i)-'a']++;
    }
    return counts;
}

This can be done in O(n) with O(1) space by doing the following (in java)

class Node{
    int data;
    Node left, right, nextRight;
}

public static void setupLevels(Node leftMost){
    Node lastOnLevel, nextOnLevel, firstOnLevel;
    //while still computing levels
    while(leftMost != null){
        //while there are still Nodes in the parent level
        while(leftMost != null){
            //if there is a new left child to consider
            nextOnLevel = leftMost.left;
            if(nextOnLevel != null){
                //if there is a previous child, attach the last child to the new one
                if(lastOnLevel != null){
                    lastOnLevel.nextRight = nextOnLevel;
                }
                lastOnLevel = nextOnLevel;
            }
            //capture the first non-null child
            if(lastOnLevel != null && firstOnLevel == null){
                firstOnLevel = lastOnLevel;
            }

            //if there is a new right child
            nextOnLevel = leftMost.right;
            if(nextOnLevel != null){
                //if there is a previous child, attach the last child to the new one
                if(lastOnLevel != null){
                   lastOnLevel.nextRight = nextOnLevel;
                }
                lastOnLevel = nextOnLevel;
            }
            //capture the first non-null child
            if(lastOnLevel != null && firstOnLevel == null){
               firstOnLevel = lastOnLevel;
            }
            
            //move to the next parent
            leftMost = leftMost.nextRight;
        }
        //prep for the next level
        leftMost = firstOnLevel;
        firstOnLevel = null;
        lastOnLevel = null;
    }
}

Not O(1) space as required

not O(1) space as required.

Since this is C, I'm using Java with the following redefinition.

O(n) runtime Complexity with roughly O(n) memory where m is the average number of children on each node.

class Node{
    ArrayList<Node> children;
    int val;
}

public static List<Node> get PostOrder(Node root){
    LinkedList<Node> results = new LinkedList<Node>();
    if(root == null){
        return results;
    }

    Stack<Node> unprocessed = new Stack<Node>();
    unprocessed.push(root);
    while(!unprocessed.isEmpty()){
        Node node = unprocessed.pop();
        results.addFirst(node);
        for(Node childNode : node.children){
            unprocessed.push(childNode);
        }
    }
    return results;
}

EDIT: The following was my first attempt. IT was recursive. I've since been told that 'iterative' means 'non-recursive'. Left this code for posterity

class Node{
    ArrayList<Node> children;
    int val;
}

public static ArrayList<Node> getPostOrder(Node root){
    ArrayList<Node> results = new ArrayList<Node>();
    if(root == null){
        return results;
    }

    for(Node child : root.children){
        results.addAll(getPostOrder(child));
    }
    results.add(root);
    
    return results;
}

In java. O(n) runtime complexity and O(t) memory where T is the wait time

public static int getRunTime(char[] tasks, in waitTime){
    if(tasks == null){
        throw new NullPointerException();
    }

    LinkedHashMap<Character, Integer> charToExecTime = new LinkedHashMap<Character, Integer>();
    int time = 0;
    for(char c : tasks){
        //compute the timing for each task
        Integer lastTime = charToExecTime.get(c);
        if(lastTime != null && lastTime + waitTime > time){
            time = lastTime + waitTime;
        }
        charToExecTime.put(c, time);
        time++;
        
        //clear out the unnecessary tasks
        ArrayList<Character> remove = new ArrayList<Character>();
        for(Entry<Character, Integer> entry : charToExecTime.entrySet()){
            if(entry.getValue() >= time){
                remove.add(entry.getValue());
            }
            else{
                break;
            }
        }
        for(Character c : remove){
            charToExecTime.remove(c);
        }
    }
    return time;
}

Just do it using the dynamic programming approach. O(n * T) complexity and O(T) memory where n is the number of tasks and T is the amount of time

public static int getMaxScore(int[] taskValue, int[] taskTime, int totalTime){
    int[] timeScore = new int[totalTime];
    int[] nextTimeScore = new int[totalTime];
    int[] temp;
    for(int i = 0; i < taskValue.length; i++){
        int taskTimeHere = taskTime[i];
        int taskValueHere = taskValue[i];
        for(int j = 0; j < totalTime; j++){
            if(taskTimeHere > j){
                int thisTask = taskValueHere + nextTimeScore[j + 1 - taskTimeHere];
                nextTimeScore[j] = Math.max(thisTask, timeScore[j]);
            }
            else{
                nextTimeScore[j] = timeScore[j];
            }
        }
        temp = nextTimeScore;
        nextTimeScore = timeScore;
        timeScore = temp;
    }
    return timeScore[totalTime -1];
}

O(n) Complexity solution (more specifically, it is O(26 + n + 26 log 26 + n 26 log 26) ) , using O(n) memory assuming ASCII characters:

public static String processStr(String str){
    if(str == null){
        throw new NullPointerException();
    }
    
    Stack<Integer>[] charStack = new Stack<Integer>[26];
    for(int i = 0; i < 26; i++){
        charStack[i] = new Stack<Integer>();
    }
    for(int i = 0; i < str.length; i++){
        charStack['a' - str.charAt(i)].add(i);
    }

    String result = genString(charStack, -1);
    for(int i = 0; i < 26; i++){
        String check = null;
        while((check = genString(charStack, i)) != null && check.compareTo(result) < 0){
            result = check;
            charStack[i].pop();
        }
    }
    return result;
}

private static String genString(Stack<Integer>[] charStack, int peek){
    if(charStack[peek].size() < 2){
        return null;
    }
    ArrayList<CharObj> charObjs = new ArrayList<CharObj>();
    for(int i = 0; i < 26; i++){
        if(i == peek){
            charObjs.add(new CharObj(charStack[i].get(1), (char)('a'+i));
        }
        else{
             if(charObjs.size() > 0){
                 charObjs.add(new CharObj(charStack[i].peek(), (char)('a'+i));
             }
        }
    }
    return genString(charObjs);
}

private static String genString(ArrayList<CharObj> charObjs){
    Collections.sort(charObjs);
    StringBuilder builder = new StringBuilder();
    for(CharObj charObj : charObjs){
        builder.append(charObj.c);
    }
    return builder.toString();
}

private static class CharObj implements Comparable<CharObj>{
    int index;
    char c;

    CharObj(int index, char c){
        this.index = index;
        this.c = c;
    }

    public int compareTo(CharObj obj){
        return this.index = obj.index;
    }
}

Complexity O(min(n+m)), memory O(1)

public static Collection<Integer> getCommon(int[] arr1, int[] arr2){
    if(arr1 == null || arr2 == null){
        throw new NullPointerException();
    }

    ArrayList<Integer> results = new ArrayList<Integer>();
    int arr1Index = 0;
    int arr2Index = 0;
    //scan the arrays
    while(arr1Index < arr1.length && arr2Index < arr2.length){
        int val1 = arr1[arr1Index];
        int val2 = arr2[arr2Index];
        //if the value in arr1 is less than arr2, move to next arr1 value
        if(val1 < val2){
            arr1Index++;
        }
        //if the value in arr2 is less than arr1, move the next arr2 value
        else if(val2 < val1){
            arr2Index++;
        }
        //otherwise add the value as a result and move to next arr1 and arr2 values
        else{
            results.add(val1);
            arr1Index++;
            arr2Index++;
        }
    }
    return results;
}

This can be done in O(n + n log n) ( O( n log n) ) complexity with O(n) memory by
1. Dividing the input strings into 4 groups based on input and output (O (n) )
a. for BB or RR like strings, simply add up the lengths
2. Sort the BR and RB collections lengths for greedy selection (this is the O(n log n) piece)
3. Ping-ponging between the RB and BR groups

public static int getLongest(Collection<String> strs){
    if(strs == null){
        throw new NullPointerException();
    }
    if(strs.size() == 0){
         return 0;
    }

    //break the input into major groupings
    int bbLength = 0;
    ArrayList<Integer> br = new ArrayList<Integer>();
    int rrLength = 0;
    ArrayList<Integer> rb = new ArrayList<Integer>();
    for(String str : strs){
        if(str.charAt(0) == 'B'){
            if(str.charAt(str.length() - 1) == 'B'){
                bbLength += str.Length();
            }
            else{
                br.add(str.length());
            }
        }
        else{
            if(str.charAt(str.length() - 1) == 'B'){
                rb.add(str.length());
            }
            else{
                rr += str.length();
             }
        }
    }
    //Sort to support greedy operations
    Collections.sort(br);
    Collections.sort(rb);

   //now do the ping ponging
   //if there are BR strings
   if(br.size() > 0){
        int val = 0;
        //if there are also RB strings
        if(rb.size() > 0){
            //if there are more BR strings, start there
            if(br.size() > rb.size()){
                val = br.remove(br.size() - 1);
            }
            //if there are more RB strings, start there
            else if(rb.size() > br.size()){
                val = rb.remove(rb.size() - 1);
            }
            //while there are both BR and RB strings, use them
            while(br.size() > 0 && rb.size() > 0){
                val += br.remove(br.size() - 1);
                val += rb.remove(rb.size() - 1);
            }
        }
        //otherwise there is only the BR string, use the max
        else{
            val += br.remove(br.size() - 1);
        }
        //add the BB and RR string lengths
        val += bbLength;
        val += rrLength;
        return val;
    }
    //if there are only RB strings, use the max there
    else if (rb.size() > 0){
        int val = rb.remove(rb.size() - 1);
        val += bbLength;
        val += rrLength;
    }
    //else there are only BB and RR strings. Use the longest one of those
    else{
        return Math.max(bbLength, rrLength);
    }
}

Here's an O(nm) algorithm using the k-select algorithm on a 2-D array. It takes O(1) memory but alters the original matrix to get the solution.

public static int getMedian(int[][] mat){
    if(mat == null){
         throw new NullPointerException();
    }

    int lo = 0;
    int hi = convertIndex(mat[0].length, mat.length, mat[0].length);
    int target = hi/2;
    int ignoredLo = 0;
    int ignoredHi = 0;
    int mid = select(mat, lo, hi);
    while(mid !=  target){
        if(mid < target){
            low = mid + 1;
        }
        else{
            hi = mid - 1;
        }
        mid = select(mat, lo, hi);
    }
    int[] indices = convertIndex(mat[0].length, mid);
    return mat[indices[0]][indices[1]];
}

private static int select(int[][] mat, int lo, int hi){
    int pivotIndex = lo;
    int[] indices = convertIndex(pivotIndex);
    int pivot = mat[indices[0]][indices[1]];
    int tempLo = lo + 1;
    int tempHi = hi;
    while(tempLo < tempHi){
        indices = convertIndex(tempLo);
        int check = mat[indices[0]][indices[1]];
        if(check > pivot){
            swap(mat, tempLo, tempHi);
            tempHi--;
        }
        else{
            tempLo++;
        }
    }
    indices = convertIndex(tempLo);
    if(mat[indices[0]][indices[1]] < pivot){
        swap(mat, tempLo, pivotIndex);
        return tempLo;
    }
    else{
        swap(mat, tempLo-1, pivotIndex);
        return tempLo -1;
    }
}

private static void swap(int[][] mat, int pos1, int pos2){
    int[] pos1Indices = convertIndex(pos1);
    int[] pos2Indices = convertIndex(pos2);
    int temp = mat[pos1Indices[0]][pos2[indices]];
    mat[pos1Indices[0]][pos2Indices[1]] = mat[pos2Indices[0]][pos2Indices[1]];
    mat[pos2Indices[0]][pos2Indices[1]] = temp;
}

private static int convertIndex(int rowSize, int row, int col){
    return rowSize * row + col;
}

private static int convertIndex(int rowSize, int index){
    int[] indices = new int[2];
    indices[0] = index / rowSize;
    indices[1] = index - (indices[0] * rowSize);
    return indices;
}

Here's an approximation that should run faster with O(m + n log n) complexity with O(n) memory: basically, find the median of each row, sort the row medians, then find the median of the row medians.

public static int getMedian(int[][] mat){
    if(mat == null){
        throw new NullPointerException();
    }
    int[] rowMedian = new int[mat[0].length];
    for(int row = 0; row < mat.length; row++){
        rowMedian[row] = getSortedMedian(mat[row]);
    }
    return getSortedMedian(arrays.sort(rowMedian));
}

private static int getSortedMedian(int[] arr){
    if(arr == null || arr.length == 0){
        throw new IllegalArgumentException();
    }
    if(arr.length % 2 == 0){
        int index = arr.length / 2;
        return (arr[index - 1] + arr[index])/2;
    }
    else{
        return arr[arr.length/2];
    }
}

Is it just me or does this sound like someone is trying to either get someone else to do their homework or to complete a take-home technical interview.

O(nm) complexity with O(nm) memory where n is the number of words and m is average number of characters.

public static List<Boolean> getAnagrams(BufferedReader in) throws IOException{
    HashSet<int[]> signatures = new HashSet<int[]>();
    ArrayList<Boolean> results = new ArrayList<Boolean>();
    String line = null;

    while((line = in.readLine()) != null){
        int[] signature = buildSignature(line);
        if(signatures.contains(signature)){
            results.add(true);
        }
        else{
            results.add(false);
            signatures.add(signature);
        }
    }
    return results;
}

private static int[] buildSignature(String str){
    int[] sig = new int[26];
    for(int i = 0; i < str.length(); i++){
        char c = str.charAt(i);
        sig[c - 'a']++;
    }
    return sig;
}

This can be done by counting the instances of each digit and then recombining it with the larger characters first. It will operate with O(1) memory, stores a 10 int array, and iterates over the ints to for a runtime complexity of O(n) where n is the number of digits in the array.

public static int maxFromDigits(int num){
    //count the digits
    int[] digits = new int[10];
    while(num > 0){
        digits[num % 10] ++;
        num /= 10;
    }
    //compose the largest integer possible
    for(int i = 9; i > -1; i--){
        while(digits[i] > 0){
            num *= 10;
            num += i;
            digits[i]--;
        }
    }
    return num;
}

Number of paths for part one = m ^ layers
Number of paths for part two = sum(i = 1 to layers) (m ^ i)
Where 'layers' is the number of layers considered i, i+1, etc

Edit:
The above approach is incorrect. After thinking about it some more, the actual count is

f(n) = m + m ( f (n -1) ) + f (n - 1)  when n > 0,  0 otherwise

where n is the number of layers.

Which roughly means
m possible paths if the only middle layer is layer 'n'
m ( f(n - 1) ) possible paths if layer 'n' is considered part of the path in combination with all the other layers < n
f(n -1) possible paths if layer 'n' is not part of the path using all the other layers < n

This simplifies to

f (n) = m + f (n -1) (m + 1)

Compute the mean. The mean value is should be effectively the centroid for any number of values. O(n) complexity and O(1) memory:

if relatively small array, use this:

public static int getMean(int[] arr){
    int mean;
    for(int val : arr){
        mean += val;
    }
    return mean / arr.length;
}

Agreed. Since the singleton is volatile, that should be fine. Not ideal.

It's normally preferable to use a Static helper class to create Singletons. That way you can assured that the singleton instance was created. And this approach doesn't require the use of synchronization. Also, the code above doesn't declare the singleton as final.

public class MySingleton{

    private static class HELPER{
        private static final MySingleton instance = new MySingleton();
    }

    MySingleton s = HELPER.instance;
}

@pbox
If you can't store anything other than the 2 digits holding the running average, then your problem is impossible. If you lack the memory to hold more than 2 digits of information, then you surely can't create supportive objects or very much code either.

In your for loops you are comparing points that have already been compared. j should start at i+1 because a line created by points P[0] and P[1] is the same as P[1] and P[0].

How about using DP to compute the total amount of consecutive 1s in every direction. And then using that information to compute the largest plus that could be created. It would take O(2n^2) which is O(n^2) time but it would be rather sucky regarding memory consumption at O(4n^2) ~ O(n^2):

public static int largestPlus(int[][] arr){
   if(arr == null){
        throw new NullPointerException();
   }

   int[][] lefts = new int[arr.length][arr[0].length];
   int[][] rights = new int[arr.length][arr[0].length];
   int[][] ups = new int[arr.length][arr[0].length];
   int[][] downs = new int[arr.length][arr[0].length];

   //compute DP cases
   for(int i = 0; i < arr.length; i++){
      ups[0][i] = arr[0][i];
      lefts[i][0] = arr[i][0];
      downs[arr.length-1][i] = arr[arr.length-1][i];
      rights[i][arr.length-1] = arr[i][arr.length-1];
   }
   for(int x = 0; x < arr.length; x++){
        for(int y = 1; y < arr.length; y++){
            if(arr[y][x] == 1){
                ups[y][x] = ups[y-1][x] + 1;
            }
            else{
                ups[y][x] = 0;
            }
            if(arr[x][y] == 1){
                lefts[x][y] = lefts[x][y-1] + 1;
            }
            else{
                lefts[x][y] = 0;
            }
            int invY = arr.length - y;
            if(arr[invY  - 1][x] == 1){
                downs[invY  - 1][x] = downs[invY ][x] + 1;
            }
            else{
                downs[invY  - 1][x] = 0;
            }
            if(arr[x][invY  - 1] == 1){
                rights[x][invY  - 1] = rights[x][invY ] + 1;
            }
            else{
                rights[x][invY  - 1] = 0;
            }
        }
    }

    //find best case
    int best = 0;
    for(int x = 0; x < arr.length; x++){
        for(int y = 0; y < arr.length; y++){
            int local = ups[x][y] < rights[x][y] ? ups[x][y] : rights[x][y];
            local = local < downs[x][y] ? local : downs[x][y];
            local = local < lefts[x][y] ? local : lefts[x][y];
            local = 4 * (local - 1) + 1;
            if(local > best){
                best = local;
            }
        }
    }
    return best;
}

Before starting the running average create this:

StreamingAverage avg = new StreamingAverage();

Every time a new number is pulled from the stream, call this:

avg.addToAverage(number);

Here's the code supporting it:

public class StreamingAverage{
    int count = 0;
    double average = 0;

    public void addToAverage(int number){
        double workingAverage = this.average * this.count;
        this.count ++;
        workingAverage += (double)number;
        this.average = workingAverage / (double)this.count;
    }

    public double getAverage(){
        return this.average;
    }
}

Assuming that 'unique' refers to line slopes. That being said, store the Slope of every possible line in a Set and check the set before returning 2 points as a line. O(n^2) complexity and O(n^2) memory.

EDIT: Forgot in original version to account for the offset in the line equation (the c in y = mx + c). That's now accounted for. Thanks Boris

class Point{
    double x, y;
}

class Line {
    double m, c;

    Line(double m, double c){
        this.m = m;
        this.c = c;
    }

    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + getOuterType().hashCode();
        long temp;
        temp = Double.doubleToLongBits(c);
        result = prime * result + (int) (temp ^ (temp >>> 32));
        temp = Double.doubleToLongBits(m);
        result = prime * result + (int) (temp ^ (temp >>> 32));
        return result;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        Point other = (Point) obj;
        if (!getOuterType().equals(other.getOuterType()))
            return false;
        if (Double.doubleToLongBits(c) != Double.doubleToLongBits(other.c))
            return false;
        if (Double.doubleToLongBits(m) != Double.doubleToLongBits(other.m))
            return false;
        return true;
    }
}

public static Collection<Point[]> getLines(Point[] points){
    if(points == null){
        throw new NullPointerException();
    }

    ArrayList<Point[]> results = new ArrayList<Point[]>();
    HashSet<Line> lineCache = new HashSet<Line>();
    for(int i = 0; i < points.length; i++){
        Point p1 = points[i];
        for(int j = i + 1; j < points.length; j++){
            Point p2 = points[j];
            double slope = (p1.x - p2.x);
            double c;
            if(slope == 0){
                slope = Double.POSITIVE_INFINITY;
                c = Double.POSITIVE_INFINITY;
            }
            else{
                slope = (p1.y - p2.y) / slope;
                c = p1.y - slope * p1.x;
            }
            Line line = new Line(slope, c);
            if(!lineCache .contains(line)){
                lineCache .add(line);
                Point[] segment= new Point[2];
                line[0] = p1;
                line[1] = p2;
                results.add(segment);
            }
        }
    }
    return results;
}

This is the most efficient code that I can make ( O(n) ):

public int fib(int n){
    int nMinus1 = 1;
    int nMinus2 = 1;
    for(int i = 1; i < n; i++){
        int temp = nMinus1 + nMinus2;
        nMinus2 = nMinus1;
        nMinus1 = temp;
    }
    return nMinus1;
}

what about if there are 33 lights in the range? 65? 1,000,000...?

Doesn't handle toggling lights off.

Shortest code, but FAR from most efficient.

public int fib(int n){
   return n < 2 ?
            1 :
            fib(n - 1) + fib(n - 2);
}

@ritwik_pandey:

Here's the test case that would show you why sorting on the start fails:
1 24
2 3
3 4
4 5
etc

How optimal do you want? This could become very ludicrous if so desired...

Rough algorithmic approach:
1. Compute the distances from Jerry to all cheeses, all cheeses to all other cheeses, and all cheeses to Jerry. Guess to be O( kNM) complexity with O(NM) memory
2. Iteratively search for pathing between all the Tom->cheeses->Jerry. This would be O(k!) complexity with O(k) memory for OPTIMAL solution. I'd probably forgo the optimal solution here and use something more easy to compute like using a Genetic Algorithm, ACO, or (egad) greedy if k is expected to be larger than 20.

Compute the quadratic result for values:

public static void printComponents(int sum, int product){
    int sqrRt = (int)Math.sqrt((sum * sum) - (4 * product));
    int posA = (-sum + sqrRt) / 2;
    int posB = product / posA;
    if(posA + posB != sum ){
        posA = (-sum - sqrRt) / 2;
        posB = product / posA;
    }
    java.lang.System.out.println(""+posA+", "+posB);
}

Average O(n log n) runtime complexity using O(n) memory though most of that is taken by the storage of the incoming values. The actual algorithm itself would take O(1) memory.

class Event implements Comparable{
    int start;
    int end;
    
    Event(int start, int end){
        this.start = start;
        this.end = end;
    }

    public int compare(Event e){
        return e.end - this.end;
    }
}

public static int getMaxParties(Event[] parties){
    Arrays.sort(parties);
    int count = 0;
    int currentEnd = -1;
    for(Event party : parties){
        if(party.start >= currentEnd){
            count++;
            currentEnd = party.end;
        }
    }
    return count;
}

@Aman_Mittal: Operations on a HashMap are considered to be amortized O(1). Much like adding an element to an ArrayList is amortized O(1)

Doesn't consider that the second element must come after the first. (ie: maximize A[m] - A[n] where m < n)

A = [0, 100, 50] should return 50.

More generalized form of the problem where attempting to get the maximum a[m] - a[n] where m - n >= 1 instead of m - n == 1 .

O(n) runtime with O(1) memory:

//returns -1 if no drop from some a[m] to a[n] where m < n could be computed
public static int maxDrop(int[] arr){
    if(arr == null){
        throw new NullPointerException();
    }
    if(arr.length == 0){
        return -1;
    }

    int bestDiff = -1;
    int max = arr[0];
    int currentDiff = -1;
    
    for(int i = 0; i < arr.length; i++){
        int val = arr[i];
        if(val > max){
            max = val;
            currentDiff = -1;
        }
        else{
            int diff = max - val;
            if(diff > currentDiff){
                currentDiff = diff;
                if(currentDiff > bestDiff){
                    bestDiff = currentDiff;
                }
            }
        }
    }
    return bestDiff;
}

I don't think this can be done. If you need to preserve Ancestry and each interior node other than 1 exception has 0 or N elements, then it can't be done.

See this example. Original tree:

_____1
____/__\
__2_____3
_/__\___/__\
4___5_6___7

If N were 3, then there is no logical way that you could reorder the tree to have only 0 or 3 children of each node (except for the single exception node) and to preserve ancestry.

Likewise, if the tree were:

________1
_____/___|____\
__2_____3_______4
_/_|_\__/_|_\____/__|__\
5_6_7_8_9_10_11_12_13

And N were 2, there is no way to reorganize the tree such that Ancestry is preserved. You'd have to add extra ancestors in the structural reordering. The tree would have to be something really deformed too like

_______1
_____/____\
____2_______3
___/__\_____/__\
__5___4___8___9
____/___\_______\
___6____7______10
_/___\____\
11__12___13

which is still invalid.

This will be the left-most descendant of the right child of a specific node.

public class Node{
    int value;
    Node left, right;
}

public static Node successor(Node node){
    if(node == null){
        throw new NullPointerException();
    }
    if(node.right == null){
        return null;
    }
    node = node.right;
    while(node.left != null){
        node = node.left;
    }
    return node;
}

Given that the lists are Objects in java, there may be concerns about the amount of memory consumed by all the distinct LinkedLists. I suspect, however, that the memory consumed by distinct LinkedLists would be more on the order of O(log n) so it wouldn't be much of an issue.

public static void sort(LinkedList<Integer> list){
    if(list == null){
        throw new NullPointerException();
    }

    //base cases
    if(list.size() == 0 || list.size() == 1){
        return;
    }

    //divide the list and sort each half
    LinkedList<Integer> firstHalf = splitLinkedList(list);
    sort(firstHalf);
    sort(list);

    //recombine the halves
    return merge(list, firstHalf);
}

private static LinkedList<Integer> splitLinkedList(LinkedList<Integer> list){
    LinkedList<Integer> firstHalf = new LinkedList<Integer>();
    int halfSize = list.size() / 2;
    for(int i = 0; i <halfSize ; i++){
        firstHalf.add(list.removeFirst());
    }
    return firstHalf;
}

private static LinkedList<Integer> merge(LinkedList<Integer> list1, LinkedList<Integer> list2){
    LinkedList<Integer> results = new LinkedList<Integer>();
    while(!list1.isEmpty() && !list2.isEmpty()){
        if(list1.peek() < list2.peek()){
            results.add(list1.removeFirst();
        }
        else{
            results.add(list2.removeFirst());
        }
    }
    results.addAll(list1);
    results.addAll(list2);
    return results;
}

Though much more readable than mine, String.split(string) operates in O(n) time already. So, effectively, your runtime is O(n+m) complexity where n is the number of characters and m is the number of tokens produced by the split. It is not as fast as simply reading the original String 1 time (character by character) and handling each token at that time ( O(n) complexity).