zahidbuet106
BAN USER- 1of 1 vote
AnswersSuppose we are detecting fraud cheques and we found the cheques with the following list of patterns are fraud:
- zahidbuet106 in United States
111122234455
1234
22334455
11111111
234567
etc.
Now if you have a new cheque and wan to detect fraud in O(1) time what data structure you want to use?| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Data Structures - 0of 0 votes
AnswersSuppose a customer buys items for $10 in a shop and the cashier swipe her card at a POS charging $10. Assume that the card has $100 balance before swiping. POS sends the $10 transaction to a machine A in the Amazon cloud. A calls a service to update transaction and card balance, and then sends acknowledgement back to the POS. But the ack got lost in the middle and POS sends another $10 transaction request. How would you make sure that the balance is $90, not $80. And how would you distinguish multiple try with two legitimate $10 transaction back to back.
- zahidbuet106 in United States
Hint: You can't use more than one transaction entry in Database and you don't have the rollback provision.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Database - 0of 0 votes
AnswersGiven a BST and a node, write the BST data structure and a method in Java
- zahidbuet106 in United States
Node findNode(Node n)
that will find the next node of n in the BST. For example, if the tree looks like:
7
/ \
5 11
/ \ /
4 6 9
/ \
2 15
Then,
findNode(2) = 4,
findNode(4) = 5,
findNode(5) = 6
findNode(6)=7
findNode(7)=9
findNode(9)=11
findNode(11)=15
Note that you are not given the root of the tree.
Hint: you may assume that you have parent pointer.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm
There is a better way in O(n) using a DP approach: Let's window size = w and array size = n, n>w.
Observe that the minimum at a position in current window is the minimum of what we would have seen so far and what we will see in future in the current window boundary. So, we can find min so far while traversing from left to right of the current window. But what about min in future? the trick is that we can traverse backwards to get the future min at a position. Also note that: windows separated by elements >=w will have no overlapping and so min so far should be reset at each block of w elements.
So, we will divide the array into [n/w] blocks. We'll keep calculate array's of min: min_so_far by traversing from start to end and min_in_future by traversing from end to start. Reset the min at the boundary of each block in the direction of traversal.
Example: [2,1,3,4,6,3,8,9,10,12,56] w=4
1. partition the array in blocks of size w=4. The last block may have less then w.
2, 1, 3, 4 | 6, 3, 8, 9 | 10, 12, 56|
2. Traverse the list from start to end and calculate min_so_far. Reset min to 0 after each block (of w elements).
min_so_far[] = 2, 1, 1, 1 | 6, 3, 3, 3 | 10, 10, 10
3. Similarly calculate min_in_future by traversing from end to start.
min_in_future[] = 1, 1, 3, 4 | 3, 3, 8, 9 | 10, 12, 56
4. now, min at each position i in current window, sliding_min(i) = min {min_in_future[i], min_so_far[i+w-1]}
sliding_min = 1, 1, 3, 3, 3, 3, 8, ....
public static int[] slidingWindowMin(final int[] in, final int w) {
final int[] min_left = new int[in.length];
final int[] min_right = new int[in.length];
min_left[0] = in[0];
min_right[in.length - 1] = in[in.length - 1];
for (int i = 1; i < in.length; i++) {
min_left[i] = (i % w == 0) ? in[i] : Math.min(min_left[i - 1], in[i]);
final int j = in.length - i - 1;
min_right[j] = (j % w == 0) ? in[j] : Math.min(min_right[j + 1], in[j]);
}
final int[] sliding_min = new int[in.length - w + 1];
for (int i = 0, j = 0; i + w <= in.length; i++) {
sliding_min[j++] = Math.min(min_right[i], min_left[i + w - 1]);
}
return sliding_min;
}
@uuuouou you could do better
1) use parent pointer to find the level of the two nodes. --> O(height) = O(lgn) for balanced tree and O(n) for unbalanced tree.
2) Now, keep two pointers: one pointing to the deeper node and second pointing to the shallower node. Also keep two lists: one for putting the nodes in the path from first node to the lowest common ancestor. Another for putting nodes in the path from second node to LCA node in reverse order (i.e. always insert in front of the list).
3) Move deeper pointer up (one parent each time) for delta=level-level2 times. Also add nodes to the proper list accordingly. --> O(lgn) for balanced tree and O(n) for unbalanced tree.
4) Now, two pointers are leveled. Move up both pointer at the same time up one parent until the pointers hit to the common parent (lca). While going up we already populate first list by the nodes in the path from first node to lca in forward order; and populated 2nd list by the nodes in the path from second node to lca in reverse order. --> O(lgn) for balanced tree and O(n) for unbalanced tree
5) concat second list with first list and voila! we have our answer. --> O(1)
overall complexity is O(lgn) for balanced tree and O(n) for unbalanced tree.
@uuuouou you could do better
1) use parent pointer to find the level of the two nodes. --> O(height) = O(lgn) for balanced tree and O(n) for unbalanced tree.
2) Now, keep two pointers: one pointing to the deeper node and second pointing to the shallower node. Also keep two lists: one for putting the nodes in the path from first node to the lowest common ancestor. Another for putting nodes in the path from second node to LCA node in reverse order (i.e. always insert in front of the list).
3) Move deeper pointer up (one parent each time) for delta=level-level2 times. Also add nodes to the proper list accordingly. --> O(lgn) for balanced tree and O(n) for unbalanced tree.
4) Now, two pointers are leveled. Move up both pointer at the same time up one parent until the pointers hit to the common parent (lca). While going up we already populate first list by the nodes in the path from first node to lca in forward order; and populated 2nd list by the nodes in the path from second node to lca in reverse order. --> O(lgn) for balanced tree and O(n) for unbalanced tree
5) concat second list with first list and voila! we have our answer. --> O(1)
overall complexity is O(lgn) for balanced tree and O(n) for unbalanced tree.
its not possible to make it O(n) and inplace at the same time. Its like heisenberg uncertainty!
@Victor was right. We could use the TreeMap to store the nodes keyed by the value. The time complexity would be O(n) but not in place and will take O(n) space.
I a suspecting the question is a malformed one.
its not O(n) .. O(n2) precisely. Counter example: 5--> 4-->3-->2-->1-->6
- zahidbuet106 May 29, 2014why O(nlgn) ? if the array is sorted and rotated then use binary search to find the element in O(lgn) time.
public static int searchInRotatedArray(final int[] a, final int key) {
final int n = a.length;
if (a[0] == key) {
return 0;
} else if (a[n - 1] == key) {
return n - 1;
}
int l = 0;
int r = n - 1;
int m = 0;
while (l <= r) {
m = (l + r) / 2;
if (a[m] == key) {
return m;
} else if (a[m] < a[l]) {
if (key > a[m] && key <= a[r]) {
l = m + 1;
} else {
r = m - 1;
}
} else {
if (key < a[m] && key >= a[l]) {
r = m - 1;
} else {
l = m + 1;
}
}
}
return -1;
}
Simple binary search with a tweak:
public static int searchFirstOccurance(final int[] a, final int key) {
if (a[0] == key) {
return 0;
}
int l = 0;
int r = a.length - 1;
int m = (l + r) / 2;
int keyPosition = Integer.MAX_VALUE;
while (l <= r) {
m = (l + r) / 2;
if (key == a[m]) {
keyPosition = Math.min(keyPosition, m);
r = m - 1;
} else if (key < a[m]) {
r = m - 1;
} else if (key > a[m]) {
l = m + 1;
}
}
return keyPosition == Integer.MAX_VALUE ? -1 : keyPosition;
}
Let's the size of the alphabet of the dictionary is a constant c. Pickup first c prime numbers from a table of primes and assign each letter a unique prime number. Now, the product of the prime numbers associated with letters of a word will be unique and all anagrams will have same product.
Maintain a Set of words. Go through the dictionary and for each word calculate the prime product of the word. If the prime product is equal to the product of the given word then add the word in the set. The set is the answer we are looking for.
overall time complexity is O(n) if maximum word length is O(1).
here is the simple code. O(n). I assumed english dictionary with 26 letters alphabet.
private static int primes[] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79,
83, 89, 97, 101};
private static long getPrimeProduct(String word) {
long key = 1;
word = word.toLowerCase();
for (int i = 0; i < word.length(); i++) {
key *= primes[word.charAt(i) - 'a'];
}
return key;
}
public static Set<String> findAllAnagramsInDictionary(final Set<String> dictionary, final String word) {
final Set<String> anagrams = new HashSet<String>();
final long wordKey = getPrimeProduct(word);
for (final String dictionaryWord : dictionary) {
if (wordKey == getPrimeProduct(dictionaryWord)) {
anagrams.add(dictionaryWord);
}
}
return anagrams;
}
here is the simple code. O(n). I assumed english dictionary with 26 letters alphabet.
private static int primes[] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79,
83, 89, 97, 101};
private static long getPrimeProduct(String word) {
long key = 1;
word = word.toLowerCase();
for (int i = 0; i < word.length(); i++) {
key *= primes[word.charAt(i) - 'a'];
}
return key;
}
public static Set<String> findAllAnagramsInDictionary(final Set<String> dictionary, final String word) {
final Set<String> anagrams = new HashSet<String>();
final long wordKey = getPrimeProduct(word);
for (final String dictionaryWord : dictionary) {
if (wordKey == getPrimeProduct(dictionaryWord)) {
anagrams.add(dictionaryWord);
}
}
return anagrams;
}
Let's the size of the alphabet of the dictionary is a constant c. Pickup first c prime numbers from a table of primes and assign each letter a unique prime number. Now, the product of the prime numbers associated with letters of a word will be unique and all anagrams will have same product.
Maintain a Set of words. Go through the dictionary and for each word calculate the prime product of the word. If the prime product is equal to the product of the given word then add the word in the set. The set is the answer we are looking for.
overall time complexity is O(n) if maximum word length is O(1).
wrong solution. Question didn't ask to swap alternate pairs instead it is asking for swapping alternate elements. For example: 1-->2-->3-->4-->5 should be transformed to 3-->4-->5-->2-->1.
public static LinkedListNode swapAlternateNodes(final LinkedListNode head) {
if (head == null || head.next == null) {
return null;
}
LinkedListNode newhead = null;
LinkedListNode prev = head;
LinkedListNode cur = prev.next;
LinkedListNode temp = null;
while (cur != null && cur.next != null) {
temp = cur.next;
prev.next = cur.next.next;
cur.next = prev;
temp.next = cur;
if (newhead == null) {
newhead = temp;
} else if (newhead.next == prev) {
newhead.next = temp;
} else if (newhead.next.next == prev) {
newhead.next.next = temp;
}
prev = cur;
cur = cur.next;
}
return newhead;
}
O(n) Kadanes algorithm.
public static int maxSumSubArray(final int[] a) {
int maxSum = 0;
int maxSoFar = 0;
int tempBegin = 0;
int begin = 0;
int end = 0;
for (int i = 0; i < a.length; i++) {
maxSoFar += a[i];
if (maxSoFar < 0) {
maxSoFar = 0;
tempBegin = i + 1;
} else if (maxSoFar > maxSum) {
maxSum = maxSoFar;
begin = tempBegin;
end = i;
}
}
for (int i = begin; i <= end; i++) {
System.out.print(a[i] + ", ");
}
return maxSum;
}
There is much better way to check if two strings are anagrams without using any maps in O(n) time and O(1) space where n is the length of the longest string.
1) Assign each of the 26 letters a unique prime number i.e. {'a'=>2, 'b'=>3, 'c'=>5, 'd'=>7, 'e'=>11, ..., 'l' = 37, ..., 's' => 67, .... ,'t' => 71,.... 'z' => 101}
2) All the anagrams of a word will have the same UNIQUE product. For example: prod(TEA) = prod(ATE) = prod(ETA) = prod(TAE) = prod(AET) = prod(EAT) = 71*11*2 = 154
public static final int primes[] = {2, 3, 5, 7, 11, 13, ......, 101} ;
public boolean isAnagram (String word1, String word2)
{
if(word1.length() != word2.length())
return false;
word1 = word1.toLower();
word2 = word2.toLower();
int word1Key = 1;
for(int i=0; i<word1.length; i++)
word1Key*=primes[word1[i]-'a'];
int word2Key = 1;
for(int i=0; i<word2.length; i++)
word2Key*=primes[word2[i]-'a'];
return word1Key == word2Key;
}
O(n) solution:
public TreeNode rightMostCousin(TreeNode root, int targetKey)
{
LinkedList<TreeNode> q = new LinkedList<TreeNode>();
int count = 0;
q.add(root);
count++;
boolean targetLevel = false;
while(!q.isEmpty())
{
TreeNode node = q.remove();
count--;
if((node.left!=null && node.left.key == targetKey) || (node.right!=null && node.right.key == targetKey))
targetLevel = true;
if(node.left != null) q.add(node.left);
if(node.right != null) q.add(node.right);
if(count == 0)
{
count = q.size();
if(targetLevel)
{
TreeNode cousin = null;
while(!q.isEmpty())
{
cousin = q.remove();
}
return cousin;
}
}
}
return null;
}
O(n) solution:
public TreeNode rightMostCousin(TreeNode root, int targetKey)
{
LinkedList<TreeNode> q = new LinkedList<TreeNode>();
int count = 0;
q.add(root);
count++;
boolean targetLevel = false;
while(!q.isEmpty())
{
TreeNode node = q.remove();
count--;
if((node.left!=null && node.left.key == targetKey) || (node.right!=null && node.right.key == targetKey))
targetLevel = true;
if(node.left != null) q.add(node.left);
if(node.right != null) q.add(node.right);
if(count == 0)
{
count = q.size();
if(targetLevel)
{
TreeNode cousin = null;
while(!q.isEmpty())
{
cousin = q.remove();
}
return cousin;
}
}
}
return null;
}
classical coin sum problem. DP solution. O(n).
public static int coinSum(final int[] coins, final int sum) {
final int m = coins.length;
final int[][] csTable = new int[sum + 1][m + 1];
// base cases: if m == 0 then no solution for any sum
for (int i = 0; i <= sum; i++) {
csTable[i][0] = 0;
}
// base case: if sum = 0 then there is only one solution for any input set: just take none of each of the items.
for (int j = 0; j <= m; j++) {
csTable[0][j] = 1;
}
for (int i = 1; i <= sum; i++) {
for (int j = 1; j <= m; j++) {
// solutions excluding coins[j]
final int s1 = csTable[i][j - 1];
// solutions including coins[i]
final int s2 = (i - coins[j - 1]) >= 0 ? csTable[i - coins[j - 1]][j] : 0;
csTable[i][j] = s1 + s2;
}
}
return csTable[sum][m];
}
classical coin sum problem. DP solution. O(n).
public static int coinSum(final int[] coins, final int sum) {
final int m = coins.length;
final int[][] csTable = new int[sum + 1][m + 1];
// base cases: if m == 0 then no solution for any sum
for (int i = 0; i <= sum; i++) {
csTable[i][0] = 0;
}
// base case: if sum = 0 then there is only one solution for any input set: just take none of each of the items.
for (int j = 0; j <= m; j++) {
csTable[0][j] = 1;
}
for (int i = 1; i <= sum; i++) {
for (int j = 1; j <= m; j++) {
// solutions excluding coins[j]
final int s1 = csTable[i][j - 1];
// solutions including coins[i]
final int s2 = (i - coins[j - 1]) >= 0 ? csTable[i - coins[j - 1]][j] : 0;
csTable[i][j] = s1 + s2;
}
}
return csTable[sum][m];
}
Use set for an O(n) solution. For space constraint sort the input and get a solution in O(nlgn) as bellow:
//O(n) with O(n) space
public static void getPairs(int[] input, int sum)
{
HashSet<Integer> h = new HashSet<Integer>();
for(int i=0;i<input.length;i++)
{
if(h.contains(sum-input[i]))
System.out.println(“Pair: (”+input[i]+”, ”+sum-input[i]+”)”);
h.add(input[i]);
}
}
//O(nlgn) with O(1) space
public static void getPairs(int[] input, int sum)
{
input = sort(input);
int start = 0;
int end = input.length-1;
StringBuilder sb = new StringBuilder();
while(start<=end)
{
if(input[start]+input[end] == sum)
sb.append(“(”+input[start]+”, ”+input[end]);
else if(input[start]+input[end] > sum)
end--;
else start++;
}
System.out.println(sb.toString());
}
Use set for an O(n) solution. For space constraint sort the input and get a solution in O(nlgn) as bellow:
//O(n) with O(n) space
public static void getPairs(int[] input, int sum)
{
HashSet<Integer> h = new HashSet<Integer>();
for(int i=0;i<input.length;i++)
{
if(h.contains(sum-input[i]))
System.out.println(“Pair: (”+input[i]+”, ”+sum-input[i]+”)”);
h.add(input[i]);
}
}
//O(nlgn) with O(1) space
public static void getPairs(int[] input, int sum)
{
input = sort(input);
int start = 0;
int end = input.length-1;
StringBuilder sb = new StringBuilder();
while(start<=end)
{
if(input[start]+input[end] == sum)
sb.append(“(”+input[start]+”, ”+input[end]);
else if(input[start]+input[end] > sum)
end--;
else start++;
}
System.out.println(sb.toString());
}
Here is the O(nlgn) code:
public static void swap(final int[] a, final int i, final int j) {
if (i == j || i < 0 || j < 0 || i > a.length - 1 || j > a.length - 1) {
return;
}
a[i] ^= a[j];
a[j] ^= a[i];
a[i] ^= a[j];
}
public static int[] nextEven(final int[] digits) {
int y = digits.length - 1;
boolean evenFound = digits[y] % 2 == 0;
// find longest increasing subarray from right to left
for (int i = digits.length - 2; i >= 0; i--) {
if (digits[i] >= digits[i + 1]) {
evenFound |= digits[i] % 2 == 0;
y = i;
} else {
break;
}
}
// if y doesn’t contain an even then extend y to left until an even found
while (!evenFound && y - 1 >= 0 && digits[y - 1] % 2 != 0) {
y--;
}
// input is already the largest permutation
if (y <= 0) {
return digits[digits.length - 1] % 2 == 0 ? digits : null;
}
//try to extend Y such that y contains an even after swapping X[a] with the Y[b]
while(y -1 >= 0){
// now X = digits[0..y-1], and Y = digits[y..digits.length-1]
// a is the rightmost element of x, i.e. a = y-1;
// find b = min of y greater than a
final int a = y - 1;
int b = -1;
for (int i = y; i < digits.length; i++) {
b = digits[i] > digits[a] && (b == -1 || (digits[i] < digits[b])) ? i : b;
}
// input is already the largest permutation
if (b == -1) {
return digits[digits.length - 1] % 2 == 0 ? digits : null;
}
// swap a and b
swap(digits, a, b);
// update max even in y
int maxEven = -1;
for (int i = y; i < digits.length; i++) {
maxEven = digits[i] % 2 == 0 && (maxEven == -1 || (maxEven != -1 && digits[i] > digits[maxEven])) ? i
: maxEven;
}
if (maxEven == -1) {
y--;
}
else{
break;
}
}
// input is already the largest permutation
if (maxEven == -1) {
return digits[digits.length - 1] % 2 == 0 ? digits : null;
}
// swap max even with rightmost position
swap(digits, maxEven, digits.length - 1);
// sort y leaving rightmost position unchanged
Arrays.sort(digits, y, digits.length - 1);
return digits;
}
Here is the O(nlgn) code:
public void swap(int[] a, int i, int j)
{
a[i]^=a[j];
a[j]^=a[i];
a[i]^=a[j];
}
public int[] nextEven(int[] digits)
{
int y = digits.length-1;
int m = digits[y]%2 == 0 ? y : -1;
//find longest increasing subarray from right to left
for (int i=digits.length-2; i>=0; i--){
if(digits[i] >= digits[i+1]){
m = digits[i]%2 == 0 && (m == -1 || (m!=-1 && digits[i] > digits[m]))? i : m;
y=i;
}
else break;
}
//if y doesn’t contain an even then extend y to left until an even found
while(m==-1 && y-1>=0 && digits[y-1]%2 != 0)
y--;
// input is already the largest permutation
if (y <=0) return digits[digits.length-1]%2 == 0? digits : null;
//now X = digits[0..y-1], and Y = digits[y..digits.length-1]
//a is the rightmost element of x, i.e. a = y-1;
//find b = min of y greater than a
int a = y-1;
int b = y;
int minb = digits[b];
for(int i=y; i<digits.length; i++)
b = digits[i] > digits[a] && digits[i] < minb ? i : b;
//swap a and b
swap(digits, a, b);
//update max even in y
m = digits[b]%2 == 0 && (m == -1 || (m!=-1 && digits[b] > digits[m]))? b : m;
//swap min even with rightmost position
swap(digits, m, digits.length-1);
//sort y leaving rightmost position unchanged
Arrays.sort(digits, y, digits.length-1);
return digits;
}
We don't need to generate permutations. We can do it in O(nlgn). Observe that if all the digits are in non-decreasing order from right to left then the input itself is the biggest. So, if we can detect the position where the non-decreasing sequence in disrupted then we can simply work on the part of the array.
For example: N = 8234961
1) Detect the longest increasing (non-decreasing) sequence y from right to left and split the input into N=xy. This is O(n). Let a = the element where the increasing sequence disrupted. Also keep track of minimum even (say m) digit in y.
N = 8234 | 961, y=961, x=8234. a=4, m = 6;
Here, we might have a special case if y doesn't contain an even digit. In this case extend x to left the point where we have found an even on the left.
For example: N = 425731; x=425, y = 731, a=5, m=Integer.MIN. Then we extend y. Now, with extended y:
N = 425731; x=42, y = 5731, a=2, m=Integer.MIN.
2) Let, b = smallest element in y greater than a.
a=4. So, b=6.
3) swap (a,b);
N = 8236 | 941; x=8236, y=941. This is O(1).
4) Find max even in Y. This is O(n).
N= 8236 | 941; X=8234, Y=941, Max even = 4.
4) swap max even with the right most digit. This is O(1).
After swapping: N= 8236 | 914; X=8234, Y=914.
Special case: After swapping it may happen that there is no even in y. So, we need to constantly satisfy that y contains an even after swapping X[a] with the Y[b]. So, keeping this constraint true we will extend y to more left until we find an even. Consider this example: 125831
5) Now, sort y in decreasing order from right to left leaving rightmost digit unchanged. This is O(nlgn) in worst case.
N= 8236 | 91 | 4 --after sort --> 8236 | 19 | 4;
That's it, now N=xy is the desired solution. N = 8236194. Total complexity = O(nlgn)
We don't need to generate permutations. We can do it in O(nlgn). Observe that if all the digits are in non-decreasing order from right to left then the input itself is the biggest. So, if we can detect the position where the non-decreasing sequence in disrupted then we can simply work on the part of the array.
For example: N = 8234961
1) Detect the longest increasing (non-decreasing) sequence y from right to left and split the input into N=xy. This is O(n). Let a = the element where the increasing sequence disrupted. Also keep track of minimum even (say m) digit in y.
N = 8234 | 961, y=961, x=8234. a=4, m = 6;
Here, we might have a special case if y doesn't contain an even digit. In this case extend x to left the point where we have found an even on the left.
For example: N = 425731; x=425, y = 731, a=5, m=Integer.MIN. Then we extend y. Now, with extended y:
N = 425731; x=42, y = 5731, a=2, m=Integer.MIN.
2) Let, b = smallest element in y greater than a. Also update minimum even accordingly i.e. m = min{m, a}. This is O(n).
a=4. So, b=6. m = min{6, 4} = 4.
3) swap (a,b); N = 8236 | 941; x=8236, y=941. This is O(1).
4) swap minimum even , m with the right most digit. This is O(1)
N= 8236 | 914; x=8234, y=914.
5) Now, sort y in decreasing order from right to left leaving rightmost digit unchanged. This is O(nlgn) in worst case.
N= 8236 | 91 | 4 --after sort --> 8236 | 19 | 4;
That's it, now N=xy is the desired solution. N = 8236194. Total complexity = O(nlgn)
use DP to solve this coin change problem.
- zahidbuet106 May 23, 2014Classical coin change problem. O(n) DP solution.
public static int coinSum(final int[] coins, final int sum) {
final int m = coins.length;
final int[][] csTable = new int[sum + 1][m + 1];
// base cases: if m == 0 then no solution for any sum
for (int i = 0; i <= sum; i++) {
csTable[i][0] = 0;
}
// base case: if sum = 0 then there is only one solution for any input set: just take none of each of the items.
for (int j = 0; j <= m; j++) {
csTable[0][j] = 1;
}
for (int i = 1; i <= sum; i++) {
for (int j = 1; j <= m; j++) {
// solutions excluding coins[j]
final int s1 = csTable[i][j - 1];
// solutions including coins[i]
final int s2 = (i - coins[j - 1]) >= 0 ? csTable[i - coins[j - 1]][j] : 0;
csTable[i][j] = s1 + s2;
}
}
return csTable[sum][m];
}
This is basically the computation of smaller element count on the right. We can do it more efficiently using balanced BST such as AVL tree. We will consider each number in an array as a BST node and insert them in a AVL tree one by one from right to left. During each insert we will keep updating the size of left subtree at the node being inserted. This will give us our desired smaller element count. We also need to handle balancing the tree while insert.
A balance tree got imbalanced on an insert when the insert on a subtree rooted at a node x makes difference between left subtree and right subtree height more than 1. We will have to consider 4 cases:
1) Insert-in-left-of-left-subtree of x: we can balance by rotating x right
2) Insert-in-right-of-right-subtree of x: we can balance by rotating x left
3) Insert-in-right-of-left-subtree of x: we need two rotations: balance left of x by rotating left. And then a right rotation of x.
4) Insert-in-left-of-right-subtree of x: we need two rotations: balance right of x by rotating right. And then a left rotation of x.
Time complexity will be O(nlgn) and space is O(n).
This is basically the computation of smaller element count on the right. We can do it more efficiently using balanced BST such as AVL tree. We will consider each number in an array as a BST node and insert them in a AVL tree one by one from right to left. During each insert we will keep updating the size of left subtree at the node being inserted. This will give us our desired smaller element count. We also need to handle balancing the tree while insert.
A balance tree got imbalanced on an insert when the insert on a subtree rooted at a node x makes difference between left subtree and right subtree height more than 1. We will have to consider 4 cases:
1) Insert-in-left-of-left-subtree of x: we can balance by rotating x right
2) Insert-in-right-of-right-subtree of x: we can balance by rotating x left
3) Insert-in-right-of-left-subtree of x: we need two rotations: balance left of x by rotating left. And then a right rotation of x.
4) Insert-in-left-of-right-subtree of x: we need two rotations: balance right of x by rotating right. And then a left rotation of x.
Time complexity will be O(nlgn) and space is O(n).
we can keep a counter to track the nodes in the same level.
public class TreeNode
{
int key;
int value;
TreeNode left;
TreeNode right;
}
public static int mostNegativeLevel(TreeNode root)
{
if(root == null)
return -1;
Queue q = new Queue<TreeNode>();
int count = 0;
int level = 0;
int maxNegativeLevel = 0;
int negativeCount = 0;
int maxNegativeCount = 0;
q.enqueue(root);
count++;
while(!q.empty())
{
TreeNode node = stack.dequeue();
negativeCount+= (node.number < 0)? 1:0;
count --;
if(node.left != null)
q.push(node.left);
if(node.right !- null)
q.push(node.right);
if(count == 0)
{
if(negativeCount > maxNegativeCount)
{
maxNegativeCount = negativeCount;
maxNegativeLevel = level;
}
count = q.size();
level++;
negativeCount = 0;
}
}
return maxnegativeLevel;
}
we can keep a counter to track the nodes in the same level.
public class TreeNode
{
int key;
int value;
TreeNode left;
TreeNode right;
}
public static int mostNegativeLevel(TreeNode root)
{
if(root == null)
return -1;
Queue q = new Queue<TreeNode>();
int count = 0;
int level = 0;
int maxNegativeLevel = 0;
int negativeCount = 0;
int maxNegativeCount = 0;
q.enqueue(root);
count++;
while(!q.empty())
{
TreeNode node = stack.dequeue();
negativeCount+= (node.number < 0)? 1:0;
count --;
if(node.left != null)
q.push(node.left);
if(node.right !- null)
q.push(node.right);
if(count == 0)
{
if(negativeCount > maxNegativeCount)
{
maxNegativeCount = negativeCount;
maxNegativeLevel = level;
}
count = q.size();
level++;
negativeCount = 0;
}
}
return maxnegativeLevel;
}
lets do it efficiently.
Input :{4,1,5}
X = 451.
Lets rank=1
If we want to fix 4 at position 0 then we need to increase the rank by number of permutations of {4, 1, 5} starting with an element less than 4. We have only 1 such element i.e. {1}. With 1 at position 0 we can have 2! permutations.
so, rank += 1X2! = 1+2 = 3
Let's fix 4 at position 0 and move our focus to position 1 with remaining elements {1, 5}. In order to fix 5 at position one we need to increase rank by number of permutations of {1, 5} starting with an element less than 5. Again {1} is such an element. With 4 fixed at position 0 and 1 at position 1 we have 1! permutations.
so, rank += 1X1! = 3+1 = 4
Lets fix 5 at position 1 and focus on position 2 with remaining elements {1}. In order to fix 1 in position 3 we need to increase rank by number of permutations starting with less than 1. We have no such element. So, with 45 fixed at first two positions and 1 at position 3 we have : 0! permutations
so, rank+=0X0! = 4+0 = 4.
public static int rank(int[] X)
{
TreeSet<Integer> smaller_count_set = new TreeSet();
int smaller_count[X.length];
smaller_count_set.put(X[X.length-1]);
smaller_count[X.length-1] = 0;
for(int i=X.length-2; i>=0; i--)
{
smaller_count_set.put(X[i]);
smaller_count[i] = smaller_count_set.headSet(X[i]).size();
}
int factorial[X.length];
factorial[0] = 1;
factorial[1] = 1;
for(int i=2; i<X.length; i++)
factorial[i] = factorial[i-2] + factorial[i-1];
int rank =1;
for(int i=0; i< X.length; i++)
{
rank+=smaller_count[i]*factorial[X.length-i-1];
}
return rank;
}
Complexity of this algorithm is O(nlgn)
- zahidbuet106 May 18, 2014lets do it efficiently.
Input :{4,1,5}
X = 451.
Lets rank=1
If we want to fix 4 at position 0 then we need to increase the rank by number of permutations of {4, 1, 5} starting with an element less than 4. We have only 1 such element i.e. {1}. With 1 at position 0 we can have 2! permutations.
so, rank += 1X2! = 1+2 = 3
Let's fix 4 at position 0 and move our focus to position 1 with remaining elements {1, 5}. In order to fix 5 at position one we need to increase rank by number of permutations of {1, 5} starting with an element less than 5. Again {1} is such an element. With 4 fixed at position 0 and 1 at position 1 we have 1! permutations.
so, rank += 1X1! = 3+1 = 4
Lets fix 5 at position 1 and focus on position 2 with remaining elements {1}. In order to fix 1 in position 3 we need to increase rank by number of permutations starting with less than 1. We have no such element. So, with 45 fixed at first two positions and 1 at position 3 we have : 0! permutations
so, rank+=0X0! = 4+0 = 4.
public static int rank(int[] X)
{
TreeSet<Integer> smaller_count_set = new TreeSet();
int smaller_count[X.length];
smaller_count_set.put(X[X.length-1]);
smaller_count[X.length-1] = 0;
for(int i=X.length-2; i>=0; i--)
{
smaller_count_set.put(X[i]);
smaller_count[i] = smaller_count_set.headSet(X[i]).size();
}
int factorial[X.length];
factorial[0] = 1;
factorial[1] = 1;
for(int i=2; i<X.length; i++)
factorial[i] = factorial[i-2] + factorial[i-1];
int rank =1;
for(int i=0; i< X.length; i++)
{
rank+=smaller_count[i]*factorial[X.length-i-1];
}
return rank;
}
Complexity of this algorithm is O(nlgn)
- zahidbuet106 May 18, 2014lets do it efficiently.
Input :{4,1,5}
X = 451.
Lets rank=1
If we want to fix 4 at position 0 then we need to increase the rank by number of permutations of {4, 1, 5} starting with an element less than 4. We have only 1 such element i.e. {1}. With 1 at position 0 we can have 2! permutations.
so, rank += 1X2! = 1+2 = 3
Let's fix 4 at position 0 and move our focus to position 1 with remaining elements {1, 5}. In order to fix 5 at position one we need to increase rank by number of permutations of {1, 5} starting with an element less than 5. Again {1} is such an element. With 4 fixed at position 0 and 1 at position 1 we have 1! permutations.
so, rank += 1X1! = 3+1 = 4
Lets fix 5 at position 1 and focus on position 2 with remaining elements {1}. In order to fix 1 in position 3 we need to increase rank by number of permutations starting with less than 1. We have no such element. So, with 45 fixed at first two positions and 1 at position 3 we have : 0! permutations
so, rank+=0X0! = 4+0 = 4.
There is much better way to check if two strings are anagrams O(n) time and O(1) space where n is the length of the longest string.
1) Assign each of the 26 letters a unique prime number i.e. {'a'=>2, 'b'=>3, 'c'=>5, 'd'=>7, 'e'=>11, ..., 'l' = 37, ..., 's' => 67, .... ,'t' => 71,.... 'z' => 101}
2) All the anagrams of a word will have the same UNIQUE product. For example: prod(TEA) = prod(ATE) = prod(ETA) = prod(TAE) = prod(AET) = prod(EAT) = 71*11*2 = 154
public static final int primes[] = {2, 3, 5, 7, 11, 13, ......, 101} ;
public boolean isAnagram (String word1, String word2)
{
if(word1.length() != word2.length())
return false;
word1 = word1.toLower();
word2 = word2.toLower();
int word1Key = 1;
for(int i=0; i<word1.length; i++)
word1Key*=primes[word1[i]-'a'];
int word2Key = 1;
for(int i=0; i<word2.length; i++)
word2Key*=primes[word2[i]-'a'];
return word1Key == word2Key;
}
There is much better way to check if two strings are anagrams without using any maps in O(n) time and O(1) space where n is the length of the longest string.
1) Assign each of the 26 letters a unique prime number i.e. {'a'=>2, 'b'=>3, 'c'=>5, 'd'=>7, 'e'=>11, ..., 'l' = 37, ..., 's' => 67, .... ,'t' => 71,.... 'z' => 101}
2) All the anagrams of a word will have the same UNIQUE product. For example: prod(TEA) = prod(ATE) = prod(ETA) = prod(TAE) = prod(AET) = prod(EAT) = 71*11*2 = 154
public static final int primes[] = {2, 3, 5, 7, 11, 13, ......, 101} ;
public boolean isAnagram (String word1, String word2)
{
word1 = word1.toLower();
word2 = word2.toLower();
int word1Key = 1;
for(int i=0; i<word1.length; i++)
word1Key*=primes[word1[i]-'a'];
int word2Key = 1;
for(int i=0; i<word2.length; i++)
word2Key*=primes[word2[i]-'a'];
return word1Key == word2Key;
}
There is much better way to check if two strings are anagrams without using any maps in O(n) time and O(1) space where n is the length of the longest string.
1) Assign each of the 26 letters a unique prime number i.e. {'a'=>2, 'b'=>3, 'c'=>5, 'd'=>7, 'e'=>11, ..., 'l' = 37, ..., 's' => 67, .... ,'t' => 71,.... 'z' => 101}
2) All the anagrams of a word will have the same UNIQUE product. For example: prod(TEA) = prod(ATE) = prod(ETA) = prod(TAE) = prod(AET) = prod(EAT) = 71*11*2 = 154
public static final int primes[] = {2, 3, 5, 7, 11, 13, ......, 101} ;
public boolean isAnagram (String word1, String word2)
{
if(word1.length() != word2.length())
return false;
word1 = word1.toLower();
word2 = word2.toLower();
int word1Key = 1;
for(int i=0; i<word1.length; i++)
word1Key*=primes[word1[i]-'a'];
int word2Key = 1;
for(int i=0; i<word2.length; i++)
word2Key*=primes[word2[i]-'a'];
return word1Key == word2Key;
}
There is a better way in O(n) using a DP approach: Let's window size = w and array size = n, n>w.
Observe that the minimum at a position in current window is the minimum of what we would have seen so far and what we will see in future in the current window boundary. So, we can find min so far while traversing from left to right of the current window. But what about min in future? the trick is that we can traverse backwards to get the future min at a position. Also note that: windows separated by elements >=w will have no overlapping and so min so far should be reset at each block of w elements.
So, we will divide the array into [n/w] blocks. We'll keep calculate array's of min: min_so_far by traversing from start to end and min_in_future by traversing from end to start. Reset the min at the boundary of each block in the direction of traversal.
Example: [2,1,3,4,6,3,8,9,10,12,56] w=4
1. partition the array in blocks of size w=4. The last block may have less then w.
2, 1, 3, 4 | 6, 3, 8, 9 | 10, 12, 56|
2. Traverse the list from start to end and calculate min_so_far. Reset min to 0 after each block (of w elements).
min_so_far[] = 2, 1, 1, 1 | 6, 3, 3, 3 | 10, 10, 10
3. Similarly calculate min_in_future by traversing from end to start.
min_in_future[] = 1, 1, 3, 4 | 3, 3, 8, 9 | 10, 12, 56
4. now, min at each position i in current window, sliding_min(i) = min {min_in_future[i], min_so_far[i+w-1]}
sliding_min = 1, 1, 3, 3, 3, 3, 8, ....
public static int[] slidingWindowMin(final int[] in, final int w) {
final int[] min_left = new int[in.length];
final int[] min_right = new int[in.length];
min_left[0] = in[0];
min_right[in.length - 1] = in[in.length - 1];
for (int i = 1; i < in.length; i++) {
min_left[i] = (i % w == 0) ? in[i] : Math.min(min_left[i - 1], in[i]);
final int j = in.length - i - 1;
min_right[j] = (j % w == 0) ? in[j] : Math.min(min_right[j + 1], in[j]);
}
final int[] sliding_min = new int[in.length - w + 1];
for (int i = 0, j = 0; i + w <= in.length; i++) {
sliding_min[j++] = Math.min(min_right[i], min_left[i + w - 1]);
}
return sliding_min;
}
There is a better way in O(n) using a DP approach: Let's window size = w and array size = n, n>w.
Observe that the minimum at a position in current window is the minimum of what we would have seen so far and what we will see in future in the current window boundary. So, we can find min so far while traversing from left to right of the current window. But what about min in future? the trick is that we can traverse backwards to get the future min at a position. Also note that: windows separated by elements >=w will have no overlapping and so min so far should be reset at each block of w elements.
So, we will divide the array into [n/w] blocks. We'll keep calculate array's of min: min_so_far by traversing from start to end and min_in_future by traversing from end to start. Reset the min at the boundary of each block in the direction of traversal.
Example: [2,1,3,4,6,3,8,9,10,12,56] w=4
1. partition the array in blocks of size w=4. The last block may have less then w.
2, 1, 3, 4 | 6, 3, 8, 9 | 10, 12, 56|
2. Traverse the list from start to end and calculate min_so_far. Reset min to 0 after each block (of w elements).
min_so_far[] = 2, 1, 1, 1 | 6, 3, 3, 3 | 10, 10, 10
3. Similarly calculate min_in_future by traversing from end to start.
min_in_future[] = 1, 1, 3, 4 | 3, 3, 8, 9 | 10, 12, 56
4. now, min at each position i in current window, sliding_min(i) = min {min_in_future[i], min_so_far[i+w-1]}
sliding_min = 1, 1, 3, 3, 3, 3, 8, ....
public static int[] slidingWindowMin(final int[] in, final int w) {
final int[] min_left = new int[in.length];
final int[] min_right = new int[in.length];
min_left[0] = in[0];
min_right[in.length - 1] = in[in.length - 1];
for (int i = 1; i < in.length; i++) {
min_left[i] = (i % w == 0) ? in[i] : Math.min(min_left[i - 1], in[i]);
final int j = in.length - i - 1;
min_right[j] = (j % w == 0) ? in[j] : Math.min(min_right[j + 1], in[j]);
}
final int[] sliding_min = new int[in.length - w + 1];
for (int i = 0, j = 0; i + w <= in.length; i++) {
sliding_min[j++] = Math.min(min_right[i], min_left[i + w - 1]);
}
return sliding_min;
}
your solution is not extendable to arbitrary window size, w.
- zahidbuet106 May 04, 2014finding all palindromic substring is nonlinear order. We don't need that for solving this problem. Here I have an efficient recursive solution:
removeAdjacentDuplicate("ABCCBCBA", 0)
public static void removeAdjacentDuplicate(String in, int cur)
{
if(in.length() == 0 || cur<0 || cur>= in.length())
return;
int len = 1;
while(cur+len<in.length() && in.charAt(cur) == in.charAt(cur+len))
len++;
StringBuilder sb = new StringBuilder(in);
sb = sb.delete(cur, cur+len);
removeAdjacentDuplicate(sb.toString(), curr--);
}
finding all palindromic substring is nonlinear order. We don't need that for solving this problem. Here I have an efficient recursive solution:
removeAdjacentDuplicate("ABCCBCBA", 0)
public static void removeAdjacentDuplicate(String in, int cur)
{
if(in.length() == 0 || cur<0 || cur>= in.length())
return;
int len = 1;
while(cur+len<in.length() && in.charAt(cur) == in.charAt(cur+len))
len++;
StringBuilder sb = new StringBuilder(in);
sb = sb.delete(cur, cur+len);
removeAdjacentDuplicate(sb.toString(), curr--);
}
I have an elegant solution in my mind which only takes O(n) time and O(1) space:
1) Assign each of the 26 letters a unique prime number i.e. {'a'=>2, 'b'=>3, 'c'=>5, 'd'=>7, 'e'=>11, ..., 'l' = 37, ..., 's' => 67, .... ,'t' => 71,.... 'z' => 101}
2) All the anagrams of the first word will have the same UNIQUE product. For example: prod(TEA) = 71*11*2 = 154
3) Now, go through each position of the 2nd word and find cumulative product at each position and keep the index of a cum-prod in a hashmap.
4) while passing through the letters of 2nd word check if the current cum-prod is divisible by the prod(2nd word). If it is the voila! we got our answer and the anagram starts at the position where cum-prod is equal to the quotient of the devision.
public static final int primes[] = {2, 3, 5, 7, 11, 13, ......, 101} ;
public String findAnagramicSubString (String haystack, String needle)
{
haystack = haystack.toLower();
needle = needle.toLower();
int needleKey = 1;
for(int i=0; i<needle.length; i++)
needleKey*=primes[needle[i]-'a'];
Map<Integer, Integer> cumprods = Maps.newHashMap();
int cumprod = 1;
for(int i=0; i<haystack.length; i++)
{
cumprod*=primes[haystack[i]-'a'];
if(cumprod%needleKey==0 && cumprods.containsKey(cumprod/needleKey))
{
return haystack.substring(cumprods.get(umprod/needleKey), needle.length);
}
cumprods.put(cumprod, i);
}
return "";
}
I have an elegant solution in my mind which only takes O(n) time and O(n) space:
1) Assign each of the 26 letters a unique prime number i.e. {'a'=>2, 'b'=>3, 'c'=>5, 'd'=>7, 'e'=>11, ..., 'l' = 37, ..., 's' => 67, .... ,'t' => 71,.... 'z' => 101}
2) All the anagrams of the first word will have the same UNIQUE product. For example: prod(TEA) = 71*11*2 = 154
3) Now, go through each position of the 2nd word and find cumulative product at each position and keep the index of a cum-prod in a hashmap.
4) while passing through the letters of 2nd word check if the current cum-prod is divisible by the prod(2nd word). If it is the voila! we got our answer and the anagram starts at the position where cum-prod is equal to the quotient of the devision.
public static final int primes[] = {2, 3, 5, 7, 11, 13, ......, 101} ;
public String findAnagramicSubString (String haystack, String needle)
{
haystack = haystack.toLower();
needle = needle.toLower();
int needleKey = 1;
for(int i=0; i<needle.length; i++)
needleKey*=primes[needle[i]-'a'];
Map<Integer, Integer> cumprods = Maps.newHashMap();
int cumprod = 1;
for(int i=0; i<haystack.length; i++)
{
cumprod*=primes[haystack[i]-'a'];
if(cumprod%needleKey==0 && cumprods.containsKey(cumprod/needleKey))
{
return haystack.substring(cumprods.get(umprod/needleKey), needle.length);
}
cumprods.put(cumprod, i);
}
return "";
}
max_row_len = Integer.Min;
max_col_len = Integer.Min;
cur_max_len = 0;
for each row
{
for each col
{
if (matrix[row][[col] == 0 || col == matrix[0].length-1)
{
if (cur_max_len > max_row_len)
max_row_len = cur_max_len;
cur_max_len = 0;
}
else cur_max_len++;
}
}
if (cur_max_len!=0 && cur_max_len > max_row_len)
max_row_len = cur_max_len;
cur_max_len = 0;
for each col
{
for each row
{
if (matrix[row][[col] == 0 || row == matrix.length-1)
{
if (cur_max_len > max_col_len)
max_col_len = cur_max_len;
cur_max_len = 0;
}
else cur_max_len++;
}
}
if (cur_max_len!=0 && cur_max_len > max_col_len)
max_col_len = cur_max_len;
max_len = max(max_row_len, max_col_len);
return sequence of 1's of size max_len;
BAD assumption. There is a better solution without any assumption
max_row_len = Integer.Min;
max_col_len = Integer.Min;
cur_max_len = 0;
for each row
{
for each col
{
if (matrix[row][[col] == 0 || col == matrix[0].length-1)
{
if (cur_max_len > max_row_len)
max_row_len = cur_max_len;
cur_max_len = 0;
}
else cur_max_len++;
}
}
if (cur_max_len!=0 && cur_max_len > max_row_len)
max_row_len = cur_max_len;
cur_max_len = 0;
for each col
{
for each row
{
if (matrix[row][[col] == 0 || row == matrix.length-1)
{
if (cur_max_len > max_col_len)
max_col_len = cur_max_len;
cur_max_len = 0;
}
else cur_max_len++;
}
}
if (cur_max_len!=0 && cur_max_len > max_col_len)
max_col_len = cur_max_len;
max_len = max(max_row_len, max_col_len);
return sequence of 1's of size max_len;
Using hash map will cost O(nlgn). There is a more efficient way to do it in O(n). As the integers are 8 bit so keep an int array of constant size 256. Now, make a pass through first array and use the element of the first array as the index of this array to update the count. Now make a pass to the second array and for each element check if this array contains positive count at the index=element.
public Set<Integer> findCommonElements(byte[] a, byte[] b)
{
int count[256];
Set<Intetger> common = HashSet<Integer>();
for(int i=0; i<a.length; i++)
count[a[i]]++;
for(int i=0; i<b.length; i++)
if(count[b[i]] > 0)
common.add(b[i]);
return common;
}
@ganeshjyothi2 why don't you think 2nd one works? Can you explain.
@ chengyuanzhang831 : Amortized hash-table provides O(1) lookup (contains) operation.
@saurabh
Activity selection is a greedy algorithm which requires you to select a job each time according to the earliest finish time. In that sense you need to select the job with earliest finish time as the initial job, not the earliest started job. Also note that (start time, finish time) assumes start time < finish time . I mapped the pair problem as a activity selection problem by considering each pair as a job and first element as the starting time and 2nd element as finishing time because (a, b) exhibits a<b relation similar to start time<finish time in activity selection.I hope this answers your question.
Special Note: Use Manacher's algorithm to find all the palindromic substring or the longest palindromic substring very simply in O(n) time!
public class ManacherLongestPalindromicSubstring{
public static String void preprocess(String in){
StringBuffer sb = new StringBuffer();
sb.append’#’);
for(int i=0; i<in.length(); i++){
sb.append(in.charAt(i));
sb.append(‘#’);
}
return sb.toString();
}
public static String LongestPalindrome(String in){
/*Preprocess the string to insert special character ‘#’ in the spaced between characters in input and the two outside edges. This is done merely to make the computation identical for both odd and even length input string. */
String S = preprocess(in);
int C = 0; //contains center of current palindrome
int R = 0; //contains the right edge of current palindrome
int[] P = new int[S.length()];
// P[i] contains the length of longest palindrome (in S not original in) centered at i
for(int i=0;i<P.length(); i++)
P[i] = 0;
// for each position find longest palindrome centered at the position, save length in P
for(int i=0; i<S.length; i++){
int i_mirror = 2*C-i; // as C - i_mirror = i - C due to symmetric property
/*When R-i > P[i_mirror] then palindrome at center i_prime contained completely within palindrome centered at C. Else R-i <= P[i_mirror] means that the palindrome at ceter i_mirror doesn’t fully contained in the palindrome centered at C. Then palindrome at i is extendable past R*/
P[i] = (R>i) ? min(P[i_mirror], R-i) : 0;
// if palindrome centered at i is extendable past R then extend R to the right edge of newly extended palindrome
while(S[i+P[i]+1] == S[i-P[i]-1])
P[i]++;
// If palindrome centered at i extend past R then update Center to i
if(i+P[i] > R){
C = i;
R = i+P[i];
}
}
return extractLongest(in, P);
}
public int extractLongest(String in, int[] P){
int longestCenter = 0;
int longestLength = 0;
for(int i=0; i<P.length; i++){
if(P[i] > longestLength){
longestLongest = P[i];
longestCenter = i;
}
}
return in.substring((longestCenter-longestLength-1)/2, longestLemgth);
}
public Set<String> allPalindromicSubstring(String in, int[] P){
HashSet<String> all = new HashSet<String>();
for(int i=0; i<P.length; i++)
if(P[i] != 0)
all.add(in.substring((i-P[i]-1)/2, P[i]));
return all;
}
}
1) For constant sized alphabet we can build suffix trees using Ukkonen's Algorithm in O(n).
2) For given string S, build a generalized suffix tree of S#S` where S' is reverse of string S and # is delimiting character.
3) Now in this suffix tree, for every suffix i in S, look for lowest common ancestor of (2n-i+1) suffix is S`.
4) count for all such suffixes in the tree to get total count of all palindromes.
5) You can even go further and get longest palindrome. Look for LCA which is deepest in the tree i.e. one whose distance from root is max.
I hope this helps. I am updating the main post.
- zahidbuet106 December 16, 2013
Repmarilynarhea, Computer Scientist at ABC TECH SUPPORT
I live my life very happily by god grace and I am working as a Gaming machine servicer and my ...
This is not O(n)...actually O(nw) and performance will be getting slower with increasing window size.
- zahidbuet106 June 02, 2014