Re: [algogeeks] MS Question
you can't implement in O(log n). It can be done in O(log n) in case of Ranked BS Tree. -- Amitesh On Sun, Jan 20, 2013 at 6:23 PM, Praveen praveensonare...@gmail.com wrote: If for all the nodes in BST we also store the size of subtree, then it is possible to find nth smallest element in O(logN). On Sun, Jan 20, 2013 at 4:57 PM, Guneesh Paul Singh gunees...@gmail.comwrote: not possible unless u use augmented bst..which itself takes o(n) to built -- -- Praveen Sonare +91-7838908235 -- --
[algogeeks] Tree - sum problem
Given a binary search tree and a target value, find all the paths (if there exists more than one) which sum up to the target value. It can be any path in the tree. It doesn't have to be from the root. -- Amitesh --
[algogeeks] inplace_merge() implementation
Hi, Just wondering if anybody know the implementation of inplace_merge() defined in C++/STL (algorithm ? Source: http://www.cplusplus.com/reference/algorithm/inplace_merge/ Thanks -- Amitesh -- 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] inplace_merge() implementation
Thanks for the reply. Yes. I know that. Can you please provide a working code? C or C++ Regards -- Amitesh On Thu, Oct 11, 2012 at 2:47 PM, Hanlei Qin qinhan...@gmail.com wrote: The inplace_merge() function is similar to the merge() function, but instead of creating a new sorted range of elements, inplace_merge() alters the existing ranges to perform the merge in-place. --- cppreference.com On Thu, Oct 11, 2012 at 4:02 PM, Amitesh Singh singh.amit...@gmail.comwrote: Hi, Just wondering if anybody know the implementation of inplace_merge() defined in C++/STL (algorithm ? Source: http://www.cplusplus.com/reference/algorithm/inplace_merge/ Thanks -- Amitesh -- 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. -- 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: puzzle
Does the pattern comes in this way? HT,TH,TT or HT(X)TH(X)TT ?? Let me know. -- Amitesh On Sat, Aug 11, 2012 at 11:24 PM, Piyush pkjee2...@gmail.com wrote: How can I find the expected number of tosses , required to obtain a {HT,TH,TT} , by using random variables?? On Friday, December 31, 2010 8:27:46 PM UTC+5:30, Dave wrote: @Anuj and Bittu: It is not necessary to know the bias. You can simulate the flip of an unbiased coin with multiple flips of a biased coin: Flip it twice. If the result is HT, consider it a Head. If the result is TH, consider it a Tail. If the result is HH or TT, repeat the process. It terminates with probability 1. Now use the resulting Head or Tail in the procecure for deciding with a biased coin. Dave On Dec 31, 7:07 am, Anuj Kumar anuj.bhambh...@gmail.com wrote: in case the coin is not biased, we can flip the coin twice and define the rules as if {H,H} comes then ignore it i.e. dont take it as a flip and the 3 other events would be valid onces and could occur with equal probabilities. In case of a biased coin please specify the probability of getting heads and that of getting tails. On Fri, Dec 31, 2010 at 4:11 PM, bittu shashank7andr...@gmail.com wrote: At a restaurant, how can Veronica choose one out of three desserts with equal probability with the help of a coin? What if the coin is biased and the bias is unknown? -- 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.com. To unsubscribe from this group, send email to algogeeks+...@**googlegroups.comalgogeeks%** 2Bunsubscribe@googlegroups.**com . For more options, visit this group at http://groups.google.com/**group/algogeeks?hl=enhttp://groups.google.com/group/algogeeks?hl=en. -- Anuj Kumar Third Year Undergraduate, Dept. of Computer Science and Engineering NIT Durgapur- Hide quoted text - - Show quoted text - -- 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/-/DZdUcelMwtUJ. 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: puzzle
if you meant to calculate the E[x] for [HT,TH,TT]. It can be solvable but very lengthy/boring. I shall give you an example which should help you. Let E[X] = x be the expected no. of coin flips to get [HT] 1) if first flip is a tail, we have wasted one flip hence. E[X1] = 1/2*(1+x) 2) if first flip is a head, and second flip is a head, hence E[X2] = 1/4*(1+1+x) 3) if first flip is a head and second flip is a tail, we are done then. hence E[X3] = 1/4*(1+1) We have, E[X] = E[X1] + E[X2] + E[X3] Solve x here. The same approach you can apply to solve the above problem. I really don't have time to do that for you. Please help yourself. Thanks -- Amitesh Singh On Sun, Aug 12, 2012 at 10:32 PM, Amitesh Singh singh.amit...@gmail.comwrote: Does the pattern comes in this way? HT,TH,TT or HT(X)TH(X)TT ?? Let me know. -- Amitesh On Sat, Aug 11, 2012 at 11:24 PM, Piyush pkjee2...@gmail.com wrote: How can I find the expected number of tosses , required to obtain a {HT,TH,TT} , by using random variables?? On Friday, December 31, 2010 8:27:46 PM UTC+5:30, Dave wrote: @Anuj and Bittu: It is not necessary to know the bias. You can simulate the flip of an unbiased coin with multiple flips of a biased coin: Flip it twice. If the result is HT, consider it a Head. If the result is TH, consider it a Tail. If the result is HH or TT, repeat the process. It terminates with probability 1. Now use the resulting Head or Tail in the procecure for deciding with a biased coin. Dave On Dec 31, 7:07 am, Anuj Kumar anuj.bhambh...@gmail.com wrote: in case the coin is not biased, we can flip the coin twice and define the rules as if {H,H} comes then ignore it i.e. dont take it as a flip and the 3 other events would be valid onces and could occur with equal probabilities. In case of a biased coin please specify the probability of getting heads and that of getting tails. On Fri, Dec 31, 2010 at 4:11 PM, bittu shashank7andr...@gmail.com wrote: At a restaurant, how can Veronica choose one out of three desserts with equal probability with the help of a coin? What if the coin is biased and the bias is unknown? -- 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.com. To unsubscribe from this group, send email to algogeeks+...@**googlegroups.comalgogeeks%** 2Bunsubscribe@googlegroups.**com . For more options, visit this group at http://groups.google.com/**group/algogeeks?hl=enhttp://groups.google.com/group/algogeeks?hl=en. -- Anuj Kumar Third Year Undergraduate, Dept. of Computer Science and Engineering NIT Durgapur- Hide quoted text - - Show quoted text - -- 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/-/DZdUcelMwtUJ. 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] Inorder Iterative code for printing paths
void printPath(node *p,node *child) { if( p child) std::cout Path: p-data =child-data std::endl; } use this before you assign 'current' to its children. e.g. printPath(p,p-left) or printPath(p,p-right); -- Amitesh On Mon, Jun 25, 2012 at 11:34 PM, Nishant Pandey nishant.bits.me...@gmail.com wrote: thiss is iterative inorder code i am using for printing all the paths of the Btree . but i am not able to manipulate the lengths properly when its perform pop up so that i can print the paths properly .. Can any one help by modifying the changes in this code . void inorder(struct node *root) { stackstruct node*stack_temp; struct node *current,*temp; int path[20]; int i =0 ,j=0; if(!root)return ; current=root; bool flag=false; //bool ctrl=false; while(!flag) { if(current) { //coutcurrent-dataendl; stack_temp.push(current); path[i++]=current-data; if(current-left == NULL current-right == NULL) { for(j=0;ji;j++) coutpath[j] ; //i--; } coutendl; current=current-left; } else { if(stack_temp.empty()) { flag=true; } else { current=stack_temp.top(); stack_temp.pop(); i--; //if(current-right) //coutcurrent-dataendl; current=current-right; if(current) i++; } } } } -- Cheers, Nishant Pandey |Specialist Tools Development | npan...@google.comgvib...@google.com | +91-9911258345 -- 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] Inorder Iterative code for printing paths
and to count no. of paths, you can do this void printPath(node *p,node *child) { static int iCountPath = 0; // or pass it as an argument non-const ref. if( p child) { ++iCountPath; std::cout Path: p-data =child-data std::endl; } } -- Amitesh On Thu, Jun 28, 2012 at 11:01 AM, Amitesh Singh singh.amit...@gmail.comwrote: void printPath(node *p,node *child) { if( p child) std::cout Path: p-data =child-data std::endl; } use this before you assign 'current' to its children. e.g. printPath(p,p-left) or printPath(p,p-right); -- Amitesh On Mon, Jun 25, 2012 at 11:34 PM, Nishant Pandey nishant.bits.me...@gmail.com wrote: thiss is iterative inorder code i am using for printing all the paths of the Btree . but i am not able to manipulate the lengths properly when its perform pop up so that i can print the paths properly .. Can any one help by modifying the changes in this code . void inorder(struct node *root) { stackstruct node*stack_temp; struct node *current,*temp; int path[20]; int i =0 ,j=0; if(!root)return ; current=root; bool flag=false; //bool ctrl=false; while(!flag) { if(current) { //coutcurrent-dataendl; stack_temp.push(current); path[i++]=current-data; if(current-left == NULL current-right == NULL) { for(j=0;ji;j++) coutpath[j] ; //i--; } coutendl; current=current-left; } else { if(stack_temp.empty()) { flag=true; } else { current=stack_temp.top(); stack_temp.pop(); i--; //if(current-right) //coutcurrent-dataendl; current=current-right; if(current) i++; } } } } -- Cheers, Nishant Pandey |Specialist Tools Development | npan...@google.comgvib...@google.com | +91-9911258345 -- 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] Question asked in Tachyon interview
It can be done using Queues in O(n). -- Amitesh On Wed, Jun 27, 2012 at 3:07 PM, hary rathor harry.rat...@gmail.com wrote: apply BFS -- 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] Adobe interview question
It can done using pure virtual destructor. struct A { //your implementation .. .. .. virtual ~A() = 0; }; A::~A() { } -- Amitesh On Fri, Jun 22, 2012 at 1:44 PM, himanshu kansal himanshukansal...@gmail.com wrote: How will u implement an abstract class in c++ w/o using pure virtual function??? will making all the constructors and assignment operators protected suffice??? i doubt since the derived classes will be able to create objects of that classand according to definition of abstract class, no object of it should be created... any other way?? -- 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] Adobe interview question
a pure virtual function does not have definition. Since pure virtual destructor has a definition so its only for not allowing the object instantiation, although it does not have any other abstract functions. -- Amitesh On Fri, Jun 22, 2012 at 1:51 PM, Amitesh Singh singh.amit...@gmail.comwrote: It can done using pure virtual destructor. struct A { //your implementation .. .. .. virtual ~A() = 0; }; A::~A() { } -- Amitesh On Fri, Jun 22, 2012 at 1:44 PM, himanshu kansal himanshukansal...@gmail.com wrote: How will u implement an abstract class in c++ w/o using pure virtual function??? will making all the constructors and assignment operators protected suffice??? i doubt since the derived classes will be able to create objects of that classand according to definition of abstract class, no object of it should be created... any other way?? -- 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] Double Linked List Represented With Single Linked List
Krishna, how can you store a address pointing to k bits value into k/2 bits? XOR is the way to do this. -- Amitesh On Thu, Jun 21, 2012 at 1:20 AM, Krishna Kishore kknarenkris...@gmail.comwrote: *np *is nothing but *next_pointer. np[x] *does mean *x-np *which is the next pointer to node. Actually I am thinking in this way about *np, *that it stores the *XOR* value of *next* and *prev* pointers.Or Since *np *is a k-bit integer, the first k/2 bits wil be used for *next*, and other k/2 bits wil be used for *prev *pointer. On Wednesday, 20 June 2012 18:28:07 UTC+5:30, adarsh kumar wrote: Simple! Just traverse the doubly linked list and keep track of next and previous of each node, and do XOR and save the result in a new pointer, what according to you is np. Be careful about boundary cases, i.e head and tail, though. On Wed, Jun 20, 2012 at 5:16 PM, Krishna Kishore kknarenkris...@gmail.com wrote: Explain how to implement doubly linked lists using only one pointer value * np[x*] per item instead of the usual two (next and prev). Assume that all pointer values can be interpreted as k-bit integers, and define* np[x] to be np[x] = next[x] XOR prev[x],*the k-bit “exclusive-or” of next[x] and prev[x]. (The value NIL is represented by 0.) Be sure to describe what information is needed to access the head of the list. Show how to implement the SEARCH, INSERT, and DELETE operations on such a list. Also show how to reverse such a list in O(1) time. This is the Question in the Book *Introduction To Algorithms *By CORMEN ( MIT Press ) Page Number : 209 , Problem No: 10.2-8. Thanks in Advance. -- 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/-/Uj1E8KXljAQJhttps://groups.google.com/d/msg/algogeeks/-/Uj1E8KXljAQJ . To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscribe@** googlegroups.com algogeeks%2bunsubscr...@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/-/JlNBCRsj9kUJ. 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] Analysis of Partial Sorting.
Thanks Hassan. But I was more interested in knowing the mathematic proof of Partial Quick Sort. -- Amitesh On Sun, Jun 17, 2012 at 7:54 PM, Hassan Monfared hmonfa...@gmail.comwrote: O(N*logM) On Sat, Jun 16, 2012 at 5:15 PM, Amitesh Singh singh.amit...@gmail.comwrote: Hi Guys, *Problem: *Rearrange a given array with n elements, so that m places contain the m smallest elements in ascending order. *Solution 2:* using QuickSort method approach. [image: n = r -p + 1] [image: \bold{PARTIAL-QUICKSORT(A,p,r,m)}: \newline if\; pr \newline q \leftarrow RANDOMIZED-PARTITION(A,p,r) \newline PARTIAL-QUICKSORT(A,p,q-1,m) \newline if \; qm-1 \newline PARTIAL-QUICKSORT(A,q+1,r,m)] http://amiteshsingh.wordpress.com/2012/06/16/partial-sorting/ I know if m = n, then complexity of Partial sorting is same as QuickSort. but what would be the *average case analysis* in terms of n and m? Any suggestion would be highly appreciated. -- Amitesh -- 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. -- 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] Microsoft question
check out this: RANDOMIZED-SELECT in O(n): http://amiteshsingh.wordpress.com/2012/06/08/iterative-randomized-select/ -- Amitesh On Sun, Jun 17, 2012 at 1:24 PM, Ashish Goel ashg...@gmail.com wrote: is the modification of the given array allowed? if yes use quick select, otherwise build tree where each node keeps count of its left subtree Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Sun, Jun 17, 2012 at 8:13 AM, Prem Nagarajan prem.cmna...@gmail.comwrote: Give an array of unsorted elements, find the kth smallest element in the array. The expected time complexity is O(n) and no extra memory space should be used. Quickselect algorithm can be used to obtain the solution. Can anyone explain how quickselect works? -- 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. -- 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] expectation values..
This problem is similar to Coupan collector problem. http://en.wikipedia.org/wiki/Coupon_collector%27s_problem In your case the answer is [image: For N-Dice ; \newline \sum_{i=1}^{N} N/i \newline for\; N =~2 ; \newline \sum_{i=1}^{2} 2/i = 2/1 + 2/2 = 3 \newline] Hope it helps! -- Amitesh On Sat, Jun 16, 2012 at 5:18 PM, Gaurav Popli gpgaurav.n...@gmail.comwrote: What is the expected number of throws of his die while it has N sides so that each number is rolled at least once? e.g for n=2 ans 3.00 n=12 ans is 37.24... i refrd to expectation tutuorial at http://www.codechef.com/wiki/tutorial-expectation but still couldnt get the logic... any help? -- 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] Analysis of Partial Sorting.
Hi Guys, *Problem: *Rearrange a given array with n elements, so that m places contain the m smallest elements in ascending order. *Solution 2:* using QuickSort method approach. [image: n = r -p + 1] [image: \bold{PARTIAL-QUICKSORT(A,p,r,m)}: \newline if\; pr \newline q \leftarrow RANDOMIZED-PARTITION(A,p,r) \newline PARTIAL-QUICKSORT(A,p,q-1,m) \newline if \; qm-1 \newline PARTIAL-QUICKSORT(A,q+1,r,m)] http://amiteshsingh.wordpress.com/2012/06/16/partial-sorting/ I know if m = n, then complexity of Partial sorting is same as QuickSort. but what would be the *average case analysis* in terms of n and m? Any suggestion would be highly appreciated. -- Amitesh -- 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] expectation values..
just curious to know if this question is asked in any interviews? Google interview? -- Amitesh On Sun, Jun 17, 2012 at 12:09 AM, Amitesh Singh singh.amit...@gmail.comwrote: This problem is similar to Coupan collector problem. http://en.wikipedia.org/wiki/Coupon_collector%27s_problem In your case the answer is [image: For N-Dice ; \newline \sum_{i=1}^{N} N/i \newline for\; N =~2 ; \newline \sum_{i=1}^{2} 2/i = 2/1 + 2/2 = 3 \newline] Hope it helps! -- Amitesh On Sat, Jun 16, 2012 at 5:18 PM, Gaurav Popli gpgaurav.n...@gmail.comwrote: What is the expected number of throws of his die while it has N sides so that each number is rolled at least once? e.g for n=2 ans 3.00 n=12 ans is 37.24... i refrd to expectation tutuorial at http://www.codechef.com/wiki/tutorial-expectation but still couldnt get the logic... any help? -- 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] Adobe interiew question
signals and logjmp/setjmp() -- Amitesh On Wed, Jun 13, 2012 at 10:40 AM, saurabh singh saurab...@gmail.com wrote: tHE first thing that comes in my mind Signals Saurabh Singh B.Tech (Computer Science) MNNIT blog:geekinessthecoolway.blogspot.com On Tue, Jun 12, 2012 at 10:26 PM, Shashank Narayan shashank7andr...@gmail.com wrote: yes u can review that link :) On Tue, Jun 12, 2012 at 9:47 PM, Anika Jain anika.jai...@gmail.comwrote: how can we implement exception handling in c? -- Regards Anika Jain -- 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 Shashank Mani Narayan Computer Science Engineering Birla Institute of Technology,Mesra ** Founder Cracking The Code Lab http://shashank7s.blogspot.com/; FB Page http://www.facebook.com/pages/Cracking-The-Code/148241881919895 Google+ http://gplus.to/wgpshashank Twitter https://twitter.com/wgpshashankhttps://twitter.com/#%21/wgpshashank Puzzled Guy @ http://ashutosh7s.blogspot.com** **FB Page http://www.facebook.com/Puzzles.For.Puzzled.Minds* * Key Person Algogeek https://groups.google.com/forum/#!forum /algogeekshttps://groups.google.com/forum/#%21forum/algogeeks **Cell +91-9740852296 * * ** * -- 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. -- 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.