Re: [algogeeks] Re: Algo Question
Am Montag, 4. März 2013 07:52:11 UTC+1 schrieb nand kishore:
I think DP soln would be :
int leastPay(int[] demands, int sum, int index) {
if(index == demands.length)
return sum;
else {
if(sum demands[index])
return leastPay(demands, sum+demands[index], index+1);
else
return Math.min(leastPay(demands, sum, index+1),
leastPay(demands, sum+demands[index], index+1));
}
}
Hi,
shouldn't this be: if(sum = demands[index])?
Thanks
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
[algogeeks] Re: Algo Question
@immars , can you explain with some example or algorithm ? Thanks Shashank On Tuesday, February 5, 2013 9:14:03 AM UTC+5:30, immars wrote: suppose: v : array of guards' request P(n): our problem: least coin spent until guard n, according to these rules M(n, x): least coin possibly combined equal to or larger than x until guard n then: P(n) = min(P(n-1)+v[n], M(n-1, v[n])) M(n, x) = min(M(n-1, x), M(n-1, x-v[n]) + v[n]) On Monday, February 4, 2013 8:24:19 PM UTC+8, marti wrote: You have N guards in a line each with a demand of coins.You can skip paying a guard only if his demand is lesser than what you have totally paid before reaching him.Find the least number of coins you spend to cross all guards. I think its a DP problem but cant come up with a formula.Another approach would be to binary search on the answer but how do I verify if no. of coins is a possible answer? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
Re: [algogeeks] Re: Algo Question
I think DP soln would be :
int leastPay(int[] demands, int sum, int index) {
if(index == demands.length)
return sum;
else {
if(sum demands[index])
return leastPay(demands, sum+demands[index], index+1);
else
return Math.min(leastPay(demands, sum, index+1),
leastPay(demands, sum+demands[index], index+1));
}
}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
Re: [algogeeks] Re: Algo Question
take this example
let the gaurds demand be
5 2 7 2 9
first guard : we have no choice but to give him 5
second guard : we have choice , either skip him and pay 7 to next guard or
pay him and save 7 from third guard .. thus clearly multiple solutions
exist but we have to give optimal one. { hint for dp }
if we know the solution for upto i-th guard, we can extend this solution to
i+1-th guard
solution here represents all the possible amounts that one can spend till
i-th guard, extending that will give us all the possible amounts for i+1 th
guard and we just select the minimum amount. thus optimal substructure is
also there.
using the below code , the output for example is 12 with possible sequence.
guard 1 : 5
guard 2 : skip
guard 3 : 7
guard 4 :skip
guard 5 :skip
// non optimized code -purely for demonstration purpose -
#include stdio.h
#include stdarg.h
#define size 5
#define amount 1000 // maximum amount asked by all the gaurds combined
int solution[size][amount];
int main (int argc, char const *argv[])
{
int arr[] = {5,2,7,2,9};
int min, i, j;
int sum = 0;
for(i = 0; isize; i++) {
sum += arr[i];
}
solution[0][arr[0]] = 1;
for(i = 1; i size; i++) {
for(j = 0; j= sum; j++) {
if(solution[i-1][j] == 1) {
if(j arr[i]) {
solution[i][j] = 1;
}
solution[i][j + arr[i]] = 1;
}
}
}
min = 10; // infinite value
for(i = 0; i sum; i++) {
if(solution[size - 1][i] i min)
min = i;
}
printf(%d, min);
return 0;
}
@marti check the solution for other testcases , I'll post the optimized
version after that.
On Wed, Feb 27, 2013 at 1:04 AM, Saurabh Paliwal
saurabh.paliwa...@gmail.com wrote:
Please mention the initial condition.
I mean I wouldn't pay to any guard (assuming their demands are all
positive numbers)
On Wed, Feb 27, 2013 at 12:39 AM, marti amritsa...@gmail.com wrote:
Sure..
http://stackoverflow.com/questions/14686745/guards-and-demand
On Monday, February 4, 2013 5:54:19 PM UTC+5:30, marti wrote:
You have N guards in a line each with a demand of coins.You can skip
paying a guard only if his demand is lesser than what you have totally paid
before reaching him.Find the least number of coins you spend to cross all
guards.
I think its a DP problem but cant come up with a formula.Another
approach would be to binary search on the answer but how do I verify if no.
of coins is a possible answer?
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an
email to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
--
-Saurabh Paliwal
B-Tech. Comp. Science and Engg.
IIT ROORKEE
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an
email to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
--
Rohit Jangid
Graduate
Deptt. of Computer Engineering
NSIT, Delhi University, India
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
Re: [algogeeks] Re: Algo Question
@marti : can u please make problem statement clear .. give one example , we can understand clearly On Tue, Feb 5, 2013 at 9:14 AM, immars imm...@gmail.com wrote: suppose: v : array of guards' request P(n): our problem: least coin spent until guard n, according to these rules M(n, x): least coin possibly combined equal to or larger than x until guard n then: P(n) = min(P(n-1)+v[n], M(n-1, v[n])) M(n, x) = min(M(n-1, x), M(n-1, x-v[n]) + v[n]) On Monday, February 4, 2013 8:24:19 PM UTC+8, marti wrote: You have N guards in a line each with a demand of coins.You can skip paying a guard only if his demand is lesser than what you have totally paid before reaching him.Find the least number of coins you spend to cross all guards. I think its a DP problem but cant come up with a formula.Another approach would be to binary search on the answer but how do I verify if no. of coins is a possible answer? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
[algogeeks] Re: Algo Question
Sure.. http://stackoverflow.com/questions/14686745/guards-and-demand On Monday, February 4, 2013 5:54:19 PM UTC+5:30, marti wrote: You have N guards in a line each with a demand of coins.You can skip paying a guard only if his demand is lesser than what you have totally paid before reaching him.Find the least number of coins you spend to cross all guards. I think its a DP problem but cant come up with a formula.Another approach would be to binary search on the answer but how do I verify if no. of coins is a possible answer? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
Re: [algogeeks] Re: Algo Question
Please mention the initial condition. I mean I wouldn't pay to any guard (assuming their demands are all positive numbers) On Wed, Feb 27, 2013 at 12:39 AM, marti amritsa...@gmail.com wrote: Sure.. http://stackoverflow.com/questions/14686745/guards-and-demand On Monday, February 4, 2013 5:54:19 PM UTC+5:30, marti wrote: You have N guards in a line each with a demand of coins.You can skip paying a guard only if his demand is lesser than what you have totally paid before reaching him.Find the least number of coins you spend to cross all guards. I think its a DP problem but cant come up with a formula.Another approach would be to binary search on the answer but how do I verify if no. of coins is a possible answer? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- -Saurabh Paliwal B-Tech. Comp. Science and Engg. IIT ROORKEE -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
[algogeeks] Re: Algo Question
suppose: v : array of guards' request P(n): our problem: least coin spent until guard n, according to these rules M(n, x): least coin possibly combined equal to or larger than x until guard n then: P(n) = min(P(n-1)+v[n], M(n-1, v[n])) M(n, x) = min(M(n-1, x), M(n-1, x-v[n]) + v[n]) On Monday, February 4, 2013 8:24:19 PM UTC+8, marti wrote: You have N guards in a line each with a demand of coins.You can skip paying a guard only if his demand is lesser than what you have totally paid before reaching him.Find the least number of coins you spend to cross all guards. I think its a DP problem but cant come up with a formula.Another approach would be to binary search on the answer but how do I verify if no. of coins is a possible answer? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
Re: [algogeeks] Re: Algo for Search in a 2D Matrix
Yes, navin thats a good solution... ... we dont need to work on the whole array but of size k x k (k rows and k columsn only). Rest of the array we can simply ignore.. complexity of youngify is O(k) for every removing every element. we have to remove k-1 elements so complexity of whole operation is o(k*k). Refer this pdf: http://lyle.smu.edu/~saad/courses/cse3358/ps5/problemset5sol.pdf Regards Saurabh On Mon, May 21, 2012 at 10:00 AM, Navin.nitjsr navin.nit...@gmail.comwrote: We can consider the 2-d matrix as a heap(also called Young Tableau). We just need to heapify(Youngify) it k-1times,then the element at 0,0 will be kth smallest element. This means we need to remove the k-1 smallest elements from matrix and still maintaining its Row-Col sorted property. Youngify algo:- 1:- put a sentinel value (i,e, INF) 0,0 2:- Now push it leftwards/downwards to maintain the initial property of matrix 3:- If at any point the current element is smaller than both its left and down element, then STOP. This is an in-place operation. We need to consider the sentinel value as highest value,not present in the matrix. It works.Although the matrix is being modified. On Monday, 10 October 2011 04:45:52 UTC+5:30, Ankur Garg wrote: Given a 2D matrix which is both row wise and column wise sorted. Propose an algorithm for finding the kth smallest element in it in least time complexity A General Max Heap can be used with k space and n+klogk complexity Any other solution or even a way by which we dont scan the whole matrix to find the solution ? I On Monday, 10 October 2011 04:45:52 UTC+5:30, Ankur Garg wrote: Given a 2D matrix which is both row wise and column wise sorted. Propose an algorithm for finding the kth smallest element in it in least time complexity A General Max Heap can be used with k space and n+klogk complexity Any other solution or even a way by which we dont scan the whole matrix to find the solution ? I On Monday, 10 October 2011 04:45:52 UTC+5:30, Ankur Garg wrote: Given a 2D matrix which is both row wise and column wise sorted. Propose an algorithm for finding the kth smallest element in it in least time complexity A General Max Heap can be used with k space and n+klogk complexity Any other solution or even a way by which we dont scan the whole matrix to find the solution ? I On Monday, 10 October 2011 04:45:52 UTC+5:30, Ankur Garg wrote: Given a 2D matrix which is both row wise and column wise sorted. Propose an algorithm for finding the kth smallest element in it in least time complexity A General Max Heap can be used with k space and n+klogk complexity Any other solution or even a way by which we dont scan the whole matrix to find the solution ? I -- 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/-/GtGv_vms-WQJ. 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: Algo for Search in a 2D Matrix
We can consider the 2-d matrix as a heap(also called Young Tableau). We just need to heapify(Youngify) it k-1times,then the element at 0,0 will be kth smallest element. This means we need to remove the k-1 smallest elements from matrix and still maintaining its Row-Col sorted property. Youngify algo:- 1:- put a sentinel value (i,e, INF) 0,0 2:- Now push it leftwards/downwards to maintain the initial property of matrix 3:- If at any point the current element is smaller than both its left and down element, then STOP. This is an in-place operation. We need to consider the sentinel value as highest value,not present in the matrix. It works.Although the matrix is being modified. On Monday, 10 October 2011 04:45:52 UTC+5:30, Ankur Garg wrote: Given a 2D matrix which is both row wise and column wise sorted. Propose an algorithm for finding the kth smallest element in it in least time complexity A General Max Heap can be used with k space and n+klogk complexity Any other solution or even a way by which we dont scan the whole matrix to find the solution ? I On Monday, 10 October 2011 04:45:52 UTC+5:30, Ankur Garg wrote: Given a 2D matrix which is both row wise and column wise sorted. Propose an algorithm for finding the kth smallest element in it in least time complexity A General Max Heap can be used with k space and n+klogk complexity Any other solution or even a way by which we dont scan the whole matrix to find the solution ? I On Monday, 10 October 2011 04:45:52 UTC+5:30, Ankur Garg wrote: Given a 2D matrix which is both row wise and column wise sorted. Propose an algorithm for finding the kth smallest element in it in least time complexity A General Max Heap can be used with k space and n+klogk complexity Any other solution or even a way by which we dont scan the whole matrix to find the solution ? I On Monday, 10 October 2011 04:45:52 UTC+5:30, Ankur Garg wrote: Given a 2D matrix which is both row wise and column wise sorted. Propose an algorithm for finding the kth smallest element in it in least time complexity A General Max Heap can be used with k space and n+klogk complexity Any other solution or even a way by which we dont scan the whole matrix to find the solution ? I -- 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/-/GtGv_vms-WQJ. 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: Algo for Search in a 2D Matrix
@ashish: ya m sorry.. i didnt read the quest properly, it was for any given
number..
On Fri, May 18, 2012 at 11:37 AM, Ashish Goel ashg...@gmail.com wrote:
Anika, what you are talking about is finding a specific element, not the
kth largest or smallest element, can you give a walk through with an
example in case i have understood you incorrectly
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Thu, May 17, 2012 at 3:33 PM, Anika Jain anika.jai...@gmail.comwrote:
there's a solution of O(log n) where 2D matrix has n rows and n columns.
Apply binary search for the search on the diagonal. when you are left with
just one element after the search apply binary search within that elements
row and its column. you will get the element. O(log n+log n+log n). so
O(log n).
On Wed, May 16, 2012 at 6:36 PM, Prem Krishna Chettri hprem...@gmail.com
wrote:
Well I hv got Something running in my mind buy ofcse need some cornor
case tuning.
If we take sqrt() of the number (say K) than we can avoid looking
into sqrt(k)-1 and sqrt(k)+1 rows and column entirely, which literally
means that the final solution is possible in constant time (the time
independent of k or matrix values), which ofcourse can go upto O(n) in
worst case where N is the Matrix of N Rows and 1 Column as we cannot use
the intelligence of sqrt function to corner the value.
Its seems okei logically to remove those rows and columns as we are
certain that they are sorted in both ways and avoid unnecessary time
looking for the place where it won't belong.
Now the issue is so clear that we can say (sqrt(k)-1)*(sqrt(k)-1)k and
now keep on adding the value to sqrt(k)+1 till U reach k and get corner
that element.
I guess it works..
On Wed, May 16, 2012 at 1:17 PM, Ashish Goel ashg...@gmail.com wrote:
Vikas, can you suggest the logic of this also? I am a bit unclear on
how the 2D arr is being used as a heap and how recursion is used to solve
this
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Thu, Oct 13, 2011 at 11:37 PM, vikas vikas.rastogi2...@gmail.comwrote:
@Sunny, good catch, k X k approach wont work
lets try to use matrix itself as heap
heapify(int cr, int cc, int Nr, int Nc){
mr = cr; mc = cc;
if(cr+1 Nr)
mr = cr+1 mc = cc;
if(cc + 1 Nc min A[cc+1][cr])
mr = cr; mc = cc+1;
if(A[cr][cc] A[mr][mc]){
swap(A[cr][cc] ,A[mr][mc]);
heapify(mr, mc, Nr, Nc);
}
extract_min(){
swap(A[0][0], A[hr][hc]);
if(hc 0) hc--;
else if(hr 0){
hr --;
hc = N;
}
if(hr | hc)
heapify(0, 0, hr, hc);
}
}
On Oct 13, 12:18 pm, sunny agrawal sunny816.i...@gmail.com wrote:
Nopes
Still it does not ensure that duplicates will not be there in the
priority
queue
what i mean is you cannot write directly
do k times{
data = pop()
// let i,j are row and col of data
push(i+1,j);
push(i,j+1);
}
you need to add the following checks
if((i+1,j) is not in the heap) push(i+1,j)
if((i,j+1) is not in the heap) push(i,j+1)
because heap does not automatically check for duplicates
and to check for duplicates we need an extra data structure other
than heap,
which stores that which (i+1,j) are already there in the heap map
can also
be used so overall complexity will go O(k* lg^2K)
On Thu, Oct 13, 2011 at 12:26 PM, anshu mishra
anshumishra6...@gmail.comwrote:
struct data
{
int row, col,
int val;
};
priority_queuedata heap;
now fine?
--
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.
--
Sunny Aggrawal
B.Tech. V year,CSI
Indian Institute Of Technology,Roorkee
--
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
Re: [algogeeks] Re: Algo for Search in a 2D Matrix
i could not understand the Order Analysis of the solution ..is it k*(lg
n)(lg m) or k*lg(mn)
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Sun, May 20, 2012 at 11:15 PM, Anika Jain anika.jai...@gmail.com wrote:
@ashish: ya m sorry.. i didnt read the quest properly, it was for any
given number..
On Fri, May 18, 2012 at 11:37 AM, Ashish Goel ashg...@gmail.com wrote:
Anika, what you are talking about is finding a specific element, not the
kth largest or smallest element, can you give a walk through with an
example in case i have understood you incorrectly
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Thu, May 17, 2012 at 3:33 PM, Anika Jain anika.jai...@gmail.comwrote:
there's a solution of O(log n) where 2D matrix has n rows and n columns.
Apply binary search for the search on the diagonal. when you are left with
just one element after the search apply binary search within that elements
row and its column. you will get the element. O(log n+log n+log n). so
O(log n).
On Wed, May 16, 2012 at 6:36 PM, Prem Krishna Chettri
hprem...@gmail.com wrote:
Well I hv got Something running in my mind buy ofcse need some cornor
case tuning.
If we take sqrt() of the number (say K) than we can avoid looking
into sqrt(k)-1 and sqrt(k)+1 rows and column entirely, which literally
means that the final solution is possible in constant time (the time
independent of k or matrix values), which ofcourse can go upto O(n) in
worst case where N is the Matrix of N Rows and 1 Column as we cannot use
the intelligence of sqrt function to corner the value.
Its seems okei logically to remove those rows and columns as we are
certain that they are sorted in both ways and avoid unnecessary time
looking for the place where it won't belong.
Now the issue is so clear that we can say (sqrt(k)-1)*(sqrt(k)-1)k and
now keep on adding the value to sqrt(k)+1 till U reach k and get corner
that element.
I guess it works..
On Wed, May 16, 2012 at 1:17 PM, Ashish Goel ashg...@gmail.com wrote:
Vikas, can you suggest the logic of this also? I am a bit unclear on
how the 2D arr is being used as a heap and how recursion is used to solve
this
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Thu, Oct 13, 2011 at 11:37 PM, vikas
vikas.rastogi2...@gmail.comwrote:
@Sunny, good catch, k X k approach wont work
lets try to use matrix itself as heap
heapify(int cr, int cc, int Nr, int Nc){
mr = cr; mc = cc;
if(cr+1 Nr)
mr = cr+1 mc = cc;
if(cc + 1 Nc min A[cc+1][cr])
mr = cr; mc = cc+1;
if(A[cr][cc] A[mr][mc]){
swap(A[cr][cc] ,A[mr][mc]);
heapify(mr, mc, Nr, Nc);
}
extract_min(){
swap(A[0][0], A[hr][hc]);
if(hc 0) hc--;
else if(hr 0){
hr --;
hc = N;
}
if(hr | hc)
heapify(0, 0, hr, hc);
}
}
On Oct 13, 12:18 pm, sunny agrawal sunny816.i...@gmail.com wrote:
Nopes
Still it does not ensure that duplicates will not be there in the
priority
queue
what i mean is you cannot write directly
do k times{
data = pop()
// let i,j are row and col of data
push(i+1,j);
push(i,j+1);
}
you need to add the following checks
if((i+1,j) is not in the heap) push(i+1,j)
if((i,j+1) is not in the heap) push(i,j+1)
because heap does not automatically check for duplicates
and to check for duplicates we need an extra data structure other
than heap,
which stores that which (i+1,j) are already there in the heap map
can also
be used so overall complexity will go O(k* lg^2K)
On Thu, Oct 13, 2011 at 12:26 PM, anshu mishra
anshumishra6...@gmail.comwrote:
struct data
{
int row, col,
int val;
};
priority_queuedata heap;
now fine?
--
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.
--
Sunny Aggrawal
B.Tech. V year,CSI
Indian Institute Of Technology,Roorkee
--
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
Re: [algogeeks] Re: Algo for Search in a 2D Matrix
Anika, what you are talking about is finding a specific element, not the
kth largest or smallest element, can you give a walk through with an
example in case i have understood you incorrectly
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Thu, May 17, 2012 at 3:33 PM, Anika Jain anika.jai...@gmail.com wrote:
there's a solution of O(log n) where 2D matrix has n rows and n columns.
Apply binary search for the search on the diagonal. when you are left with
just one element after the search apply binary search within that elements
row and its column. you will get the element. O(log n+log n+log n). so
O(log n).
On Wed, May 16, 2012 at 6:36 PM, Prem Krishna Chettri
hprem...@gmail.comwrote:
Well I hv got Something running in my mind buy ofcse need some cornor
case tuning.
If we take sqrt() of the number (say K) than we can avoid looking into
sqrt(k)-1 and sqrt(k)+1 rows and column entirely, which literally means
that the final solution is possible in constant time (the time independent
of k or matrix values), which ofcourse can go upto O(n) in worst case where
N is the Matrix of N Rows and 1 Column as we cannot use the intelligence of
sqrt function to corner the value.
Its seems okei logically to remove those rows and columns as we are
certain that they are sorted in both ways and avoid unnecessary time
looking for the place where it won't belong.
Now the issue is so clear that we can say (sqrt(k)-1)*(sqrt(k)-1)k and
now keep on adding the value to sqrt(k)+1 till U reach k and get corner
that element.
I guess it works..
On Wed, May 16, 2012 at 1:17 PM, Ashish Goel ashg...@gmail.com wrote:
Vikas, can you suggest the logic of this also? I am a bit unclear on how
the 2D arr is being used as a heap and how recursion is used to solve this
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Thu, Oct 13, 2011 at 11:37 PM, vikas vikas.rastogi2...@gmail.comwrote:
@Sunny, good catch, k X k approach wont work
lets try to use matrix itself as heap
heapify(int cr, int cc, int Nr, int Nc){
mr = cr; mc = cc;
if(cr+1 Nr)
mr = cr+1 mc = cc;
if(cc + 1 Nc min A[cc+1][cr])
mr = cr; mc = cc+1;
if(A[cr][cc] A[mr][mc]){
swap(A[cr][cc] ,A[mr][mc]);
heapify(mr, mc, Nr, Nc);
}
extract_min(){
swap(A[0][0], A[hr][hc]);
if(hc 0) hc--;
else if(hr 0){
hr --;
hc = N;
}
if(hr | hc)
heapify(0, 0, hr, hc);
}
}
On Oct 13, 12:18 pm, sunny agrawal sunny816.i...@gmail.com wrote:
Nopes
Still it does not ensure that duplicates will not be there in the
priority
queue
what i mean is you cannot write directly
do k times{
data = pop()
// let i,j are row and col of data
push(i+1,j);
push(i,j+1);
}
you need to add the following checks
if((i+1,j) is not in the heap) push(i+1,j)
if((i,j+1) is not in the heap) push(i,j+1)
because heap does not automatically check for duplicates
and to check for duplicates we need an extra data structure other
than heap,
which stores that which (i+1,j) are already there in the heap map can
also
be used so overall complexity will go O(k* lg^2K)
On Thu, Oct 13, 2011 at 12:26 PM, anshu mishra
anshumishra6...@gmail.comwrote:
struct data
{
int row, col,
int val;
};
priority_queuedata heap;
now fine?
--
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.
--
Sunny Aggrawal
B.Tech. V year,CSI
Indian Institute Of Technology,Roorkee
--
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
Anika Jain
--
You received this message because you are
Re: [algogeeks] Re: Algo for Search in a 2D Matrix
there's a solution of O(log n) where 2D matrix has n rows and n columns.
Apply binary search for the search on the diagonal. when you are left with
just one element after the search apply binary search within that elements
row and its column. you will get the element. O(log n+log n+log n). so
O(log n).
On Wed, May 16, 2012 at 6:36 PM, Prem Krishna Chettri hprem...@gmail.comwrote:
Well I hv got Something running in my mind buy ofcse need some cornor case
tuning.
If we take sqrt() of the number (say K) than we can avoid looking into
sqrt(k)-1 and sqrt(k)+1 rows and column entirely, which literally means
that the final solution is possible in constant time (the time independent
of k or matrix values), which ofcourse can go upto O(n) in worst case where
N is the Matrix of N Rows and 1 Column as we cannot use the intelligence of
sqrt function to corner the value.
Its seems okei logically to remove those rows and columns as we are
certain that they are sorted in both ways and avoid unnecessary time
looking for the place where it won't belong.
Now the issue is so clear that we can say (sqrt(k)-1)*(sqrt(k)-1)k and
now keep on adding the value to sqrt(k)+1 till U reach k and get corner
that element.
I guess it works..
On Wed, May 16, 2012 at 1:17 PM, Ashish Goel ashg...@gmail.com wrote:
Vikas, can you suggest the logic of this also? I am a bit unclear on how
the 2D arr is being used as a heap and how recursion is used to solve this
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Thu, Oct 13, 2011 at 11:37 PM, vikas vikas.rastogi2...@gmail.comwrote:
@Sunny, good catch, k X k approach wont work
lets try to use matrix itself as heap
heapify(int cr, int cc, int Nr, int Nc){
mr = cr; mc = cc;
if(cr+1 Nr)
mr = cr+1 mc = cc;
if(cc + 1 Nc min A[cc+1][cr])
mr = cr; mc = cc+1;
if(A[cr][cc] A[mr][mc]){
swap(A[cr][cc] ,A[mr][mc]);
heapify(mr, mc, Nr, Nc);
}
extract_min(){
swap(A[0][0], A[hr][hc]);
if(hc 0) hc--;
else if(hr 0){
hr --;
hc = N;
}
if(hr | hc)
heapify(0, 0, hr, hc);
}
}
On Oct 13, 12:18 pm, sunny agrawal sunny816.i...@gmail.com wrote:
Nopes
Still it does not ensure that duplicates will not be there in the
priority
queue
what i mean is you cannot write directly
do k times{
data = pop()
// let i,j are row and col of data
push(i+1,j);
push(i,j+1);
}
you need to add the following checks
if((i+1,j) is not in the heap) push(i+1,j)
if((i,j+1) is not in the heap) push(i,j+1)
because heap does not automatically check for duplicates
and to check for duplicates we need an extra data structure other than
heap,
which stores that which (i+1,j) are already there in the heap map can
also
be used so overall complexity will go O(k* lg^2K)
On Thu, Oct 13, 2011 at 12:26 PM, anshu mishra
anshumishra6...@gmail.comwrote:
struct data
{
int row, col,
int val;
};
priority_queuedata heap;
now fine?
--
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.
--
Sunny Aggrawal
B.Tech. V year,CSI
Indian Institute Of Technology,Roorkee
--
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
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.
Re: [algogeeks] Re: Algo for Search in a 2D Matrix
Vikas, can you suggest the logic of this also? I am a bit unclear on how
the 2D arr is being used as a heap and how recursion is used to solve this
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Thu, Oct 13, 2011 at 11:37 PM, vikas vikas.rastogi2...@gmail.com wrote:
@Sunny, good catch, k X k approach wont work
lets try to use matrix itself as heap
heapify(int cr, int cc, int Nr, int Nc){
mr = cr; mc = cc;
if(cr+1 Nr)
mr = cr+1 mc = cc;
if(cc + 1 Nc min A[cc+1][cr])
mr = cr; mc = cc+1;
if(A[cr][cc] A[mr][mc]){
swap(A[cr][cc] ,A[mr][mc]);
heapify(mr, mc, Nr, Nc);
}
extract_min(){
swap(A[0][0], A[hr][hc]);
if(hc 0) hc--;
else if(hr 0){
hr --;
hc = N;
}
if(hr | hc)
heapify(0, 0, hr, hc);
}
}
On Oct 13, 12:18 pm, sunny agrawal sunny816.i...@gmail.com wrote:
Nopes
Still it does not ensure that duplicates will not be there in the
priority
queue
what i mean is you cannot write directly
do k times{
data = pop()
// let i,j are row and col of data
push(i+1,j);
push(i,j+1);
}
you need to add the following checks
if((i+1,j) is not in the heap) push(i+1,j)
if((i,j+1) is not in the heap) push(i,j+1)
because heap does not automatically check for duplicates
and to check for duplicates we need an extra data structure other than
heap,
which stores that which (i+1,j) are already there in the heap map can
also
be used so overall complexity will go O(k* lg^2K)
On Thu, Oct 13, 2011 at 12:26 PM, anshu mishra
anshumishra6...@gmail.comwrote:
struct data
{
int row, col,
int val;
};
priority_queuedata heap;
now fine?
--
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.
--
Sunny Aggrawal
B.Tech. V year,CSI
Indian Institute Of Technology,Roorkee
--
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: Algo for Search in a 2D Matrix
Well I hv got Something running in my mind buy ofcse need some cornor case
tuning.
If we take sqrt() of the number (say K) than we can avoid looking into
sqrt(k)-1 and sqrt(k)+1 rows and column entirely, which literally means
that the final solution is possible in constant time (the time independent
of k or matrix values), which ofcourse can go upto O(n) in worst case where
N is the Matrix of N Rows and 1 Column as we cannot use the intelligence of
sqrt function to corner the value.
Its seems okei logically to remove those rows and columns as we are
certain that they are sorted in both ways and avoid unnecessary time
looking for the place where it won't belong.
Now the issue is so clear that we can say (sqrt(k)-1)*(sqrt(k)-1)k and now
keep on adding the value to sqrt(k)+1 till U reach k and get corner that
element.
I guess it works..
On Wed, May 16, 2012 at 1:17 PM, Ashish Goel ashg...@gmail.com wrote:
Vikas, can you suggest the logic of this also? I am a bit unclear on how
the 2D arr is being used as a heap and how recursion is used to solve this
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Thu, Oct 13, 2011 at 11:37 PM, vikas vikas.rastogi2...@gmail.comwrote:
@Sunny, good catch, k X k approach wont work
lets try to use matrix itself as heap
heapify(int cr, int cc, int Nr, int Nc){
mr = cr; mc = cc;
if(cr+1 Nr)
mr = cr+1 mc = cc;
if(cc + 1 Nc min A[cc+1][cr])
mr = cr; mc = cc+1;
if(A[cr][cc] A[mr][mc]){
swap(A[cr][cc] ,A[mr][mc]);
heapify(mr, mc, Nr, Nc);
}
extract_min(){
swap(A[0][0], A[hr][hc]);
if(hc 0) hc--;
else if(hr 0){
hr --;
hc = N;
}
if(hr | hc)
heapify(0, 0, hr, hc);
}
}
On Oct 13, 12:18 pm, sunny agrawal sunny816.i...@gmail.com wrote:
Nopes
Still it does not ensure that duplicates will not be there in the
priority
queue
what i mean is you cannot write directly
do k times{
data = pop()
// let i,j are row and col of data
push(i+1,j);
push(i,j+1);
}
you need to add the following checks
if((i+1,j) is not in the heap) push(i+1,j)
if((i,j+1) is not in the heap) push(i,j+1)
because heap does not automatically check for duplicates
and to check for duplicates we need an extra data structure other than
heap,
which stores that which (i+1,j) are already there in the heap map can
also
be used so overall complexity will go O(k* lg^2K)
On Thu, Oct 13, 2011 at 12:26 PM, anshu mishra
anshumishra6...@gmail.comwrote:
struct data
{
int row, col,
int val;
};
priority_queuedata heap;
now fine?
--
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.
--
Sunny Aggrawal
B.Tech. V year,CSI
Indian Institute Of Technology,Roorkee
--
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] Re: algo for number of Hamiltonian (undirected) cycles on the circulant graph C_n(1,2).
@Manish: Let b(n) = a(n) - 2. Then b(n) = b(n-1) + b(n-2) - b(n-5). We
can write this recurrence as a matrix multiplication as follows:
-- -- -- -- ----
| b(n+1) || 1 1 0 0 0 -1 || b(n)|
| b(n) || 1 0 0 0 0 0 || b(n-1) |
| b(n-1) || 0 1 0 0 0 0 || b(n-2) |
| b(n-2) | = | 0 0 1 0 0 0 | x | b(n-3) |
| b(n-3) || 0 0 0 1 0 0 || b(n-4) |
| b(n-4) || 0 0 0 0 1 0 || b(n-5) |
-- -- -- -- ----
Then
k
-- -- -- -- ----
| b(n+k) || 1 1 0 0 0 -1 || b(n)|
| b(n+k-1) || 1 0 0 0 0 0 || b(n-1) |
| b(n+k-2) || 0 1 0 0 0 0 || b(n-2) |
| b(n+k-3) | = | 0 0 1 0 0 0 | x | b(n-3) |
| b(n+k-4) || 0 0 0 1 0 0 || b(n-4) |
| b(n+k-5) || 0 0 0 0 1 0 || b(n-5) |
-- -- -- -- ----
so computing A^k = A to the kth power will do the trick. You can do
this in O(log(k)) operations.
Dave
On Jan 25, 9:23 am, manish patel manispatel...@gmail.com wrote:
This is a question from spoj. can anyone tell me how to approach this
problem.
https://www.spoj.pl/problems/JZPCIR/
Jumping Zippy likes to jump. He jumps every day and feels boring. Then he
think of a new way to jump. He jumps on a big round plaza. The plaza is
divided into n sectors numbered clockwise from 0 to n-1. Firstly, he stands
on sector 0. Each time, when he is stand on sector x, he can jump to sector
(x-2)%n, (x-1)%n, (x+1)%n or (x+2)%n. His goal is to jump to each sector
exactly once and jump back to sector 0 at last. And for the first jump, he
never jumps to sector n-1 or sector n-2. He wants to find the number of
different ways in which he can complete his goal.
Input
First line is a number t, which is the number of testcases. (1=t=1000)
The following t lines, each line contains a integer n, which is the number
of sectors. (5=n=10^18)
Then following t lines, each line contains a integer n, which is the number
of sectors. (5=n=10^18)
* *
*Output*
For each query n, output a line which contains one integer, the number of
different ways Zippy can complete his goal in, modulo 10^9+9.
Example
*Input:*
5
5
6
7
8
9
*Output:*
12
16
23
29
41
PS- after googling i found this as:
Number of sequences of length n with elements {-2,-1,+1,+2}, counted up to
simultaneous reversal and negation, such that the sum of elements of the
whole sequence but of no proper subsequence equals 0 modulo n. For n=4,
the number of Hamiltonian (undirected) cycles on the circulant graph
C_n(1,2).
And the recurrence is a(n)=a(n-1)+a(n-2)-a(n-5)-2
--but i am sure this will give TLE. (n=10^18)
Can anyone tell how to solve this problem ...
With Regards
Manish Patel
BTech
Computer Science And Engineering
National Institute of Technology -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.
[algogeeks] Re: algo for number of Hamiltonian (undirected) cycles on the circulant graph C_n(1,2).
@Dave: Can you tell us how you got there from the problem description?
On Jan 25, 11:02 am, Dave dave_and_da...@juno.com wrote:
@Manish: Let b(n) = a(n) - 2. Then b(n) = b(n-1) + b(n-2) - b(n-5). We
can write this recurrence as a matrix multiplication as follows:
-- -- -- -- -- --
| b(n+1) | | 1 1 0 0 0 -1 | | b(n) |
| b(n) | | 1 0 0 0 0 0 | | b(n-1) |
| b(n-1) | | 0 1 0 0 0 0 | | b(n-2) |
| b(n-2) | = | 0 0 1 0 0 0 | x | b(n-3) |
| b(n-3) | | 0 0 0 1 0 0 | | b(n-4) |
| b(n-4) | | 0 0 0 0 1 0 | | b(n-5) |
-- -- -- -- -- --
Then
k
-- -- -- -- -- --
| b(n+k) | | 1 1 0 0 0 -1 | | b(n) |
| b(n+k-1) | | 1 0 0 0 0 0 | | b(n-1) |
| b(n+k-2) | | 0 1 0 0 0 0 | | b(n-2) |
| b(n+k-3) | = | 0 0 1 0 0 0 | x | b(n-3) |
| b(n+k-4) | | 0 0 0 1 0 0 | | b(n-4) |
| b(n+k-5) | | 0 0 0 0 1 0 | | b(n-5) |
-- -- -- -- -- --
so computing A^k = A to the kth power will do the trick. You can do
this in O(log(k)) operations.
Dave
On Jan 25, 9:23 am, manish patel manispatel...@gmail.com wrote:
This is a question from spoj. can anyone tell me how to approach this
problem.
https://www.spoj.pl/problems/JZPCIR/
Jumping Zippy likes to jump. He jumps every day and feels boring. Then he
think of a new way to jump. He jumps on a big round plaza. The plaza is
divided into n sectors numbered clockwise from 0 to n-1. Firstly, he stands
on sector 0. Each time, when he is stand on sector x, he can jump to sector
(x-2)%n, (x-1)%n, (x+1)%n or (x+2)%n. His goal is to jump to each sector
exactly once and jump back to sector 0 at last. And for the first jump, he
never jumps to sector n-1 or sector n-2. He wants to find the number of
different ways in which he can complete his goal.
Input
First line is a number t, which is the number of testcases. (1=t=1000)
The following t lines, each line contains a integer n, which is the number
of sectors. (5=n=10^18)
Then following t lines, each line contains a integer n, which is the number
of sectors. (5=n=10^18)
* *
*Output*
For each query n, output a line which contains one integer, the number of
different ways Zippy can complete his goal in, modulo 10^9+9.
Example
*Input:*
5
5
6
7
8
9
*Output:*
12
16
23
29
41
PS- after googling i found this as:
Number of sequences of length n with elements {-2,-1,+1,+2}, counted up to
simultaneous reversal and negation, such that the sum of elements of the
whole sequence but of no proper subsequence equals 0 modulo n. For n=4,
the number of Hamiltonian (undirected) cycles on the circulant graph
C_n(1,2).
And the recurrence is a(n)=a(n-1)+a(n-2)-a(n-5)-2
--but i am sure this will give TLE. (n=10^18)
Can anyone tell how to solve this problem ...
With Regards
Manish Patel
BTech
Computer Science And Engineering
National Institute of Technology -Allahabad- Hide quoted text -
- Show quoted text -
--
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: algo for number of Hamiltonian (undirected) cycles on the circulant graph C_n(1,2).
@Don: I got there from the recurrence in the last paragraph of
Manish's posting.
Dave
On Jan 25, 12:24 pm, Don dondod...@gmail.com wrote:
@Dave: Can you tell us how you got there from the problem description?
On Jan 25, 11:02 am, Dave dave_and_da...@juno.com wrote:
@Manish: Let b(n) = a(n) - 2. Then b(n) = b(n-1) + b(n-2) - b(n-5). We
can write this recurrence as a matrix multiplication as follows:
-- -- -- -- -- --
| b(n+1) | | 1 1 0 0 0 -1 | | b(n) |
| b(n) | | 1 0 0 0 0 0 | | b(n-1) |
| b(n-1) | | 0 1 0 0 0 0 | | b(n-2) |
| b(n-2) | = | 0 0 1 0 0 0 | x | b(n-3) |
| b(n-3) | | 0 0 0 1 0 0 | | b(n-4) |
| b(n-4) | | 0 0 0 0 1 0 | | b(n-5) |
-- -- -- -- -- --
Then
k
-- -- -- -- -- --
| b(n+k) | | 1 1 0 0 0 -1 | | b(n) |
| b(n+k-1) | | 1 0 0 0 0 0 | | b(n-1) |
| b(n+k-2) | | 0 1 0 0 0 0 | | b(n-2) |
| b(n+k-3) | = | 0 0 1 0 0 0 | x | b(n-3) |
| b(n+k-4) | | 0 0 0 1 0 0 | | b(n-4) |
| b(n+k-5) | | 0 0 0 0 1 0 | | b(n-5) |
-- -- -- -- -- --
so computing A^k = A to the kth power will do the trick. You can do
this in O(log(k)) operations.
Dave
On Jan 25, 9:23 am, manish patel manispatel...@gmail.com wrote:
This is a question from spoj. can anyone tell me how to approach this
problem.
https://www.spoj.pl/problems/JZPCIR/
Jumping Zippy likes to jump. He jumps every day and feels boring. Then he
think of a new way to jump. He jumps on a big round plaza. The plaza is
divided into n sectors numbered clockwise from 0 to n-1. Firstly, he
stands
on sector 0. Each time, when he is stand on sector x, he can jump to
sector
(x-2)%n, (x-1)%n, (x+1)%n or (x+2)%n. His goal is to jump to each sector
exactly once and jump back to sector 0 at last. And for the first jump, he
never jumps to sector n-1 or sector n-2. He wants to find the number of
different ways in which he can complete his goal.
Input
First line is a number t, which is the number of testcases. (1=t=1000)
The following t lines, each line contains a integer n, which is the number
of sectors. (5=n=10^18)
Then following t lines, each line contains a integer n, which is the
number
of sectors. (5=n=10^18)
* *
*Output*
For each query n, output a line which contains one integer, the number of
different ways Zippy can complete his goal in, modulo 10^9+9.
Example
*Input:*
5
5
6
7
8
9
*Output:*
12
16
23
29
41
PS- after googling i found this as:
Number of sequences of length n with elements {-2,-1,+1,+2}, counted up
to
simultaneous reversal and negation, such that the sum of elements of the
whole sequence but of no proper subsequence equals 0 modulo n. For n=4,
the number of Hamiltonian (undirected) cycles on the circulant graph
C_n(1,2).
And the recurrence is a(n)=a(n-1)+a(n-2)-a(n-5)-2
--but i am sure this will give TLE. (n=10^18)
Can anyone tell how to solve this problem ...
With Regards
Manish Patel
BTech
Computer Science And Engineering
National Institute of Technology -Allahabad- Hide quoted text -
- Show quoted text -
--
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: algo qstn
int grid[200][200] = {{0}};
int x=100;
int y=100;
int d = 0;
int count = 0;
for(int i = 0; i 1018; ++i)
{
x += BCBA[d] - 'B';
y += CBAB[d] - 'B';
count += CA[grid[x][y]] - 'B';
d = (grid[x][y] ? BCDA[d] : DABC[d]) - 'A';
grid[x][y] ^= 1;
}
printf(%d\n, count);
On Jan 18, 4:28 am, Ravi Ranjan ravi.cool2...@gmail.com wrote:
i m searching for the approach to solve. can u please tell the
approach instead of answer
--
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: algo qstn
class Ant
{
private readonly IDictionarystring, Col _blacks = new
Dictionarystring, Col();
private Direction _curDir;
private int _x;
private int _y;
public Ant()
{
_curDir = Direction.North;
_x = 10;
_y = 10;
}
public IDictionarystring, Col Move()
{
_x = _curDir == Direction.East ? _x + 1 : _curDir ==
Direction.West ? _x - 1 : _x;
_y = _curDir == Direction.North ? _y + 1 : _curDir ==
Direction.South ? _y - 1 : _y;
if (GetColorAt(_x, _y) == Col.White)
{
_blacks.Add(GenKey(_x, _y), Col.Black);
_curDir = (Direction)((uint)(_curDir + 1) % 4);
}
else
{
_blacks.Remove(GenKey(_x, _y));
_curDir = (Direction)((uint)(_curDir - 1) % 4);
}
return _blacks;
}
private Col GetColorAt(int x, int y)
{
string key = GenKey(x, y);
return _blacks.ContainsKey(key) ? Col.Black : Col.White;
}
private static string GenKey(int x, int y)
{
return string.Format({0}:{1}, x, y);
}
}
calling Move() 1018 and at the end you will get a map length == number
of blacks
On Jan 18, 4:28 am, Ravi Ranjan ravi.cool2...@gmail.com wrote:
i m searching for the approach to solve. can u please tell the
approach instead of answer
--
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: algo qstn
i m searching for the approach to solve. can u please tell the approach instead of answer -- 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: algo qstn
120 On Jan 17, 5:59 am, Umer Farooq the.um...@gmail.com wrote: 0 On 1/16/12, Ravi Ranjan ravi.cool2...@gmail.com wrote: An ant moves on a regular grid of squares that are coloured either black or white. The ant is always oriented in one of the cardinal directions (left, right, up or down) and moves from square to adjacent square according to the following rules: - if it is on a black square, it flips the color of the square to white, rotates 90 degrees counterclockwise and moves forward one square. - if it is on a white square, it flips the color of the square to black, rotates 90 degrees clockwise and moves forward one square. Starting with a grid that is entirely white, how many squares are black after 1018 moves of the ant? source http://projecteuler.net/problem=349 -- 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. -- Umer -- 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: algo qstn
+1 Jaimedp On Jan 17, 1:05 pm, jaimedp jaim...@gmail.com wrote: 120 On Jan 17, 5:59 am, Umer Farooq the.um...@gmail.com wrote: 0 On 1/16/12, Ravi Ranjan ravi.cool2...@gmail.com wrote: An ant moves on a regular grid of squares that are coloured either black or white. The ant is always oriented in one of the cardinal directions (left, right, up or down) and moves from square to adjacent square according to the following rules: - if it is on a black square, it flips the color of the square to white, rotates 90 degrees counterclockwise and moves forward one square. - if it is on a white square, it flips the color of the square to black, rotates 90 degrees clockwise and moves forward one square. Starting with a grid that is entirely white, how many squares are black after 1018 moves of the ant? source http://projecteuler.net/problem=349 -- 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. -- Umer- Hide quoted text - - Show quoted text - -- 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: Algo for Search in a 2D Matrix
If O(k*logk) solution is acceptable then it is very simple.
maintain a min heap.
push a[0][0],
i = 0;
while ( i k)
{
pop an element. --- O(log(i)) -- coz number of elements in heap is i;
push the two adjacent element that is one right and right below. ---
O(log(i));
i++;
}
last element popped will be answer.
size of heap at every iteration will increase by one coz we are inserting
two elements and removing one element at every iteration.
If anyone has doubt on correctness of this solution can ask.
--
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: Algo for Search in a 2D Matrix
push the two adjacent element that is one right and below -- 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: Algo for Search in a 2D Matrix
@Anshu pushing adjacent element will cause duplicate entries in the heap try the following example: 1 2 3 4 5 6 7 2 3 4 5 6 7 8 3 4 5 6 7 8 9 4 5 6 7 8 9 10 so we also need to maintain a data structure that can efficiently tell that which cell has been pushed into the heap already. On Thu, Oct 13, 2011 at 11:35 AM, anshu mishra anshumishra6...@gmail.comwrote: push the two adjacent element that is one right and below -- 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. -- Sunny Aggrawal B.Tech. V year,CSI Indian Institute Of Technology,Roorkee -- 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: Algo for Search in a 2D Matrix
struct data
{
int row, col,
int val;
};
priority_queuedata heap;
now fine?
--
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: Algo for Search in a 2D Matrix
Nopes
Still it does not ensure that duplicates will not be there in the priority
queue
what i mean is you cannot write directly
do k times{
data = pop()
// let i,j are row and col of data
push(i+1,j);
push(i,j+1);
}
you need to add the following checks
if((i+1,j) is not in the heap) push(i+1,j)
if((i,j+1) is not in the heap) push(i,j+1)
because heap does not automatically check for duplicates
and to check for duplicates we need an extra data structure other than heap,
which stores that which (i+1,j) are already there in the heap map can also
be used so overall complexity will go O(k* lg^2K)
On Thu, Oct 13, 2011 at 12:26 PM, anshu mishra anshumishra6...@gmail.comwrote:
struct data
{
int row, col,
int val;
};
priority_queuedata heap;
now fine?
--
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.
--
Sunny Aggrawal
B.Tech. V year,CSI
Indian Institute Of Technology,Roorkee
--
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: Algo for Search in a 2D Matrix
@Sunny, good catch, k X k approach wont work
lets try to use matrix itself as heap
heapify(int cr, int cc, int Nr, int Nc){
mr = cr; mc = cc;
if(cr+1 Nr)
mr = cr+1 mc = cc;
if(cc + 1 Nc min A[cc+1][cr])
mr = cr; mc = cc+1;
if(A[cr][cc] A[mr][mc]){
swap(A[cr][cc] ,A[mr][mc]);
heapify(mr, mc, Nr, Nc);
}
extract_min(){
swap(A[0][0], A[hr][hc]);
if(hc 0) hc--;
else if(hr 0){
hr --;
hc = N;
}
if(hr | hc)
heapify(0, 0, hr, hc);
}
}
On Oct 13, 12:18 pm, sunny agrawal sunny816.i...@gmail.com wrote:
Nopes
Still it does not ensure that duplicates will not be there in the priority
queue
what i mean is you cannot write directly
do k times{
data = pop()
// let i,j are row and col of data
push(i+1,j);
push(i,j+1);
}
you need to add the following checks
if((i+1,j) is not in the heap) push(i+1,j)
if((i,j+1) is not in the heap) push(i,j+1)
because heap does not automatically check for duplicates
and to check for duplicates we need an extra data structure other than heap,
which stores that which (i+1,j) are already there in the heap map can also
be used so overall complexity will go O(k* lg^2K)
On Thu, Oct 13, 2011 at 12:26 PM, anshu mishra
anshumishra6...@gmail.comwrote:
struct data
{
int row, col,
int val;
};
priority_queuedata heap;
now fine?
--
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.
--
Sunny Aggrawal
B.Tech. V year,CSI
Indian Institute Of Technology,Roorkee
--
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: Algo for Search in a 2D Matrix
@Shiva, not necessarily in upper half take the transpose of example put by Dave and see by yourself There are few observations for this question: 1. kth smallest will always lie in first k*k matrix 2. it wont be part of sqrt(k)*sqrt(k) matrix Thus rest all need to be searched recursively to find the element Any suggestions ? On Oct 10, 10:55 am, shiva@Algo shiv.jays...@gmail.com wrote: id we see the pattern then we can easily find that the kth smallest element lie on the upper half of the k*k submatrix(on the upperleft corner ) we can do search on (k*k)/2 elements to find that On Mon, Oct 10, 2011 at 10:36 AM, Dave dave_and_da...@juno.com wrote: @Shubham: So if the matrix is 1 2 3 4 and you want the 2nd smallest, are you saying that it is 4? Dave On Oct 9, 7:40 pm, shubham goyal shubhamgoyal.n...@gmail.com wrote: im assuming it be a square matrix then kth smallest element will be in a first k*k sub matrix. jst look for smallest element in the diagonal of this matrix. it will give the kth smallest element . On Mon, Oct 10, 2011 at 4:45 AM, Ankur Garg ankurga...@gmail.com wrote: Given a 2D matrix which is both row wise and column wise sorted. Propose an algorithm for finding the kth smallest element in it in least time complexity A General Max Heap can be used with k space and n+klogk complexity Any other solution or even a way by which we dont scan the whole matrix to find the solution ? I -- 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: Algo for Search in a 2D Matrix
i dont think k*k submatrix approach works at all what if k =n size of submatrix will be n*n, which is matrix itself heap seems to be a good approach with a coloring scheme that helps in avoiding duplicates in heap ?? On Wed, Oct 12, 2011 at 7:18 PM, vikas vikas.rastogi2...@gmail.com wrote: @Shiva, not necessarily in upper half take the transpose of example put by Dave and see by yourself There are few observations for this question: 1. kth smallest will always lie in first k*k matrix 2. it wont be part of sqrt(k)*sqrt(k) matrix Thus rest all need to be searched recursively to find the element Any suggestions ? On Oct 10, 10:55 am, shiva@Algo shiv.jays...@gmail.com wrote: id we see the pattern then we can easily find that the kth smallest element lie on the upper half of the k*k submatrix(on the upperleft corner ) we can do search on (k*k)/2 elements to find that On Mon, Oct 10, 2011 at 10:36 AM, Dave dave_and_da...@juno.com wrote: @Shubham: So if the matrix is 1 2 3 4 and you want the 2nd smallest, are you saying that it is 4? Dave On Oct 9, 7:40 pm, shubham goyal shubhamgoyal.n...@gmail.com wrote: im assuming it be a square matrix then kth smallest element will be in a first k*k sub matrix. jst look for smallest element in the diagonal of this matrix. it will give the kth smallest element . On Mon, Oct 10, 2011 at 4:45 AM, Ankur Garg ankurga...@gmail.com wrote: Given a 2D matrix which is both row wise and column wise sorted. Propose an algorithm for finding the kth smallest element in it in least time complexity A General Max Heap can be used with k space and n+klogk complexity Any other solution or even a way by which we dont scan the whole matrix to find the solution ? I -- 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. -- Sunny Aggrawal B.Tech. V year,CSI Indian Institute Of Technology,Roorkee -- 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: Algo for Search in a 2D Matrix
Here is a solution based on the fact that the matrix is quiet similar to a
min heap. each cell is smaller than its down and right neighbor.
Note :- This solution modifies the original matrix.
Algo -
repeat k-1 times
set a[0][0] = INFINITY
minHeapify the Matrix (see implementation below). This will create
holes in the matrix that can be filled with INFINITY.
return a[0][0];
- Complexity O(k*(m+n)) for a m x n matrix.
- Here is a java implementation of the same.
public static int kthSmallest(int[][] a, int k)
{
final int INF = Integer.MAX_VALUE;
int rows = a.length;
int cols = a[0].length;
if (k rows*cols)
{
System.out.println(Matrix has less than + k + elements.);
return INF;
}
while(--k 0)
{
a[0][0] = INF; int i=0, j=0;
// MinHeapify the matrix again.
while(true)
{
int down = INF; int right = INF;
if(i rows-1) down = a[i+1][j];
if(j cols-1)right = a[i][j+1];
if((down == INF) (right == INF))
break;
if(down right)
{
int temp = a[i][j];
a[i][j] = down;
a[i+1][j] = temp;
i++;
}
else
{
int temp = a[i][j];
a[i][j] = right;
a[i][j+1] = temp;
j++;
}
}
}
return a[0][0];
}
Feedback welcome :-)
- Ravindra
On Wed, Oct 12, 2011 at 8:18 PM, sunny agrawal sunny816.i...@gmail.comwrote:
i dont think k*k submatrix approach works at all
what if k =n size of submatrix will be n*n, which is matrix itself
heap seems to be a good approach with a coloring scheme that helps in
avoiding duplicates in heap ??
On Wed, Oct 12, 2011 at 7:18 PM, vikas vikas.rastogi2...@gmail.comwrote:
@Shiva, not necessarily in upper half
take the transpose of example put by Dave and see by yourself
There are few observations for this question:
1. kth smallest will always lie in first k*k matrix
2. it wont be part of sqrt(k)*sqrt(k) matrix
Thus rest all need to be searched recursively to find the element
Any suggestions ?
On Oct 10, 10:55 am, shiva@Algo shiv.jays...@gmail.com wrote:
id we see the pattern then we can easily find that the kth smallest
element
lie on the upper half of the k*k submatrix(on the upperleft corner )
we can do search on (k*k)/2 elements to find that
On Mon, Oct 10, 2011 at 10:36 AM, Dave dave_and_da...@juno.com wrote:
@Shubham: So if the matrix is
1 2
3 4
and you want the 2nd smallest, are you saying that it is 4?
Dave
On Oct 9, 7:40 pm, shubham goyal shubhamgoyal.n...@gmail.com wrote:
im assuming it be a square matrix
then kth smallest element will be in a first k*k sub matrix.
jst look for smallest element in the diagonal of this matrix.
it will give the kth smallest element .
On Mon, Oct 10, 2011 at 4:45 AM, Ankur Garg ankurga...@gmail.com
wrote:
Given a 2D matrix which is both row wise and column wise sorted.
Propose an
algorithm for finding the kth smallest element in it in least time
complexity
A General Max Heap can be used with k space and n+klogk complexity
Any other solution or even a way by which we dont scan the whole
matrix to
find the solution ?
I
--
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.
--
Sunny Aggrawal
B.Tech. V year,CSI
Indian Institute Of Technology,Roorkee
--
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
Re: [algogeeks] Re: Algo for Search in a 2D Matrix
id we see the pattern then we can easily find that the kth smallest element lie on the upper half of the k*k submatrix(on the upperleft corner ) we can do search on (k*k)/2 elements to find that On Mon, Oct 10, 2011 at 10:36 AM, Dave dave_and_da...@juno.com wrote: @Shubham: So if the matrix is 1 2 3 4 and you want the 2nd smallest, are you saying that it is 4? Dave On Oct 9, 7:40 pm, shubham goyal shubhamgoyal.n...@gmail.com wrote: im assuming it be a square matrix then kth smallest element will be in a first k*k sub matrix. jst look for smallest element in the diagonal of this matrix. it will give the kth smallest element . On Mon, Oct 10, 2011 at 4:45 AM, Ankur Garg ankurga...@gmail.com wrote: Given a 2D matrix which is both row wise and column wise sorted. Propose an algorithm for finding the kth smallest element in it in least time complexity A General Max Heap can be used with k space and n+klogk complexity Any other solution or even a way by which we dont scan the whole matrix to find the solution ? I -- 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] Re: Algo for Search in a 2D Matrix
@Shubham: So if the matrix is 1 2 3 4 and you want the 2nd smallest, are you saying that it is 4? Dave On Oct 9, 7:40 pm, shubham goyal shubhamgoyal.n...@gmail.com wrote: im assuming it be a square matrix then kth smallest element will be in a first k*k sub matrix. jst look for smallest element in the diagonal of this matrix. it will give the kth smallest element . On Mon, Oct 10, 2011 at 4:45 AM, Ankur Garg ankurga...@gmail.com wrote: Given a 2D matrix which is both row wise and column wise sorted. Propose an algorithm for finding the kth smallest element in it in least time complexity A General Max Heap can be used with k space and n+klogk complexity Any other solution or even a way by which we dont scan the whole matrix to find the solution ? I -- 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: Algo for in-place Stack Reversal.
I'm not sure if I got the question correct.
How about change the address of stack to point to top and then
modify the push,pop functions to retrieve values as
push(int a){
stack[--top] = a;
}
int pop(){
return (stack[a++]);
}
I know there is serious limitation of not able to add elements without
removal, and the
size of the stack is limited by no. of elements before the modification.
this is an idea, but we are not working on data, so, not sure if this is
acceptable.
--
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/-/1EnHa1NZCisJ.
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: Algo for in-place Stack Reversal.
If initially we have : 4 3 2 1 then we need this : 1 2 3 4 We need to do in-place. Even if we can do with loops then how. -- 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/-/KCU16KgzPqgJ. 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: Algo for in-place Stack Reversal.
yeah... i think its not possible without manipulating the pointers and then use general retrieval logic. reversal retrieval cannot be done without extra space, and without modifying the DS. (like I mentioned before, changing the stack to point to top manipulating the push, pop functions.) Otherwise, its not possible. -- 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/-/wvRUuv1O-eoJ. 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: Algo
use DFS. at any poit of time if u find a node such that it has no left and right child, then you are at leaf. find sum of all values in the stack. for that u can use another stack. On Oct 7, 4:15 pm, Deepak arora deepakarora...@gmail.com wrote: Please tell the algo of this problem hasPathSum() We'll define a root-to-leaf path to be a sequence of nodes in a tree starting with the root node and proceeding downward to a leaf (a node with no children). We'll say that an empty tree contains no root-to-leaf paths. So for example, the following tree has exactly four root-to-leaf paths: 5 / \ 4 8 / / \ 11 13 4 / \ \ 7 2 1 Root-to-leaf paths: path 1: 5 4 11 7 path 2: 5 4 11 2 path 3: 5 8 13 path 4: 5 8 4 1 For this problem, we will be concerned with the sum of the values of such a path -- for example, the sum of the values on the 5-4-11-7 path is 5 + 4 + 11 + 7 = 27. thanks.. -- 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: Algo
we find sum of all path... like- path 1: 5 4 11 7=27 path 2: 5 4 11 2=22 path 3: 5 8 13=26 path 4: 5 8 4 1 =18 -- 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: Algo
thanks tpawan10 -- 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: Algo
try this..after passing root pointer and 0 to the function
void summer(node *r,int sum)
{
if(r)
{
if(!r-left !r-right)
{
coutsum+r-dataendl;
return;
}
summer(r-left,sum+(r-data));
summer(r-right,sum+(r-data));
}
}
On Fri, Oct 7, 2011 at 10:31 PM, Deepak arora deepakarora...@gmail.comwrote:
thanks tpawan10
--
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.
--
*Dheeraj Sharma*
--
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: Algo Book
Data Structures and Algorithm Analysis by Mark Allen Weiss On Sep 6, 3:39 pm, siddharam suresh siddharam@gmail.com wrote: @neha: there is site calledhttp://library.nu register there, u'll get majority of the books. Thank you, Sid. On Tue, Sep 6, 2011 at 3:54 PM, Prashant Kulkarni prashant.r.k...@gmail.com wrote: The Algorithm Design Manual By Steve S. Skiena -- Prashant Kulkarni On Tue, Sep 6, 2011 at 3:48 PM, Udit Gupta uditgupta...@gmail.com wrote: Fundamentals of Computer Algorithms by Sartaj Sahni On Tue, Sep 6, 2011 at 3:45 PM, Neha Gupta nehagup...@gmail.com wrote: hey guys , do tell me a book for algo( other than cormen) with good no. of illustrations or any resource or link on net(especially for dp, backtracking, np problems etc ) -- 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.
Re: [algogeeks] Re: Algo to identify loose ends of each cable in minimum time.
I think Dave is right and his solution also seems correct. Answer is 20KM i.e. 2 trips. Good work @Dave. On Wed, Apr 6, 2011 at 7:43 PM, Dave dave_and_da...@juno.com wrote: @Bittu: Actually, this is an easier problem than the Graham-Knowlton Problem. It the GKP, you can only connect wires at one end and test at the other. In this problem, this restriction is not given. The algorithm I presented allows you to identify the wires with two one- way trips by first connecting wires at one end and then connecting them at the other end. Dave On Apr 5, 5:27 am, bittu shashank7andr...@gmail.com wrote: its the The Graham-Knowlton Problem in their paper this proble4ms i published is published goole it you will get answer explanation Thanks Regards Shashank Mani CSE, BIT Mesra -- 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. -- Munish -- 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: Algo to identify loose ends of each cable in minimum time.
its the The Graham-Knowlton Problem in their paper this proble4ms i published is published goole it you will get answer explanation Thanks Regards Shashank Mani CSE, BIT Mesra -- 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: Algo to identify loose ends of each cable in minimum time.
At the first end, connect pairs of wires together, leaving two wires unconnected. Go to the other end. Find a pair of connected wires, and number them #2 and #3. Find another pair and label them #4 and #5. Repeat for all of the pairs, with the last pair labeled #118 and #119. There remains two wires that are not connected to each other. Label one of these #1 and the other #120. Connect #1 to #2, #3 to #4, etc, leaving #119 and 120 unconnected. Go back to the first end. One of the originally unconnected wires still is unconnected. Label it #120 and label the other originally connected wire #1. Now find the wire connected to #1 and label it #2. The wire that originally was connected with new wire #2 can be labeled #3. The wire that is now connected to the newly labeled #3 is #4. In this way, all of the wires can be identified on both ends in two trips (one round trip). If it is necessary to disconnect the connections at the other end, a third trip is necessary. Dave On Apr 4, 5:17 am, Munish Goyal munish.go...@gmail.com wrote: Hi, Just posted another problem, which comes in category of hard problems. http://industryinterviewquestions.blogspot.com/2011/04/least-number-o... -- Munish -- 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: algo for mirror a tree
assuming its a binary tree
Node* mirror(Node* root){
if(root==NULL)
return;
Node* mirrorLeft = mirror(root-left)'
Node* mirrorRight = mirror(root-right);
root-left = mirrorRight;
root-right=mirrorLeft;
return root;
}
On Mar 11, 4:50 am, AKS abhijeet.k.s...@gmail.com wrote:
can u elaborate a bit ??
with sm example if possible
On Mar 11, 4:52 am, priyank desai priyankd...@gmail.com wrote:
Do a post order traversal of the tree and swap its child instead of
printing the node values.
On Mar 10, 8:19 am, Subhransupanigrahi subhransu.panigr...@gmail.com
wrote:
Hey guys,
you guys have came across many time with mirror a tree. if anyone has
effective ways interms of memory efficiency way to implement mirror of
a tree.
Sent from my iPhone
--
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: algo for mirror a tree
can u elaborate a bit ?? with sm example if possible On Mar 11, 4:52 am, priyank desai priyankd...@gmail.com wrote: Do a post order traversal of the tree and swap its child instead of printing the node values. On Mar 10, 8:19 am, Subhransupanigrahi subhransu.panigr...@gmail.com wrote: Hey guys, you guys have came across many time with mirror a tree. if anyone has effective ways interms of memory efficiency way to implement mirror of a tree. Sent from my iPhone -- 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: algo for mirror a tree
Do a post order traversal of the tree and swap its child instead of printing the node values. On Mar 10, 8:19 am, Subhransupanigrahi subhransu.panigr...@gmail.com wrote: Hey guys, you guys have came across many time with mirror a tree. if anyone has effective ways interms of memory efficiency way to implement mirror of a tree. Sent from my iPhone -- 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: ALgo help pls
In my opinion also, this is a Majority vote algorithm as mentioned by Navin and as coded by Dave. Only point I would add to @Dave's code is that it wont be possible to find if the majority element has 2n/3 occurance as majority element keeps changing during the run and as the majority algorithm tells you a number which has greater than n/2 occurrence. So all you need to do is another liner scan after the majority element is found to check if its count is 2n/3. @Narsimha Raju: your failure to find 2n/3 occurrence by adding a for loop is expected. Please reply if we are able to add a for loop into code above (given by @Dave) to find if majority element has 2n/3 occurance. Thanks, Sourav On Sep 22, 9:02 am, Navin Naidu navinmna...@gmail.com wrote: Use majority vote algorithm: http://userweb.cs.utexas.edu/~moore/best-ideas/mjrty/index.html On Wed, Sep 22, 2010 at 9:12 AM, pre pre.la...@gmail.com wrote: Hi all, pls help me solve this problem.. Design an algorithm to find the majority element of an array.. majority element must be an element tht has the cardinality greater than 2n/3 where n is the number of elements in the array and the time complexity must be a linear time.. ie o(n).. hint : use mode or median to solve .. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards, - NMN -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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: ALgo help pls
Try something like this:
int FindMajority( int n , int a[] )
{
int majority = a[0];
int count = 1;
for( i = 1 ; i n ; ++i )
{
if( a[i] == majority )
{
++count;
}
else
{
if( count == 0 )
{
majority = a[i];
count = 1;
}
else
{
--count;
}
}
}
return majority;
}
It will find an element that occurs at least n/2 times in the array.
If you need to verify that the element occurs 2n/3 times, add a loop
to count the number of occurences of majority before the return.
On Sep 21, 10:42 pm, pre pre.la...@gmail.com wrote:
Hi all,
pls help me solve this problem..
Design an algorithm to find the majority element of an array..
majority element must be an element tht has the cardinality greater
than 2n/3 where n is the number of elements in the array and the time
complexity must be a linear time.. ie o(n)..
hint : use mode or median to solve ..
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@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: ALgo help pls
solution in o(n log n)
can be ( as if solution exit only one element cam be a majority element in
the given array)
1. sort the array in O(nlogn)
2. x = a[2n/3]
if(a[0]==x)
{ if(x== a[(2n/3])+1)
return (x)
}
On Wed, Sep 22, 2010 at 5:53 AM, Dave dave_and_da...@juno.com wrote:
Try something like this:
int FindMajority( int n , int a[] )
{
int majority = a[0];
int count = 1;
for( i = 1 ; i n ; ++i )
{
if( a[i] == majority )
{
++count;
}
else
{
if( count == 0 )
{
majority = a[i];
count = 1;
}
else
{
--count;
}
}
}
return majority;
}
It will find an element that occurs at least n/2 times in the array.
If you need to verify that the element occurs 2n/3 times, add a loop
to count the number of occurences of majority before the return.
On Sep 21, 10:42 pm, pre pre.la...@gmail.com wrote:
Hi all,
pls help me solve this problem..
Design an algorithm to find the majority element of an array..
majority element must be an element tht has the cardinality greater
than 2n/3 where n is the number of elements in the array and the time
complexity must be a linear time.. ie o(n)..
hint : use mode or median to solve ..
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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: ALgo help pls
@coolfrogs: How can more than one element exist of 2n/3 times repeated..
@dave: can u add that for loop and send as i tried but could not succeed
On Wed, Sep 22, 2010 at 6:23 PM, coolfrog$
dixit.coolfrog.div...@gmail.comwrote:
solution in o(n log n)
can be ( as if solution exit only one element cam be a majority element in
the given array)
1. sort the array in O(nlogn)
2. x = a[2n/3]
if(a[0]==x)
{ if(x== a[(2n/3])+1)
return (x)
}
On Wed, Sep 22, 2010 at 5:53 AM, Dave dave_and_da...@juno.com wrote:
Try something like this:
int FindMajority( int n , int a[] )
{
int majority = a[0];
int count = 1;
for( i = 1 ; i n ; ++i )
{
if( a[i] == majority )
{
++count;
}
else
{
if( count == 0 )
{
majority = a[i];
count = 1;
}
else
{
--count;
}
}
}
return majority;
}
It will find an element that occurs at least n/2 times in the array.
If you need to verify that the element occurs 2n/3 times, add a loop
to count the number of occurences of majority before the return.
On Sep 21, 10:42 pm, pre pre.la...@gmail.com wrote:
Hi all,
pls help me solve this problem..
Design an algorithm to find the majority element of an array..
majority element must be an element tht has the cardinality greater
than 2n/3 where n is the number of elements in the array and the time
complexity must be a linear time.. ie o(n)..
hint : use mode or median to solve ..
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Regards,
C. Narsimha Raju
MS, IIIT Hyderabad.
http://research.iiit.ac.in/~narsimha_raju/
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@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: ALgo help pls
@ Narsimha Raju : yes only one such can element exit...
@Pre :
Is there any algorithm to find median or mode in o(n)...
because common approach are :
Find the Median of: 9, 3, 44, 17, 15 (Odd amount of numbers)
Line up your numbers: 3, 9, 15, 17, 44 (smallest to largest)
The Median is: 15 (The number in the middle)
Find the mode of:
9, 3, 3, 44, 17 , 17, 44, 15, 15, 15, 27, 40, 8,
Put the numbers is order for ease:
3, 3, 8, 9, 15, 15, 15, 17, 17, 27, 40, 44, 44,
The Mode is 15 (15 occurs the most at 3 times)
On Wed, Sep 22, 2010 at 8:01 AM, Narsimha Raju cnarsimhar...@gmail.comwrote:
@coolfrogs: How can more than one element exist of 2n/3 times repeated..
@dave: can u add that for loop and send as i tried but could not succeed
On Wed, Sep 22, 2010 at 6:23 PM, coolfrog$
dixit.coolfrog.div...@gmail.com wrote:
solution in o(n log n)
can be ( as if solution exit only one element cam be a majority element
in the given array)
1. sort the array in O(nlogn)
2. x = a[2n/3]
if(a[0]==x)
{ if(x== a[(2n/3])+1)
return (x)
}
On Wed, Sep 22, 2010 at 5:53 AM, Dave dave_and_da...@juno.com wrote:
Try something like this:
int FindMajority( int n , int a[] )
{
int majority = a[0];
int count = 1;
for( i = 1 ; i n ; ++i )
{
if( a[i] == majority )
{
++count;
}
else
{
if( count == 0 )
{
majority = a[i];
count = 1;
}
else
{
--count;
}
}
}
return majority;
}
It will find an element that occurs at least n/2 times in the array.
If you need to verify that the element occurs 2n/3 times, add a loop
to count the number of occurences of majority before the return.
On Sep 21, 10:42 pm, pre pre.la...@gmail.com wrote:
Hi all,
pls help me solve this problem..
Design an algorithm to find the majority element of an array..
majority element must be an element tht has the cardinality greater
than 2n/3 where n is the number of elements in the array and the time
complexity must be a linear time.. ie o(n)..
hint : use mode or median to solve ..
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Regards,
C. Narsimha Raju
MS, IIIT Hyderabad.
http://research.iiit.ac.in/~narsimha_raju/http://research.iiit.ac.in/%7Enarsimha_raju/
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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: ALgo help pls
Using hashing we can't do it? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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: algo for counting integers in a stream
@divya This is a widely known issue and lot of work has been done on it. See http://www.americanscientist.org/issues/pub/the-britney-spears-problem/1 for a discussion on this and more. On Jul 3, 10:03 am, divya sweetdivya@gmail.com wrote: You are provided with a stream of integers, design a data structure to store the number of occurrences of each integer. If the set of integers is known, then the problem becomes simple. If the set of integers is known: Have a hash of the known set of integers. Parse the input stream, hash it to get the key and increase its corresponding value. how to do efficiently if the set is not known? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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: Algo to find all the possible subsets in a set
tell us the logic... ankur --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] Re: Algo to find all the possible subsets in a set
If the set has fewer elements than an integer has bits, just count
from 1 to MAXINT. If bit i is 0, the element is not in the set, and if
bit i is 1, the element is in the set.
Dave
On Aug 26, 2:20 pm, AKS abhijeet.k.s...@gmail.com wrote:
Hello fellas,
i am lookin for an algorithm to find all the possible subsets in a
given set
So, if the Set is say, A={a,b,c} omit the null set
o/p: --- {a} {b} {c} {a,b} {b,c} {a,c} {a,b,c} omit the
null set
regards,
Abhijeet
--~--~-~--~~~---~--~~
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
-~--~~~~--~~--~--~---
[algogeeks] Re: Algo to find all the possible subsets in a set
Please see http://geeksforgeeks.org/?p=588
Well explained and coded solution.
On Thu, Aug 27, 2009 at 5:28 AM, Dave dave_and_da...@juno.com wrote:
If the set has fewer elements than an integer has bits, just count
from 1 to MAXINT. If bit i is 0, the element is not in the set, and if
bit i is 1, the element is in the set.
Dave
On Aug 26, 2:20 pm, AKS abhijeet.k.s...@gmail.com wrote:
Hello fellas,
i am lookin for an algorithm to find all the possible subsets in a
given set
So, if the Set is say, A={a,b,c} omit the null set
o/p: --- {a} {b} {c} {a,b} {b,c} {a,c} {a,b,c} omit the
null set
regards,
Abhijeet
--~--~-~--~~~---~--~~
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
-~--~~~~--~~--~--~---
[algogeeks] Re: Algo to find all the possible subsets in a set
The following will generate an output like this - 0
0 1
0 1 2
0 1 2 3
0 1 3
0 2 3
0 3
1
1 2
1 2 3
1 3
2
2 3
3
using these indices you can generate from any given set.
class SetGenerator
{
public:
SetGenerator(size_t length)
: LENGTH(length)
{ indices.reserve(length);}
const vectorsize_t generate_set()
{
if ( indices.empty() )
indices.push_back(0);
else if ( (LENGTH - 1) == indices[0])
{
indices.clear();
}
else
{
if ( LENGTH != (indices.back() + 1) )
{
indices.push_back(indices.back() + 1);
}
else
{
if ( (LENGTH-1) == ++indices.at(indices.size() - 2) || 2
== indices.size() )
indices.pop_back();
}
}
return indices;
}
private:
const size_tLENGTH;
vectorsize_t indices;
};
...
SetGenerator gen(5);
do
{
const vectorsize_t idxs = gen.generate_set();
if ( idxs.empty() )
break;
copy(idxs.begin(), idxs.end(), ostream_iteratorsize_t(cout, ));
cout'\n';
} while( true );
On Wed, Aug 26, 2009 at 12:20 PM, AKS abhijeet.k.s...@gmail.com wrote:
Hello fellas,
i am lookin for an algorithm to find all the possible subsets in a
given set
So, if the Set is say, A={a,b,c} omit the null set
o/p: --- {a} {b} {c} {a,b} {b,c} {a,c} {a,b,c} omit the
null set
regards,
Abhijeet
--
Yesterday is History.
Tomorrow is a Mystery.
Today is a Gift! That is why it is called the Present :).
http://sites.google.com/site/ramaswamyr
--~--~-~--~~~---~--~~
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
-~--~~~~--~~--~--~---
[algogeeks] Re: Algo to find all the possible subsets in a set
can i have the algorithm only in plain simple english rather than havin the whole code ??? it ll be really helpful if u tell me the logic --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] Re: Algo to find all the possible subsets in a set
You just gt generate this pattern of indices into the set - 0 0 1 0 1 2 0 1 2 3 0 1 3 0 2 3 0 3 1 1 2 1 2 3 1 3 2 2 3 3 just figure out the conditions to generate the above yourself ... and you'll figure out what the code does On Wed, Aug 26, 2009 at 10:01 PM, Abhijeet Kumar abhijeet.k.s...@gmail.comwrote: can i have the algorithm only in plain simple english rather than havin the whole code ??? it ll be really helpful if u tell me the logic -- Yesterday is History. Tomorrow is a Mystery. Today is a Gift! That is why it is called the Present :). http://sites.google.com/site/ramaswamyr --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] Re: Algo Question
This can be formulated as a 0-1 integer programming problem.
Define the matrix A such that a(i,j) = 1 if machine i is connected to
machine j, and = 0 otherwise (with the interpretation that every
machine is connected to itself).
Let x be a vector whose elements are in the set {0, 1}, where x(j) = 0
means that machine j is not an administrative machine and x(j) = 1
means that it is.
Then the 0-1 integer programming problem is:
detemine x to
minimize sum{ x(i) }
subject to [A*x](i) = 1.
The inequality above means that the i'th component of the matrix-
vector product A*x is = 1. It simply means that machine i is
connected to at least one administrative machine.
You should be able to find software or algorithms to solve 0-1 integer
programming problems.
Dave
On Jul 1, 7:47 am, priya k priya.annau...@gmail.com wrote:
we have many machines connected to each other. However, administering these
machines is a great hassle. That is because a machine can be administered
only by a machine connected directly to it (a machine that is an
administrator can administrator itself). So, the system administrators have
decided to convert some of the machines in the network to administrative
machines. However, the cost of converting a machine to an administrative
machine is $100, which is pretty high. So, the system administrators
approach you to help them out.
You will be given a list of machines which have a direct connection between
them. You need to compute the least cost that the company needs to incur so
that every machine in the final network is administrable by at least one of
the machines converted to administrative machines.
You are given as input the node pairs which are connected to each other. You
are supposed to find the least amount of money in dollars that you need to
spend so that every machine in the network is administered by at least one
administrator machine.
--~--~-~--~~~---~--~~
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
-~--~~~~--~~--~--~---
[algogeeks] Re: Algo Question
The problem seems to be minimum dominating set problem (which is NP-complete
i think). But since the number of nodes will be =26, it can be solved by
some intelligent brute force.
Something like this might work:
Take all subsets of the given nodes. Iteratively keep increasing the size of
the subsets. i.e., take all 1-size subsets of nodes .. then take all subsets
of size 2, then 3 and so on ... Now see if the current subset of the given
node set forms the dominating set. If yes then problem is solved and the
solution can be printed.
On Wed, Jul 1, 2009 at 9:24 PM, Dave dave_and_da...@juno.com wrote:
This can be formulated as a 0-1 integer programming problem.
Define the matrix A such that a(i,j) = 1 if machine i is connected to
machine j, and = 0 otherwise (with the interpretation that every
machine is connected to itself).
Let x be a vector whose elements are in the set {0, 1}, where x(j) = 0
means that machine j is not an administrative machine and x(j) = 1
means that it is.
Then the 0-1 integer programming problem is:
detemine x to
minimize sum{ x(i) }
subject to [A*x](i) = 1.
The inequality above means that the i'th component of the matrix-
vector product A*x is = 1. It simply means that machine i is
connected to at least one administrative machine.
You should be able to find software or algorithms to solve 0-1 integer
programming problems.
Dave
On Jul 1, 7:47 am, priya k priya.annau...@gmail.com wrote:
we have many machines connected to each other. However, administering
these
machines is a great hassle. That is because a machine can be administered
only by a machine connected directly to it (a machine that is an
administrator can administrator itself). So, the system administrators
have
decided to convert some of the machines in the network to administrative
machines. However, the cost of converting a machine to an administrative
machine is $100, which is pretty high. So, the system administrators
approach you to help them out.
You will be given a list of machines which have a direct connection
between
them. You need to compute the least cost that the company needs to incur
so
that every machine in the final network is administrable by at least one
of
the machines converted to administrative machines.
You are given as input the node pairs which are connected to each other.
You
are supposed to find the least amount of money in dollars that you need
to
spend so that every machine in the network is administered by at least
one
administrator machine.
--~--~-~--~~~---~--~~
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
-~--~~~~--~~--~--~---
[algogeeks] Re: algo for finding the union of two sets ...
Yup there are . Refer horowitz sahani book on algorithms called fundamentals of algorithms On Mon, Jun 23, 2008 at 4:36 PM, zee [EMAIL PROTECTED] wrote: do we have an algo for finding the union of two sets ??? data structure suitable for set operations -- Ciao, Ajinkya --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: algo for finding the union of two sets ...
On Jun 23, 12:36 pm, zee [EMAIL PROTECTED] wrote: do we have an algo for finding the union of two sets ??? Lots of them. data structure suitable for set operations Depends. The only real constraint in the definition of a set is that the elements are unique. So the choice of structure depends on how much you know about what the sets consists of and what kind of operations you plan to use on the sets. For example, if you've got a very limited number of elements that can be in the set, you can get away with a bit array, and a union can be done with a bitwise or. Geoff --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: algo.....
Can you be a little more specific? (constraint satisfaction describes a class of problems). You can find some information on simulated annealing on Google (that is, if you actually try). On Feb 7, 4:50 am, monty 1987 [EMAIL PROTECTED] wrote: Hi Can anyone tell me about constraint satisfaying algorithm(simulated annealing)?? --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Algo.. phone book
just store list of phone number as leaf in trie. What abt collisions in Trie?? Like if same name then??? Still don't understand why you all so eager to use Trie, in my point of view this is improper data structure in this case. --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Algo.. phone book
HI, The phone numbers can be stored at the leaf nodes as said by andrey. And why will there be a collission? All the names stored has to unique. If the names are not unique then we must have an extra pointer to the leaf node, which stores the list of phone numbers, so that the multiple entried are stored! The leaf node must have an extra pointer, which points to the phone numbers.. This can be similar to that of a single linked list. Sorted arrays and binary trees are not as much suitable as compared to trie. There is a possibility of splayness in a binary tree. And also dont only look for the complexity in terms of big oh notation. Also look for the number or iterations or exact number of iterations in case of a search for sorting. For ex, 2n and 3n both are O(n) but we might always wish to prefer 2n than 3n comparisons. Compalies like google appreciate if the complexity is of 2n rather than 3n. On Nov 10, 2007 1:42 PM, Andrey [EMAIL PROTECTED] wrote: just store list of phone number as leaf in trie. What abt collisions in Trie?? Like if same name then??? Still don't understand why you all so eager to use Trie, in my point of view this is improper data structure in this case. --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Algo.. phone book
I was asked the same question in my google interview!! The best solution for this is to use the TRIE data structure!! Google TRIE data structure for more details. It also gives an optimized search complexity. On Nov 8, 2007 11:40 AM, Rajat Gogri [EMAIL PROTECTED] wrote: If you have to implement a phone book of 10 millin people in NYC, what data structure would you use and why ? Show the implementation if HashTable or Binary Trees? Thanks, Raj --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Algo.. phone book
I thought about trie first but then I've change my mind and decided that I'd rater use a simple binary tree or even an sorted array. As we have quite limited set of first names and surnames we can easily index them i.e. store them in sorted array and use an index in the array indead of the entire name/surname (the array like this can also be easily compressed). Then we store pairs (surname_index, name_index) in sorted array and perform binary search by request. The complexity will be. log(S) - to find the index of surname where S is number of different surnames + log(N) - to find the index of name where N is number of different names + log(10 000 000) - to find pair (surname_index, name_index) The memory consumption estimate is clear. Can you estimate complexity and memory consmption of trie? That would be interesting!!! On Nov 9, 2:59 pm, Varun S V [EMAIL PROTECTED] wrote: I was asked the same question in my google interview!! The best solution for this is to use the TRIE data structure!! Google TRIE data structure for more details. It also gives an optimized search complexity. On Nov 8, 2007 11:40 AM, Rajat Gogri [EMAIL PROTECTED] wrote: If you have to implement a phone book of 10 millin people in NYC, what data structure would you use and why ? Show the implementation if HashTable or Binary Trees? Thanks, Raj --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Algo.. phone book
How about using a Red-Black tree ? On 11/9/07, Andrey [EMAIL PROTECTED] wrote: I thought about trie first but then I've change my mind and decided that I'd rater use a simple binary tree or even an sorted array. As we have quite limited set of first names and surnames we can easily index them i.e. store them in sorted array and use an index in the array indead of the entire name/surname (the array like this can also be easily compressed). Then we store pairs (surname_index, name_index) in sorted array and perform binary search by request. The complexity will be. log(S) - to find the index of surname where S is number of different surnames + log(N) - to find the index of name where N is number of different names + log(10 000 000) - to find pair (surname_index, name_index) The memory consumption estimate is clear. Can you estimate complexity and memory consmption of trie? That would be interesting!!! On Nov 9, 2:59 pm, Varun S V [EMAIL PROTECTED] wrote: I was asked the same question in my google interview!! The best solution for this is to use the TRIE data structure!! Google TRIE data structure for more details. It also gives an optimized search complexity. On Nov 8, 2007 11:40 AM, Rajat Gogri [EMAIL PROTECTED] wrote: If you have to implement a phone book of 10 millin people in NYC, what data structure would you use and why ? Show the implementation if HashTable or Binary Trees? Thanks, Raj -- Ciao, Ajinkya --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Algo.. phone book
No reasons, the structure is static so sorted array is the fastest way. Don't know how about trie, it's hard to estimate... On 9 нояб, 18:16, Ajinkya Kale [EMAIL PROTECTED] wrote: How about using a Red-Black tree ? On 11/9/07, Andrey [EMAIL PROTECTED] wrote: I thought about trie first but then I've change my mind and decided that I'd rater use a simple binary tree or even an sorted array. As we have quite limited set of first names and surnames we can easily index them i.e. store them in sorted array and use an index in the array indead of the entire name/surname (the array like this can also be easily compressed). Then we store pairs (surname_index, name_index) in sorted array and perform binary search by request. The complexity will be. log(S) - to find the index of surname where S is number of different surnames + log(N) - to find the index of name where N is number of different names + log(10 000 000) - to find pair (surname_index, name_index) The memory consumption estimate is clear. Can you estimate complexity and memory consmption of trie? That would be interesting!!! On Nov 9, 2:59 pm, Varun S V [EMAIL PROTECTED] wrote: I was asked the same question in my google interview!! The best solution for this is to use the TRIE data structure!! Google TRIE data structure for more details. It also gives an optimized search complexity. On Nov 8, 2007 11:40 AM, Rajat Gogri [EMAIL PROTECTED] wrote: If you have to implement a phone book of 10 millin people in NYC, what data structure would you use and why ? Show the implementation if HashTable or Binary Trees? Thanks, Raj -- Ciao, Ajinkya --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Algo.. phone book
What abt collisions in Trie?? Like if same name then??? On Nov 9, 2007 7:49 AM, Andrey [EMAIL PROTECTED] wrote: I thought about trie first but then I've change my mind and decided that I'd rater use a simple binary tree or even an sorted array. As we have quite limited set of first names and surnames we can easily index them i.e. store them in sorted array and use an index in the array indead of the entire name/surname (the array like this can also be easily compressed). Then we store pairs (surname_index, name_index) in sorted array and perform binary search by request. The complexity will be. log(S) - to find the index of surname where S is number of different surnames + log(N) - to find the index of name where N is number of different names + log(10 000 000) - to find pair (surname_index, name_index) The memory consumption estimate is clear. Can you estimate complexity and memory consmption of trie? That would be interesting!!! On Nov 9, 2:59 pm, Varun S V [EMAIL PROTECTED] wrote: I was asked the same question in my google interview!! The best solution for this is to use the TRIE data structure!! Google TRIE data structure for more details. It also gives an optimized search complexity. On Nov 8, 2007 11:40 AM, Rajat Gogri [EMAIL PROTECTED] wrote: If you have to implement a phone book of 10 millin people in NYC, what data structure would you use and why ? Show the implementation if HashTable or Binary Trees? Thanks, Raj --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Algo to get GCD of given numbers
int gcd(int a, int b) { return (b==0 ? a : gcd(b,a%b)); }
http://en.wikipedia.org/wiki/Euclidean_algorithm
On 8/17/07, Muntasir Azam Khan [EMAIL PROTECTED] wrote:
On Aug 17, 6:53 pm, anshu [EMAIL PROTECTED] wrote:
Do you think sorting would help here?
I mean, arranging the numbers in descending order and then computing
progressively.
Why I am suggesting sorting is that considering an array like the
following
2, 80, 36, 70, 150, 300
It would be pretty expensive to do the euclidean algo first with
gcd(2, 80 ) = 2 --- O(40)
gcd(2, 36 )= 2 -- O(18)
gcd(2 , 70) =
gcd(2, 150)
vs
gcd(150, 300) = 150
gcd(70,150) = 10
etc..
I don't know, but this is easily found by running tests on sorted vs
unsorted input.
I don't think this really matters much, unless you are using really
big numbers, and even then I am not sure.
Muntasir
--~--~-~--~~~---~--~~
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 [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---
[algogeeks] Re: Algo to get GCD of given numbers
On Aug 17, 6:53 pm, anshu [EMAIL PROTECTED] wrote: Do you think sorting would help here? I mean, arranging the numbers in descending order and then computing progressively. Why I am suggesting sorting is that considering an array like the following 2, 80, 36, 70, 150, 300 It would be pretty expensive to do the euclidean algo first with gcd(2, 80 ) = 2 --- O(40) gcd(2, 36 )= 2 -- O(18) gcd(2 , 70) = gcd(2, 150) vs gcd(150, 300) = 150 gcd(70,150) = 10 etc.. I don't know, but this is easily found by running tests on sorted vs unsorted input. I don't think this really matters much, unless you are using really big numbers, and even then I am not sure. Muntasir --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Algo to get GCD of given numbers
Google is your friend. - Original Message - From: sumedh sakdeo To: algogeeks@googlegroups.com Sent: Sunday, August 12, 2007 9:37 PM Subject: [algogeeks] Algo to get GCD of given numbers Write algorithm for finding the GCD of given numbers. --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Algo to get GCD of given numbers
On Aug 12, 9:54 pm, sumedh sakdeo [EMAIL PROTECTED] wrote: well i have made this ... ·Find minimum of n numbers. ·Run loop from i=1 to minimum number ·Check if i is divisible by all the three numbers ·If yes, gcd=i ·Continue the step till you get the gcd which is less than or equal to minimum of three numbers anyone can do it less complexity? On 8/12/07, Muntasir Azam Khan [EMAIL PROTECTED] wrote: Google is your friend. - Original Message - *From:* sumedh sakdeo [EMAIL PROTECTED] *To:* algogeeks@googlegroups.com *Sent:* Sunday, August 12, 2007 9:37 PM *Subject:* [algogeeks] Algo to get GCD of given numbers Write algorithm for finding the GCD of given numbers. Try this http://en.wikipedia.org/wiki/Euclidean_algorithm Once you can find the gcd of two numbers, you can easily extend this to get the GCD of n numbers. gcd(a,b,c )= gcd ( a, gcd( b, c ) ) Hope this helps, Muntasir --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: algo to schedule a league
On Aug 11, 9:23 am, pushpen singh [EMAIL PROTECTED] wrote:
I have to schedule a league involving 16 teams.
In the league all teams are going to play against all other teams.
so there are going to be 120 matches all together.
The leagues is divided into 15 phases of 8 matches each .
In the one phase all teams are going to play one match each.
so for 16 teams we will have 8 matches with the condition
that if two teams have already played against each other
in a previous phase they will not play against each other again.
Please suggest some efficient algorithm for scheduling this.
Also which team plays against which other team is decided
randomly.
A simple rotation scheme is probably good enough for this problem. If
you start with A plays I; B plays J; ... H plays P, then just hold A
in the same place and rotate all the others. It's not very hard to
prove this works.
Here it is in C:
#include stdio.h
#define N 8
int main(void)
{
char matches[2][N] = {
ABCDEFGH,
IJKLMNOP
};
int phase, i, t;
for (phase = 0; phase 2*N - 1; phase++) {
printf(\nphase %2d:, phase + 1);
for (i = 0; i N; i++)
printf( [%c-%c], matches[0][i], matches[1][i]);
t = matches[1][0];
matches[1][0] = matches[0][1];
for (i = 1; i N - 1; i++)
matches[0][i] = matches[0][i + 1];
matches[0][N - 1] = matches[1][N - 1];
for (i = N - 1; i 1; i--)
matches[1][i] = matches[1][i - 1];
matches[1][1] = t;
}
return 0;
}
Output:
phase 1: [A-I] [B-J] [C-K] [D-L] [E-M] [F-N] [G-O] [H-P]
phase 2: [A-B] [C-I] [D-J] [E-K] [F-L] [G-M] [H-N] [P-O]
phase 3: [A-C] [D-B] [E-I] [F-J] [G-K] [H-L] [P-M] [O-N]
phase 4: [A-D] [E-C] [F-B] [G-I] [H-J] [P-K] [O-L] [N-M]
phase 5: [A-E] [F-D] [G-C] [H-B] [P-I] [O-J] [N-K] [M-L]
phase 6: [A-F] [G-E] [H-D] [P-C] [O-B] [N-I] [M-J] [L-K]
phase 7: [A-G] [H-F] [P-E] [O-D] [N-C] [M-B] [L-I] [K-J]
phase 8: [A-H] [P-G] [O-F] [N-E] [M-D] [L-C] [K-B] [J-I]
phase 9: [A-P] [O-H] [N-G] [M-F] [L-E] [K-D] [J-C] [I-B]
phase 10: [A-O] [N-P] [M-H] [L-G] [K-F] [J-E] [I-D] [B-C]
phase 11: [A-N] [M-O] [L-P] [K-H] [J-G] [I-F] [B-E] [C-D]
phase 12: [A-M] [L-N] [K-O] [J-P] [I-H] [B-G] [C-F] [D-E]
phase 13: [A-L] [K-M] [J-N] [I-O] [B-P] [C-H] [D-G] [E-F]
phase 14: [A-K] [J-L] [I-M] [B-N] [C-O] [D-P] [E-H] [F-G]
phase 15: [A-J] [I-K] [B-L] [C-M] [D-N] [E-O] [F-P] [G-H]
--~--~-~--~~~---~--~~
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 [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---
[algogeeks] Re: algo problem
Linear time isn't enough. Think about what the term 'subsequence' means. Muntasir - Original Message - From: Hari Nathan To: algogeeks@googlegroups.com Sent: Tuesday, April 17, 2007 9:52 AM Subject: [algogeeks] Re: algo problem Isn't linear time enough? Go form the begining to the end, whenever a[i] a[i+1] you a new subsequence. You can keep track of where each one ends and then pick the longest. On 4/15/07, Sachin [EMAIL PROTECTED] wrote: http://en.wikipedia.org/wiki/Longest_increasing_subsequence_problem This link depicts an algorithm, which is O(nlogn) algo. Approach: dynamic programming. On 4/15/07, Daniel Bastidas [EMAIL PROTECTED] wrote: if you can find the programming challenge book, there is a Longest Increasing Subsequence algorithm On 4/14/07, Muntasir Azam Khan [EMAIL PROTECTED] wrote: This is a very common problem. Search for 'Longest Increasing Subsequence' at Google. Muntasir - Original Message - *From:* monty 1987 [EMAIL PROTECTED] *To:* algogeeks@googlegroups.com *Sent:* Saturday, April 14, 2007 5:52 PM *Subject:* [algogeeks] algo problem My problem is to find out longest subsequence of integers in increasing order in an array of integers. If any one have solution tell it to me. --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: algo problem
Isn't linear time enough? Go form the begining to the end, whenever a[i] a[i+1] you a new subsequence. You can keep track of where each one ends and then pick the longest. On 4/15/07, Sachin [EMAIL PROTECTED] wrote: http://en.wikipedia.org/wiki/Longest_increasing_subsequence_problem This link depicts an algorithm, which is O(nlogn) algo. Approach: dynamic programming. On 4/15/07, Daniel Bastidas [EMAIL PROTECTED] wrote: if you can find the programming challenge book, there is a Longest Increasing Subsequence algorithm On 4/14/07, Muntasir Azam Khan [EMAIL PROTECTED] wrote: This is a very common problem. Search for 'Longest Increasing Subsequence' at Google. Muntasir - Original Message - *From:* monty 1987 [EMAIL PROTECTED] *To:* algogeeks@googlegroups.com *Sent:* Saturday, April 14, 2007 5:52 PM *Subject:* [algogeeks] algo problem My problem is to find out longest subsequence of integers in increasing order in an array of integers. If any one have solution tell it to me. --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: algo problem
http://en.wikipedia.org/wiki/Longest_increasing_subsequence_problem This link depicts an algorithm, which is O(nlogn) algo. Approach: dynamic programming. On 4/15/07, Daniel Bastidas [EMAIL PROTECTED] wrote: if you can find the programming challenge book, there is a Longest Increasing Subsequence algorithm On 4/14/07, Muntasir Azam Khan [EMAIL PROTECTED] wrote: This is a very common problem. Search for 'Longest Increasing Subsequence' at Google. Muntasir - Original Message - *From:* monty 1987 [EMAIL PROTECTED] *To:* algogeeks@googlegroups.com *Sent:* Saturday, April 14, 2007 5:52 PM *Subject:* [algogeeks] algo problem My problem is to find out longest subsequence of integers in increasing order in an array of integers. If any one have solution tell it to me. --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: algo problem
This is a very common problem. Search for 'Longest Increasing Subsequence' at Google. Muntasir - Original Message - From: monty 1987 To: [EMAIL PROTECTED] Sent: Saturday, April 14, 2007 5:52 PM Subject: [algogeeks] algo problem My problem is to find out longest subsequence of integers in increasing order in an array of integers. If any one have solution tell it to me. --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to [EMAIL PROTECTED] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: algo to find common parts in strings?
burrows wheeler transform, find runs, find locations from suffix array --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups-beta.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: algo to find common parts in strings?
This is what grammar-based compression algorithms do. You should be
able to find many by searching for those words.
Flo wrote:
I am searching an algorithm that can find common parts within a set of
given strings. For example given the four strings
MinXBla MinYBla MinPhiBla MinThetaBla
The algorithm should see that the strings start with Min, then comes a
variable string, and then they end with Bla. An extra would be if it
would also return the list of variable strings, here {X,Y,Phi,Theta}.
What if I add another level? For example given the 8 strings:
fMinXBla fMinYBla fMinPhiBla fMinThetaBla
nMinXBla nMinYBla nMinPhiBla nMinThetaBla
Where we have almost the same situation as before, however a variable
string is prepended to each string. The list of variables is now 2
dimensional {f,n}{X,Y,Phi,Theta}.
I am happy if somebody knows the name such an algorithm, if it exists,
so I can look up the details myself.
Greetings
Flo
--~--~-~--~~~---~--~~
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 [EMAIL PROTECTED]
For more options, visit this group at
http://groups-beta.google.com/group/algogeeks
-~--~~~~--~~--~--~---
[algogeeks] Re: algo to find common parts in strings?
What if this happens?
MinPhiBla MinThetaBla MinZuhaBla
Should it be: {P,T,Zu}, {i,eta,a} ?
-- Flávio Santos
--~--~-~--~~~---~--~~
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 [EMAIL PROTECTED]
For more options, visit this group at
http://groups-beta.google.com/group/algogeeks
-~--~~~~--~~--~--~---
