[algogeeks] Complexity doubt
guys can anyone tell me the link from where i can read about the big o ,big w and big q ...i read from corma but i didnt get theses from that...thnx in advance -- 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] Indus Valley Partners Paper Pattern
please go through this blog http://interviewdestiny.blogspot.in/2011/11/indus-valley-partners-procedure-in-2011.html it shows the coding problems asked but I don't remember the apti ques. On Mon, Aug 20, 2012 at 10:53 PM, vipul jain vjvipu...@gmail.com wrote: yar i forgot those coding question and there were 20 question and covering each and every topic of apti but u shud score 18 out of it becoz simole hote h vo On Mon, Aug 20, 2012 at 7:37 PM, Arun Kindra arunkin...@gmail.com wrote: Is it for campus recruitment process or Off campus? And can u specify the Apti topic, and is there any analytical reasoning? If possible plz share Coding ques. -- 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 Regards Vipul Jain lVth yr Information Technology Nit Jaipur -- 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 *Ravi Maggon Member Technical - IT/Front Office D.E. Shaw Co. -- 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] Gate complaxity question
*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.
Re: [algogeeks] Gate complaxity question
Because you can always find a positive constant c for which following inequality hold true. A(n) = cW(n) i.e. the avg. case time complexity always upper bounded by worst case time complexity. Which is the definition of Big O. 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. -- 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
You have to discard option d because , according to definition of small o notation if f(n) =o(g(n)) then for ALL constants c 0 you have f(n) cg(n). or Lim(n-infinite) f(n)/g(n) = 0. On Sat, Aug 25, 2012 at 10:24 PM, vishal yadav vishalyada...@gmail.comwrote: Because you can always find a positive constant c for which following inequality hold true. A(n) = cW(n) i.e. the avg. case time complexity always upper bounded by worst case time complexity. Which is the definition of Big O. 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. -- 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
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_and_da...@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/**
msg/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-x06vpkJ.
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] Amazon Q
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.
Re: [algogeeks] Re: Printing random word from file
@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 javascript:
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/**
msg/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-x06vpkJ.
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/-/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.
