Re: [algogeeks] Minimum Triplet Distance
On Mon, Dec 20, 2010 at 11:18 AM, Nikhil Agarwal
nikhil.bhoja...@gmail.comwrote:
I have a solution.I cant prove the correctness but by intuition I can
conclude.This is O(1) solution.
As we have 3 sorted arrays A,B,C.So only first and last element of these 3
lists will be contributing for min/max tuple.Rest elements will be varying
from that max to min.
Suppose a={-1,-1,0}
b={-1,3,7,8,10}
c={0,1,2,3,4,5}
so -1,0 of A ,-1,10 of B and 0,5 of C will be contributing .So we find all
possible 8 tuples.In this case its for (x,y,z)=(-1,-1,0) giving a tuple 1
[max(-2,-1,1)] and so on.
Find minimum of these tuples i.e. 1.That will be the answer.Solution if
O(8) equilvalent to O(1).Please provide counter if you can find.
On Mon, Dec 20, 2010 at 10:54 AM, yq Zhang zhangyunq...@gmail.com wrote:
This question is equivalent to finding the minimum window contains 3 words
in a document given the position of appearance of each word in the document
by array A, B, C. This could be solved by a typical sliding window algorithm
which is O(n).
Thanks
On Sun, Dec 19, 2010 at 9:06 PM, Saurabh Koar
saurabhkoar...@gmail.comwrote:
@yq: Plz explain your algorithm.
On 12/20/10, yq Zhang zhangyunq...@gmail.com wrote:
Are A, B, C sorted? If so, I believe there is a O(n1+n2+n3) solution
for
this question.
Thanks
On Sun, Dec 19, 2010 at 9:57 AM, Saurabh Koar
saurabhkoar...@gmail.comwrote:
You are given 3 integer arrays A, B and C of length n1, n2 and n3
respectively. All arrays are sorted. We define triplet of these 3
arrays as (x,y,z) where x is any integer from A, y from B and z from
C. We define distance of triplet as maximum difference among triplet
elements, i.e. Maximum of x – y, y – z or z – x. Write a program to
find minimum triplet distance. (means there are n1*n2*n3 number of
possible triplets are possible...among all triplets which triplet has
minimum distance...Give only distance, but not triplet elements). Your
program must be as much efficient as possible.
--
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
algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@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.
--
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.
--
Thanks Regards
Nikhil Agarwal
Senior Undergraduate
Computer Science Engineering,
National Institute Of Technology, Durgapur,India
http://tech-nikk.blogspot.com
http://beta.freshersworld.com/communities/nitd
--
Thanks Regards
Nikhil Agarwal
Senior Undergraduate
Computer Science Engineering,
National Institute Of Technology, Durgapur,India
http://tech-nikk.blogspot.com
http://beta.freshersworld.com/communities/nitd
--
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: Minimum Triplet Distance
I have a solution.I cant prove the correctness but by intuition I can
conclude.This is O(1) solution.
As we have 3 sorted arrays A,B,C.So only first and last element of
these 3 lists will be contributing for min/max tuple.Rest elements
will be varying from that max to min.
Suppose a={-1,-1,0}
b={-1,3,7,8,10}
c={0,1,2,3,4,5}
so -1,0 of A ,-1,10 of B and 0,5 of C will be contributing .So we find
all possible 8 tuples.Find minimum of these tuples.That will be the
answer.Solution if O(8) equilvalent to O(1).Please provide counter if
you can find.
On Dec 20, 11:13 am, yq Zhang zhangyunq...@gmail.com wrote:
ok. Suppose you have 3 pointers i, j, k point to the element in A, B, C
respectively. Initialize i = j =k = 0.
for each step, you will compare A[i], B[j], C[k].
if A[i] is the smallest, i++
if B[j] is the smallest, j++
if C[k] is the smallest, k++
(this assumes numbers in A,B,C are unique, you should be able to eliminate
this restriction by changing above logic a little bit.)
for each step compute the current triple distance and keep the minimum.
Thanks
On Sun, Dec 19, 2010 at 9:51 PM, Saurabh Koar saurabhkoar...@gmail.comwrote:
@yq: Heyy yq..I m not interested in what is equivalent to what and
what is not not equivalent to what..I m interested to a specific
optimized algorithm for the specific problem stated above.If u can
figure out equivalence u can also devise the algorithm for the above
problem.Nw would u please state that??or provide any link??
--
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] Minimum Triplet Distance
I have a solution.I cant prove the correctness but by intuition I can
conclude.This is O(1) solution.
As we have 3 sorted arrays A,B,C.So only first and last element of these 3
lists will be contributing for min/max tuple.Rest elements will be varying
from that max to min.
Suppose a={-1,-1,0}
b={-1,3,7,8,10}
c={0,1,2,3,4,5}
so -1,0 of A ,-1,10 of B and 0,5 of C will be contributing .So we find all
possible 8 tuples.In this case its for (x,y,z)=(-1,-1,0) giving a tuple 1
[max(-2,-1,1)] and so on.
Find minimum of these tuples i.e. 1.That will be the answer.Solution if O(8)
equilvalent to O(1).Please provide counter if you can find.
On Mon, Dec 20, 2010 at 11:43 AM, yq Zhang zhangyunq...@gmail.com wrote:
ok. Suppose you have 3 pointers i, j, k point to the element in A, B, C
respectively. Initialize i = j =k = 0.
for each step, you will compare A[i], B[j], C[k].
if A[i] is the smallest, i++
if B[j] is the smallest, j++
if C[k] is the smallest, k++
(this assumes numbers in A,B,C are unique, you should be able to eliminate
this restriction by changing above logic a little bit.)
for each step compute the current triple distance and keep the minimum.
Thanks
On Sun, Dec 19, 2010 at 9:51 PM, Saurabh Koar saurabhkoar...@gmail.comwrote:
@yq: Heyy yq..I m not interested in what is equivalent to what and
what is not not equivalent to what..I m interested to a specific
optimized algorithm for the specific problem stated above.If u can
figure out equivalence u can also devise the algorithm for the above
problem.Nw would u please state that??or provide any link??
--
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.
--
Thanks Regards
Nikhil Agarwal
Senior Undergraduate
Computer Science Engineering,
National Institute Of Technology, Durgapur,India
http://tech-nikk.blogspot.com
http://beta.freshersworld.com/communities/nitd
--
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] Minimum Triplet Distance
I have a solution.I cant prove the correctness but by intuition I can
conclude.This is O(1) solution.
As we have 3 sorted arrays A,B,C.So only first and last element of these 3
lists will be contributing for min/max tuple.Rest elements will be varying
from that max to min.
Suppose a={-1,-1,0}
b={-1,3,7,8,10}
c={0,1,2,3,4,5}
so -1,0 of A ,-1,10 of B and 0,5 of C will be contributing .So we find all
possible 8 tuples.Find minimum of these tuples.That will be the
answer.Solution if O(8) equilvalent to O(1).Please provide counter if you
can find.
On Mon, Dec 20, 2010 at 10:54 AM, yq Zhang zhangyunq...@gmail.com wrote:
This question is equivalent to finding the minimum window contains 3 words
in a document given the position of appearance of each word in the document
by array A, B, C. This could be solved by a typical sliding window algorithm
which is O(n).
Thanks
On Sun, Dec 19, 2010 at 9:06 PM, Saurabh Koar saurabhkoar...@gmail.comwrote:
@yq: Plz explain your algorithm.
On 12/20/10, yq Zhang zhangyunq...@gmail.com wrote:
Are A, B, C sorted? If so, I believe there is a O(n1+n2+n3) solution for
this question.
Thanks
On Sun, Dec 19, 2010 at 9:57 AM, Saurabh Koar
saurabhkoar...@gmail.comwrote:
You are given 3 integer arrays A, B and C of length n1, n2 and n3
respectively. All arrays are sorted. We define triplet of these 3
arrays as (x,y,z) where x is any integer from A, y from B and z from
C. We define distance of triplet as maximum difference among triplet
elements, i.e. Maximum of x – y, y – z or z – x. Write a program to
find minimum triplet distance. (means there are n1*n2*n3 number of
possible triplets are possible...among all triplets which triplet has
minimum distance...Give only distance, but not triplet elements). Your
program must be as much efficient as possible.
--
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
algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@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.
--
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.
--
Thanks Regards
Nikhil Agarwal
Senior Undergraduate
Computer Science Engineering,
National Institute Of Technology, Durgapur,India
http://tech-nikk.blogspot.com
http://beta.freshersworld.com/communities/nitd
--
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] Amazon Interview Question about Linked Lists
See inline ..
On Sat, Dec 18, 2010 at 12:09 PM, siva viknesh sivavikne...@gmail.comwrote:
Given a linked list structure where every node represents a linked list
and contains two pointers of its type:
(i) pointer to next node in the main list.
(ii) pointer to a linked list where this node is head.
Write a C function to flatten the list into a single linked list.
Eg.
If the given linked list is
1 -- 5 -- 7 -- 10
| | |
2 6 8
| |
3 9
|
4
then convert it to
1 - 2 - 3 - 4 - 5 - 6 - 9 - 7 - 8 -10
My solution - not tested :
struct node
{
int data;
struct node *fwd; //pointer to next node in the main list.
struct node *down; //pointer to a linked list where this node is head.
}*head,*temp,*temp2;
temp=head;
while(temp-fwd!=NULL)
{
temp2=temp-fwd;
while(temp-down!=NULL)
{
temp=temp-down;
}
temp-down=temp2;
// how will the code access the flattened linked list by down or by fwd ? In
this case there in no particular pointer by which the code can access the
linked list. Try to write a function to print the flattened linked list.
temp-fwd=NULL;
temp=temp2;
}
plz notify me if anything...other solutions and optimizations are welcome
--
Regards,
$iva
--
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,
Rishi Agrawal
--
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] Pythagorean triples
can we find Pythagorean triples in an unsorted array in write program so that have minimum time complexity. regards Shashank -- 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: Generic Linked list
hi,
you can find an description of same problem at
http://code-forum.blogspot.com/2010/12/generic-linked-list.html
if you find any question please leave a comment.
Regards
Priyaranjan
Software Engg
Samsung RD
On Dec 17, 12:11 pm, siva viknesh sivavikne...@gmail.com wrote:
How to implement a generic linked list??
..this is one of the frequently asked interview question
..for this we have to use void pointers
struct node
{
void *data;
struct node *link;
};
..can anybody plz give more detailed explanation and complete implementation
on this??
And what is its use??
thanks in advance...
--
Regards,
$iva
--
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: Minimum Triplet Distance
@Saurabh: This response is pretty surly for someone asking for free help. Dave On Dec 19, 11:51 pm, Saurabh Koar saurabhkoar...@gmail.com wrote: @yq: Heyy yq..I m not interested in what is equivalent to what and what is not not equivalent to what..I m interested to a specific optimized algorithm for the specific problem stated above.If u can figure out equivalence u can also devise the algorithm for the above problem.Nw would u please state that??or provide any link?? -- 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: Minimum Triplet Distance
@Dave : Ya I understand.Thank u. @yq: Sorry!! :( -- 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: subsorted array
@mohit
suppose the input array is {4,7,8,6,5,11,13,17,0,1,2,3}
1.first step of Ur algorithm gives j=2,k=9 (index of 8 and 1)
2.in the second step min and max comes out to be 5 and 13
3.now first element in A[0]..A[j-1] greater than min is 7(index 1) and first
element in
A[k+1]A[n] less than max is 1(index 9)
so final answer accordingly is A[1]..A[9]
but clearly for the given input it shud be the whole array itself not
any sub-array
please clarify if iam wrong
Thanx
On Mon, Dec 20, 2010 at 10:45 AM, awesomeandroid
priyaranjan@gmail.comwrote:
i have posted this problem along with solution to my blog check :
http://code-forum.blogspot.com/2010/12/find-minimum-length-unsorted-subarray.html
On Dec 18, 10:57 pm, snehal jain learner@gmail.com wrote:
Given an unsorted array arr[0..n-1] of size n, find the minimum length
subarray arr[s..e] such that sorting this subarray makes the whole
array sorted.
--
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.
--
bhupendra dubey
--
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: Pythagorean triples
Unless sorting the array is forbidden, sort it and then use the obvious O(n^2) algorithm. This can be done with only O(1) extra space. If O(n) extra space is available, either use it to copy and sort the original array, or use it as a hash table, again achieving O(n^2) in either case. If sorting is forbidden and using extra space is forbidden, then I doubt that any algorithm less than O(n^3) exists. Dave On Dec 20, 4:41 am, bittu shashank7andr...@gmail.com wrote: can we find Pythagorean triples in an unsorted array in write program so that have minimum time complexity. regards Shashank -- 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] Amazon Interview Question about Linked Lists
temp=head;
temp1=temp-fwd;
while(temp-fwd!=NULL)
{
temp2=temp;
while(temp2-down!=NULL)
temp2=temp2-link;
temp2-down=temp1;
temp-fwd=NULL;
temp=temp1;
temp1=temp1-fwd;
}
U can print the linked list using down pointer.Hope this will
work.Correct me if I m wrong.
--
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] Amazon Interview Question about Linked Lists
@Rishi:I think Shiva's code is also fine.U can access the list easily
by using down pointer in his code.
Because he is assigning temp-down=temp2 and then he is making temp-fwd=NULL.
On 12/20/10, Saurabh Koar saurabhkoar...@gmail.com wrote:
temp=head;
temp1=temp-fwd;
while(temp-fwd!=NULL)
{
temp2=temp;
while(temp2-down!=NULL)
temp2=temp2-link;
temp2-down=temp1;
temp-fwd=NULL;
temp=temp1;
temp1=temp1-fwd;
}
U can print the linked list using down pointer.Hope this will
work.Correct me if I m wrong.
--
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] Amazon Interview Question about Linked Lists
@Rishi:I think Shiva's code is also fine.U can access the list easily by using down pointer in his code. Because he is assigning temp-down=temp2 and then he is making temp-fwd=NULL. -- 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] fibonacci problem
Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be: 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... Find the sum of all the even-valued terms in the sequence which do not exceed four million. I'm just a beginner..plz help. -- 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: maximize result
@juver++: Do we need a 2-D array or 1-D array will be sufficient? That means if I take 1-D array then max[i] will represent the maximum value of the subexpression from 0 to i.and for i+1 we will use the result we have got in max[i].Thus we will be able to calculate max[N-1] which is the maximum value of the total expression. Please notify me if I am missing something. On 12/19/10, juver++ avpostni...@gmail.com wrote: It's a classic dynamic programming problem. min[i][j] - minimum value for the subexpression starting at i-th position and ending at j-th, max[i][j] - the same but stores maximum value. Use these value to calculate value max[0][N-1], N - size of the expression. -- 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. -- 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: spy in the city
Every question can eliminate 1 person so you can identify the spy in N-1 questions. Bhavesh On 19 December 2010 23:46, Dave dave_and_da...@juno.com wrote: Here is an algorithm: spy = 1 for i = 2 to N do if person[spy] knows person[i] then person[i] is not the spy. else if person[i] knows person[spy] then person[spy] is not the spy, set spy = i end if end for for i = 1 to spy-1 do if (person[spy] does not know person[i]) or (person[i] knows person[spy]) then there is no spy, set spy = undefined, break end if end for If there is a spy, you find him in at least 2*N - 2 questions and at most 4*N - 4 questions. Dave On Dec 19, 8:01 am, snehal jain learner@gmail.com wrote: There is a city of N people. The government learnt that some unfriendly nation planted a spy there. A spy possesses unique characteristics: he knows everybody in the city, but nobody knows him. You are a counteragent sent by the government to catch the spy. You may ask the people in the city only one question: Do you know the person X? You may ask as many people as you wish, and one person may be asked as many times as you wish. All the people, including the spy, always answer honestly. How many questions you need to find out who is the spy? -- 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: Minimum Triplet Distance
@davesaura， i dont understand what did you mean. Sent from Nexus one On Dec 20, 2010 6:13 AM, Saurabh Koar saurabhkoar...@gmail.com wrote: @Dave : Ya I understand.Thank u. @yq: Sorry!! :( -- 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: Adobe Quest....
On Sun, Dec 19, 2010 at 2:36 AM, Dave dave_and_da...@juno.com wrote: For 32-bit integers: x = ((x 16) 0X) | ((x 0X) 16); x = ((x 8) 0X00FF00FF) | ((x 0X00FF00FF) 8); x = ((x 4) 0X0F0F0F0F) | ((x 0X0F0F0F0F) 4); x = ((x 2) 0X) | ((x 0X) 2); x = ((x 1) 0X) | ((x 0X) 1); - Can U please explain the logic of this code ? x is now the binary reversal of its original value. Dave On Dec 18, 1:28 pm, Ankur Khurana ankur.kkhur...@gmail.com wrote: you mean reverse or make 1 to 0 or 0 to 1 ? On Sun, Dec 19, 2010 at 12:52 AM, bittu shashank7andr...@gmail.com wrote: Write an Efficient C Program to Reverse Bits of a Number -- 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 athttp:// groups.google.com/group/algogeeks?hl=en.- 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 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. -- Pratik Kathalkar CoEP BTech IT 8149198343 -- 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: maximize result
Keep 2D arrray. For each segment (i, j) calculate min and max value for the subexpression. To do this, iterate k over (i, j), check operation at k-th position and choose the best one. -- 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: fibonacci problem
What is the problem you encountered? Do you need code? -- 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: Adobe Quest....
@Pratik: The first line swaps the leftmost 16 bits with the rightmost 16 bits. The second line swaps all adjacent pairs of 8-bit quantities. The third line swaps all adjacent pairs of 4-bit quantities. Etc. Dave On Dec 20, 11:29 am, Pratik Kathalkar dancewithpra...@gmail.com wrote: On Sun, Dec 19, 2010 at 2:36 AM, Dave dave_and_da...@juno.com wrote: For 32-bit integers: x = ((x 16) 0X) | ((x 0X) 16); x = ((x 8) 0X00FF00FF) | ((x 0X00FF00FF) 8); x = ((x 4) 0X0F0F0F0F) | ((x 0X0F0F0F0F) 4); x = ((x 2) 0X) | ((x 0X) 2); x = ((x 1) 0X) | ((x 0X) 1); - Can U please explain the logic of this code ? x is now the binary reversal of its original value. Dave On Dec 18, 1:28 pm, Ankur Khurana ankur.kkhur...@gmail.com wrote: you mean reverse or make 1 to 0 or 0 to 1 ? On Sun, Dec 19, 2010 at 12:52 AM, bittu shashank7andr...@gmail.com wrote: Write an Efficient C Program to Reverse Bits of a Number -- 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 athttp:// groups.google.com/group/algogeeks?hl=en.- 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 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. -- Pratik Kathalkar CoEP BTech IT 8149198343- 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 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: fibonacci problem
@Shalini: You can find a table of Fibonacci numbers at http://en.wikipedia.org/wiki/Fibonacci_number#List_of_Fibonacci_numbers. You will notice that every third number in the sequence is even, and that there are only 11 even ones less than 4 million. So grab some paper and a pencil or your calculator and add them up. Dave On Dec 20, 9:06 am, Shalini Sah shalinisah.luv4cod...@gmail.com wrote: Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be: 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... Find the sum of all the even-valued terms in the sequence which do not exceed four million. I'm just a beginner..plz help. -- 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: maximize result
@Pranav - Your greedy solution fails. Sample test case - 7*0+0*7+7 :) DP is the way to go for this. -Swapnil -- 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: Minimum Triplet Distance
@Nikhil - Not sure on what you mean by O(8). And O(1) doesn't work anyway. -Swapnil -- 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: subsorted array
simple and nice! n log n time... I however believe there's a way to get the solution in O(n) time... On Dec 19, 6:45 am, Ankur Khurana ankur.kkhur...@gmail.com wrote: how about sorting the array in an auxillary array first. then compare the elements in sorted and un sorted array. the first elements to differ from start and end in unsorted array constitute the sub array we are finding. i dont know this solution seems to easy , it might be wrong. Any comments ? On Sun, Dec 19, 2010 at 8:03 PM, Ankur Murarka ankur.murarka@gmail.com wrote: Doesnt the time complexity seem to be a li'l large?? Looks like its taking exponential time... On Sun, Dec 19, 2010 at 5:01 PM, mohit ranjan shoonya.mo...@gmail.com wrote: Let A[0..n] be the array Step 1: Start from A[0] and find out the first element, beyond which array in not sorted, let's call it A[j] Step 2: Start from A[n], move backward and find first element beyond which array in not sorted, let's call it A[k] so we have A[0]A[j].A[k]A[n] -- -- sorted sorted now scan A[j] to A[k], and find any element that is smaller than any number in A[0]-A[j], if any element is found, mark it as new j similarly scan A[j]-A[k] and find any element that is larger than any number in A[k]-A[n], if any element is found, mark it as new k final j and k are the answer... Mohit On Sun, Dec 19, 2010 at 2:32 AM, Dan dant...@aol.com wrote: On Dec 18, 9:57 am, snehal jain learner@gmail.com wrote: Given an unsorted array arr[0..n-1] of size n, find the minimum length subarray arr[s..e] such that sorting this subarray makes the whole array sorted. Sounds like a simple homework problem 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 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. -- 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. -- 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. -- 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: subsorted array
@Snehal - Please avoid posting problems that have been solved somewhere else already. That decreases the value of this group. More people will be active here if we see new problems. Hope you get the point, no offence intended. -Swapnil -- 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: Minimum Triplet Distance
@yq: Can u plzz inform what was ur approach/logic while deriving the condition that index will be increased of that array which contains minimum of three elements to get the desired ans? It will be very helpful.Thanks in advance. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to 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: What can be done in c but not c++?
class is keyword in C++ but not in C.
void main()
{
int class =0;
return;
}
On Dec 17, 2:35 am, siva viknesh sivavikne...@gmail.com wrote:
We can assign any type of pointer to void pointer without cast in c but not
in c++.
Declare variable names that are keywords in C++ but not C.
...if anybody knows more do update in this thread.:).
--
Regards,
$iva
--
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] ankit sablok wants to chat
--- ankit sablok wants to stay in better touch using some of Google's coolest new products. If you already have Gmail or Google Talk, visit: http://mail.google.com/mail/b-a96b6b68ce-69e1b8743a-fR2v0p_gvlyJsBnTMH_Mq01Kcnk You'll need to click this link to be able to chat with ankit sablok. To get Gmail - a free email account from Google with over 2,800 megabytes of storage - and chat with ankit sablok, visit: http://mail.google.com/mail/a-a96b6b68ce-69e1b8743a-fR2v0p_gvlyJsBnTMH_Mq01Kcnk Gmail offers: - Instant messaging right inside Gmail - Powerful spam protection - Built-in search for finding your messages and a helpful way of organizing emails into conversations - No pop-up ads or untargeted banners - just text ads and related information that are relevant to the content of your messages All this, and its yours for free. But wait, there's more! By opening a Gmail account, you also get access to Google Talk, Google's instant messaging service: http://www.google.com/talk/ Google Talk offers: - Web-based chat that you can use anywhere, without a download - A contact list that's synchronized with your Gmail account - Free, high quality PC-to-PC voice calls when you download the Google Talk client We're working hard to add new features and make improvements, so we might also ask for your comments and suggestions periodically. We appreciate your help in making our products even better! Thanks, The Google Team To learn more about Gmail and Google Talk, visit: http://mail.google.com/mail/help/about.html http://www.google.com/talk/about.html (If clicking the URLs in this message does not work, copy and paste them into the address bar of your browser). -- 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: celebrity twitters
It can be thought of as a binary tree Assume n=8. At first level all 8 people are present, i.e leaves of the tree. 1 asks 2 if 2 knows 1, 3 asks 4 if 4 knows 3 etc .. If 2 knows 1, then 1 goes to next level, else 2. Thus n/2 questions are asked at level 1 and the height will be log(n). The total questions asked will n. 1 2 3 4 5 6 7 8 145 8 1 5 8 5 8 8 On Dec 19, 4:25 pm, Senthilnathan Maadasamy senthilnathan.maadas...@gmail.com wrote: Note that there cannot be more than one celebrity in the group. Here is an O(n) solution: Choose a random candidate x as a possible celebrity. Let S be the set of remaining n-1 candidates. While (S is not empty) Remove another candidate y from S and ask if y follows x. If y follows x, y is not a celebrity. If y does not follow x, x is not a celebrity and hence let y be the new x. After this, we are left with only one possible celebrity x. We still need to verify if x is actually a celebrity. Check if the remaining n-1 candidates follow x. If yes, x is a celebrity. If no, there is no celebrity in the group. -- 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] bits groups
How do you count the number of zero group bits in a number? group bits is any consecutive zero or one bits, for example, 2 is represented as 010 has two zero bits groups the least significant bit and the group starts after one. Also, I am in a bad need for algorithms on bits manipulation if any one has a reference, please share -- 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: maximize result
@juver++: gt it.thanks -- 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] Adobe Interview Question
you can't find...
are these mutually exclusive or independent? think twice, draw venn diag
there would be cases when AB as well as CD, in such cases foo2 will NOT be
called
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Wed, Dec 15, 2010 at 12:36 AM, bittu shashank7andr...@gmail.com wrote:
void foo1()
{
if(AB)
Then {_/* */}
else
if(CD)
then foo2()
}
How many time foo2() would get called given
AB 25% of the times and CD 75% of the times and foo1() is called
5000 times
although i had diff...solution..but i wants to confirm wid others..so
hav a look
Regards
Shashank Mani
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 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] Adobe Interview Question
I second Ashish,
These two events are independent
On Tue, Dec 21, 2010 at 10:57 AM, Ashish Goel ashg...@gmail.com wrote:
you can't find...
are these mutually exclusive or independent? think twice, draw venn diag
there would be cases when AB as well as CD, in such cases foo2 will NOT
be called
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Wed, Dec 15, 2010 at 12:36 AM, bittu shashank7andr...@gmail.comwrote:
void foo1()
{
if(AB)
Then {_/* */}
else
if(CD)
then foo2()
}
How many time foo2() would get called given
AB 25% of the times and CD 75% of the times and foo1() is called
5000 times
although i had diff...solution..but i wants to confirm wid others..so
hav a look
Regards
Shashank Mani
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 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.
--
Cheers
Naveen Kumar
--
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] Adobe Interview Question
Yeah, the events are independent .. But the statements (if/then) are
not independent !! The second else executes when the first if fails.
Utkarsh Srivastava ,
Final Year, Under Grad Student
B.Tech, Computer Science Engineering
Indian Institute of Technology, Guwahati,India
On Tue, Dec 21, 2010 at 11:07 AM, Naveen Kumar
naveenkumarve...@gmail.com wrote:
I second Ashish,
These two events are independent
On Tue, Dec 21, 2010 at 10:57 AM, Ashish Goel ashg...@gmail.com wrote:
you can't find...
are these mutually exclusive or independent? think twice, draw venn diag
there would be cases when AB as well as CD, in such cases foo2 will NOT
be called
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Wed, Dec 15, 2010 at 12:36 AM, bittu shashank7andr...@gmail.com
wrote:
void foo1()
{
if(AB)
Then {_/* */}
else
if(CD)
then foo2()
}
How many time foo2() would get called given
AB 25% of the times and CD 75% of the times and foo1() is called
5000 times
although i had diff...solution..but i wants to confirm wid others..so
hav a look
Regards
Shashank Mani
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 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.
--
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.
--
Cheers
Naveen Kumar
--
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.
--
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.
