CareerCup

O(n) time, O(1) space

static int reverseSignElement(int[] array, int target) {
		if (array == null || array.length == 0)
			return 0;
		int sum = 0;
		for (int i : array) {
			sum += i;
		}
		for (int i : array) {
			if (sum - 2*i == target)
				return i;
		}
		return 0;
	}

after calling this function, "minDiff" will hold the minimum difference. O(n) time.

static void findBSTMinimumValueDifference(Node root) {
		 if (root != null) {
			 findBSTMinimumValueDifference(root.left);
			 if (previous != null && minDiff > root.value - previous.value) {
				 minDiff = root.value - previous.value;
			 }
			 previous = root;
			 findBSTMinimumValueDifference(root.right);
		 }
	 }
	 
static int minDiff = Integer.MAX_VALUE;
static Node previous;

Recursion + Kadane's + Backtracking

public class ContinuesOnesByFlipping {

	public static class Result { int max; public Result(int m) {max = m;}}
	
	public static void main(String[] args) {
		int[] array = new int[] {1,0,1,0,1,1,0,0,0,1,0,1,1,1,0,1};
		int k = 3;
		
		System.out.println("Result = "+ maxOnes(array, k));
	}
	
	public static int maxOnes(int[] array, int k) {
		Result r = new Result(0);
		maxOnes(array, k, 0, r);
		return r.max;
	}
	
	public static void maxOnes(int[] array, int k, int start, Result r) {
		if (k == 0) {
			r.max = Math.max(maxOnesKadane(array), r.max);
		}
		for (int i = start; i < array.length; i++) {
			if (array[i] == 0 && k > 0) {
				array[i] = 1;
				maxOnes(array, k - 1, i + 1, r);
				array[i] = 0;
			}
		}
	}
	
	public static int maxOnesKadane(int[] array) {
		int maxSoFar = 0;
		int maxEndingHere = 0;
		for (int i = 0; i < array.length; i++) {
			if (array[i] == 1) {
				maxEndingHere += 1;
			} else if (array[i] == 0) {
				maxEndingHere = 0;
			}
			if (maxEndingHere > maxSoFar) {
				maxSoFar = maxEndingHere;
			}
		}
		return maxSoFar;
	}
}

@ilgor: This will work for +1 increment arithmetic sequences, however it will not work when the increment is > 1 (for example [3,8,13,18,23])

The idea is the following:
1. Create an array of lines between each point
2. Group lines with the same slope
3. For each line in the "same-slope" group
3.1 Create an array of lines between each of the midpoints
3.2 Find the max number of collinear midpoints

Below is implementation in Java

import java.util.ArrayList;
import java.util.HashMap;

public class FoldingPlane {

	public static void main(String[] args) {
		ArrayList<Point> points = new ArrayList<>();
		points.add(new Point(-2, 1));
		points.add(new Point(0 , 2));
		points.add(new Point(0 ,-1));
		points.add(new Point(1 ,-2));
		points.add(new Point(2 , 0));
		points.add(new Point(2 , 1));
		points.add(new Point(1 , 2));
		points.add(new Point(2 , 2));
		
		int max = maximumNumberOfPairsWhenFolded(points);
		
		System.out.println("max="+max);
	}
	
	static int maximumNumberOfPairsWhenFolded(ArrayList<Point> points) {
		// 1. Create an array of lines between each point
		ArrayList<Line> lines = constructLinesfromPoints(points);
		// 2. Group lines with the same slope
		HashMap<Double, ArrayList<Line>> mapFromSlopesToLines = constructMapfromSlopesToLines(lines);

		int max = 0;
		// 3. For each line in the group
		for (ArrayList<Line> slopeLines : mapFromSlopesToLines.values()) {
			// 3.1 Create an array of lines between each of the midpoints
			ArrayList<Line> linesFromMidPoints = constructLinesfromMidPoints(slopeLines);
			// 3.2 Find the max number of collinear midpoints
			max = Math.max(max, maxNumberOfCollinearMidPointsInLines(linesFromMidPoints));
		}
		return max;
	}
	
	static ArrayList<Line> constructLinesfromPoints(ArrayList<Point> points) {
		ArrayList<Line> result = new ArrayList<>();
		for (int i = 0; i < points.size(); i++) {
			for (int j = i+1; j < points.size(); j++) {
				result.add(new Line(points.get(i), points.get(j)));
			}
		}
		return result;
	}
	
	static ArrayList<Line> constructLinesfromMidPoints(ArrayList<Line> lines) {
		ArrayList<Line> result = new ArrayList<>();
		for (int i = 0; i < lines.size(); i++) {
			for (int j = i+1; j < lines.size(); j++) {
				result.add(new Line(lines.get(i).midPoint, lines.get(j).midPoint));
			}
		}
		return result;
	}
	
	static HashMap<Double, ArrayList<Line>> constructMapfromSlopesToLines(ArrayList<Line> lines) {
		HashMap<Double, ArrayList<Line>> map = new HashMap<>();
		for (Line l : lines) {
			ArrayList<Line> slopeLines;
			if (map.get(l.slope) == null) { slopeLines = new ArrayList<>(); } 
			else { slopeLines = map.get(l.slope); }
			slopeLines.add(l);
			map.put(l.slope, slopeLines);
		}
		return map;
	}
	
	static int maxNumberOfCollinearMidPointsInLines(ArrayList<Line> linesFromMidPoints) {
		HashMap<Double, ArrayList<Line>> map = new HashMap<>();
		for (Line l : linesFromMidPoints) {
			ArrayList<Line> slopeLines;
			if (map.get(l.slope) == null) { slopeLines = new ArrayList<>(); } 
			else { slopeLines = map.get(l.slope); }
			slopeLines.add(l);
			map.put(l.slope, slopeLines);
		}
		int max = 0;
		for (ArrayList<Line> lines : map.values()) {
			max = Math.max(max, lines.size());
		}
		return max;
	}
	
	static class Point {
		double x;
		double y;
		public Point(double x, double y) {
			this.x = x;
			this.y = y;
		}
		public String toString() {
			return "("+x+","+y+")";
		}
	}
	
	static class Line {
		double slope;
		Point midPoint;
		public Line(Point p1, Point p2) {
			if (p1.x != p2.x) {
				slope = (p2.y - p1.y)/(p2.x - p1.x);
			} else {
				slope = Double.MAX_VALUE;
			}
			midPoint = new Point((p1.x + p2.x)/2, (p1.y + p2.y)/2);
		}
		public String toString() {
			return "(sl="+slope+", mp="+midPoint+")";
		}
	}
}

That also works for unsorted array of positive integers.

O(n) time complexity
+ O(n) space for verification

import java.util.HashSet;

public class ArithmeticSequence {

	public static void main(String[] args) {
		int[] array = new int[] {31,21,11,41,61,51,71};
		System.out.println("is Arithmetic ? "+isArithmeticSequence(array));
	}
	
	static boolean isArithmeticSequence(int[] array) {
		if (array.length == 0) 
			return false;
		if (array.length == 1) 
			return true;

		// find minimum element in array
		int min = min(array);
		
		// find the diff between elements as a double
		double diff = diff(array, min);
		// and check if it is an integer
		if (diff != (int)diff) 
			return false;
		
		// if the diff looks valid, verify solution
		return verify(array, (int)diff, min);
	}
	
	static double diff(int[] array, int min) {
		int n = array.length;
		double sum = 0;
		
		for (int i = 0; i < array.length; i++) {
			sum += array[i];
		}
		return (2*sum/n - 2*min)/(n-1);
	}
	
	static boolean verify(int[] array, int diff, int min) {
	
		HashSet<Integer> set = new HashSet<>();
		for (int i:array) set.add(i);
		for (int i:array) {
			if (i != min && !set.contains(i-diff)) {
				return false;
			}
		}
		return true;
	}
	
	static int min(int[] array) {
		int min = Integer.MAX_VALUE;
		for (int i = 0; i < array.length; i++) {
			if (array[i] < min) min = array[i];
		}
		return min;
	}
}

This solution has exponential time & space complexity (getting OutOfMemoryError when converting 42 to 733).

Please check out my solution that is O(logm) worst case.

Worst case complexity is O(logn) :)

Solution based on simple arithmetic.

import java.util.ArrayList;
import java.util.Collections;

public class ConvertWithOperations {

	public static int convert(int m, int n, ArrayList<String> path) {
		if (m == n) {
			return 0;
		}
		if (m > n) { //  only way is to do -1 (m-n) times
			path.add(("'-1' "+(m-n)+" times"));
			return m-n;
		}
		if (m <= 0 && n > 0) {
			return -1; // not possible
		}
		if (n % 2 == 1) { // n is odd
			path.add(("'-1'"));
			return 1 + convert(m, n+1, path);
			
		} else { // n is even
			path.add(("'x2'"));
			return 1 + convert(m, n/2, path);
		}
	}
	
	public static void main(String[] args) {
		int m = 42;
		int n = 733;
		ArrayList<String> path = new ArrayList<String>();
		System.out.println("# Operations: "+convert(m,n, path));
		Collections.reverse(path);
		System.out.println("Operations: "+path);
	}
}

Prints:

# Operations: 26
Operations: ['-1' 19 times, 'x2', 'x2', 'x2', 'x2', '-1', 'x2', '-1']

Cool idea! An alternative to euclidean distance.
The algorithm to search for the smallest displacement over a period of time would still require sorting/heap etc, but it's a nice approach :)

import java.util.ArrayList;
import java.util.HashMap;

public class LongestSequenceCircular {

	public static void main(String[] args) {
		Node n = createList();
		
		// First, find the length of the linked list 
		int length = length(n);
		System.out.println("Max sequence length is " + findLongestSequenceLength(n, length));
		
	}
	
	public static int findLongestSequenceLength(Node n, int length) {
		HashMap<Integer, ArrayList<Integer>> map = new HashMap<Integer, ArrayList<Integer>>();
		Node curr = n;
		// create a map between node value and list of indexes it appears
		for (int i = 0; i < length; i++) {
			if (!map.containsKey(curr.val)) {
				ArrayList<Integer> arr = new ArrayList<Integer>();
				map.put(curr.val, arr);
			}
			map.get(curr.val).add(i);
			curr = curr.next;
		}
		int max = 0;
		// find the longest sequence among all values in the map
		for (Integer i : map.keySet()) {
			if (map.get(i).size() == 1) continue; // just one occurrence of the value will not form a sequence
			int maxLocal = findLongestSequenceForValue(map.get(i), length);
			max = Math.max(max, maxLocal);
		}
		return max;
	}
	
	public static int findLongestSequenceForValue(ArrayList<Integer> arr, int maxLength) {
		int max = 0;
		// since indexes are in ascending order we can find the max sequence in this iteration
		for (int i=0; i<arr.size() - 1; i++) {
			int diff = arr.get(i+1) - arr.get(i);
			max = Math.max(max, diff);
		}
		// also check sequence length in case we wrap to the beginning of the linked list
		int finalDiff = maxLength - 1 - arr.get(arr.size() - 1) + arr.get(0); 
		return Math.max(max, finalDiff);
	}
	
	public static int length(Node n) {
		if (n == null) return 0;
		Node slow = n;
		Node fast = n.next;
		int result = 1;
		while (fast != null) {
			if (fast == slow) return result;
			if (fast.next == slow) return result + 1;
			slow = slow.next;
			fast = fast.next.next;
			result++;
		}
		return result;
	}
	
	public static Node createList() {
		Node n = new Node(3);
		n.next = new Node(8);
		n.next.next = new Node(9);
		n.next.next.next = new Node(7);
		n.next.next.next.next = new Node(2);
		n.next.next.next.next.next = new Node(1);
		n.next.next.next.next.next.next = new Node(3);
		n.next.next.next.next.next.next.next = new Node(4);
		n.next.next.next.next.next.next.next.next = new Node(6);
		n.next.next.next.next.next.next.next.next.next = n;
		return n;
	}
	
	public static class Node
	{
		int val;
		Node next;
		public Node(int val) { this.val = val; }
	}

}

O(n^2) for a nxn matrix

import java.util.Arrays;

public class ShiftMatrix {

	public static void main(String[] args) {
		int[][] matrix = new int[][] { 
				new int[] {1,  2,  3,  4,  5}, 
				new int[] {6,  7,  8,  9,  10},
				new int[] {11, 12, 13, 14, 15},
				new int[] {16, 17, 18, 19, 20},
				new int[] {21, 22, 23, 24, 25} };

		ShiftMatrix.shift(matrix);
		for (int[] i : matrix)
			System.out.println(Arrays.toString(i));
	}

	public static void shift(int[][] matrix) {
		int curCol = matrix[0].length - 1;
		int curRow = 0;

		while (curRow != matrix.length) {
			while (curCol != 0) {
				swap(matrix, curRow, curCol, curCol - 1);
				curCol--;
			}
			curCol = matrix[0].length - 1;
			curRow++;
		}
	}
	
	public static void swap(int[][] matrix, int row, int fromCol, int toCol) {
		int temp = matrix[row][fromCol];
		matrix[row][fromCol] = matrix[row][toCol];
		matrix[row][toCol] = temp;
	}
}

Prints:

[5, 1, 2, 3, 4]
[10, 6, 7, 8, 9]
[15, 11, 12, 13, 14]
[20, 16, 17, 18, 19]
[25, 21, 22, 23, 24]

You are right Sean. Thanks for pointing that out!

Java solution
(String parsing of score can be avoided by using some form of tuple to represent it)

public static void printAllScorePossibilities(int t1, int t2) {
		Queue<List<String>> q = new LinkedList<List<String>>();
		Stack<String> initialPath = new Stack<String>();
		initialPath.add("0-0");
		q.add(initialPath);
		
		while (!q.isEmpty()) {
			List<String> tmpPath = q.poll();
			String lastNode = tmpPath.get(tmpPath.size() - 1);
			if (lastNode.equals(t1 + "-" + t2)) {
				System.out.println(tmpPath);
			}
			String[] s = lastNode.split("-");
			int t1Curr = Integer.parseInt(s[0]);
			int t2Curr = Integer.parseInt(s[1]);
			if (t1Curr < t1) {
				List<String> newPath = new ArrayList<String>(tmpPath);
				newPath.add((t1Curr+1)+"-"+t2Curr);
				q.add(newPath);
			}
			if (t2Curr < t2) {
				List<String> newPath = new ArrayList<String>(tmpPath);
				newPath.add(t1Curr+"-"+(t2Curr+1));
				q.add(newPath);
			}
		}
	}
	
	public static void main(String[] args) {
		printAllScorePossibilities(3,2);
	}

Prints:

[0-0, 1-0, 2-0, 3-0, 3-1, 3-2]
[0-0, 1-0, 2-0, 2-1, 3-1, 3-2]
[0-0, 1-0, 2-0, 2-1, 2-2, 3-2]
[0-0, 1-0, 1-1, 2-1, 3-1, 3-2]
[0-0, 1-0, 1-1, 2-1, 2-2, 3-2]
[0-0, 1-0, 1-1, 1-2, 2-2, 3-2]
[0-0, 0-1, 1-1, 2-1, 3-1, 3-2]
[0-0, 0-1, 1-1, 2-1, 2-2, 3-2]
[0-0, 0-1, 1-1, 1-2, 2-2, 3-2]
[0-0, 0-1, 0-2, 1-2, 2-2, 3-2]

Java solution

public class TriangleMaxSum {

	public static void main(String[] args) {
		String triangle = "5#9#6#4#6#8#0#7#1#5";
		System.out.println(TriangleMaxSum.maxSum(triangle));
	}
	
	public static String maxSum(String triangle) {
		String[] nums = triangle.split("#");
		int start, sum, diff, end = 1;
		start = sum = diff = 0;
		for (;;) {
			sum += maxVal(nums, start, end);
			if (end == nums.length) return sum+"";
			diff = end - start;
			start = end;
			end += diff + 1;
			if (end > nums.length) return "Invalid";
		}
	}
	
	public static int maxVal(String[] array, int start, int end) {
		int intValue, max = Integer.MIN_VALUE;
		for (int i = start; i < end; i++) {
			intValue = Integer.parseInt(array[i]);
			if (intValue > max) max = intValue;
		}
		return max;
	}
}

Using a modified version of radix sort

public class MaxPermutation {

	public static void main(String[] args) {
		int[] numbers = new int[]{9,918,917};
		//int[] numbers = new int[]{1,112,113};
		//int[] numbers = new int[]{8,991,89,51,5,0};
		//int[] numbers = new int[]{9015,901};
		MaxPermutation.sort(numbers);
		for (int i = 0; i < numbers.length / 2; i++) {
			int temp = numbers[i]; 
			numbers[i] = numbers[numbers.length - 1 -i];
			numbers[numbers.length - 1 -i] = temp;
		}
		for (int i = 0; i < numbers.length; i++) {
            System.out.print(numbers[i]+" ");    
		}
        System.out.println(); 
	}
	
	public static void sort(int[] a)
    {
        int i, m = a[0], exp = 1, n = a.length;
        int[] b = new int[10];
        for (i = 1; i < n; i++)
            if (a[i] > m)
                m = a[i];
        while (m / exp > 0)
        {
            int[] bucket = new int[10];
 
            for (i = 0; i < n; i++) {
            	int exp_t = exp;
            	while (exp_t > 0 && a[i] / exp_t == 0) exp_t /= 10;
            	if (exp_t == 0) exp_t = 1;
                bucket[(a[i] / exp_t) % 10]++;
            }
            for (i = 1; i < 10; i++)
                bucket[i] += bucket[i - 1];
            for (i = n - 1; i >= 0; i--) {
            	int exp_t = exp;
            	while (exp_t > 0 && a[i] / exp_t == 0) exp_t /= 10;
            	if (exp_t == 0) exp_t = 1;
                b[--bucket[(a[i] / exp_t) % 10]] = a[i];
            }
            for (i = 0; i < n; i++)
                a[i] = b[i];
            exp *= 10;    
        }
    }  
}

Java implementation using flood fill, O(n^2)

public class IslandCount {

	public static void main(String[] args) {

		int[][] sea = new int[][] { 
				new int[] {0,  1,  0,  1,  0},
				new int[] {0,  0,  1,  1,  1},
				new int[] {1,  0,  0,  1,  0},
				new int[] {0,  1,  1,  0,  0},
				new int[] {1,  0,  1,  0,  1} };
		
		int numOfIslands = IslandCount.countIslands(sea);
		System.out.println("Number of islands is "+numOfIslands);
	}
	
	public static int countIslands(int[][] sea) {
		boolean[][] checked = new boolean[sea.length][sea.length];
		for (int i = 0; i < sea.length; i++) {
			for (int j = 0; j < sea.length; j++) {
				checked[i][j] = false;
			}
		}
		return countIslands(sea, checked);
	}
	
	public static int countIslands(int[][] sea, boolean[][] checked) {
		int numOfIslands = 0;
		for (int i = 0; i < sea.length; i++) {
			for (int j = 0; j < sea.length; j++) {
				if (checked[i][j]) 
					continue;
				if (sea[i][j] == 0) {
					checked[i][j] = true;
					continue;
				}
				numOfIslands++;
				floodFill(i, j, sea, checked); 
			}
		}
		return numOfIslands;
	}
	
	public static void floodFill(int row, int col, int[][] sea, boolean[][] checked) {
		if (sea[row][col] == 0 || checked[row][col]) return;
		checked[row][col] = true;
		if (col < sea.length - 1) floodFill(row, col+1, sea, checked);
		if (row < sea.length - 1) floodFill(row+1, col, sea, checked);
		if (col > 0) floodFill(row, col-1, sea, checked);
		if (row > 0) floodFill(row-1, col, sea, checked);
	}

}

O(n) solution

public static void main(String[] args) {
		String S = "adobecodebanc";
		String T = "abc";
		
		System.out.println(smallestSubstring(S,T));
	}


	public static String smallestSubstring(String S, String T) {
		
		Map<Character, Integer> map = new HashMap<Character, Integer>();
		int bestResultLength = Integer.MAX_VALUE;
		String bestSubstring = "";
		
		for (Character c : T.toCharArray()) {
			map.put(c, -1);
		}
		
		for (int i = 0; i < S.length(); i++) {
			if (map.containsKey(S.charAt(i))) {
				map.put(S.charAt(i), i);
				String interimResult = substring(S, map);
				if (interimResult != null && interimResult.length() < bestResultLength) {
					bestSubstring = interimResult;
					bestResultLength = interimResult.length();
				}
			}
		}
		return bestSubstring;
	}
	
	public static String substring(String S, Map<Character, Integer> map) {
		ArrayList<Integer> list = new ArrayList<Integer>(map.values());
		for (Integer i : list) {
			if (i == -1) return null;
		}
		Collections.sort(list);
		return S.substring(list.get(0), list.get(list.size() - 1) + 1);
	}

public static void moveZeroesToEnd(int[] arr) {
		int start = 0;
		int end = arr.length - 1;
		
		while (start < end) {
			while (arr[start] != 0 && start < arr.length - 1) 
				start++;
			while (arr[end] == 0 && end > 0) 
				end--;
			if (start >= end) break;

			// swap start with end
			int temp = arr[start];
			arr[start] = arr[end];
			arr[end] = temp;
		}
	}

I believe that the question asks for buy/sell values that are not containing local minimums and maximums in between. Just a straight gain from buy to sell instances.
The author of this question may need to clarify though.

Modified version of Kadane's algorithm which tracks from and to indexes, O(n) time.

public static int maxProfit(int[] input) {
		int maxSoFar = 0;
		int maxEndingHere = 0;
		int maxEndingHerePrev = 0;
		int maxBest = 0;
		int fromTemp = -1;
		int from = -1;
		int to = -1;
		for (int i = 1; i < input.length  ; i++) {
			maxEndingHere = maxEndingHere + input[i] - input[i-1 ];
			if (maxEndingHere < maxEndingHerePrev) { maxEndingHere = 0; fromTemp = i; }
			if (maxSoFar < maxEndingHere) maxSoFar = maxEndingHere;
			maxEndingHerePrev = maxEndingHere;
			if (maxEndingHere > maxBest) {
				from = fromTemp;
				to = i;
				maxBest = maxEndingHere;
			}
		}
		System.out.println("Max profit is "+maxBest + ". Buy at "+input[from]+", sell at "+input[to]);
		return maxBest;
	}

This code returns 40 instead of 35 for input [10, 30, 42, 15, 20, 50, 10, 25].
It counts max profit between 10 (1st element) and 50, instead of 15 (4th element) and 50.

O(n)

public static void sortByIndex(char[] array, int[] indexes) {
		if (array.length != indexes.length) return;

		for (int i = 0; i < array.length; i++) {
			// swap value
			char temp = array[indexes[i]]; 
			array[indexes[i]] = array[i];
			array[i] = temp;
			// swap index
			int tInd = indexes[indexes[i]];
			indexes[indexes[i]] = indexes[i];
			indexes[i] = tInd;
		}
	}

Using a modified version of Kadane's Algorithm
O(n) time, O(1) space

public static int maxDrop(int[] input) {
		int maxSoFar = 0;
		int maxEndingHere = 0;
		for (int i = 0; i < input.length - 1 ; i++) {
			maxEndingHere = maxEndingHere + input[i] - input[i + 1];
			if (maxEndingHere < 0) maxEndingHere = 0;
			if (maxSoFar < maxEndingHere) maxSoFar = maxEndingHere;
		}
		 return maxSoFar;
	}