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

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

Worst case time complexity is still $O(n)$ since in the worst case, you need to remove all the “”s.
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;
}

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

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

__ATA.cmd.push(function() {
__ATA.initDynamicSlot({
location: 120,
formFactor: '001',
label: {
},
creative: {
},
privacySettings: {
text: 'Privacy',

}
}
});
});


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

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,
// 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--];
}
}

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:

All of them must be less the smallest element in $B$. So they should still be in the leading positions to maintain the ordering.
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>>();

// same row
for (int k = 0; k < solution[i].length; ++k)
// same column
for (int k = 0; k < solution.length; ++k)

// diagonal
int x = i;
int y = j;
while (++x < solution.length
&& ++y < solution[i].length)
x = i;
y = j;
while (++x < solution.length && --y >= 0)
x = i;
y = j;
while (--x >= 0 && ++y < solution[i].length)
x = i;
y = j;
while (--x >= 0 && --y >= 0)

eightQueenProblem(n - 1, blocks, solution);

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

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

Use of columnForRow[] should be marked. It simplifies 2-D problem to 1-D.
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.



## Number of ways of representing n cents using quarters, dimes, nickels and pennies

Given an infinite number of quarters (25 cents), dimes (10 cents), nickels (5 cents) and pennies (1 cent), write code to calculate the number of ways of representing n cents.

My initial thoughts:

• Base case: $n < 0$. No way to do it.
• Recursion: Represent $n$ by using 1 quarter if possible + # ways of representing $(n-25)$ cents. Or, Represent $n$ by using 1 nickel if possible + # ways of representing $(n-10)$ cents. Or, Represent $n$ by using 1 nickels if possible + # ways of representing $(n-5)$ cents. And we always have 1 way to represent $n$ cents using $n$ pennies.

My initial codes:

	public static int waysOfRepresentingNCents(int n) {
if (n < 0)
return 0;
else {
int ways = 0;
if (n >= 25)
ways += waysOfRepresentingNCents(n - 25);
if (n >= 10)
ways += waysOfRepresentingNCents(n - 10);
if (n >= 5)
ways += waysOfRepresentingNCents(n - 5);
ways += 1;
return ways;
}
}

Logic error.

INPUT: n = 15.
EXPECTED OUTPUT: 6 ways of representing 15 cents
ACTUAL OUTPUT: 7.
PROBLEM: Duplicate counting: 10 + 5 and 5 + 10 are the same way of representing 15 cents but they are counted twice. So we should have ordering.

Solution:
public static int makeChange(int n, int denom) {
int next_denom = 0;
switch (denom) {
case 25:
next_denom = 10;
break;
case 10:
next_denom = 5;
break;
case 5:
next_denom = 1;
break;
case 1:
return 1;
}
int ways = 0;
for (int i = 0; i * denom <= n; i++) {
ways += makeChange(n - i * denom, next_denom);
}
return ways;
}



## Implement the “paint fill” function

Implement the “paint fill” function that one might see on many image editing programs. That is, given a screen (represented by a 2-dimensional array of Colors), a point, and a new color, fill in the surrounding area until you hit a border of that color.

My initial thoughts:

• Base case: the point is at the border. Do nothing.
• Recursion: check the up, down, left and right point to see if we can fill in.

My initial codes (solution):

	public static void paintFillRecur(Color[][] screen,
int x, int y, Color origin, Color toBeFilled) {
if (screen[x][y].equals(origin)) {
screen[x][y] = toBeFilled;

if (x - 1 >= 0)
paintFillRecur(screen, x - 1,
y, origin, toBeFilled);
if (x + 1 < screen.length)
paintFillRecur(screen, x + 1,
y, origin, toBeFilled);
if (y - 1 >= 0)
paintFillRecur(screen, x,
y - 1, origin, toBeFilled);
if (y + 1 < screen[0].length)
paintFillRecur(screen, x,
y + 1, origin, toBeFilled);
}
}



## All valid combinations of n-pairs of parentheses

Implement an algorithm to print all valid (i.e., properly opened and closed) combinations of n-pairs of parentheses.
EXAMPLE:
input: 3 (i.e., 3 pairs of parentheses)
output: ()()(), ()(()), (())(), ((()))

My initial thoughts:
First of all, the output in the example is not correct. It misses this case: (()()).

• Base case: $n=1$, print “()”.
• Recursion: Suppose we have all permutation of %latex n-1\$ parentheses. Then for each permutation, we can insert a pair of parentheses into $2(n-1)+1=2n-1$ positions to create a permutation of $n$ parentheses. Of course, we need to check whether this permutation exists or not.

My initial code:

	public static Set<String> allCombinationsOfParentheses(int n) {
if (n == 1) {
Set<String> result = new HashSet<String>();
return result;
} else if (n > 1) {
Set<String> result = new HashSet<String>();
String parenthesis = "()";
Set<String> subResult = allCombinationsOfParentheses(n - 1);
for (String combination : subResult) {
for (int i = 0; i <= combination.length(); ++i) {
String newCombination = combination.substring(0, i)
+ parenthesis + combination.substring(i);
}
}
return result;
} else {
return null;
}
}

Solution:
We can solve this problem recursively by recursing through the string. On each iteration, we have the index for a particular character in the string. We need to select either a left or a right paren. When can we use left, and when can we use a right paren?

Left: As long as we haven’t used up all the left parentheses, we can always insert a left paren.
Right: We can insert a right paren as long as it won’t lead to a syntax error. When will we get a syntax error? We will get a syntax error if there are more right parentheses than left.

So, we simply keep track of the number of left and right parentheses allowed. If there are left parens remaining, we’ll insert a left paren and recurse. If there are more right parens remaining than left (e.g., if there are more left parens used), then we’ll insert a right paren and recurse.
public static void printPar(int l, int r, char[] str, int count) {
if (l < 0 || r < l)
return; // invalid state
if (l == 0 && r == 0) {
System.out.println(str); // found one, so print it
} else {
if (l > 0) { // try a left paren, if there are some available
str[count] = '(';
printPar(l - 1, r, str, count + 1);
}

if (r > l) { // try a right paren, if there’s a matching left
str[count] = ')';
printPar(l, r - 1, str, count + 1);
}
}
}

public static void printPar(int count) {
char[] str = new char[count * 2];
printPar(count, count, str, 0);
}