I think i hve figured out the actual answer .
Suppose we maintain a queue of N words in the memory.
With two things
1. front 2. rear
As a new word enters (recognized by a space)
-> front = front.next;
if(it is already there in the list )
++frequency of occurence;
else{
-> temp = rear;
-> r
list lastNWords contains last N words, first being the one encountered
most recently
// suppose following function gets called whenever a new word is encountered
void addNewWord(string newWord, map::iterator>& mp,
list& lastNWords)
{
lastNWords.push_front(newWord);
if(mp.find(newWord) !
@Richa
Okey..
For this scenario,
Extracting a node => output the root node, decrement its frequency
count and remove the root node only if frequency count becomes 0.
Heapify.
Adding a node => locate a node which corresponds to same character as
the inserted char in O(N) time, if it exists and incr
First of all GoogleGroups suxs, its takes so.. long for the new
post/reply to appear.
Secondly I think we can improve the algorithm by having a hash table
auxillary to the max heap we have constructed.
Here the size of the hashtable is the size of the alphabet set (a
constant).
In that case w
Well Hi to all ,
I think the things aren't so complicated as they look here
I suppose there is a list of N numbers in a Linked List(along with the
frequency).
Whenever a user types a new word (recognized by a space),
this word is matched with the available words in the list
if (match)
{
++frequ
@dufus :
suppose the words occurs like ( at the last of the document or u can say
that in the window of size N , the scenario is )
l, b,b,b, c , d,d, e a
so ur max heap will make it
b(3)
d(2)c(1)
e(1) a (1) l(1)
now explain me what happens when b or
@ Arun :
I guess what ever solution you have proposed will give us the most
frequantly used N words out of the whole document .As you said, getting K
largest element out of total elements.
Here we want , last N words in the document in the decreasing order of their
occurance.
2009/8/17 richa gupta
I think the teoreticaly easiest solution is to have two balanced binary
search trees interlinked. on for finding by string, second for keeping count
second can keep subtree sizes, and every time you check the position and if
it changes then you can update list, you do not have to make more
computat
no I missed the chance bcoz of this question.
Arun,
On Sat, Aug 15, 2009 at 12:45 PM, Dufus wrote:
>
> Hmm..
> @Richa I am assuming the frequency 4,2,7,1 of A,B,C,D word is within
> the last N words window(not in the whole window).
>
> If thats true then I think q can be solved be done in two st
Hmm..
@Richa I am assuming the frequency 4,2,7,1 of A,B,C,D word is within
the last N words window(not in the whole window).
If thats true then I think q can be solved be done in two steps:-
Step 1: we can reach the last n elements using two pointers approach
in O(M-N) i.e. O(M) time
// M = numbe
@ Dufus,
suppose words A, B,C, D occurs at the frequacny 4, 2, 7 ,1 then the code
shud be able to list it like C, A, B, D .
On 2009-08-14, Dufus wrote:
>
>
> @Arun: Did you get the job? (No offence meant)
> @Richa: Could you please elaborate what decreasing order means?
> Assuming decreasing or
@Arun: Did you get the job? (No offence meant)
@Richa: Could you please elaborate what decreasing order means?
Assuming decreasing order means ..last word should be printed in the
end..and if the user adds (appends) new word then it should also be
printed,
this can be done quite elegantly using si
I said that to the interviewer push all elements in max heap and delete k
times
but it requires heap of size 'n'
and he asked me for the most optimal version
of using heap of size 'K' only.
On Fri, Aug 14, 2009 at 4:46 PM, umesh kewat wrote:
> Do just opposite thing to get result delete k eleme
we can also use a queue.add the new word to the front of the queue and
remove word at the rear end of the queue.
On Fri, Aug 14, 2009 at 3:25 PM, Arun N wrote:
>
> This question was asked to me in Amazon interview
>
> 1)use hash table to store a word and its count
> now the problem is reduced t
Do just opposite thing to get result delete k elements from Max heap of
element der u also get k largest numbers
On Fri, Aug 14, 2009 at 3:25 PM, Arun N wrote:
>
> This question was asked to me in Amazon interview
>
> 1)use hash table to store a word and its count
> now the problem is reduce
This question was asked to me in Amazon interview
1)use hash table to store a word and its count
now the problem is reduced to find 'K' largest numbers(based on count) in
the hash table
the optimal solution is to use minheap of size 'K'
add first k elements in the minheap
now take the k+1 eleme
16 matches
Mail list logo
