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
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 F-S.
Say there is a loop starting at the B-th node (B>=1), and the loop size is L >= 1 (self-loop 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 i-th 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])
The following Java code only requires 1-pass 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;
}
Complexity analysis for n-by-n 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 non-square 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-(n-1), 0);
int col = Math.min(i, n-1);
while (row < m && col >=0) {
System.out.print(matrix[row++][col--] + " ");
}
}
}
}
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 = end-1;
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, left-1);
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
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 K-th 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" == K-1, pivot is the K-th element.
3.2 If # "< pivot" < K-1, pick a new pivot in the "> pivot" partition and repeat.
3.3 If # "< pivot" > K-1, 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 column-wise. We can do this:
1. Pick a pivot
2. Start a walk from the top-right of M, move left if current element >= pivot, move down otherwise.
3. The left-most 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] = n-1;
}
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_row-th 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_row-th row
//the scan_row-th 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 K-th element
return pivot;
else if (smallerThanPivot < K - 1) {
/* Current pivot is too small.
* The K-th 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 K-th 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.
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 ill-form 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);
}
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(Amount-Denominations[i], Denominations, i+1);
}
return result;
}
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 i-th 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[end-1], depending if (end-start+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 );
}
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;
}
}
}
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[p1-1][p2] && s1.charAt(p1-1)==s3.charAt(p1+p2-1) )
|| ( p2 > 0 && DP[p1][p2-1] && s2.charAt(p2-1)==s3.charAt(p1+p2-1) );
}
}
return DP[s1.length()][s2.length()];
}
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;
}
}
Assuming the list doesn't contain duplicates. It's just a simple variation of binary search.
Test Case:
Output:
- chriscow January 31, 2014