Find an element in a matrix whose rows and columns are sorted

Given a matrix in which each row and each column is sorted, write a method to find an element in it.

My initial thoughts:
We are kind-of doing a 2D binary search here. Each time we find the center of the matrix. If that is the element we are looking for, then return it. Notice that the center divide the matrix into four parts: upper-left, upper-right, bottom-left and bottom-right. If the element we are looking for is less than the center, then it cannot be in the bottom-right part, where every elements are even greater than the center. If the element we are searching is greater than the center, then it cannot be in the upper-left part. Hence, each time we approximately eliminate \frac{1}{4} of the entire matrix. Therefore we have the recursion: T(n)=3T(n/4)+O(1), whose solution is O(n)=n^{0.75}.

My initial codes:

	public static Pair<Integer> findInMatrix(int[][] data, int rowLow,
			int rowHigh, int colLow, int colHigh, int element) {
		if (rowLow > rowHigh || colLow > colHigh)
			return null;
		new LinkedList<Pair<Integer>>();
		int rowMid = (rowLow + rowHigh) / 2;
		int colMid = (colLow + colHigh) / 2;
		int mid = data[rowMid][colMid];
		if (mid == element)
			return new Pair<Integer>(rowMid, colMid);
		else if (element < mid) {
			Pair<Integer> topLeft = findInMatrix(data, rowLow, rowMid - 1,
					colLow, colMid - 1, element);
			if (topLeft == null) {
				Pair<Integer> topRight = findInMatrix(data, rowLow, rowMid - 1,
						colMid, colHigh, element);
				if (topRight == null) {
					Pair<Integer> bottomLeft = findInMatrix(data, rowMid,
							rowHigh, colLow, colMid - 1, element);
					return bottomLeft;
				} else
					return topRight;
			} else
				return topLeft;
		} else { // element > mid
			Pair<Integer> topRight = findInMatrix(data, rowLow, rowMid - 1,
					colMid + 1, colHigh, element);
			if (topRight == null) {
				Pair<Integer> bottomLeft = findInMatrix(data, rowMid + 1,
						rowHigh, colLow, colMid, element);
				if (bottomLeft == null) {
					Pair<Integer> bottomRight = findInMatrix(data, rowMid,
							rowHigh, colMid + 1, colHigh, element);
					return bottomRight;
				} else
					return bottomLeft;
			} else
				return topRight;
		}
	}

Solution:
This algorithm works by elimination. Every move to the left (–col) eliminates all the elements below the current cell in that column. Likewise, every move down eliminates all the elements to the left of the cell in that row.

	public static Pair<Integer> FindElem(int[][] mat, int elem, int M, int N) {
		int row = 0;
		int col = N - 1;
		while (row < M && col >= 0) {
			if (mat[row][col] == elem) {
				return new Pair<Integer>(row, col);
			} else if (mat[row][col] > elem) {
				col--;
			} else {
				row++;
			}
		}
		return null;
	}

Comments: Brilliant. Time complexity O(m+n).

Searching in a sorted array of strings with empty strings

Given a sorted array of strings which is interspersed with empty strings, write a method to find the location of a given string.
Example: find “ball” in [“at”, “”, “”, “”, “ball”, “”, “”, “car”, “”, “”, “dad”, “”, “”] will return 4
Example: find “ballcar” in [“at”, “”, “”, “”, “”, “ball”, “car”, “”, “”, “dad”, “”, “”] will return -1

My initial thoughts:
The worst we can do is O(n) where we just do a linear search. I tried to do better in the sense that we do a binary search, however if we encounter “”, we have to exam both sides. In this way, worst case we still do a O(n) search but in average, it’s better off.

My initial codes:

	public static int findLocation(String[] array, int i, int j, String str) {
		int mid;
		while (i <= j) {
			mid = (i + j) / 2;
			if (array[mid].equals("")) {
				int leftIndex = findLocation(array, i, mid - 1, str);
				if (leftIndex == -1)
					return findLocation(array, mid + 1, j, str);
				else
					return leftIndex;
			} else {
				if (str.compareTo(array[mid]) == 0)
					return mid;
				if (str.compareTo(array[mid]) < 0)
					j = mid - 1;
				if (str.compareTo(array[mid]) > 0)
					i = mid + 1;
			}
		}
		return -1;
	}

Solution:

	public static int search(String[] strings, String str, int first, int last) {
		while (first <= last) {
			// Ensure there is something at the end
			while (first <= last && strings[last] == "") {
				--last;
			}
			if (last < first) {
				return -1; // this block was empty, so fail
			}
			int mid = (last + first) >> 1;
			while (strings[mid] == "") {
				++mid; // will always find one
			}
			int r = strings[mid].compareTo(str);
			if (r == 0)
				return mid;
			if (r < 0) {
				first = mid + 1;
			} else {
				last = mid - 1;
			}
		}
		return -1;
	}

	public static int search(String[] strings, String str) {
		if (strings == null || str == null)
			return -1;
		if (str == "") {
			for (int i = 0; i < strings.length; i++) {
				if (strings[i] == "")
					return i;
			}
			return -1;
		}
		return search(strings, str, 0, strings.length - 1);
	}

Comments:

  1. Worst case time complexity is still O(n) since in the worst case, you need to remove all the “”s.
  2. Covers the cases where the target we are looking for is indeed, empty string. Also some error conditions have been handled.

Sorting a 2GB file with one string per line

If you have a 2GB file with one string per line, which sorting algorithm would you use to sort the file and why?

My initial thoughts:
Because 2GB size of strings are way too huge to be put into main memory, I came up with two ways:

  1. K-way merge sort. Divide the file into K pieces, transfer them into main memory and sort them.
  2. Bucket sort. Sort each character in order.

Solution:
When an interviewer gives a size limit of 2GB, it should tell you something – in this case, it suggests that they don’t want you to bring all the data into memory.
So what do we do? We only bring part of the data into memory..
Algorithm:
How much memory do we have available? Let’s assume we have X MB of memory available.

  1. Divide the file into K chunks, where X * K = 2 GB. Bring each chunk into memory and sort the lines as usual using any O(nlogn) algorithm. Save the lines back to the file.
  2. Now bring the next chunk into memory and sort.
  3. Once we’re done, merge them one by one.

The above algorithm is also known as external sort. Step 3 is known as N-way merge.
The rationale behind using external sort is the size of data. Since the data is too huge and we can’t bring it all into memory, we need to go for a disk based sorting algorithm.

Search for an element in a rotated array

Given a sorted array of n integers that has been rotated an unknown number of times, give an O(logn) algorithm that finds an element in the array. You may assume that the array was originally sorted in increasing order.
EXAMPLE:
Input: find 5 in array (15 16 19 20 25 1 3 4 5 7 10 14)
Output: 8 (the index of 5 in the array)

My initial thoughts:
Using the idea of binary search, we can find the breakpoint (e.g. 1 in the input) of the array in O(\log n). Then we divide the original array into two sorted sub-arrays. We can then do regular binary search for both of them in O(\log n). So altogether we still have O(\log n) running time.

My initial codes:

	public static int find(int[] array, int search) {
		int i = 0;
		int j = array.length - 1;
		int mid;
		do {
			mid = (i + j) / 2;
			if (array[mid] < array[mid - 1])
				break;
			else {
				i = mid + 1;
			}
		} while (i <= j);

		int leftIndex = binarySearch(array, 0, 
				mid - 1, search);
		if (leftIndex != -1)
			return leftIndex;
		else
			return binarySearch(array, mid, 
					array.length - 1, search);
	}

	private static int binarySearch(int[] array, 
			int i, int j, int search) {
		int mid;
		do {
			mid = (i + j) / 2;
			if (array[mid] == search)
				return mid;
			else if (array[mid] < search) {
				i = mid + 1;
			} else {
				j = mid - 1;
			}
		} while (i <= j);
		return -1;
	}

Solution:

	public static int search(int a[], int l, int u, int x) {
		while (l <= u) {
			int m = (l + u) / 2;
			if (x == a[m]) {
				return m;
			} else if (a[l] <= a[m]) { // sorted sub-array
				// regular binary search
				if (x > a[m]) {
					l = m + 1;
				} else if (x >= a[l]) { // x might fall
					// before the smallest element
					u = m - 1;
				} else {
					l = m + 1;
				}
			} 
			// implicit condition: a[l] > a[m]
			else if (x < a[m]) // left part
				u = m - 1;
			else if (x <= a[u]) // right part
				l = m + 1;
			else
				u = m - 1;
		}
		return -1;
	}

Comments:
Need to consider all the possible relations of a[l], a[m], a[u] and x.

Sort an array of strings so that anagrams are next to each other

Write a method to sort an array of strings so that all the anagrams are next to each other.

My initial thoughts:
Do a bubble-sort kind sort. Check if two pairs of strings are anagrams or not, if yes, swap.

My initial codes:

	private static boolean areAnagrams(String s1, String s2) {
		if (s1.length() != s2.length() || s1 == null || s2 == null)
			return false;
		s1 = s1.toLowerCase();
		s2 = s2.toLowerCase();
		int[] table = new int[26];
		for (int i = 0; i < s1.length(); ++i) {
			int index = s1.charAt(i) - 'a';
			table[index]++;
		}
		for (int i = 0; i < s2.length(); ++i) {
			int index = s2.charAt(i) - 'a';
			if (table[index] <= 0)
				return false;
			table[index]--;
		}
		for (int i = 0; i < 26; ++i) {
			if (table[i] > 0)
				return false;
		}
		return true;
	}

	private static void swap(String[] strings, int i, int j) {
		String temp = strings[i];
		strings[i] = strings[j];
		strings[j] = temp;
	}

	public static void sortAnagrams(String[] strings) {
		for (int i = 0; i < strings.length - 1; ++i) {
			for (int j = i + 1; j < strings.length; ++j) {
				if (areAnagrams(strings[i], strings[j]))
					swap(strings, i + 1, j);
			}
		}
	}

Comments after running:
It does not guarantee the alphabetical orderings of strings:

  • INPUT: “xyz”, “ca”, “ab”, “ac”, “ba”, “zyx”
  • EXPECTED OUTPUT: “ab”, “ba”, “ac”, “ca”, “xyz”, “zyx”
  • ACTUAL OUTPUT: “xyz”, “zyx”, “ab”, “ba”, “ac”, “ca”

Solution:

	public class AnagramComparator implements Comparator<String> {
		public String sortChars(String s) {
			char[] content = s.toCharArray();
			Arrays.sort(content);
			return new String(content);
		}

		public int compare(String s1, String s2) {
			return sortChars(s1).compareTo(sortChars(s2));
		}
	}

	public static void main(String[] args) {
		String[] strings = { "xyz", "ca", "ab", "ac", "ba", "zyx" };
		AnagramComparator comparator = new AnagramComparator();
		Arrays.sort(strings, comparator);
	}

Merge two sorted arrays

You are given two sorted arrays, A and B, and A has a large enough buffer at the end to hold B. Write a method to merge B into A in sorted order.

My initial thoughts:
This is part of the merge-sort. Denote the size of A as m and size of B as n, then we have a O(m+n) linear algorithm.

My initial codes:

	public static int[] merge(int[] A, int[] B) {
		int i = 0;
		int j = 0;
		int[] merged = new int[A.length + B.length];
		int index = 0;
		while (i != A.length && j != B.length) {
			if (A[i] <= B[j]) {
				merged[index++] = A[i];
				i++;
			} else {
				merged[index++] = B[j];
				j++;
			}
		}
		if (i != A.length) {
			for (int m = i; m < A.length; ++m)
				merged[index++] = A[m];
		}
		if (j != B.length) {
			for (int m = j; m < B.length; ++m)
				merged[index++] = B[m];
		}
		return merged;
	}

Comments after running:
It takes O(m+n) additional space. Plus, I don’t utilize the fact that A has a large enough buffer at the end to hold B.

Solution:

public static void bufferMerge(int[] A, int[] B, 
			int sizeAdata, int sizeB) {
		// Assume sizeAdata + sizeB = A.length
		// i.e., B exactly fits into the buffer at the end of A
		int k = A.length - 1; // Index of last location of array A
		int i = sizeAdata - 1;// Index of last element in array A
		int j = sizeB - 1;// Index of last element in array B

		// Start comparing from the last element and merge A and B
		while (i >= 0 && j >= 0) {
			if (A[i] > B[j]) {
				A[k--] = A[i--];
			} else {
				A[k--] = B[j--];
			}
		}
		while (j >= 0) {
			A[k--] = B[j--];
		}
	}

Comments:
Highlighted line 17. We don’t need to consider the case where j reaches 0 where i is still greater than 0. In that case, it means array A has some leading elements left. Then we don’t need to move them because:

  1. All of them must be less the smallest element in B. So they should still be in the leading positions to maintain the ordering.
  2. As we assume the size of elements in A + size of B = size of A, we don’t have any empty positions. Therefore those elements should be sitting exactly the same positions as before. (We don’t need to shift them to the right)

Eight queen puzzle

Write an algorithm to print all ways of arranging eight queens on a chess board so that none of them share the same row, column or diagonal.

My initial thoughts:

  • Base case: 0 queens to put on the board, then print out the solution.
  • Recursion: put 1 queen in valid position, then put the other n-1 queens.

My initial codes:

	public static void eightQueenProblem(int n, Set<Pair<Integer>> blocks,
			int[][] solution) {
		if (n == 0) {
			for (int i = 0; i < solution.length; ++i) {
				for (int j = 0; j < solution[i].length; ++j)
					System.out.print(solution[i][j]);
				System.out.println();
			}
			System.out.println();
			return;
		} else {
			for (int i = 0; i < solution.length; ++i) {
				for (int j = 0; j < solution[i].length; ++j) {
					if (!blocks.contains(new Pair<Integer>(i, j))) {
						solution[i][j] = 1;

						Set<Pair<Integer>> backup = new HashSet<Pair<Integer>>();
						backup.addAll(blocks);

						// same row
						for (int k = 0; k < solution[i].length; ++k)
							blocks.add(new Pair<Integer>(i, k));
						// same column
						for (int k = 0; k < solution.length; ++k)
							blocks.add(new Pair<Integer>(k, j));

						// diagonal
						int x = i;
						int y = j;
						while (++x < solution.length
								&& ++y < solution[i].length)
							blocks.add(new Pair<Integer>(x, y));
						x = i;
						y = j;
						while (++x < solution.length && --y >= 0)
							blocks.add(new Pair<Integer>(x, y));
						x = i;
						y = j;
						while (--x >= 0 && ++y < solution[i].length)
							blocks.add(new Pair<Integer>(x, y));
						x = i;
						y = j;
						while (--x >= 0 && --y >= 0)
							blocks.add(new Pair<Integer>(x, y));

						eightQueenProblem(n - 1, blocks, solution);

						blocks = backup;
						solution[i][j] = 0;
					}
				}
			}
		}
	}

Comments after running:
Way too many duplicate solutions because there is no ordering of assigning positions.

Solution:

	public static void eightQueenProblem(int row, int[] columnForRow,
			int[][] solution) {
		if (row == 8) {
			for (int i = 0; i < solution.length; ++i) {
				for (int j = 0; j < solution[i].length; ++j) {
					System.out.print(solution[i][j]);
				}
				System.out.println();
			}
			count++;
			System.out.println();
		} else {
			for (int i = 0; i < solution[0].length; ++i) {
				columnForRow[row] = i;
				if (check(row, columnForRow)) {
					solution[row][i] = 1;
					eightQueenProblem(row + 1, columnForRow, solution);
					solution[row][i] = 0;
				}
				columnForRow[row] = -1;
			}
		}
	}

	private static boolean check(int row, int[] columnForRow) {
		for (int i = 0; i < row; ++i) {
			int diff = Math.abs(columnForRow[row] - columnForRow[i]);
			if (diff == 0 || diff == row - i)
				return false;
		}
		return true;
	}

Comments:

  1. Use of columnForRow[] should be marked. It simplifies 2-D problem to 1-D.
  2. It is simply try & error approach with backtracking. It tries to assign position line by line therefore eliminating the duplicate solution. However, solutions are not unique in terms of rotations.

Previous Older Entries