Max submatrix sum in a matrix

Given an NxN matrix of positive and negative integers, write code to find the sub- matrix with the largest possible sum.

Thoughts:
Go through each submatrix (O(n^4) of them) and compute their sums, keeping track of the curren maximum. Without additional optimization, the computation of sums cost O(n^4), giving total a O(n^6) algorithm. We can precompute some sums to reduce the total costs to O(n^4):
Let’s say we need to compute the sum of the submatrix (startRow, startCol) -> (endRow, endCol), S. We can first pre-compute the sum of (0,0) -> (endRow, endCol) denote as S_{1}, the sum of (0,0) -> (endRow, startCol-1) denote as S_{2}, the sum of (0,0) -> (startRow-1, endCol) denote as S_{3} and the sum of (0,0) -> (startRow-1, startCol-1) denote as S_{4}, then S = S_{1} - S{2} - S{3} + S{4}. Hence, we can pre-compute sums of (0,0) -> (i,j) for every pair of (i,j). Then we searching, the computation of sum of submatrix will only need a single operation.

Codes:

	private static int[][] sums;

	private static void preComputeSums(int[][] matrix) {
		sums = new int[matrix.length][matrix[0].length];
		for (int i = 0; i < matrix.length; ++i) {
			for (int j = 0; j < matrix[i].length; ++j) {
				if (i == 0 && j == 0)
					sums[i][j] = matrix[i][j];
				else if (j == 0)
					sums[i][j] = sums[i - 1][j] + matrix[i][j];
				else if (i == 0)
					sums[i][j] = sums[i][j - 1] + matrix[i][j];
				else
					sums[i][j] = sums[i - 1][j] + sums[i][j - 1]
							- sums[i - 1][j - 1] + matrix[i][j];
			}
		}
	}
	
	private static int computeSum(int[][] matrix, int startRow, int endRow,
			int startCol, int endCol) {
		if (startRow == 0 && startCol == 0)
			return sums[endRow][endCol];
		else if (startRow == 0)
			return sums[endRow][endCol] - sums[endRow][startCol - 1];
		else if (startCol == 0)
			return sums[endRow][endCol] - sums[startRow - 1][endCol];
		else
			return sums[endRow][endCol] - sums[endRow][startCol - 1]
					- sums[startRow - 1][endCol]
					+ sums[startRow - 1][startCol - 1];
	}

	public static int[][] findSubmatrixWithMaxSum(int[][] matrix) {
		preComputeSums(matrix);
		int startRow = 0, endRow = 0;
		int startCol = 0, endCol = 0;
		int maxSum = Integer.MIN_VALUE;
		for (int i = 0; i < matrix.length; ++i) {
			for (int j = 0; j < matrix[i].length; ++j) {
				for (int rowPtr = i; rowPtr < matrix.length; ++rowPtr) {
					for (int colPtr = j; 
						colPtr < matrix[rowPtr].length; ++colPtr) {
						int sum = computeSum(matrix, i, rowPtr, j, colPtr);
						if (sum > maxSum) {
							maxSum = sum;
							startRow = i;
							endRow = rowPtr;
							startCol = j;
							endCol = colPtr;
						}
					}
				}
			}
		}

		int[][] subMatrix = new int[endRow - startRow + 1][endCol - startCol
				+ 1];
		for (int i = startRow; i <= endRow; ++i)
			System.arraycopy(matrix[i], startCol, subMatrix[i - startRow], 0,
					endCol - startCol + 1);
		return subMatrix;
	}

Find max subsquare whose border values are all 1

Imagine you have a square matrix, where each cell is filled with either black or white. Design an algorithm to find the maximum subsquare such that all four borders are filled with black pixels.

Thoughts:
We are going to scan column by column, checking to see if this column can be the left-border of the desired subsquare. Along each column, we build “sliding windows”, from large size to small size. The size of the window is the size of the subsquare. The winodw starts at different row, moving from top to bottom. When the window is fixed in a position, we chan check if this subsquare is valid or not. If so, we update the max subsquare we have found then continue.

Example:
111
011
000

  1. 1st column:
    1. 1st row: window size = 3: {{1,1,1,},{0,1,1},{0,0,0}} is not valid; window size = 2: {{1,1,},{0,1}} is not valid; window size = 1: {{1}} is valid, so update it.
    2. 2nd row: window size = 2: {{0,1},{0,0}} is not valid; window size = 1: no need to check. already have a current max subsquare with size 1.
  2. 2nd column:
    1. 1st row: window size = 2: {{1,1},{1,1}} is valid, so update it; window size = 1: no need to check.
    2. 2nd row: no need to check. Max subsquare can be found is of size 2, but we already have a valid one with size 2.
  3. 3rd column:No need to check.

Codes:

	public static int[][] findMaxSubsquare(int[][] square) {
		int[][] maxSubsquare = null;
		int maxSize = 0;
		for (int col = 0; square.length - col > maxSize; ++col) {
			for (int row = 0; square.length - row > maxSize; ++row) {
				for (int size = square.length - Math.max(row, col); 
							size > maxSize; --size) {
					if (isValidSubsquare(square, row, col, size)) {
						maxSize = size;
						maxSubsquare = new int[size][size];
						for (int i = row; i < size + row; ++i)
							System.arraycopy(square[i], col, maxSubsquare[i
									- row], 0, size);
					}
				}
			}
		}
		return maxSubsquare;
	}

	private static boolean isValidSubsquare(int[][] square, int row, int col,
			int size) {
		// up and bottom border
		for (int j = col; j < col + size; ++j) {
			if (square[row][j] == 0)
				return false;
			if (square[row + size - 1][j] == 0)
				return false;
		}
		// left and right border
		for (int i = row; i < row + size; ++i) {
			if (square[i][col] == 0)
				return false;
			if (square[i][col + size - 1] == 0)
				return false;
		}
		return true;
	}

Transform one word into another by changing only one letter at a time

Given two words of equal length that are in a dictionary, write a method to transform one word into another word by changing only one letter at a time. The new word you get in each step must be in the dictionary.
EXAMPLE
Input: DAMP, LIKE
Output: DAMP -> LAMP -> LIMP -> LIME -> LIKE

Thoughts:
This is essentially a modified version of Breadth-First-Search. For each word, its braches are those words that can be tranformed from it by changing only one letter. We need to keep track of a route-map so that when we hit the destination, we can backtrack to retrieve the route we have been.

Codes:

	public static List<String> transform(String src, String des,
			Set<String> dictionary) {
		Queue<String> Q = new LinkedList<String>();
		Set<String> visited = new HashSet<String>();
		Map<String, String> routes = new HashMap<String, String>();
		Q.add(src);
		visited.add(src);
		while (!Q.isEmpty()) {
			String t = Q.poll();
			if (t.equals(des)) {
				LinkedList<String> list = new LinkedList<String>();
				while (t != null) {
					list.add(0, t);
					t = routes.get(t);
				}
				return list;
			}
			for (String o : getAllTransformations(t, dictionary)) {
				if (!visited.contains(o)) {
					visited.add(o);
					Q.add(o);
					routes.put(o, t);
				}
			}
		}
		return null;
	}

	private static List<String> getAllTransformations(String src,
			Set<String> dictionary) {
		List<String> results = new LinkedList<String>();
		for (int i = 0; i < src.length(); ++i) {
			for (char c = 'A'; c <= 'Z'; ++c) {
				String newStr = src.substring(0, i) + c + src.substring(i + 1);
				if (!src.equals(newStr) && dictionary.contains(newStr))
					results.add(newStr);
			}
		}
		return results;
	}

Online median finding and maintainence

Numbers are randomly generated and passed to a method. Write a program to find and maintain the median value as new values are generated.

Thoughts:
We maintain two heaps: minHeap and maxHeap. If we represent these two heaps in terms of list, minHeap is in descending order whereas maxHeap is in ascending order. If we manage to maintain these two heaps while getting new numbers, the median is either in the first place of minHeap or in the first place of maxHeap (or the average of these two). Consider the example of sequence of numbers: 1, 2, 3, 4 and 5. The maintainence of minHeap, maxHeap are shown below:
After 1 coming:
minHeap: 1
maxHeap:
median : 1

After 2 coming:
minHeap: 1
maxHeap: 2
median : 1.5

After 3 coming:
minHeap: 1
maxHeap: 2 3
median : 2

After 4 coming:
minHeap: 1 2
maxHeap: 3 4
median : 2.5

After 5 coming:
minHeap: 1 2
maxHeap: 3 4 5
median : 3

Codes:

	public static class maxComparator implements Comparator<Double> {
		public int compare(Double o1, Double o2) {
			return -o1.compareTo(o2);
		}
	}

	static PriorityQueue<Double> minHeap = new PriorityQueue<Double>(11,
			new maxComparator());
	static PriorityQueue<Double> maxHeap = new PriorityQueue<Double>();

	public static void addToHeap(double number) {
		if (minHeap.size() == maxHeap.size()) {
			if (minHeap.isEmpty())
				minHeap.add(number);
			else if (number > minHeap.peek())
				maxHeap.add(number);
			else { // number < minHeap.peek()
				maxHeap.add(minHeap.poll());
				minHeap.add(number);
			}
		} else if (minHeap.size() > maxHeap.size()) {
			if (number > minHeap.peek())
				maxHeap.add(number);
			else { // number <= minHeap.peek()
				maxHeap.add(minHeap.poll());
				minHeap.add(number);
			}
		} else { // minHeap.size() < maxHeap.size()
			if (number < maxHeap.peek())
				minHeap.add(number);
			else { // number >= maxHeap.peek()
				minHeap.add(maxHeap.poll());
				maxHeap.add(number);
			}
		}
	}

	public static double getMedian() {
		if (minHeap.size() == maxHeap.size())
			return (minHeap.peek() + maxHeap.peek()) / 2;
		else if (minHeap.size() > maxHeap.size())
			return minHeap.peek();
		else
			return maxHeap.peek();
	}

Search a long string for small strings in an array

Given a string s and an array of smaller strings T, design a method to search s for each small string in T.

Thoughts:
We can first get all the suffices of s and check for each element t in T to see if t is the beginning part of any suffices. To make this more efficient, we acn build a suffix tree and do the operations.
For example, s = “mississippi”; T = { “is”, “sip”, “hi”, “sis” }. The suffices of s are: [0] -> “mississippi”, [1] -> “ississippi”, [2] -> “ssissippi”, [3] -> “sissippi”, [4] -> “issippi”, [5] -> “ssippi”, [6] -> “sippi”, [7] -> “ippi”, [8] -> “ppi”, [9] -> “pi” and [10] -> “i”. Then for “is” in T, we see it sits in the beginning of suffices [1] and [4]. for “sip”, we see it in [6]. We do not see any “hi” in the suffices but we do see “sis” in [3].

Codes:

	public static class SuffixTree {
		SuffixTreeNode root = new SuffixTreeNode();

		public SuffixTree(String s) {
			for (int i = 0; i < s.length(); ++i) {
				root.insert(s.substring(i), i);
			}
		}

		public List<Integer> getIndexes(String s) {
			return root.getIndices(s);
		}
	}

	public static class SuffixTreeNode {
		private char c;
		private List<Integer> indices = new ArrayList<Integer>();;
		private Map<Character, SuffixTreeNode> children = 
			new HashMap<Character, SuffixTreeNode>();

		public void insert(String s, int index) {
			indices.add(index);
			if (s != null && s.length() > 0) {
				char character = s.charAt(0);
				if (children.keySet().contains(character)) {
					children.get(character).insert(
							s.substring(1), index);
				} else {
					SuffixTreeNode child = new SuffixTreeNode();
					children.put(character, child);
					child.insert(s.substring(1), index);
				}
			}
		}

		public List<Integer> getIndices(String s) {
			if (s == null || s.length() == 0)
				return indices;
			else {
				char character = s.charAt(0);
				if (children.containsKey(character))
					return children.get(character).getIndices(
							s.substring(1));
				else
					return null;
			}
		}
	}

Longest word made of other words in an array

Write a program to find the longest word made of other words.
EXAMPLE
Input: test, tester, testertest, testing, testingtester
Output: testingtester

Thoughts:

  1. Sort the array according to the length of the string. Longest first.
  2. Starting from the beginning of the resulted array, i.e., the longest string, for each word in the array:
    1. for each of the following word otherWord in the array, processing in order, i.e., from the longest to the shortest
    2. if word contains otherWord, delete otherWord from word and keep searching towards even shorter string.
    3. if at any step word becomes empty, meaning that it can be divided into several shorter words in the array, we should return it since that’s exactly what we wish to find.

Codes:

	public static class LengthComparator implements Comparator<String> {
		public int compare(String o1, String o2) {
			if (o1.length() < o2.length())
				return 1;
			else if (o1.length() > o2.length())
				return -1;
			else
				return 0;
		}
	}

	public static String longestWordMadeOfOtherWords(String[] words) {
		Arrays.sort(words, new LengthComparator());
		for (String word : words) {
			String backup = new String(word);
			for (String otherWord : words) {
				if (!otherWord.equals(backup) && word.contains(otherWord)) {
					word = word.replace(otherWord, "");
				}
			}
			if (word.length() == 0)
				return backup;
		}
		return null;
	}

Find largest 1M numbers in 1B numbers

Describe an algorithm to find the largest 1 million numbers in 1 billion numbers. Assume that the computer memory can hold all one billion numbers.

Thoughts:
We can certainly sort those numbers and return the last 1 million of them. That takes O(n\log n).
If we think about it, we actually do not need to sort them. After all, we just need the largest 1 million numbers, in whatever orders. Therefore we can sort of “partially” sort the numbers and try to find the parts that we need. To do this, we get inspiration from Quicksort, where we get two partitions around pivot during each run:

[elements < pivot][elements >= pivot]

For simplicity, Let us denote the number of elements in the right part as m.
If m is exactly equal to 1 million, we have found the largest 1 million numbers!
If m is larger than 1 million, we need to keep looking for the 1 million numbers, but in the left part of the array this time. We can do this in a recursive way.
If m is less than 1 million, we first remember those m numbers and then we search for the largest (1 million – m) numbers in the left part of the array. Again, recursion here.
Using the random pivot choosing approach, this algorithm takes O(n) time complexity and it does not need any additional space since we can do the partition in place.

Codes:

	public static int quickPartition(int[] array, int low, int high) {
		if (high <= low)
			return -1;

		// randomly choose a pivot
		int index = new Random().nextInt(high - low + 1) + low;
		int pivot = array[index];

		// swap the pivot to the front
		int num = array[index];
		array[index] = array[low];
		array[low] = num;

		// partition as in Quicksort
		int L = low + 1;
		int R = high;

		while (R >= L) {
			while (R >= L && array[L] < pivot)
				L++;
			while (R >= L && array[R] >= pivot)
				R--;
			if (R >= L) {
				int temp = array[L];
				array[L] = array[R];
				array[R] = temp;
				L++;
				R--;
			}
		}

		// swap the pivot back to appropriate position.
		num = array[R];
		array[R] = array[low];
		array[low] = num;

		return R;
	}

	public static List<Integer> largestM(int[] numbers, int M, int low, int high) {
		// RIndex = index of pivot
		int RIndex = quickPartition(numbers, low, high);
		// mFound = # of the largest numbers
		int mFound = high + 1 - RIndex;

		List<Integer> results = new LinkedList<Integer>();

		if (mFound == M) { // Done!
			int i = RIndex;
			for (; i <= high; ++i)
				results.add(numbers[i]);
			return results;

		} else if (mFound > M) { // Keep looking
			// check if those mFound elements are actually the same
			boolean duplicates = true;
			for (int i = RIndex; i <= high; ++i) {
				if (numbers[i] != numbers[RIndex])
					duplicates = false;
			}

			if (!duplicates)
				return largestM(numbers, M, RIndex, high);
			else {
				// if they are the same, just return M duplicates of them
				for (int k = 0; k < M; ++k)
					results.add(numbers[RIndex]);
				return results;
			}
		} else { // Has found some, keep looking for the rest
			int i = RIndex;
			for (; i < numbers.length; ++i)
				results.add(numbers[i]);

			results.addAll(largestM(numbers, M - mFound, low, RIndex - 1));
			return results;
		}

	}

Previous Older Entries