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

	}

Shortest distances between two words in a file

You have a large text file containing words. Given any two words, find the shortest distance (in terms of number of words) between them in the file. Can you make the searching operation in O(1) time? What about the space complexity for your solution?

My initial thoughts:
We can build and store the mapping between pairs of words to their shortest distance. That is O(n^2) space complexity. But the query is constant since it’s just one step of look-up.

My initial codes:

	private static Map<HashSet<String>, Integer> distances = 
			new HashMap<HashSet<String>, Integer>();

	public static int query(String word1, String word2) {
		return distances.get(new Pair<String>(word1, word2));
	}

	public static void buildMap(String text) {
		// clean up the text
		String[] temp = text.split("[\\s\\p{Punct}]");
		List<String> words = new ArrayList<String>();
		for (String word : temp) {
			word = word.trim();
			if (!word.isEmpty()) {
				words.add(word);
			}
		}

		// build the mapping between pairs of words to
		// their shortest distances
		for (int i = 0; i < words.size(); ++i) {
			for (int j = i + 1; j < words.size(); ++j) {
				if (!words.get(i).equals(words.get(j))) {
					HashSet<String> pair = new HashSet<String>();
					pair.add(words.get(i));
					pair.add(words.get(j));
					if (distances.keySet().contains(pair)) {
						int curr = distances.get(pair);
						if (j - i < curr)
							distances.put(pair, j - i);
					} else {
						distances.put(pair, j - i);
					}
				}
			}
		}
	}

Solution:
Please refer to the book: Cracking the Coding Interview.
Another way to solve this is by:

  1. Pre-processing: Store the locations for different words in a hashtable. One scan of the text: O(n) time complexity. Approximately O(n) space complexity.
  2. Query: Modified binary search. For example, query is (hello, world). Lookup in the hashtable we have “hello” -> [1,2] and “world” -> [5,8,9]. We search 1 in [5,8,9] to find the nearest, which is 5. So the distance is 4. We search 2 in [5,8,9] to find the nearest, which is 5 again, yielding distance 3, less than 4. So the shortest distance between “hello” and “world” is 3. In practice, number of locations for a word is relatively small comparing to the size of the text, hence the cost of query/search is nearly constant.

Implementation of the modified binary search:

	private static Map<String, ArrayList<Integer>> locations = new HashMap<String, ArrayList<Integer>>();

	private static void storeLocations(String[] text) {
		for (int i = 0; i < text.length; ++i) {
			String word = text[i];
			if (locations.keySet().contains(word)) {
				ArrayList<Integer> location = locations.get(word);
				location.add(i);
				Collections.sort(location);
				locations.put(word, location);
			} else {
				ArrayList<Integer> location = new ArrayList<Integer>();
				location.add(i);
				locations.put(word, location);
			}
		}
	}

	private static int modified_binary_search(ArrayList<Integer> array,
			int target) {
		int low = 0;
		int high = array.size();
		while (low < high) {
			int mid = low + (high - low) / 2;
			if (target == array.get(mid))
				return target;
			if (target < array.get(mid))
				high = mid;
			else
				low = mid + 1;
		}
		if (low >= 0 && low < array.size())
			return array.get(low);
		else
			return array.get(array.size() - 1);
	}

	private static int shortest_distance(String a, String b) {
		int min = Integer.MAX_VALUE;
		for (int index_a : locations.get(a)) {
			ArrayList<Integer> array = locations.get(b);
			int nearest_index_b = modified_binary_search(array, index_a);
			int distance = Math.abs(nearest_index_b - index_a);
			if (distance < min)
				min = distance;
		}
		return min;
	}

Count the number of 2s between 0 and n

Write a method to count the number of 2s between 0 and n.

My initial thoughts:
We need recursion. For a number, we split it into two parts: the MSB and the reminder. For example, 319 has MSB of 3 and reminder of 19.

  1. Count the number of 2s for MSB:
    1. If MSB > 2: We will have 1 or 10 or 100 or 1000, etc 2s. In this case of 319, we have 100 2s (occurring at MSB from 200 to 299).
    2. If MSB == 2: We will have reminder+1 2s. For example if we have n = 219, we have 20 2s (occurring at MSB from 200 to 219).
  2. Count the number of 2s for reminder, two parts:
    1. Recursively count the number of 2s for the tens. For example of n = 319, we’d like to recursively count number of 2s from 1 to 100. We then know we have 3 times that number of 2s. This is like: we know number 12 has a 2, so we know number 12, 112 and 212 have three 2s.
    2. Count the number of 2s causing from the reminder. For example of n = 319, we’d like to recursively count number of 2s from 1 to 19. That counts for the number of 2s appearing from 301 to 319.

My initial codes:

	// Take n = 319 as example
	public static int numberOf2s(int n) {
		if (n < 2)
			return 0;

		int result = 0;
		int power10 = 1;
		while (power10 * 10 < n) {
			power10 *= 10;
		}
		// power10 = 100
		int msb = n / power10; // 3
		int reminder = n % power10; // 19

		// Count # of 2s from MSB
		if (msb > 2)
			// This counts the first 2 from 200 to 299
			result += power10;
		if (msb == 2)
			// If n = 219, this counts the first 2
			// from 200 to 219 (20 of 2s).
			result += reminder + 1;

		// Count # of 2s from reminder
		// This (recursively) counts for # of 2s from 1 to 100
		// msb = 3, so we need to multiply by that.
		result += msb * numberOf2s(power10);
		// This (recursively) counts for # of 2s from 1 to reminder
		result += numberOf2s(reminder);

		return result;
	}

Randomly generate m integers from an array of size n

Write a method to randomly generate a set of m integers from an array of size n Each element must have equal probability of being chosen.

My initial thoughts:
Maintain the following loop: randomly select an element from the right part and swap it with the i-th element from 0 to m at the left part. Output the first m element in the array.

My initial codes:

	public static int[] chooseNFromM(int[] array, int m) {
		if (m > array.length)
			return null;
		int[] results = new int[m];
		for (int i = 0; i < m; ++i) {
			int index, temp;
			do {
				index = new Random().nextInt(array.length);
			} while (index < i);
			temp = array[index];
			array[index] = array[i];
			array[i] = temp;
		}
		for (int i = 0; i < m; ++i) {
			results[i] = array[i];
		}
		return results;
	}

Solution:
Please refer to the book: Cracking the Coding Interview.
Comments:

  1. We don’t need to keep generating random numbers. We just need to label which ones are ‘dead’ (in this case, 0 to i) and generate random index in the valid range (i+1 to n).
  2. We should first make an copy of the original array as we don’t want to modify it.

Previous Older Entries