[algogeeks] Amazon Question
You are provided with a stream of numbers, design a data structure to store the numbers in the stream along with their no. of occurrences. Regards Shashank Mani -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Amazon Question
are we given range of numbers ? On Sun, Dec 26, 2010 at 4:39 PM, bittu shashank7andr...@gmail.com wrote: You are provided with a stream of numbers, design a data structure to store the numbers in the stream along with their no. of occurrences. Regards Shashank Mani -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Amazon Question
i think if it given , can we consider a hash table ? On Sun, Dec 26, 2010 at 4:39 PM, Ankur Khurana ankur.kkhur...@gmail.com wrote: are we given range of numbers ? On Sun, Dec 26, 2010 at 4:39 PM, bittu shashank7andr...@gmail.com wrote: You are provided with a stream of numbers, design a data structure to store the numbers in the stream along with their no. of occurrences. Regards Shashank Mani -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Amazon Question
with BST we can query the occurence in lg (n)
On Sun, Dec 26, 2010 at 5:19 PM, mohit ranjan shoonya.mo...@gmail.com wrote:
@Radha
With BST, the time taken to search a node depends on size (n), which will
keep on increasing as stream grows long, whereas we need to calculate freq
within the fixed time interval for all numbers...
any better solution ?
Mohit
On Sun, Dec 26, 2010 at 4:48 PM, radha krishnan
radhakrishnance...@gmail.com wrote:
An Augmented and self Balancin Binary Search Tree Will suffice
Tree {
int element;
int occurence;
}
when u have the element in the BST increment the occurence
Else create a New node
Total Complexity is O(n lgn )
Correct me if am wrong
lg n -- for finding the previous occurence of the number
On Sun, Dec 26, 2010 at 4:39 PM, bittu shashank7andr...@gmail.com wrote:
You are provided with a stream of numbers, design a data structure to
store the numbers in the stream along with their no. of occurrences.
Regards
Shashank Mani
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Amazon Question
hmm..
ok let me try to explain my point...
suppose in stream, the rate is 1 integer/k time, so within k time we need to
process that number and be ready for next number.
Now when stream has just started, n is small so log(n) is OK, but a time
will come when log(n)k and then numbers will start accumulating
Mohit
On Sun, Dec 26, 2010 at 6:25 PM, radha krishnan
radhakrishnance...@gmail.com wrote:
with BST we can query the occurence in lg (n)
On Sun, Dec 26, 2010 at 5:19 PM, mohit ranjan shoonya.mo...@gmail.com
wrote:
@Radha
With BST, the time taken to search a node depends on size (n), which will
keep on increasing as stream grows long, whereas we need to calculate
freq
within the fixed time interval for all numbers...
any better solution ?
Mohit
On Sun, Dec 26, 2010 at 4:48 PM, radha krishnan
radhakrishnance...@gmail.com wrote:
An Augmented and self Balancin Binary Search Tree Will suffice
Tree {
int element;
int occurence;
}
when u have the element in the BST increment the occurence
Else create a New node
Total Complexity is O(n lgn )
Correct me if am wrong
lg n -- for finding the previous occurence of the number
On Sun, Dec 26, 2010 at 4:39 PM, bittu shashank7andr...@gmail.com
wrote:
You are provided with a stream of numbers, design a data structure to
store the numbers in the stream along with their no. of occurrences.
Regards
Shashank Mani
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Amazon Question
may be we can assume that klog(n)
else i dont see a way out than hashing , because that is the only
thing less that log(n).
On Sun, Dec 26, 2010 at 6:37 PM, mohit ranjan shoonya.mo...@gmail.com wrote:
hmm..
ok let me try to explain my point...
suppose in stream, the rate is 1 integer/k time, so within k time we need to
process that number and be ready for next number.
Now when stream has just started, n is small so log(n) is OK, but a time
will come when log(n)k and then numbers will start accumulating
Mohit
On Sun, Dec 26, 2010 at 6:25 PM, radha krishnan
radhakrishnance...@gmail.com wrote:
with BST we can query the occurence in lg (n)
On Sun, Dec 26, 2010 at 5:19 PM, mohit ranjan shoonya.mo...@gmail.com
wrote:
@Radha
With BST, the time taken to search a node depends on size (n), which
will
keep on increasing as stream grows long, whereas we need to calculate
freq
within the fixed time interval for all numbers...
any better solution ?
Mohit
On Sun, Dec 26, 2010 at 4:48 PM, radha krishnan
radhakrishnance...@gmail.com wrote:
An Augmented and self Balancin Binary Search Tree Will suffice
Tree {
int element;
int occurence;
}
when u have the element in the BST increment the occurence
Else create a New node
Total Complexity is O(n lgn )
Correct me if am wrong
lg n -- for finding the previous occurence of the number
On Sun, Dec 26, 2010 at 4:39 PM, bittu shashank7andr...@gmail.com
wrote:
You are provided with a stream of numbers, design a data structure to
store the numbers in the stream along with their no. of occurrences.
Regards
Shashank Mani
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Find all the subset of an array whose sum is equal to some number
http://en.wikipedia.org/wiki/Subset_sum_problem On Dec 25, 10:52 pm, radha krishnan radhakrishnance...@gmail.com wrote: This s similar to the problemhttps://www.spoj.pl/problems/SUBSUMS/ we have to split the array into 2 arrays say A,B generate all subsets of each array(both A and B) and another array(A1,B1) to store the sum of each subset now take each element of A1 and binarysearch B1 to achieve this sum assume k=2^(n/2) overall complexity is (2*(2^(n/2)) + 2*(k(lgk)) +k lgk) 2^(n/2) for each subset so 2*(2^(n/2)) k(lg k) -- sorting so 2*(k lg k) k(lgk)--binary search On Sat, Dec 25, 2010 at 10:38 PM, Puneet Ginoria punnu.gino...@gmail.com wrote: sorry i forgot to attach here it is On Sat, Dec 25, 2010 at 10:34 PM, Puneet Ginoria punnu.gino...@gmail.com wrote: This attachment contains the code for the above program in SML language and it uses lambda calculus. On Sat, Dec 25, 2010 at 9:18 PM, juver++ avpostni...@gmail.com wrote: What you need to get for the answer - amount of such subsets or display them? First problem can be solved using DP. Second - brute force. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] 10 Most Frequent Search Text
Radix-Trie + Additional Payload Counter - Ursprüngliche Mitteilung - When we type in google for search it will generate search text. For a stream of searchtext how you will find most 10 frequent search text. Give an efficient data structure for this. and also solve it with possible minimum complexity. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] 10 Most Frequent Search Text
@Chi: Would you please explain the process in a little bit more details? It will be helpful. Is Trie and Radix-Trie same? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] DIVIDE TWO VARYING LENGTH NUMBERS.
DIVIDE TWO VARYING LENGTH NUMBERS EX: ONE CAN BE UPTO 60 DIGIT AND OTHER 40 DIGIT Well,I thought of an approach.Store each digit of each number in two separate integer arrays(From right to left).Then apply the subtraction method.Will it be feasible? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] 10 Most Frequent Search Text
A trie is a binary tree with it nodes has as many leafs as is suitable. A binary tree has only 2 leafs per nodes. In a trie it happens that a node doesn't contain any leafs. This happens over many nodes. This is considerable a waste of space. A radix-trie tries to eliminate this empty nodes by compressing them into 1 node. The difference between a radix-trie and suffix-trie is that a suffix-trie can solve text-based problems. A radix-trie is good to store a dictionnary and search for words. Or associative arrays. Or ip addresses. Unlike balanced trees, radix trees permit lookup, insertion, and deletion in O(k) time rather than O(log n). This doesn't seem like an advantage, since normally k ≥ log n, but in a balanced tree every comparison is a string comparison requiring O(k) worst-case time, many of which are slow in practice due to long common prefixes. In a trie, all comparisons require constant time, but it takes m comparisons to look up a string of length m. Radix trees can perform these operations with fewer comparisons and require many fewer nodes. K=key n=string I have a written a kart-trie in php: https://sourceforge.net/projects/kart-trie The only difference to a radix-trie is that the decision to branch either left or right is used with a key of 32-bit. - Ursprüngliche Mitteilung - @Chi: Would you please explain the process in a little bit more details? It will be helpful. Is Trie and Radix-Trie same? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] DIVIDE TWO VARYING LENGTH NUMBERS.
I think that won't be feasible bcoz of high time complexity. Either you can use Python language which provides its own big number pakage or check this link. http://www.cse.iitd.ernet.in/~suban/CSL102/rsa/node21.html On Mon, Dec 27, 2010 at 2:17 AM, Aniket aniket...@gmail.com wrote: DIVIDE TWO VARYING LENGTH NUMBERS EX: ONE CAN BE UPTO 60 DIGIT AND OTHER 40 DIGIT Well,I thought of an approach.Store each digit of each number in two separate integer arrays(From right to left).Then apply the subtraction method.Will it be feasible? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: 1s and 0s
bits manipulation tricks is cool to solve these kind of questions. On Sun, Dec 26, 2010 at 3:27 PM, Praveen Baskar praveen200...@gmail.comwrote: Your Second approach is cool :) On Wed, Dec 22, 2010 at 1:06 PM, juver++ avpostni...@gmail.com wrote: Use bits manipulation tricks. 1. There is a way to remove a group of consecutive 1's from the right: A = n (n + 1). Then check if A==0 then OK. 2. Second approach: B=n+1, check if B (B-1) (this checks if B is a power of 2, so it contains only 1 set bit) is zero then OK. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- B. Praveen -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- What are we to be? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] random function
Linear congruential sequence maybe a simple approach. A[n]=(a*A[n-1]+b)%c, But it's another problem how to chose a,b,c. On Sat, Dec 25, 2010 at 1:05 PM, Puneet Ginoria punnu.gino...@gmail.comwrote: volume 2 , chapter 3 On Fri, Dec 24, 2010 at 11:13 AM, Puneet Ginoria punnu.gino...@gmail.comwrote: There is a book called The art of computer programming by donald knuth. He had discussed the random function in great detail. On Tue, Dec 21, 2010 at 8:06 PM, snehal jain learner@gmail.comwrote: How do you write your own random function? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- What are we to be? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
