Array of products of all other numbers

Given an array A of size N, return another resulting array B of the same size N, where B[i] is the products of all numbers in A except for A[i].
EXAMPLE:
INPUT: A = [1,2,3,4]
OUTPUT: B = [24, 12, 8, 6]

My initial thoughts:
We can first compute the products of everything, in the example, this is 1*2*3*4 = 24. Then for each element in the resulting array, we divide the total products by that element in the original array, that is: 24 = 24/1; 12 = 24/2; 8 = 24/3; 6 = 24/4. We need to be careful with the edge cases: where there are zero(s). We cannot divide by zero. Hence, we modify the algorithm. We first compute the products of non-zeros and count the number of zeros in A. Then for position i in B, if A[i]=0, we check if there are at least 2 zeros, if yes, B[i]=0. If not, B[i] should be equal to the products of non-zeros. If A[i]\ne0, we check if there is at least 1 zero, if yes, B[i]=0. Otherwise, B[i] is the product of non-zeros divided by $A[i]$.

Codes:

public static long[] getArrayOfProducts(int[] original) {
        int zeroCounts = 0;
        long products = 1;
        for(int number : original) {
            if(number == 0)
                zeroCounts++;
            else
                products *= number;
        }
        
        long[] result = new long[original.length];
        for(int i = 0; i < result.length; ++i) {
            if(original[i] == 0) {
                if(zeroCounts > 1)
                    result[i] = 0;
                else
                    result[i] = products;
            } else if(zeroCounts > 0) {
            	result[i] = 0;
            } else {
                result[i] = products / original[i];
            }
        }
        
        return result;
    }

Better Solution:
According to the post here:

public static long[] getArrayOfProducts2(int[] original) {
    	long[] results = new long[original.length];
    	results[0] = 1;
    	for(int i = 1; i < original.length; ++i) {
    		results[i] = results[i-1]*original[i-1];
    	}
    	
    	long temp = 1;
    	for(int i = results.length - 1; i >= 0; --i) {
    		results[i] *= temp;
    		temp *= original[i];
    	}
    	return results;
    }

Notice:
If the product is too large so that we hit integer/long overflow, we need to handle that, probably by introducing additional variables to store temporary products.

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

Previous Older Entries