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
A simple recursive solution
public static TreeNode Mirror(TreeNode root)
{
if (!root) return null;
TreeNode node = new TreeNode();
node.data = root.data;
node.left = Mirror(root.right);
node.right = Mirror(root.left);
return node;
}
An efficient O(n) solution without using any additional data structure or buffer.
public static String removeDuplicate(String in){
StringBuilder sb = new StringBuilder();
int flag = 0;
in = in.toLower();
for(int i=0; i<in.length(); i++){
int mask = 1<<(int)in.charAt(i);
if(! flag&mask) //char not seen so far
sb.append(in.charAt(i));
flag |= mask;
}
return sb.toString();
}
An efficient O(n) solution without using any additional data structure or buffer.
public static String removeDuplicate(String in)
{
StringBuilder sb = new StringBuilder();
int flag = 0;
in = in.toLower();
for(int i=0; i<in.length(); i++)
{
int mask = 1<<(int)in.charAt(i);
if(! flag&mask) //char not seen so far
sb.append(in.charAt(i));
flag |= mask;
}
return sb.toString();
}
you can do this using suffix Tree and Suffix arrays. O(nlgn) solution
1. For constant sized alphabet we can build suffix trees using Ukkonen's Algorithm in O(n).
2. Traverse the tree lexicographically and populate the suffix array.
3. Pass over suffix array once to get total number of palindromic substrings in the input string.
More Specifically:
This can be done in linear time using suffix trees:
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.
Here is an O(n) solution;
Suppose the array is A = {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}
The longest biotonic sequence would be the sequence {0, 8, 12, 14, 13, 11, 7} of size 7
Motivation:
The solution is a variant of of LIS (Longest Increasing Subsequence) problem.
Idea:
We need to construct two arrays lis[] and lds[] using Dynamic Programming solution of LIS problem.
lis[i] : stores the length of the Longest Increasing subsequence ending with arr[i].
lds[i]: stores the length of the longest Decreasing subsequence starting from arr[i].
Finally, we need to return the max value of (lis[i] + lds[i] – 1) where i is from 0 to n-1. Keep the marker to the elements being chosen to be used to output the subsequence later.
Here is O(n) solution
public static void SubArraySumModK(int A[], int K)
{
int sum = 0;
Map<Integer, ArrayList<Integer>> candidates = new HashMap<Integer, ArrayList<Integer>>();
for(int i=0; i<A.length; i++)
{
sum += A[i];
if(!candidates.containsKey(sum%K))
candidates.put(sum%K, new ArrayList<Integer>());
candidates.get(sum%K).add(i);
}
//output all the pairs for each of the key
}
Here is a tail recursive solution using one pointer. O(n):
public static LinkedList reverse(LinkedList head, LinkedList reversed){
if(head==null) return reversed;
LinkedList current = new LinkedList();
current = head;
head = head.next;
current->next = reversed;
return reverse(head, current);
}
Here is an implementation
Use Manacer's algorithm to find them in O(n)
public class ManacerLongestPalindromicSubstring{
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. Otherwise R-i <= P[i_mirror] means that the palindrome at ceter i_mirror doesn’t fully contained in the palindrome centered at C. In this case 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;
}
}
Use Manacer's algorithm to find them in O(n)
public class ManacherLongestPalindromicSubstring{
public static String 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. Otherwise R-i <= P[i_mirror] means that the palindrome at ceter i_mirror doesn’t fully contained in the palindrome centered at C. In this case 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;
}
}
Use Manacher's algorithm to find them in O(n)
public class ManacerLongestPalindromicSubstring{
public static String 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. Otherwise R-i <= P[i_mirror] means that the palindrome at ceter i_mirror doesn’t fully contained in the palindrome centered at C. In this case 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;
}
}
yeah you can do it in O(n) using KMP string matching algorithm. Use the prefix function in KMP algorithm and do the tweaks.
- zahidbuet106 December 16, 2013These are not optimal solution and inefficient ,O(n^2) although simple. I would rather go for obvious modifications into KMP String matching algorithm's prefix function calculation in O(n) time.
- zahidbuet106 December 16, 2013This problem is a simple counting problem which can be solved in O(n) time and O(1) space as follows:
public static char getFirsUnique(char[] buf)
{
int count[256] = {0};
for (int i=0;i<buf.length;i++)
count[buf[i]]++;
for(int i=0; i<buf.length;i++)
if(count[buf[i]] == 1) return buf[i];
return 0;
}
O(nlgn) using Activity Selection Problem:
1) Sort the pairs according to their second element --> O(nlgn)
2) Select the first pair from the sorted array and print it. --> O(1)
3) Do following for remaining pairs in the sorted array. --> O(n)
---------------> If the first element of this pair is greater than the 2nd element of previously selected pair then select this pair and print it.
public static int LongestChainPairs(Pair[] pairs)
{
Collection.sort(pairs); //Assume that Pair class implements comparable with the compareTo() method such that (a, b) < (c,d) iff b<c
int chainLength = 0;
//select the first pair of the sorted pairs array
pairs[0].print(); //assume print method prints the pair as “(a, b) ”
chainLength++;
int prev = 0;
for(int i=1;i<pairs.length; i++)
{
if(pairs[i].first >= pairs[prev].second)
{
pairs[i].print();
chainLength++;
prev = i;
}
}
return chainLength;
}
@Scott your assumption is wrong about the array of pairs i.e. the your double array input is already sorted according to 2nd element. What of the array is not sorted. For example : {(50, 90), (5,24), (39,60), (15, 28), (27,40)}. Then you are selecting blindly the first pair as the start of the chain. So, O(n) solution of yours only works if the array is sorted.
isn't the problem is similar to O(nlgn) activity selection problem?
1) Sort the pairs according to their second element --> O(nlgn)
2) Select the first pair from the sorted array and print it. --> O(1)
3) Do following for remaining pairs in the sorted array. --> O(n)
---------------> If the first element of this pair is greater than the 2nd element of previously selected pair then select this pair and print it.
O(nlgn) solution:
public static int LongestChainPairs(Pair[] pairs)
{
Collection.sort(pairs); //Assume that Pair class implements comparable with the compareTo() method such that (a, b) < (c,d) iff b<c
int chainLength = 0;
//select the first pair of the sorted pairs array
pairs[0].print(); //assume print method prints the pair as “(a, b) ”
chainLength++;
int prev = 0;
for(int i=1;i<pairs.length; i++)
{
if(pairs[i].first >= pairs[prev].second)
{
pairs[i].print();
chainLength++;
prev = i;
}
}
return chainLength;
}
@rp ..yeah you are right. silly little mistake. corrected it.
- zahidbuet106 December 13, 2013O(n) queue implementation:
public static void printLevelOrder(TreeNode* root)
{
if(!root) return;
Queue* q = new Queue();
TreeNode* node;
int count = 0;
int level = 0;
q->push(root);
count++;
print(“Level 0: ”);
while(!q.isEmpty())
{
node = q->pop();
print(node->data+” ”);
if(node->left) q->push(node->left);
if(node->right) q->push(node->right);
if(--count == 0)
{
count = q->size();
level ++;
print(“\nLevel ”+level+”: ”);
}
}
}
O(n) queue implementation:
public static void printLevelOrder(TreeNode* root)
{
if(!root) return;
Queue* q = new Queue();
TreeNode* node;
int count = 0;
int level = 0;
q->push(root);
count++;
print(“Level 0: ”);
while(!q.isEmpty())
{
node = q->pop();
print(node->data+” ”);
if(node->left) q->push(node->left);
if(node->right) q->push(node->right);
if(--count == 0)
{
count = q->size();
level ++;
print(“\nLevel ”+level+”: ”);
}
}
}
O(nlgn) solution:
public static List<Pair> getMinDiff(int[] A)
{
ArrayList<Pair> pairs;
int minDiff = Integer.MAX;
A=quicksort(A);
for(int i=0;i<A.length-1;i++)
{
if (abs(A[i+1]-A[i]) < minDiff)
{
pairs = new ArrayList<Pair>();
pairs.add(new Pair(A[i], A[i+1]));
minDiff = abs(A[i+1]-A[i]) ;
}
else if (abs(A[i+1]-A[i]) == minDiff)
{
pairs.add(new Pair(A[i], A[i+1]));
}
}
return pairs;
}
@radu.a.popa: yeah you are right. It was a typo. Fixed it now!
- zahidbuet106 December 10, 2013Set a prime number for each of the letters a to z say 2 to 101. Now, all anagram can be represented by a unique number which can be calculated as a product of all the numbers associated the characters in the word. For example: Boy and Yob are anagrams and the associated numbers are : 3x47x97 and 97x47x3 respectively, which are equal.
So, keep a hashmap with the primeproduct as the key and the list of same anagrams as the value.
public class Anagrams
{
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 int hash(String word)
{
int hash = 0;
word = word.toLower();
for(int i=0; i< word.length(); i++)
hash*=primes[word[i] - ‘a’];
return hash;
}
public static void anagrams(String fileContent)
{
String[] words = fileContent.trim().split(“ ”, false);
HashMap<Integer, HashSet<String>> anagrams;
for(int i=0; i<words.length; i++)
{
int wordKey = hash(word);
if(!anagrams.contains(wordKey))
anagrams.put(wordKey, new HashSet<String());
anagrams.get(wordKey).add(word);
}
print(anagrams);
}
}
Set a prime number for each of the letters a to z say 2 to 101. Now, all anagram can be represented by a unique number which can be calculated as a product of all the numbers associated the characters in the word. For example: Boy and Yob are anagrams and the associated numbers are : 3x47x97 and 97x47x3 respectively, which are equal.
So, keep a hashmap with the primeproduct as the key and the list of same anagrams as the value.
public class Anagrams
{
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 int hash(String word)
{
int hash = 0;
word = word.toLower();
for(int i=0; i< word.length(); i++)
hash*=primes[word[i] - ‘a’];
return hash;
}
public static void anagrams(String fileContent)
{
String[] words = fileContent.trim().split(“ ”, false);
HashMap<Integer, HashSet<String>> anagrams;
for(int i=0; i<words.length; i++)
{
int wordKey = hash(word);
if(!anagrams.contains(wordKey))
anagrams.put(wordKey, new HashSet<String());
anagrams.get(wordKey).add(word);
}
print(anagrams);
}
}
Use kadane's algorithm to solve in O(n)
public static List<Integer> maxSumSubArray(int[] A)
{
int sumSoFar = A[0];
int maxSum = 0;
int tempBegin = 0;
int begin = 0;
inr end = 0;
for(int i=1; i<A.length; i++)
{
if(sumSoFar < 0)
{
sumSoFar = A[i];
tempBegin = i;
}
else sumSoFar+=A[i];
if(sumSoFar > maxSum)
{
maxSum = sumSoFar;
begin = tempBegin;
end = i;
}
}
ArrayList<Integer> result = new ArrayList();
for(int i=begin; i<=end; i++)
result.add(A[i]);
return result;
}
Use Kadanes algorithm to solve in O(n) time.
public static List<Integer> maxSumSubArray(int[] A)
{
int sumSoFar = A[0];
int maxSum = 0;
int tempBegin = 0;
int begin = 0;
inr end = 0;
for(int i=1; i<A.length; i++)
{
if(sumSoFar < 0)
{
sumSoFar = A[i];
tempBegin = i;
}
else sumSoFar+=A[i];
if(sumSoFar > maxSum)
{
maxSum = sumSoFar;
begin = tempBegin;
end = i;
}
}
ArrayList<Integer> result = new ArrayList();
for(int i=begin; i<end; i++)
result.add(A[i]);
return result;
}
O(1) space O(n) time solution
1. Scan the string from left to right and keep an array for saving position a character last encountered during the scan.
2. While scanning before updating the lastSeen array check if the character already encountered in the current scan so far.
3. If the character was not encountered that means you can add this to the longest SubString found so far.
4. Otherwise the character already encountered in the current scan which means we have encountered a duplicate. So, we ignore the substring from beginning to this position as this makes the future sequence containing duplicates.
5. While calculating longest substring so far encountered keep the tracking for absolute longest one.
public static String longestNonDupSubstr(String str)
{
String longestSoFar;
String longestSubStr;
char current;
int lastSeen[256];
for(int i=0; i<256; i++)
lastSeen[i] = -1;
for(int i=0; i<str.length(); i++)
{
current = str.charAt(i);
if(lastSeen[current] == -1)
longestSoFar = longestSoFar + current;
else
longestSoFar = str.substring(lastSeen[current]+1, i+1);
lastSeen[current] = i;
if(longestSoFar.length() > longestSubstr.length())
longestSubStr = longestSoFar;
}
return longestSubStr;
}
There is no need to consume O(n) space by using hashtable. Use fixed size array instead as characters are limited.
public static String longestNonDupSubstr(String str)
{
String longestSoFar;
String longestSubStr;
char current;
int lastSeen[256];
for(int i=0; i<256; i++)
lastSeen[i] = -1;
for(int i=0; i<str.length(); i++)
{
current = str.charAt(i);
if(lastSeen[current] == -1)
longestSoFar = longestSoFar + current;
else
longestSoFar = str.substring(lastSeen[current]+1, i+1);
lastSeen[current] = i;
if(longestSoFar.length() > longestSubstr.length())
longestSubStr = longestSoFar;
}
return longestSubStr;
}
O(n) time and O(n) space solution:
1. Keep a hashtable(HashSet would suffice) to keep the elements already seen while passing through array once.
2. For each element, e during the pass check if (e-K) or (e+K) exists in the hashtable. If exists then increment a count.
3. Add the scanned element in the hashtable.
public static int diffPairs(int[] A, int K)
{
HashSet<Integer> hs = new HashSet<Integer>();
int count =0;
for(int i=0; i<A.length; i++)
{
if(hs.contains(A[i] - K))
count++;
if(hs.contains(A[i]+K))
count++;
hs.add(A[i]);
}
return count;
}
If we don't have the space then there is another solution with O(1) space and O(nlgn) time.
1. Sort the array
2. For each position in the sorted array, e1 search for an element e2>e1 in the sorted array such that A[e2]-A[e1] = diff.
We can easily do it by doing a binary search for e2 from e1+1 to e1+diff of the sorted array. Note that we don't have to search in the whole array as the element with difference = diff will be apart atmost by diff number of elements.
public static int diffPairs2(final int[] A, final int diff) {
Arrays.sort(A);
int count = 0;
int matchKey = 0;
int matchIndex = -1;
for (int i = 0; i < A.length; i++) {
// if we are in e1=A[i] and searching for a match=e2, e2>e1 such that e2-e1= diff then e2=e1+diff
// So, potential match to search in the rest of the sorted array is match = A[i] + diff; We will do a binary
// search. Also note that the math should be at most |diff| element away to right of the current position i
matchKey = A[i] + diff;
matchIndex = binarySearch(A, Math.min(i + 1, A.length - 1), Math.min(i + diff, A.length - 1), matchKey);
count += (matchIndex != -1) ? 1 : 0;
}
return count;
}
DLL remove() operation is O(1) only if we have the entry pointer to the element. Which pointer you are saving in the HashMap? Your algorithm was good but implementation is not straightforward in Java. How will you get a pointer to an element of the DLL??
This problem is a simple counting problem which can be solved in O(n) time and O(1) space as follows:
public static char getFirsUnique(char[] buf)
{
int count[256] = {0};
for (int i=0;i<buf.length;i++)
count[buf[i]]++;
for(int i=0; i<buf.length;i++)
if(count[buf[i]] == 1) return buf[i];
return 0;
}
public class Permutation
{
stringBuilder output;
String input;
boolean used[];
public Permutation(String in)
{
this.input = in;
output = new StringBuilder();
used = new Booolean[n];
}
public void Permute(String in)
{
if(in.length() == output.length())
{
print(output.toString());
}
for(int i=0;i<in.length; i++)
{
if(used[i]) continue;
output.append(input.charAt(i));
used[i] = true;
permute(in.substring(i));
used[i] = false;
output.setLength(output.length() - 1);
}
}
}
public class AutoSuggestion
{
//assuming max word length to be 80
int frequency[80][26] = {0};
int mostFreequent[80] = {0};
public AutoSuggestion(String filename)
{
BufferredReader br = new BufferredReader(new FileReader(fileName));
String word = “”;
while((word=br.readLine())!=null)
{
word = word.toLower();
for(int i=0;i<word.length();i++)
{
frequency[i][word.charAt(i)-’a’]++;
}
}
for(int i=0;i<80; i++)
{
int maxPos = 0;
int maxFreq = -1;
for(int j=0;j<26; j++)
{
if(frequency[i][j] > maxFreq)
{
maxFreq = frequency[i][j];
maxPos = j;
}
}
mostFrequent[i] = maxPos;
}
}
public String suggest(String text)
{
if(text.length() > 80)
return “”;
StringBuilder sb = new StringBuilder(text);
sb.append(mostFrequent[text.length()]);
return sb.toString();
}
}
O(n) time and O(n) space
public static int firstDuplicate(int[] input)
{
Set<Integer> uniqes = new HashSet<Integer>();
for(int i=0;i<input.length;i++)
{
if(uniques.contains(input[i]))
return input[i];
uniques.put(input[i]);
}
}
public static void printReverseWordOrder(String str)
{
String[] words = str.split(“ ”);
ArrayUtils.reverse(words);
StringBuilder sb = new StringBuilder();
for(String word: words)
sb,append(word);
System.out.println(sb.toString());
}
The idea is to see the pattern.
We can notice that such spiral starts from (0,0) and traverse the edges of the (nxn) matrix with (0,0) as the top left corner and completes first round at just below the (0,0). Similarly, 2nd round continues from (1,1) and traverse edges of the (n-1)x(n-1) submatrix with (1,1) as the top left corner and completes the round just below (1,1).
That means for each round i, we traverse the a (n-i)x(n-i) submatrix with (i,i) as the top left corner as follows:
1. traverse the top row left to right from (i,i) to (i, n-i-1)
2. traverse the rightmost column down from (i+1, n-i-1) to (n-i-1, n-i-1) [note: we didn't start from (i, n-i-1) as we have already traversed (i, n-i-1); similarly we didn't finish at (n-i-1, n-i-1) as we will start the next step from there]
3. traverse the bottom row right to left from (n-i-1, n-i-1) to (n-i-1, i).
4. Traverse leftmost column up from (n-i-2, i) to (i+1, i).
Now, question is how many rounds to go? It depends on n. We can notice that each round i we are traversing a submatrix with (0,0) and (n-i-1, n-i-1) as the right diagonal corners. We are traversing two elements of the diagonal of the original matrix per round. So, no of rounds is n/2. If n is odd then the the middle element of the right diagonal should be left after n/2 rounds as described above.
void PrintSpiral(int[][] input)
{
//assuming square matrix
int n = input.length;
StringBuilder sb = new StringBuilder();
for(int i=0; i<n/2;i++)
{
for(int j=i; j<n-i; j++)
sb.append(input[i][j]);
for(int j=i+1; j<n-i-1; j++)
sb.append(input[j][n-i-1]);
for(int j=n-i-1; j>=i; j--)
sb.append(input[n-i-1][j]);
for(int j=n-i-2; j>=i-1; j++)
sb.append(input[n-i-1][j]);
}
if(n%2 == 1)
sb.append(input[n/2][n/2]);
System.out.println(sb.toString());
}
Tree is a directed acyclic graph. So, there should have only one path from root to any node in the tree. If this property is violated then the graph is not a tree and might have the potential chance for having a loop. We can easily check this by checking number of incoming edges to a node.
1) If a non-root node has more than one incoming edge then loop exists only if the edge is from a child to an ancestor.
2) If the root contains an incoming edge then loop surely exists.
If we have a tree like
a
/ \
b c
/ \
d e
Now assume there is an edge from d to b (d, a). This edge will create a loop according to (2). Now assume an edge from d to b: (d, b). Then there will be a loop according to (1). But if e have an edge from e to c : (e,c) then there exist no loop although the tree is not tree anymore as there are more than one path from root to c.
Tree is a directed acyclic graph. So, there should have only one path from root to any node in the tree. If this property is violated then the graph is not a tree and might have the potential chance for having a loop. We can easily check this by checking number of incoming edges to a node.
1) If a non-root node has more than one incoming edge then loop exists only if the edge is from a child to an ancestor.
2) If the root contains an incoming edge then loop surely exists.
If we have a tree like
a
/ \
b c
/ \
d e
Now assume there is an edge from d to b (d, a). This edge will create a loop according to (2). Now assume an edge from d to b: (d, b). Then there will be a loop according to (1). But if e have an edge from e to c : (e,c) then there exist no loop although the tree is not tree anymore as there are more than one path from root to c.
int maxPath(TreeNode* root, int *height)
{
if(!root)
{
*height = 0;
return 0;
}
int lh=0, rh=0;
int ld = diameter(root->left, &lh);
int rd = diameter(root->right, &rh);
*height = 1+max(lh, rh);
return max(max(ld, rd), 1+lh+rh);
}
Approach 1: w/o sorting it’ll be O(n^2) as we need to iterate the 2nd list for each element of 1st list
Approach 2: sort the arrays with O(nlgn), n is the size of larger array. Then for each element in first array find the last element of a decreasing diff sequence in the 2nd array. The sequence starts from the next element of the previous sequence’s last element in the 2nd array. So, we are scanning both the array at most once and hence the complexity is O(m+n) = O(n). Total complexity: O(nlgn)+O(n) = O(nlgn)
O(nlgn) solution:
int minDiff(int[] A, int B[])
{
int i, j, diff, Prevdiff, mindiff = MAX_INTEGER;
quicksort(A);
quicksort(B);
for(i=0, j=0; i<A.length; i++)
{
prevdiff = MAX_INTEGER;
while(j<B.length && (diff = Math.abs(A[i]-B[j])) <= prevDiff)
{
prevDiff = diff;
j++;
}
if(prevDiff <= mindiff)
mindiff = prevDiff;
}
return mindiff;
}
O(nlgn) with O(1) space solution
1. Sort the array.
2. Scan the sorted array from left to right. keep minDiff to contain the min difference between two elements during the scan.
3. If diff between two consecutive is less than minDiff so far then create a list and add the pair.
4. if diff between two consecutive is equal to minDiff that means there is already a list. Add the pair to the list.
public static List<Pair> getMinDiff(int[] A)
{
ArrayList<Pair> pairs;
int minDiff = Integer.MAX;
A=quicksort(A);
for(int i=0;i<A.length-1;i++)
{
if (abs(A[i+1]-A[i]) < minDiff)
{
pairs = new ArrayList<Pair>();
pairs.add(new Pair(A[i], A[i+1]));
minDiff = abs(A[i+1]-A[i]) ;
}
else if (abs(A[i+1]-A[i]) == minDiff)
{
pairs.add(new Pair(A[i], A[i+1]));
}
}
return pairs;
}
I think we don't need to construct any kind of automata as it is a simple pattern o match. Below is a simple implementation in C:
int regex(char* str, char* pattern)
{
int str_marker=0;
int pattern_marker=0;
while(str[str_marker] && pattern[pattern_marker])
{
if(str[str_marker] == pattern[pattern_marker])
{
str_marker++;
if(pattern[pattern_marker+1] == ‘+’)
pattern[pattern_marker+1]=’*’;
if(pattern[pattern_marker+1] != ’*’)
pattern_marker++;
}
else if(pattern[pattern_marker+1]==’*’)
{
pattern_marker+=2;
}
else return 0;
}
return str[str_marker] == pattern[pattern_marker];
}
Here is a simple code in C:
int regex(char* str, char* pattern)
{
int str_marker=0;
int pattern_marker=0;
while(str[str_marker] && pattern[pattern_marker])
{
if(str[str_marker] == pattern[pattern_marker])
{
str_marker++;
if(pattern[pattern_marker+1] == ‘+’)
pattern[pattern_marker+1]=’*’;
if(pattern[pattern_marker+1] != ’*’)
pattern_marker++;
}
else if(pattern[pattern_marker+1]==’*’)
{
pattern_marker+=2;
}
else return 0;
}
return str[str_marker] == pattern[pattern_marker];
}
I wrote exactly what the interviewer asked me.... may be it was confusing but it is what exactly was asked...
but this is good in a sense that people now solves complex version of the problem. That is good anyway :)
@abhisek, you are wrong... the patterns are prefixes from beginning . See my comment above.
- zahidbuet106 February 15, 2013let me clear the confusion about the question the interviewer asked me:
first of all, the numbers in the pattern are not consecutive so, 36512 could be a prefix. Interviewer asked me first what data structure would you use for efficiently detecting a new cheque. I answered Trie. He said, good, that's the best choice to go. Now, If I say you need to match in O(1) time does your solution still correct. I said yes as we know that number of digits in a cheque number is fixed. SO length of prefixes are constant. That means traversing the trie for a prefix is of constant order i.e. O(1). It is a easy stuff guys, not that complex!!
it was told that visiting root node is unnecessary because for example the node in question might be most deep node in the tree.
- zahidbuet106 February 13, 2013yeah your soln will not work. For example, it'll fail for next(6)=7.. you need to backtrack to grand parent...
- zahidbuet106 February 13, 2013with Hashmap you can not do it because prefixes may contain other prefix. it'll take O(n) ultimately.
Eugene is right... .we don't want the runtime to be proportional to the number of patterns... in that sense it is order of constant time actually.
Here was my solution:
public class Node
{
public Node left;
public Node right;
public Node parent;
public int value
public static Node findNext(Node n)
{
Node parent p=n.parent
if(parent == null)
return findNode(parent.left);
if(n==parent.left && parent.right == null)
return parent;
else if(n==parent.right && parent.right != null))
return findNode(parent.right);
}
}
Use trie.
- zahidbuet106 February 13, 2013Machine A is in cloud so it doesn't save state of a transaction. The next transactin could go through machine B.
Answer is to send remaining balance in the transaction instead of transaction amount. This is a standard practice in payment systems.
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 ...
A simple recursive solution--
- zahidbuet106 December 16, 2013