Re: [algogeeks] Find the Max from each sub-array of size k
Your algo is good but i don get the part where A[i] (current element) is less than the first element? Do we enqueue it? And if yes, when the front element is popped out , how is the next max found in front of the queue? If you could give an example with the growing queue. On Friday, 2 September 2011 15:43:41 UTC+5:30, WgpShashank wrote: Hi Anup , here is naive approach There is a sliding window of size w which is moving from the very left of the array to the very right. You can only see the w numbers in the window. Each time the sliding window moves rightwards by one position. Following is an example: The array is [1 3 -1 -3 5 3 6 7], and w is 3. Window position Max --- - [1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7 The obvious solution with run time complexity of O(nw) is which is not efficient enough. Every time the window is moved, we have to search for the maximum from w elements in the window. where w is size of window n is size of array 1st Method(Naive Approach) Data Structure Used : Array Algorithm: A.for all i=0 to n-w+1 (we should have at-least w elements in window) B.for all j=i to i+w (keep incrementing windows size form left to right) C find maximum inn each window print it or put in array (Auxiliary) For more efficient approaches you can have a look here http://shashank7s.blogspot.com/2011/06/given-array-and-integer-k-find-maximum.html correct me if anything wrong or other approaches you can thing of ? Thanks Shashank Mani Computer Science Birla Institute of Technology Mesra -- 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/-/giQA3tSNZtAJ. 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] Precedence or Associativity
Consider the following code: int i=0,j=0,k=0; int x = ++i || ++j ++k; O/P: x=1,i=1,j=0,k=0 Now, the logic operators are evaluated left to right and if the output is determined by left hand side expression right hand side is not evaluated. But the precedence of || hence ++j++k should be dealt with first.The output says once ++i evaluates to 1 further expression is not considered. Can anyone explain this anomaly? As of i know associativity is considered when precedence of operators is the same eg: x*y/z will be evaluated left to right. -- 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/-/rr41g1Q8q38J. 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: Can anyone plz explain how we get this output
The arguments in printf are evaluated from right to left.
first ++a gives 11 , then a is 11 and a++(bcoz postfix) is also 11
But the final value is copied to the prefix argument (++a) and just 'a'.
The postfix argument(a++) will retain the value it obtained.
On Sat, Jun 16, 2012 at 3:49 PM, rvkmr102 rvkmr...@gmail.com wrote:
If you evaluate the expressions from right to left and print the result
from left to right , it will be clear.
On Thursday, June 14, 2012 11:41:04 AM UTC+5:30, Ajesh js wrote:
main()
{
int a=10,b=5;
printf(%d %d %d\n,a++,a,++a);
printf(%d %d %d\n,++b,b,b++);
}
output
11 12 12
7 7 5
--
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/-/rpQU8ga6Ev4J.
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] Microsoft question
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.
Re: [algogeeks] Microsoft question
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.
Re: [algogeeks] MS Question: Reverse stack using push, pop without any auxiliary data structure
This solution works perfectly :) On Friday, June 15, 2012 10:59:22 AM UTC+5:30, Navin Kumar wrote: I corrected in function InsertAtBottom :In my code isntead of (!IsEmptyStack) use IsEmptyStack On Fri, Jun 15, 2012 at 10:49 AM, Navin Kumar algorithm.i...@gmail.comwrote: @all: In my code isntead of (!IsEmptyStack) use IsEmptyStack Logic : First pop the all element and then start putting element at bottom in reverse order i.e. the element which is fetched last is put at the bottom and so on. ex: let our stack is: 1 2 3 4 (1 is at bottom). function Call is will be: Reverse(S) --Reverse(S) --Reverse(S) --Reverse(S) --stack empty so return InsertAtBottom(4) InsertAtBottom(3)InsertAtBottom(2) InsertAtBottom(1) going back First 1 will be placed at bottom: stack content :1 now 2 will be placed at bottom: stack content will be: 2 1 now 3 will be placed at bottom: stack content will be: 3 2 1 now 4 will be placed at bottom: stack content will be:4 3 2 1 On Thu, Jun 14, 2012 at 2:46 PM, Nishant Pandey nishant.bits.me...@gmail.com wrote: stack means inbuild stack we cant use any DS from our program explicitly. On Thu, Jun 14, 2012 at 2:44 PM, rahul patil rahul.deshmukhpa...@gmail.com wrote: to store items in stack you will need some DS. Do they mean you cant use any auxillary DS than stack ? On Thu, Jun 14, 2012 at 2:24 PM, Ashish Goel ashg...@gmail.com wrote: 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. -- Regards, Rahul Patil -- 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. -- 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 view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/pcs-ebKU_t8J. 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] Precedence or Associativity
Hello Dear.. This Age Old question is Still Haunting Ppls.. In fact this ain't a question at all.. this Should be known while we start writing first of the C/C++ programming.. Well.. Just to make some ppls Life easier here it goes AGAIN.. ++i=++0=1 so it will be one.. Now as OR means. either of the half must not be 0 and so || says, I hv got statement true (Which in case of OR is NOT EQUAL TO 1 by evaluating left portion only) So. OR Says well, I got wat I wan't Don't need to check the other expression and so it won't execute. At that instance the value of the variable are i as I said becomes 1 j and k no execution and x is assigned to 1 as the total expression evaluates as success ( Remember Success means 1 and it not the value of i which is assigned to x ) and so the output will follow as it is. Prem On Sun, Jun 17, 2012 at 12:50 PM, enchantress elaenjoy...@gmail.com wrote: Consider the following code: int i=0,j=0,k=0; int x = ++i || ++j ++k; O/P: x=1,i=1,j=0,k=0 Now, the logic operators are evaluated left to right and if the output is determined by left hand side expression right hand side is not evaluated. But the precedence of || hence ++j++k should be dealt with first.The output says once ++i evaluates to 1 further expression is not considered. Can anyone explain this anomaly? As of i know associativity is considered when precedence of operators is the same eg: x*y/z will be evaluated left to right. -- 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/-/rr41g1Q8q38J. 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
refer to kth order statistics in the book intro to algorithms by coreman -- Amol Sharma Final Year Student Computer Science and Engineering MNNIT Allahabad http://gplus.to/amolsharma99 http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://www.simplyamol.blogspot.com/http://facebook.com/amolsharma99 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] 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..
got it ..thanks!!
and this was not asked in any interview as i know...i read this quesn from
SPOJ..
On Sun, Jun 17, 2012 at 12:13 AM, Amitesh Singh singh.amit...@gmail.comwrote:
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.
--
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.
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.
Re: [algogeeks] expectation values..
Can you provide the link??
On Sun, Jun 17, 2012 at 5:08 PM, Gaurav Popli gpgaurav.n...@gmail.comwrote:
got it ..thanks!!
and this was not asked in any interview as i know...i read this quesn from
SPOJ..
On Sun, Jun 17, 2012 at 12:13 AM, Amitesh Singh
singh.amit...@gmail.comwrote:
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.
--
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,*
*Piyush Kapoor,*
*2nd year,CSE
IT-BHU*
--
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] spoj problem : NSTEPS
here is my code for the above problem:
#includestdio.h
#includestdlib.h
int main()
{
int i,x[1],y[1],val;
long n;
scanf(%d,n);
for(i=0;in;i++)
{
scanf(%d,x[i]);
scanf(%d,y[i]);
}
for(i=0;in;i++)
{
if(x[i] == y[i] x[i]%2 == 0)
{
val = x[i]+y[i];
printf(%d\n,val);
}
else if(x[i] == y[i] x[i]%2 != 0)
{
val = (x[i]+y[i])-1;
printf(%d\n,val);
}
else if(x[i] != y[i] x[i]%2 == 0 (x[i]-y[i]) == 2)
{
val = (x[i]+y[i]);
printf(%d\n,val);
}
else if(x[i] != y[i] x[i]%2 != 0 (x[i]-y[i]) == 2)
{
val = (x[i]+y[i])-1;
printf(%d\n,val);
}
else
printf(No Number\n);
}
return 0;
}
i am getting WA . plz help me regarding this.
--
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] spoj problem : NSTEPS
array size not sufficient coz n can be greater than 1
try x[100], y[100] :-)
On Sun, Jun 17, 2012 at 9:32 PM, Mayank Singh
singh13490may...@gmail.com wrote:
here is my code for the above problem:
#includestdio.h
#includestdlib.h
int main()
{
int i,x[1],y[1],val;
long n;
scanf(%d,n);
for(i=0;in;i++)
{
scanf(%d,x[i]);
scanf(%d,y[i]);
}
for(i=0;in;i++)
{
if(x[i] == y[i] x[i]%2 == 0)
{
val = x[i]+y[i];
printf(%d\n,val);
}
else if(x[i] == y[i] x[i]%2 != 0)
{
val = (x[i]+y[i])-1;
printf(%d\n,val);
}
else if(x[i] != y[i] x[i]%2 == 0 (x[i]-y[i]) == 2)
{
val = (x[i]+y[i]);
printf(%d\n,val);
}
else if(x[i] != y[i] x[i]%2 != 0 (x[i]-y[i]) == 2)
{
val = (x[i]+y[i])-1;
printf(%d\n,val);
}
else
printf(No Number\n);
}
return 0;
}
i am getting WA . plz help me regarding this.
--
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] 4Sum
The solution which hemesh gave was solution to 3SUM hard problem the best solution for which can be achieved in n^2 . And the original question is a kind of 4SUM hard problem for which best possible solution i think is again n^3 and Amol what you told is not n^3 , finding all triplets will itself take n^3 and doing a binary search again that sums upto n^3*logn. @shashank it is not a variation of 3SUM problem as in 3SUM problem a+b+c = some constant , but in your case it is b+c+d = s-a, where a can change again and again so if you do even apply 3SUM logic to it you will have to do it for every a which will make it n^2*n = n^3 On Sat, Jun 16, 2012 at 2:45 AM, sanjay pandey sanjaypandey...@gmail.comwrote: @hemesh cud u plz elaborate wat is b[k]=a[i]+a[j]...n also ur solution... -- 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
@Ashish Building a treeis of O(nlogn) complexity. Linear solution is much appreciated. On Sun, Jun 17, 2012 at 2:00 PM, Amitesh Singh singh.amit...@gmail.comwrote: 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. -- 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] Suggestion needed
Hello everyone, Please anyone suggest that what books,sites,etc. should be preffered while preparing for topics such as networking, dbms, os, aptitude for placements. Any advice would be helpful! (Sorry for posting not related to group) Thanks. -- Prakhar Jain IIIT Allahabad B.Tech IT 3rd Year Mob no: +91 9454992196 E-mail: rit2009...@iiita.ac.in jprakha...@gmail.com -- 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] Precedence or Associativity
Short-circuiting On Sun, Jun 17, 2012 at 10:02 PM, rn rnjailamb...@gmail.com wrote: But the precedence of || hence ++j++k should be dealt with first ? -- 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/-/PRR2PS377oEJ. 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..
If we expand it.. E(t) = E(t1) + E(t2) + E(t3) + ... + E(tn);
here I am able to derive E(t1) as N/1 using the expression E(t1) = 1/N +
((N-1)/N)(E(t1) + 1);
but how do I proceed?
How do I derive the E(t2) and so on??
What do these values mean??
Does it mean like E(t2) is the no. of expected throws to get value 2??
Any help on this?
On Sunday, 17 June 2012 00:09:13 UTC+5:30, amitesh wrote:
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 view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/xLsfC_Gc8z0J.
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] Precedence or Associativity
yea it s short circuiting -- 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] Precedence or Associativity
Prem Krishna Chettri +1 * * The precedence of || has higher priority than || . check in this case: int i=0,j=0,k=0; int x =i++ || ++j k; the output is : x=0 i=1 j=1 k=0 the control flows from L to R . First 'i' is incremented( but i=0 is checked as it's post increment, but in o/p i=1), since || finds 0 (ie i=0 ) at its left, the control flows further to the right and evaluates ++j. Now ++jk is equivalent to 10, which makes it 0, (notice is evaluated first). now 0 || 0 is evaluated, which comes out to be 0, so x is assigned 0 as the total expression evaluates as false. * * On Sun, Jun 17, 2012 at 11:26 PM, rahul venkat rahul911...@gmail.comwrote: yea it s short circuiting -- 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. -- Firoz Khursheed Computer Science Engineering -- 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] 4Sum
@jalag: in amol's solution binary search will take log(n^3) bcz size of sum array is n^3 not it will take n^3*logn . -- 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.
