chriscow
BAN USERI used a trie to store the dictionary.
setup is just ordinary routine of building a trie.
isMatch is similar to the ordinary lookup in trie, with addition to check for wildcard '.' in both words in dict as well as the word in query.
public class wildCardMatchList {
private class trieNode {
HashMap<Character, trieNode> children;
boolean wordEnd;
public trieNode() {
children = new HashMap<Character, trieNode>();
wordEnd = false;
}
}
private trieNode root;
public void setup(String[] dict) {
this.root = new trieNode();
this.root.wordEnd = true; // for empty string
for (String word:dict) {
add(this.root, word);
}
}
public boolean isMatch(String word) {
return match(this.root, word);
}
private void add(trieNode parent, String word) {
if (word.isEmpty()) {
parent.wordEnd = true;
return;
}
char letter = word.charAt(0);
String surfix = word.substring(1);
trieNode child = null;
if (!parent.children.containsKey(letter))
child = new trieNode();
add(child, surfix);
parent.children.put(letter, child);
}
private boolean match(trieNode parent, String word) {
if (word.isEmpty()) return parent.wordEnd;
char letter = word.charAt(0);
String surfix = word.substring(1);
if (letter != '.') {
if (parent.children.containsKey(letter) && match(parent.children.get(letter), surfix)) return true;
if (parent.children.containsKey('.') && match(parent.children.get('.'), surfix)) return true;
}
else { // letter == '.'
for (trieNode child : parent.children.values())
if (match(child, surfix)) return true;
}
return false;
}
public static void main(String[] args) {
String[] dict = { "hello", "mi." };
wildCardMatchList list = new wildCardMatchList();
list.setup(dict);
String[] words = {"hello", ".ell.", "hel.a", "hel.", "mix"};
for (String w : words) {
System.out.println(w + " : " + list.isMatch(w));
}
}
}
Test case:
dict = { "hello", "mi." }
Output:
hello : true
.ell. : true
hel.a : false
hel. : false
mix : true
... : true
.... : false
..... : true

chriscow
January 31, 2014 Say in each step, the fast pointer moves F nodes ahead and the slow pointer moves S nodes. So in each step, the distance between the two pointers increases by FS.
Say there is a loop starting at the Bth node (B>=1), and the loop size is L >= 1 (selfloop is OK). If it takes N steps to detect the loop, we should have
N >= B and (F  S) * N % L == 0
This is easy to see that
N = L * K / ( F  S )
where K is the smallest number such that L * K >= B and L * K % ( F  S ) == 0.
Then the total cost for detecting a loop can be formulated as
( F + S ) * N = L * K * ( F + S ) / ( F  S )
subject to L * K >= B and L * K % ( F  S ) == 0
Now consider the case when L and F  S are mutually prime and the loop starts at the head of the list. In this case, we need at least K = F  S to satisfy L * K % ( F  S ) == 0. Then the cost becomes
L * ( F + S )
So we should pick the smallest F and S possible to reduce cost. So F = 2 and S = 1 is the best choice.
 chriscow January 31, 2014For those boxes that canBePicked == false, we can just ignore them.
Now consider only the the boxes that canBePicked == true. Say their weights are
w[1], w[2], w[3], ......
At step i, totalWeight = w[1]+...+w[i] and curWeight = w[i]. So it's obvious that
Prob(box i is picked at step i) = w[i]/(w[1]+...+w[i])
This is true for all i.
Suppose there are n boxes (canBePicked) in total, in order to return the ith box at the end, we need:
1. box i is picked at step i, AND
2. box j is NOT picked at step j for all j>i. So the probability of returning box i is
Prob(box i is picked at step i)
* Prob(box i+1 is NOT picked at step i+1)
* Prob(box i+2 is NOT picked at step i+2)
......
* Prob(box n is NOT picked at step n)
=
Prob(box i is picked at step i)
* ( 1  Prob(box i+1 is picked at step i+1) )
* ( 1  Prob(box i+2 is picked at step i+2) )
......
* ( 1  Prob(box n is picked at step n) )
= w[i]/(w[1]+...+w[i]) * ( 1  w[i+1]/(w[1]+...+w[i+1]) )* ( 1  w[i+2]/(w[1]+...+w[i+2] ) * ... * ( 1  w[n]/(w[1]+...+w[n]))
= w[i]/(w[1]+...+w[n])

chriscow
January 29, 2014 The following Java code only requires 1pass scan through the boxArray. The same idea also works to pick a random node in a linked list in 1 pass without first knowing the size of the list.
public Box pickRandomBox(Box[] boxArray) {
Box picked = null;
double totalWeight= 0;
for (Box box : boxArray) {
if (!box.canBePicked()) continue;
int curWeight = box.getWeight();
totalWeight += curWeight;
if (Math.random() <= curWeight/totalWeight) picked = box;
}
return picked;
}

chriscow
January 29, 2014 Complexity analysis for nbyn matrix:
Just like in QuickSelect, with good pivots, it will take O(log(n^2)) = O(logn) recursions. In each recursion, it takes O(nlogn) to find the new pivot using PriorityQueue (essentially doing heapsort), and O(n) for partitioning the matrix with the pivot.
So complexity is O(n^2 logn).
The following code also works for nonsquare matrix
public void printMatrixAntiDiag(int[][] matrix) {
if (matrix.length > 0 && matrix[0].length > 0) {
int m = matrix.length, n = matrix[0].length;
int layer = m + n  1;
for (int i = 0; i < layer; i++) {
int row = Math.max(i(n1), 0);
int col = Math.min(i, n1);
while (row < m && col >=0) {
System.out.print(matrix[row++][col] + " ");
}
}
}
}

chriscow
January 29, 2014 This is my java code for quicksort
public class QuickSort {
public static void quickSort(int[] arr, int start, int end) {
if (start >= 0 && end < arr.length && start < end) {
int pivot = arr[start];
swap(arr, start, end);
int left = start, right = end1;
while (left < right) {
while (left < arr.length && arr[left] < pivot ) left++;
while (right >= 0 && arr[right] > pivot) right;
if (left < right) swap(arr, left++, right);
}
if (arr[left] > pivot) swap(arr, left, end);
quickSort(arr, start, left1);
quickSort(arr, left+1, end);
}
}
private static void swap(int[] arr, int p, int q) {
int tmp = arr[q];
arr[q] = arr[p];
arr[p] = tmp;
}
}
Test case:
1, 2, 1, 6, 4, 5 > 1, 1, 2, 6, 4, 5
5, 4, 3, 2, 1 > 1, 2, 3, 4, 5

chriscow
January 28, 2014 By "Sorted 2D array", it usually only means that each row and column is sorted! It only means:
matrix[i][j] <= matrix[i][j+1] and matrix[i][j] <= matrix[i+1][j]
That's it! Nothing more! Otherwise the question is just way toooooooooooooooo trivial to be an Amazon interview question.
Educate yourself about "Young Tableau" on wikipedia.
We can do something similar to the QuickSelect approach for finding the Kth smallest element of an unsorted 1D array. In QuickSelect:
1. Pick a pivot
2. Partition the 1D array into "< pivot" and "> pivot"
3.1 If # "< pivot" == K1, pivot is the Kth element.
3.2 If # "< pivot" < K1, pick a new pivot in the "> pivot" partition and repeat.
3.3 If # "< pivot" > K1, pick a new pivot in the "< pivot" partition and repeat.
With random pivot, the mean complexity is O(n) in an array of size n.
For this problem, given matrix M[][] of m rows and n columns, sorted both row and columnwise. We can do this:
1. Pick a pivot
2. Start a walk from the topright of M, move left if current element >= pivot, move down otherwise.
3. The leftmost element in each row visited in step 2 partitions M into "< pivot" and "> pivot". Pick the new pivot similar to the 1D case.
Here is my complete Java code:
import java.util.PriorityQueue;
public class kSelect2DMatrix {
public static int kSmallest2D (int[][] matrix, int K) {
assert ( matrix.length > 0 && matrix[0].length > 0) : "Empty matrix!";
int m = matrix.length, n = matrix[0].length;
int scan_row, scan_col;
int pivot, smallerThanPivot;
/* Use two arrays to keep track of
* the left and right boundaries (inclusive) of the candidates in each row
*/
int[] left = new int[m];
int[] right = new int[m];
for (int i = 0; i<m; i++) {
left[i] = 0;
right[i] = n1;
}
while (true) {
pivot = getPivot(matrix, left, right);
scan_row = 0;
scan_col = n  1;
smallerThanPivot = 0;
//Keep track of the last element < pivot (starting from left) in each row
int[] lastSmallerThanPivot = new int[m];
for (int i = 0; i < m; i++) lastSmallerThanPivot[i] = 1;
while (scan_row < m && scan_col >= 0) {
if ( matrix[scan_row][scan_col] >= pivot ) scan_col; //move left
else {
//scan_col+1 elements in the scan_rowth row are smaller than pivot
lastSmallerThanPivot[scan_row] = scan_col ;
scan_row++; //move down
}
}
//if exit the inner while loop with scan_col < 0 in the scan_rowth row
//the scan_rowth row and the rows below have no element smaller than pivot
for (int i = 0; i < m; i++) smallerThanPivot += (lastSmallerThanPivot[i] + 1);
if (smallerThanPivot == K  1)
//found the Kth element
return pivot;
else if (smallerThanPivot < K  1) {
/* Current pivot is too small.
* The Kth element cannot be to the elements <= lastSmallerThanPivot[i] in row i
* Update left boundary.
*/
for (int i = 0; i < m; i++) left[i] = Math.max(left[i], lastSmallerThanPivot[i]+1);
}
else {
/* Current pivot is too large.
* The Kth element cannot be to the elements > lastSmallerThanPivot[i] in row i
* Update right boundary.
*/
for (int i = 0; i < m; i++) right[i] = Math.min(right[i], lastSmallerThanPivot[i]);
}
}
}
public static int getPivot(int[][] matrix, int[] left, int[] right) {
PriorityQueue<Integer> queue = new PriorityQueue<Integer>();
for (int i = 0; i < left.length; i++) {
if (left[i] < matrix[0].length) queue.add(matrix[i][left[i] + (right[i]  left[i]) / 2]);
}
int qSize = queue.size(), pivot=0;
for (int i = 0; i <= qSize/2; i++) pivot = queue.poll();
return pivot;
}
public static void main(String[] args) {
int[][] matrix = {{1, 2, 3}, {4, 6, 7}, {5, 8, 9}};
System.out.println(kSmallest2D(matrix, 5));
}
}
Test case:
matrix =
1, 2, 3
4, 6, 7
5, 8, 9
K = 5
Output = 5.
matrix =
1, 2, 3
4, 5, 6
7, 8, 9
K = 5
Output = 5.

chriscow
January 27, 2014 This code assumes there is only one root in the tree formed with the given set of edges.
If the input edges form more than one tree, extra care should be taken.
public TreeNode buildTree (int[][] edges) {
// Check for illform input
if (edges.length == 0  edges[0].length != 2) return null;
HashMap<Integer, TreeNode> nodes = new HashMap<Integer, TreeNode>();
int root = edges[0][0];
TreeNode parent, child;
for (int i = 0; i < edges.length; i++) {
for (int j = 0; j<1; j++)
if ( !nodes.containsKey(edges[i][j]) )
nodes.add(edges[i][h], new TreeNode(edges[i][j]));
parent = nodes.get(edges[i][0]);
child = nodes.get(edges[i][1]);
if (parent.left == null) parent.left = child;
else {
assert parent.right == null : "A node has more than 2 children. NOT VALID BINARY TREE!";
parent.right = child;
}
root = (root == edges[i][1]) ? edges[i][0]:root;
}
return nodes.get(root);
}

chriscow
January 27, 2014 public int makeChange(int Amount, int[] Denominations) {
return makeChange_using_K_and_After(Amount, Denominations, 0);
}
public int makeChange_using_K_and_After(int Amount, int[] Denominations, int K) {
if (Amount < 0  K >= Denominations.length ) return 0;
if (Amount == 0) return 1;
int result = 0;
for (int i = K; i < Denominations.length; i++) {
result += makeChange_using_K_and_After(AmountDenominations[i], Denominations, i+1);
}
return result;
}

chriscow
January 27, 2014 Consider target is 5 and the tree is
5
/ \
1 10
/ \
6 11
currNode = root to start with. Now let me walk through the iteration for you:
1. currNode = 5 == target, so currNode = currNode.right = 10.
2. currNode = 10 > target = 5, so candidate = 10 and currNode = currNode.left = 6.
3. currNode = 6 > target = 5, so candidate = 6 and currNode = currNode.left = null.
4. currNode = null. Exit while loop.
Please make sure you understand what is a BST.
Binary search won't work in this problem.
The catch is that there the target value can be in the range of multiple rows or columns.
Take the example with looking for x=12 in the following matrix:
1, 2, 3, 4, 5
6, 10, 20, 30, 40
7, 11, 21, 31, 41
8, 12, 22, 32, 42
9, 13, 23, 33, 43
You have 4 rows and 4 columns that can potentially contain 12. Which row and column should you continue the iteration in binary search?
 chriscow January 26, 2014Once you add that line, the complexity becomes O(mn) with m being the length of the 2nd string. Basically, at ith position of str1, you check
if (str1.charAt(i+j) == str2.charAt(j))
for j=0 to str2.length()1. If it passes, you get the answer. But if it fails, you move to the (i+1)position and start all over again.
 chriscow January 25, 2014If the question is really just to find the min and max in a[25],...,a[75], I don't see the point of specifying the start and end locations instead of just finding the min and max in the whole array. I think we need some clarification.
Anyway, if it is really just to find the min and max, here is a slightly better way to do it:
public void findMinMax(int[] array, int start, int end) {
if (start < 0  end >= array.length  start > end)
System.out.println("Invalid inputs");
else {
int tmpMin, tmpMax;
int min = end;
int max = end;
// for loop checks even number of entries starting from array[start],
// up to array[end] or array[end1], depending if (endstart+1)%2==0 or not
for (int i = start; i < end; i+=2) {
if (array[i] <= array[i+1]) {
tmpMin = i;
tmpMax = i+1;
}
else { // array[i] > array[i+1]
tmpMin = i+1;
tmpMax = i;
}
min = ( array[min] <= array[tmpMin] ) ? min : tmpMin;
max = ( array[max] >= array[tmpMax] ) ? max : tmpMax;
}
System.out.println("Min = " + Integer.toString(array[min]) + " at index " + Integer.toString(min));
System.out.println("Max = " + Integer.toString(array[max]) + " at index " + Integer.toString(max));
}
}
It takes 3 comparisons for every 2 array entries, while the naive solution takes 2 comparisons for every entry.
 chriscow January 25, 2014I assume b is integer.
Java code:
public double power(double a, int b) {
// Base case with 0 exponent
if (b == 0) return 1;
// Negative exponent
if (b < 0) {
assert a != 0; // Negative exponent for base 0 is not allowed
return 1. / power(a, b);
}
// General case of positive exponent
double half = power(a, b / 2);
return half * half * ( (b % 2 == 1) ? a : 1 );
}

chriscow
January 25, 2014 If the program is going to be used only once. What the tip suggests is good enough. Taking O(nm) time, where n is the length of the longer string and m is the length of the shorter one.
If it is going to be used many times for checking different substrings, first build the surffix tree of the long string. Then checking a substring of length m only takes O(m) time.
/**
* Definition for binary tree with next pointer.
* public class TreeLinkNode {
* int val;
* TreeLinkNode left, right, next;
* TreeLinkNode(int x) { val = x; }
* }
*/
public class Solution {
public void linkSibling(TreeLinkNode root) {
TreeLinkNode currhead = root;
while (currhead!=null) {
while (currhead!=null && currhead.left==null && currhead.right==null)
currhead = currhead.next;
TreeLinkNode dummy = new TreeLinkNode(0);
TreeLinkNode tail = dummy;
while (currhead!=null) {
if (currhead.left!=null) {
tail.next = currhead.left;
tail = tail.next;
}
if (currhead.right!=null) {
tail.next = currhead.right;
tail = tail.next;
}
currhead = currhead.next;
}
currhead = dummy.next;
}
}
}

chriscow
January 24, 2014 Java DP solution
public boolean isInterleave(String s1, String s2, String s3) {
if ( (s1.length()+s2.length()) != s3.length() ) return false;
boolean[][] DP= new boolean[s1.length()+1][s2.length()+1];
//base case: an empty string is always the interleave of two other empty string
for (int p1 = 0; p1 <= s1.length(); p1++) {
for (int p2 = 0; p2 <= s2.length(); p2++) {
DP[p1][p2] = ( p1==0 && p2==0 ) //Base case of 2 empty strings
 ( p1 > 0 && DP[p11][p2] && s1.charAt(p11)==s3.charAt(p1+p21) )
 ( p2 > 0 && DP[p1][p21] && s2.charAt(p21)==s3.charAt(p1+p21) );
}
}
return DP[s1.length()][s2.length()];
}

chriscow
January 24, 2014 A basic inorder traversal can solve the problem as other posters have pointed out. But it is wasteful. In the case the target is in the right subtree of the root, traversing the whole left subtree is useless.
In fact, a modified binary search is more suitable here. Notice that
successor = the smallest node larger than target
Finding the first entry larger than target in a sorted array is a simple variation of binary search in a sorted array. Here we can use a similar idea for binary search in BST.
During the binary search in BST, there are two cases:
1. if currNode <= target, the successor must be in the right subtree. Continue the binary search in the right subtree.
2. if currNode > target, two possibilities here: successor is also in the left subtree, or currNode is the successor if target is the largest in the subtree. Memorize currNode as the candidate for successor. It will be overwritten if target is in the left subtree of some other node further down.
When return, pay attention to the two corner cases when the successor doesn't not exist:
1. target cannot be found in the tree;
2. target is the largest in the tree, so it has no inorder successor.
Here is my Java implementation.
public class inorderSuccessor {
public static TreeNode iterativeSolution(TreeNode root, TreeNode target) {
if (root == null  target == null) return null;
boolean targetFound = false;
TreeNode currNode = root, candidate=null;
while (currNode != null) {
if (currNode.val == target.val) {
targetFound = true;
currNode = currNode.right;
}
else if (currNode.val > target.val) {
candidate = currNode;
currNode = currNode.left;
}
else {// currNode.val < target.val
currNode = currNode.right;
}
}
return targetFound ? candidate : null;
}
}

chriscow
January 24, 2014
Assuming the list doesn't contain duplicates. It's just a simple variation of binary search.
Test Case:
Output:
 chriscow January 31, 2014