[algogeeks] amazon Interview
You are given many slabs each with a length and a breadth. A slab i can be put on slab j if both dimensions of i are less than that of j. In this similar manner, you can keep on putting slabs on each other. Find the maximum stack possible which you can create out of the given slabs and for general n-dimesions -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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 Q
Q1 Solution: . we can use doubly linked list with hash to implement all the
operation in O(1).
By keeping track of head and tail pointer we can do enqueue and dequeue in
O(1) time.
In hash we will keep track of each element present in linked list(queue).
With node value as a hash key and address of node as a value. So for
searching we can do it in O(1).
For deleting an element we will directly take address of that value from
hash and delete it. O(1) time.
Q2. /*my code will return NULL if not palindrome and head if it is
palindrome */
count = totalnode/2;
//odd = 0 if totalnode is even else 1
struct node *checkPalindrome(struct node *head, int count)
{
struct node *temp;
if(count == 0) {
if(odd head-next) return head-next;
else return head;
}
if(count 0)
temp = checkPalindrome(head-next, count - 1);
if(temp (temp-data == head-data ) !temp-next)
return head;
else if (temp (temp-data == head-data ))
return temp-next;
else return NULL;
}
On Sun, Aug 26, 2012 at 12:41 AM, Ashish Goel ashg...@gmail.com wrote:
Q1. Design a data structure for the following operations:
I.Enqueue
II. Dequeue
III. Delete a given number(if it is present in the queue,
else do nothing)
IV. isNumberPresent
All these operations should take O(1) time.
Q2. Check if a linked list (each char is a node) is palindrome,
recursively.
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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 algogeeks@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 Interview
its a LIS problem. need to think for n-dimension... On 8/26/12, Ravi Ranjan ravi.cool2...@gmail.com wrote: You are given many slabs each with a length and a breadth. A slab i can be put on slab j if both dimensions of i are less than that of j. In this similar manner, you can keep on putting slabs on each other. Find the maximum stack possible which you can create out of the given slabs and for general n-dimesions -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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 algogeeks@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] CISCO Written Test ??
Hi all, Whether anyone appeared for CISCO this year? If so pls provide me the *written test pattern* as well as the interview process. Thanks in advance!! -- Regards, Swaminathan M -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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] Gate complaxity question
see A(n)ie the average case will always be smaller or equal to the worst case... ie something like... A(n)= c. w(n) for some c as constt ... which the definition of big O... correct me if i'm wrong.. On Sat, Aug 25, 2012 at 7:11 PM, rahul sharma rahul23111...@gmail.comwrote: *Let w(n) and A(n) denote respectively, the worst case and average case running time of an algorithm executed on an input of size n. which of the following is ALWAYS TRUE?* (A) [image: A(n) = \Omega(W(n))] (B) [image: A(n) = \Theta(W(n))] (C) [image: A(n) = O(W(n))] (D) [image: A(n) = o(W(n))] answer is c plz explain y??? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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. -- Regards, GAURAV CHAWLA +919992635751 +919654127192 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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] ATRENTA PAPERS
Atrenta is visiting our campus on tuesday.Can anyone please mail me the placement papers of atrenta.. Thanks in acknowledgement... -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/z88-Sf-venoJ. To post to this group, send email to algogeeks@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 Interview
Yeah Atul is right.
Here is my solution:--
1) first rearrange the dimensions of slabs i.e. put bigger dimension in y
and smaller dimenson in x (rotate the slab)
2) then arrange all slabs in increasing order of x dimension
3) and then find the longest increasing sub-sequence based on y
dimension..
Ex:- (2,5),(5,1),(1,3),(1,2),(6,1)
Step-1= (2,5),(1,5),(1,3),(1,2),(1,6)
Step-2= (1,2),(1,3),(1,5),(1,6),(2,5)
Step-3= LIS=4 { (1,2),(1,3),(1,5),(1,6) OR (1,2),(1,3),(1,5),(2,5) }
Correct me if i wrong...
On Sun, Aug 26, 2012 at 3:54 PM, atul anand atul.87fri...@gmail.com wrote:
its a LIS problem.
need to think for n-dimension...
On 8/26/12, Ravi Ranjan ravi.cool2...@gmail.com wrote:
You are given many slabs each with a length and a breadth. A slab i can
be
put on slab j if both dimensions of i are less than that of j. In this
similar manner, you can keep on putting slabs on each other. Find the
maximum stack possible which you can create out of the given slabs
and for general n-dimesions
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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 algogeeks@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.
--
--
‘Kailash Bagaria’
B-tech 4th year
Computer Science Engineering
Indian Institute of Technology, Roorkee
Roorkee, India (247667)
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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] max sum b/w 2 leaf nodes in a binary tree
Hi, Can anyone suggest the best approach for finding max sum b/w 2 leaf nodes in a binary tree ( not BST ) ? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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] max sum b/w 2 leaf nodes in a binary tree
its the diameter of tree. you can find implementation on geeksforgeeks On 8/25/12, kunal rustgi rustogi.ku...@gmail.com wrote: Hi, Can anyone suggest the best approach for finding max sum b/w 2 leaf nodes in a binary tree ( not BST ) ? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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 algogeeks@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 Interview
@kailash : you can simply find area of each slab area=x*y ,,,store it;
then just run LIS on this area.
On 8/26/12, Kailash Bagaria kbkailashbaga...@gmail.com wrote:
Yeah Atul is right.
Here is my solution:--
1) first rearrange the dimensions of slabs i.e. put bigger dimension in y
and smaller dimenson in x (rotate the slab)
2) then arrange all slabs in increasing order of x dimension
3) and then find the longest increasing sub-sequence based on y
dimension..
Ex:- (2,5),(5,1),(1,3),(1,2),(6,1)
Step-1= (2,5),(1,5),(1,3),(1,2),(1,6)
Step-2= (1,2),(1,3),(1,5),(1,6),(2,5)
Step-3= LIS=4 { (1,2),(1,3),(1,5),(1,6) OR (1,2),(1,3),(1,5),(2,5)
}
Correct me if i wrong...
On Sun, Aug 26, 2012 at 3:54 PM, atul anand atul.87fri...@gmail.com
wrote:
its a LIS problem.
need to think for n-dimension...
On 8/26/12, Ravi Ranjan ravi.cool2...@gmail.com wrote:
You are given many slabs each with a length and a breadth. A slab i can
be
put on slab j if both dimensions of i are less than that of j. In this
similar manner, you can keep on putting slabs on each other. Find the
maximum stack possible which you can create out of the given slabs
and for general n-dimesions
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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 algogeeks@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.
--
--
‘Kailash Bagaria’
B-tech 4th year
Computer Science Engineering
Indian Institute of Technology, Roorkee
Roorkee, India (247667)
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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 algogeeks@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 Interview
@Atul007: No, because a (1,4) tile will not fit on a (2,3) tile.
Dave
On Sunday, August 26, 2012 7:45:27 AM UTC-5, atul007 wrote:
@kailash : you can simply find area of each slab area=x*y ,,,store it;
then just run LIS on this area.
On 8/26/12, Kailash Bagaria kbkailas...@gmail.com javascript: wrote:
Yeah Atul is right.
Here is my solution:--
1) first rearrange the dimensions of slabs i.e. put bigger dimension in
y
and smaller dimenson in x (rotate the slab)
2) then arrange all slabs in increasing order of x dimension
3) and then find the longest increasing sub-sequence based on y
dimension..
Ex:- (2,5),(5,1),(1,3),(1,2),(6,1)
Step-1= (2,5),(1,5),(1,3),(1,2),(1,6)
Step-2= (1,2),(1,3),(1,5),(1,6),(2,5)
Step-3= LIS=4 { (1,2),(1,3),(1,5),(1,6) OR
(1,2),(1,3),(1,5),(2,5)
}
Correct me if i wrong...
On Sun, Aug 26, 2012 at 3:54 PM, atul anand
atul.8...@gmail.comjavascript:
wrote:
its a LIS problem.
need to think for n-dimension...
On 8/26/12, Ravi Ranjan ravi.c...@gmail.com javascript: wrote:
You are given many slabs each with a length and a breadth. A slab i
can
be
put on slab j if both dimensions of i are less than that of j. In
this
similar manner, you can keep on putting slabs on each other. Find the
maximum stack possible which you can create out of the given slabs
and for general n-dimesions
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to
algo...@googlegroups.comjavascript:.
To unsubscribe from this group, send email to
algogeeks+...@googlegroups.com javascript:.
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
algo...@googlegroups.comjavascript:.
To unsubscribe from this group, send email to
algogeeks+...@googlegroups.com javascript:.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
--
‘Kailash Bagaria’
B-tech 4th year
Computer Science Engineering
Indian Institute of Technology, Roorkee
Roorkee, India (247667)
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algo...@googlegroups.comjavascript:.
To unsubscribe from this group, send email to
algogeeks+...@googlegroups.com javascript:.
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 view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/ABJAgG77YhkJ.
To post to this group, send email to algogeeks@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 Interview
@dave : correct..
i guess this will work :-
sort in decreasing area.
then run LIS such that for i j , length( i ) length( j ) width(
i ) width( j )
On 8/26/12, Dave dave_and_da...@juno.com wrote:
@Atul007: No, because a (1,4) tile will not fit on a (2,3) tile.
Dave
On Sunday, August 26, 2012 7:45:27 AM UTC-5, atul007 wrote:
@kailash : you can simply find area of each slab area=x*y ,,,store it;
then just run LIS on this area.
On 8/26/12, Kailash Bagaria kbkailas...@gmail.com javascript: wrote:
Yeah Atul is right.
Here is my solution:--
1) first rearrange the dimensions of slabs i.e. put bigger dimension in
y
and smaller dimenson in x (rotate the slab)
2) then arrange all slabs in increasing order of x dimension
3) and then find the longest increasing sub-sequence based on y
dimension..
Ex:- (2,5),(5,1),(1,3),(1,2),(6,1)
Step-1= (2,5),(1,5),(1,3),(1,2),(1,6)
Step-2= (1,2),(1,3),(1,5),(1,6),(2,5)
Step-3= LIS=4 { (1,2),(1,3),(1,5),(1,6) OR
(1,2),(1,3),(1,5),(2,5)
}
Correct me if i wrong...
On Sun, Aug 26, 2012 at 3:54 PM, atul anand
atul.8...@gmail.comjavascript:
wrote:
its a LIS problem.
need to think for n-dimension...
On 8/26/12, Ravi Ranjan ravi.c...@gmail.com javascript: wrote:
You are given many slabs each with a length and a breadth. A slab i
can
be
put on slab j if both dimensions of i are less than that of j. In
this
similar manner, you can keep on putting slabs on each other. Find the
maximum stack possible which you can create out of the given slabs
and for general n-dimesions
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to
algo...@googlegroups.comjavascript:.
To unsubscribe from this group, send email to
algogeeks+...@googlegroups.com javascript:.
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
algo...@googlegroups.comjavascript:.
To unsubscribe from this group, send email to
algogeeks+...@googlegroups.com javascript:.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
--
‘Kailash Bagaria’
B-tech 4th year
Computer Science Engineering
Indian Institute of Technology, Roorkee
Roorkee, India (247667)
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to
algo...@googlegroups.comjavascript:.
To unsubscribe from this group, send email to
algogeeks+...@googlegroups.com javascript:.
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 view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/ABJAgG77YhkJ.
To post to this group, send email to algogeeks@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 algogeeks@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 Q
Q2) get to n/2 nodes Reverse link list after n/2 nodes Now check from 1st node and n/2 node for equality Can make the checking for equality function recursive Sent from my iPhone 4 On 26-Aug-2012, at 12:41 AM, Ashish Goel ashg...@gmail.com wrote: Q1. Design a data structure for the following operations: I.Enqueue II. Dequeue III. Delete a given number(if it is present in the queue, else do nothing) IV. isNumberPresent All these operations should take O(1) time. Q2. Check if a linked list (each char is a node) is palindrome, recursively. Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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 algogeeks@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] Gate complaxity question
@ll...thnx a lot On Sat, Aug 25, 2012 at 8:22 PM, GAURAV CHAWLA togauravcha...@gmail.comwrote: see A(n)ie the average case will always be smaller or equal to the worst case... ie something like... A(n)= c. w(n) for some c as constt ... which the definition of big O... correct me if i'm wrong.. On Sat, Aug 25, 2012 at 7:11 PM, rahul sharma rahul23111...@gmail.comwrote: *Let w(n) and A(n) denote respectively, the worst case and average case running time of an algorithm executed on an input of size n. which of the following is ALWAYS TRUE?* (A) [image: A(n) = \Omega(W(n))] (B) [image: A(n) = \Theta(W(n))] (C) [image: A(n) = O(W(n))] (D) [image: A(n) = o(W(n))] answer is c plz explain y??? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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. -- Regards, GAURAV CHAWLA +919992635751 +919654127192 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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 algogeeks@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: CISCO Written Test ??
written test will be (apti + tech) no negative marking apti from time , speed and distance, probablity , mixtures , profit and loss (easy) 2 qs to infer from the passage given(critical reasoning) 1 DI set (too simple) and technical qs 2 simple C o/p qs A large %age of qs was from digital logic design , OS , networking only 1 qs(which layer guarantees reliable end to end transmission) do practice the qs given on various sites,most of the qs are just repeated... Interview process :- resume based -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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: Printing random word from file
Okay..missed it..thnx fr info..
Your approach is nice..it took me some time to understand your code's
though.. Great answer!!
On Aug 26, 2012 3:55 AM, Dave dave_and_da...@juno.com wrote:
@Kunal: Yes. You are missing that you don't know the number of words in
the file in advance. So, to use your method, you would have to read the
file once to find n, and then read through it again to select the lucky_pos
th word. The method I proposed only requires reading the file once.
Furthermore, assuming that rand() produces a random non-negative integer,
rand()%n is not equiprobable for all values of n. Consider n = 3. Then
since rand() takes on 2^31 values, rand()%3 cannot take on the values 0, 1,
and 2 with equal probability since 2^31 is not divisible by 3.
Dave
On Saturday, August 25, 2012 1:44:03 PM UTC-5, Kunal Patil wrote:
How about using rand()%n ??
Like, calculate lucky_pos = rand()%n
Then print word at lucky_pos th position...
Am I missing anything? All words are still equiprobable to get printed
right?
On Aug 20, 2012 11:45 AM, Dave dave_an...@juno.com wrote:
@Navin: Okay. Here is a paraphrase. Assume double function random()
returns a uniformly distributed random number = 0.0 and 1.0.
read first word from file into string save;
int i = 1
while not EOF
{
read next word from file into string temp;
i++;
if( i * random() 1.0 )
copy temp to save;
}
print save;
Dave
On Monday, August 20, 2012 12:02:54 AM UTC-5, Navin Kumar wrote:
@Dave sir, I didn't get your logic. Can you please elaborate it?
On Sun, Aug 19, 2012 at 4:08 AM, Dave dave_an...@juno.com wrote:
@Navin: Here is the algorithm:
Save the first word.
For i = 2, 3, ..., n = number of words in the file
replace the saved word with the i-th word with probability 1/i.
When EOF is reached, every word in the file will have probability 1/n
of being the saved word. Print it.
Dave
On Saturday, August 18, 2012 1:28:56 AM UTC-5, Navin Kumar wrote:
Print a *Random word* from a file. Input is path to a file,
constraints- No extra memory like hashing etc. All the words in the
file should have equal probability.
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To view this discussion on the web visit https://groups.google.com/d/*
*ms**g/algogeeks/-/HxO-wNzEP9gJhttps://groups.google.com/d/msg/algogeeks/-/HxO-wNzEP9gJ
.
To post to this group, send email to algo...@googlegroups.com.
To unsubscribe from this group, send email to algogeeks+...@**
googlegroups.com**.
For more options, visit this group at http://groups.google.com/**group
**/algogeeks?hl=en http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To view this discussion on the web visit https://groups.google.com/d/**
msg/algogeeks/-/crET-x06vpkJhttps://groups.google.com/d/msg/algogeeks/-/crET-x06vpkJ
.
To post to this group, send email to algo...@googlegroups.com.
To unsubscribe from this group, send email to algogeeks+...@**
googlegroups.com.
For more options, visit this group at http://groups.google.com/**
group/algogeeks?hl=en http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/pvqb27sRhFAJ.
To post to this group, send email to algogeeks@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 algogeeks@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] Question on checking divisibility of binomial coefficients of a number by a prime number
In mathematics, *binomial coefficients* are a family of positive integers that occur as coefficients in the binomial theorem. [image: \tbinom nk]denotes the number of ways of choosing k objects from n different objects. However when n and k are too large, we often save them after modulo operation by a prime number P. Please calculate how many binomial coefficients of n become to 0 after modulo by P. *Input* The first of input is an integer T , the number of test cases. Each of the following T lines contains 2 integers, n and prime P. *Output* For each test case, output a line contains the number of [image: \tbinom nk]s (0=k=n) each of which after modulo operation by P is 0. *Sample Input* 3 2 2 3 2 4 3 *Sample Output* 1 0 1 *Constraints:* T is less than 100 n is less than 10500. P is less than 109. I Have applied a logic that if any binomial coefficient can be written as n!/(n-k)!k! so if (n/p)((n-k)/p+k/p) so that coefficient will be divisiblr by prime number p. but the problem is range of is so large so if i give an input of that much range it will take more then 15 min . although complexity of my code is O(n/2) but my program keep on running because of very high range of input. Can anyone help me in this please?? Thank you -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/ow00hepNjeMJ. To post to this group, send email to algogeeks@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: Printing random word from file
@Dave: Can you throw some light on random() function?? How it is generating
numbers between 0.0 and 1.0, and how many digits are there after the
point...because if there is only one digit then we will not be able to
print words after 10th place because 10*0.1(lowest number generated by
random())=1...since lowest number generated by the random() function is not
able to convert 10th word into printable situation,so we can't print words
above 10th place (inclusive) so it's not solving the original
problem???
On Sun, Aug 26, 2012 at 3:55 AM, Dave dave_and_da...@juno.com wrote:
@Kunal: Yes. You are missing that you don't know the number of words in
the file in advance. So, to use your method, you would have to read the
file once to find n, and then read through it again to select the lucky_pos
th word. The method I proposed only requires reading the file once.
Furthermore, assuming that rand() produces a random non-negative integer,
rand()%n is not equiprobable for all values of n. Consider n = 3. Then
since rand() takes on 2^31 values, rand()%3 cannot take on the values 0, 1,
and 2 with equal probability since 2^31 is not divisible by 3.
Dave
On Saturday, August 25, 2012 1:44:03 PM UTC-5, Kunal Patil wrote:
How about using rand()%n ??
Like, calculate lucky_pos = rand()%n
Then print word at lucky_pos th position...
Am I missing anything? All words are still equiprobable to get printed
right?
On Aug 20, 2012 11:45 AM, Dave dave_an...@juno.com wrote:
@Navin: Okay. Here is a paraphrase. Assume double function random()
returns a uniformly distributed random number = 0.0 and 1.0.
read first word from file into string save;
int i = 1
while not EOF
{
read next word from file into string temp;
i++;
if( i * random() 1.0 )
copy temp to save;
}
print save;
Dave
On Monday, August 20, 2012 12:02:54 AM UTC-5, Navin Kumar wrote:
@Dave sir, I didn't get your logic. Can you please elaborate it?
On Sun, Aug 19, 2012 at 4:08 AM, Dave dave_an...@juno.com wrote:
@Navin: Here is the algorithm:
Save the first word.
For i = 2, 3, ..., n = number of words in the file
replace the saved word with the i-th word with probability 1/i.
When EOF is reached, every word in the file will have probability 1/n
of being the saved word. Print it.
Dave
On Saturday, August 18, 2012 1:28:56 AM UTC-5, Navin Kumar wrote:
Print a *Random word* from a file. Input is path to a file,
constraints- No extra memory like hashing etc. All the words in the
file should have equal probability.
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To view this discussion on the web visit https://groups.google.com/d/*
*ms**g/algogeeks/-/HxO-wNzEP9gJhttps://groups.google.com/d/msg/algogeeks/-/HxO-wNzEP9gJ
.
To post to this group, send email to algo...@googlegroups.com.
To unsubscribe from this group, send email to algogeeks+...@**
googlegroups.com**.
For more options, visit this group at http://groups.google.com/**group
**/algogeeks?hl=en http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To view this discussion on the web visit https://groups.google.com/d/**
msg/algogeeks/-/crET-x06vpkJhttps://groups.google.com/d/msg/algogeeks/-/crET-x06vpkJ
.
To post to this group, send email to algo...@googlegroups.com.
To unsubscribe from this group, send email to algogeeks+...@**
googlegroups.com.
For more options, visit this group at http://groups.google.com/**
group/algogeeks?hl=en http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/pvqb27sRhFAJ.
To post to this group, send email to algogeeks@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.
--
--
‘Kailash Bagaria’
B-tech 4th year
Computer Science Engineering
Indian Institute of Technology, Roorkee
Roorkee, India (247667)
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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: Question on checking divisibility of binomial coefficients of a number by a prime number
@Ankit: Apply Lucas' Theorem, which you can find written up in Wikipedia. Dave On Sunday, August 26, 2012 3:57:18 PM UTC-5, Ankit Singh wrote: In mathematics, *binomial coefficients* are a family of positive integers that occur as coefficients in the binomial theorem. [image: \tbinom nk]denotes the number of ways of choosing k objects from n different objects. However when n and k are too large, we often save them after modulo operation by a prime number P. Please calculate how many binomial coefficients of n become to 0 after modulo by P. *Input* The first of input is an integer T , the number of test cases. Each of the following T lines contains 2 integers, n and prime P. *Output* For each test case, output a line contains the number of [image: \tbinom nk]s (0=k=n) each of which after modulo operation by P is 0. *Sample Input* 3 2 2 3 2 4 3 *Sample Output* 1 0 1 *Constraints:* T is less than 100 n is less than 10500. P is less than 109. I Have applied a logic that if any binomial coefficient can be written as n!/(n-k)!k! so if (n/p)((n-k)/p+k/p) so that coefficient will be divisiblr by prime number p. but the problem is range of is so large so if i give an input of that much range it will take more then 15 min . although complexity of my code is O(n/2) but my program keep on running because of very high range of input. Can anyone help me in this please?? Thank you -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/aLFSGCkdtmsJ. To post to this group, send email to algogeeks@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: CISCO Written Test ??
Der were many questions from electronics part also..20 apti 20 electronic ques 10 c/netwrking ques..So computer science people will have a tough luck.So revise basics of electronics. ques like half wave rectifier efficiency were asked On Sun, Aug 26, 2012 at 10:24 PM, deepikaanand swinyanand...@gmail.comwrote: written test will be (apti + tech) no negative marking apti from time , speed and distance, probablity , mixtures , profit and loss (easy) 2 qs to infer from the passage given(critical reasoning) 1 DI set (too simple) and technical qs 2 simple C o/p qs A large %age of qs was from digital logic design , OS , networking only 1 qs(which layer guarantees reliable end to end transmission) do practice the qs given on various sites,most of the qs are just repeated... Interview process :- resume based -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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. -- * Thanks And Sincere Regards Apoorv Gupta Btech Final Year Computer Science And Engineering MNNIT Allahabad * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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 Interview
but how to solve this problem for with n-dimension ??
On Sun, Aug 26, 2012 at 6:47 PM, atul anand atul.87fri...@gmail.com wrote:
@dave : correct..
i guess this will work :-
sort in decreasing area.
then run LIS such that for i j , length( i ) length( j ) width(
i ) width( j )
On 8/26/12, Dave dave_and_da...@juno.com wrote:
@Atul007: No, because a (1,4) tile will not fit on a (2,3) tile.
Dave
On Sunday, August 26, 2012 7:45:27 AM UTC-5, atul007 wrote:
@kailash : you can simply find area of each slab area=x*y ,,,store it;
then just run LIS on this area.
On 8/26/12, Kailash Bagaria kbkailas...@gmail.com javascript:
wrote:
Yeah Atul is right.
Here is my solution:--
1) first rearrange the dimensions of slabs i.e. put bigger dimension
in
y
and smaller dimenson in x (rotate the slab)
2) then arrange all slabs in increasing order of x dimension
3) and then find the longest increasing sub-sequence based on y
dimension..
Ex:- (2,5),(5,1),(1,3),(1,2),(6,1)
Step-1= (2,5),(1,5),(1,3),(1,2),(1,6)
Step-2= (1,2),(1,3),(1,5),(1,6),(2,5)
Step-3= LIS=4 { (1,2),(1,3),(1,5),(1,6) OR
(1,2),(1,3),(1,5),(2,5)
}
Correct me if i wrong...
On Sun, Aug 26, 2012 at 3:54 PM, atul anand
atul.8...@gmail.comjavascript:
wrote:
its a LIS problem.
need to think for n-dimension...
On 8/26/12, Ravi Ranjan ravi.c...@gmail.com javascript: wrote:
You are given many slabs each with a length and a breadth. A slab i
can
be
put on slab j if both dimensions of i are less than that of j. In
this
similar manner, you can keep on putting slabs on each other. Find
the
maximum stack possible which you can create out of the given slabs
and for general n-dimesions
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to
algo...@googlegroups.comjavascript:.
To unsubscribe from this group, send email to
algogeeks+...@googlegroups.com javascript:.
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
algo...@googlegroups.comjavascript:.
To unsubscribe from this group, send email to
algogeeks+...@googlegroups.com javascript:.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
--
‘Kailash Bagaria’
B-tech 4th year
Computer Science Engineering
Indian Institute of Technology, Roorkee
Roorkee, India (247667)
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to
algo...@googlegroups.comjavascript:.
To unsubscribe from this group, send email to
algogeeks+...@googlegroups.com javascript:.
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 view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/ABJAgG77YhkJ.
To post to this group, send email to algogeeks@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 algogeeks@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.
