Re: [algogeeks] Adobe Written Test - 25 SEPT 2010
Which edition of barron? On Wed, Sep 28, 2011 at 6:05 PM, VIHARRI viharri@gmail.com wrote: 1. Java uses stack for byte code in JVM - each instruction is of one byte, so how many such instructions are possible in an operating system. 2. Three processes p1, p2, p3, p4 - each have sizes 1GB, 1.2GB, 2GB, 1GB. And each processes is executed as a time sharing fashion. Will they be executed on an operating system. 3. write a recursive program for reversing the linked list. 4. write a program for checking the given number is a palindrome. ( dont use string / array for converting number ). 5. write a recursive program for multiplying two numbers a and b, with additions. The program should take care of doing min # additions as that of which ever number is lower between a and b. 6. There are two sets A and B with n integers, write a program to check the whether there exists two numbers a in A and b in B such that a+b = val ( val is given ); 7. write a program to return the row number which has max no of one's in an array of NxN matrix where all 1's occur before any 0's starts. 8. For every number that has 3 in its units place has one multiple which has all one's i.e. 111 is such multiple and 13 has a multiple 11. Write a program to find such multiple for any number that has 3 at its units place. 9. what are the maximum no of edges that can be connected in a graph of n vertices and 0 edges such that after adding edges given graph is still disconnected. 10. One Question on critical section. For Analytical Test - Prepare the Questions in the barrons book of sample paper - 2 ( they have give two passages ) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks regards Bhupendra -- 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] Anagram problem
Sort each of the word and form a trie , if any words comes again you get one sch case. On Wed, Jul 18, 2012 at 2:12 PM, vindhya chhabra vindhyachha...@gmail.comwrote: yes,sorry count sort will be O(n) so better.thanks On Wed, Jul 18, 2012 at 1:43 PM, saurabh singh saurab...@gmail.comwrote: ^sorting a string would be o(n^2logn) if u use q.sort.count sort would be better. Saurabh Singh B.Tech (Computer Science) MNNIT blog:geekinessthecoolway.blogspot.com On Wed, Jul 18, 2012 at 1:08 PM, vindhya chhabra vindhyachha...@gmail.com wrote: sort the list,sort the word(use quick sort(nlogn time))- and den search using binary search(logn time) or we can evn do by hashing-hash the word,den for every word keep decreasing the counter,if the hash array is zero ,anagram,else reset the hash array for given input for the checking the next word. On Wed, Jul 18, 2012 at 2:07 AM, Navin Kumar algorithm.i...@gmail.comwrote: Assuming a preexisting list of 100 words, how would you efficiently see if a word received from input is an anagram of any of the 100 words? -- 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/-/5kuxjymYEc4J. 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. -- Vindhya Chhabra -- 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. -- Vindhya Chhabra -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks regards Bhupendra -- 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] Amazon Interview Question
Consider trees:
1 3
2 3 2
1
pre order traversal is same still (1 , 2 ,3) even though ist tree doesn't
satisfy the criteria . So I don't think it can be determined.
On Wed, Jul 4, 2012 at 4:16 PM, Ashish Goel ashg...@gmail.com wrote:
Q4
vectorString prefix;
prefix[0]=NULL;
prefixCount =1;
for (int i=0;in;i++)
for (int j=0;jn;j++)
for (int k=0; kprefixCount;k++)
{
if (visited[i][j]) continue;
visited[i][j] = true;
String s=prefix[k]+a[i][j];
if (isWord(s) { printWord(s); prefix[k]=s; continue;}
else if isPrefix(s) prefix[prefixCount++] = s;
else removePrefix(prefix[k], prefixCount);
prefix[prefixCount++] = String(a[i][j];
}
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Wed, Jul 4, 2012 at 4:13 PM, Ashish Goel ashg...@gmail.com wrote:
1. inverted hasp map
2. not clear
3. VLR, how do you identify end of L and start of R, question incomplete
4. One problem: consider
...
a b...
c d...
...
if ab is a prefix, can aba be another prefix, i would assume so. But if
that is true, i am not sure if this program will come to an end.
vectorString prefix;
prefix[0]=NULL;
prefixCount =1;
for (int i=0;in;i++)
for (int j=0;jn;j++)
for (int k=0; kprefixCount;k++)
{
String s=prefix[k]+a[i][j];
if (isWord(s) { printWord(s); prefix[k]=s; continue;}
else if isPrefix(s) prefix[prefixCount++] = s;
else removePrefix(prefix[k], prefixCount);
prefix[prefixCount++] = String(a[i][j];
}
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Wed, Jul 4, 2012 at 12:22 PM, Decipher ankurseth...@gmail.com wrote:
Find the next higher number in set of permutations of a given number
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Thanks regards
Bhupendra
--
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] Amazon Interview Question
1. For first question trie of given word will be best option.
Space complexity O(total length of words) (worst case)
Time complexity O(T) . T length of input text (Newspaper)
2. consider it to be a 4 digit number ABCD . Find maximum Most
significant digit say it is C , and out of these nos find maximum value of
next digit say A and so on . Suppose Final no. is CADB
Now next highest permutation will be the no. just greater than this and
made of these digits . This is easy.
On Wed, Jul 4, 2012 at 5:17 PM, Bhupendra Dubey bhupendra@gmail.comwrote:
Consider trees:
1 3
2 3 2
1
pre order traversal is same still (1 , 2 ,3) even though ist tree doesn't
satisfy the criteria . So I don't think it can be determined.
On Wed, Jul 4, 2012 at 4:16 PM, Ashish Goel ashg...@gmail.com wrote:
Q4
vectorString prefix;
prefix[0]=NULL;
prefixCount =1;
for (int i=0;in;i++)
for (int j=0;jn;j++)
for (int k=0; kprefixCount;k++)
{
if (visited[i][j]) continue;
visited[i][j] = true;
String s=prefix[k]+a[i][j];
if (isWord(s) { printWord(s); prefix[k]=s; continue;}
else if isPrefix(s) prefix[prefixCount++] = s;
else removePrefix(prefix[k], prefixCount);
prefix[prefixCount++] = String(a[i][j];
}
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Wed, Jul 4, 2012 at 4:13 PM, Ashish Goel ashg...@gmail.com wrote:
1. inverted hasp map
2. not clear
3. VLR, how do you identify end of L and start of R, question incomplete
4. One problem: consider
...
a b...
c d...
...
if ab is a prefix, can aba be another prefix, i would assume so. But if
that is true, i am not sure if this program will come to an end.
vectorString prefix;
prefix[0]=NULL;
prefixCount =1;
for (int i=0;in;i++)
for (int j=0;jn;j++)
for (int k=0; kprefixCount;k++)
{
String s=prefix[k]+a[i][j];
if (isWord(s) { printWord(s); prefix[k]=s; continue;}
else if isPrefix(s) prefix[prefixCount++] = s;
else removePrefix(prefix[k], prefixCount);
prefix[prefixCount++] = String(a[i][j];
}
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Wed, Jul 4, 2012 at 12:22 PM, Decipher ankurseth...@gmail.comwrote:
Find the next higher number in set of permutations of a given number
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Thanks regards
Bhupendra
--
Thanks regards
Bhupendra
--
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] Amazon Interview Question
For question 5.
Even this doesn't seems right
Consider this scenario
Match b/w Winner
a vs b a
a vs c c
b vs c b
What will be order ?? acb or bca
On Wed, Jul 4, 2012 at 5:38 PM, Bhupendra Dubey bhupendra@gmail.comwrote:
1. For first question trie of given word will be best option.
Space complexity O(total length of words) (worst case)
Time complexity O(T) . T length of input text (Newspaper)
2. consider it to be a 4 digit number ABCD . Find maximum Most
significant digit say it is C , and out of these nos find maximum value of
next digit say A and so on . Suppose Final no. is CADB
Now next highest permutation will be the no. just greater than this and
made of these digits . This is easy.
On Wed, Jul 4, 2012 at 5:17 PM, Bhupendra Dubey
bhupendra@gmail.comwrote:
Consider trees:
1 3
2 3 2
1
pre order traversal is same still (1 , 2 ,3) even though ist tree
doesn't satisfy the criteria . So I don't think it can be determined.
On Wed, Jul 4, 2012 at 4:16 PM, Ashish Goel ashg...@gmail.com wrote:
Q4
vectorString prefix;
prefix[0]=NULL;
prefixCount =1;
for (int i=0;in;i++)
for (int j=0;jn;j++)
for (int k=0; kprefixCount;k++)
{
if (visited[i][j]) continue;
visited[i][j] = true;
String s=prefix[k]+a[i][j];
if (isWord(s) { printWord(s); prefix[k]=s; continue;}
else if isPrefix(s) prefix[prefixCount++] = s;
else removePrefix(prefix[k], prefixCount);
prefix[prefixCount++] = String(a[i][j];
}
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Wed, Jul 4, 2012 at 4:13 PM, Ashish Goel ashg...@gmail.com wrote:
1. inverted hasp map
2. not clear
3. VLR, how do you identify end of L and start of R, question incomplete
4. One problem: consider
...
a b...
c d...
...
if ab is a prefix, can aba be another prefix, i would assume so. But if
that is true, i am not sure if this program will come to an end.
vectorString prefix;
prefix[0]=NULL;
prefixCount =1;
for (int i=0;in;i++)
for (int j=0;jn;j++)
for (int k=0; kprefixCount;k++)
{
String s=prefix[k]+a[i][j];
if (isWord(s) { printWord(s); prefix[k]=s; continue;}
else if isPrefix(s) prefix[prefixCount++] = s;
else removePrefix(prefix[k], prefixCount);
prefix[prefixCount++] = String(a[i][j];
}
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Wed, Jul 4, 2012 at 12:22 PM, Decipher ankurseth...@gmail.comwrote:
Find the next higher number in set of permutations of a given number
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Thanks regards
Bhupendra
--
Thanks regards
Bhupendra
--
Thanks regards
Bhupendra
--
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] Amazon Interview Question
Sorry i typed wrongly
tree is
2
1 3
preorder traversal is 123 and same for other tree as well. Please check !
On Wed, Jul 4, 2012 at 5:24 PM, a g ag20071...@gmail.com wrote:
1
2 3 is not a BST and its pre-order traversal is 1 2 3, pre
order of other is 3 2 1 .
On Wed, Jul 4, 2012 at 5:17 PM, Bhupendra Dubey
bhupendra@gmail.comwrote:
Consider trees:
1 3
2 3 2
1
pre order traversal is same still (1 , 2 ,3) even though ist tree
doesn't satisfy the criteria . So I don't think it can be determined.
On Wed, Jul 4, 2012 at 4:16 PM, Ashish Goel ashg...@gmail.com wrote:
Q4
vectorString prefix;
prefix[0]=NULL;
prefixCount =1;
for (int i=0;in;i++)
for (int j=0;jn;j++)
for (int k=0; kprefixCount;k++)
{
if (visited[i][j]) continue;
visited[i][j] = true;
String s=prefix[k]+a[i][j];
if (isWord(s) { printWord(s); prefix[k]=s; continue;}
else if isPrefix(s) prefix[prefixCount++] = s;
else removePrefix(prefix[k], prefixCount);
prefix[prefixCount++] = String(a[i][j];
}
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Wed, Jul 4, 2012 at 4:13 PM, Ashish Goel ashg...@gmail.com wrote:
1. inverted hasp map
2. not clear
3. VLR, how do you identify end of L and start of R, question incomplete
4. One problem: consider
...
a b...
c d...
...
if ab is a prefix, can aba be another prefix, i would assume so. But if
that is true, i am not sure if this program will come to an end.
vectorString prefix;
prefix[0]=NULL;
prefixCount =1;
for (int i=0;in;i++)
for (int j=0;jn;j++)
for (int k=0; kprefixCount;k++)
{
String s=prefix[k]+a[i][j];
if (isWord(s) { printWord(s); prefix[k]=s; continue;}
else if isPrefix(s) prefix[prefixCount++] = s;
else removePrefix(prefix[k], prefixCount);
prefix[prefixCount++] = String(a[i][j];
}
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Wed, Jul 4, 2012 at 12:22 PM, Decipher ankurseth...@gmail.comwrote:
Find the next higher number in set of permutations of a given number
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Thanks regards
Bhupendra
--
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.
--
Thanks regards
Bhupendra
--
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] symmetric binary tree
Create the mirror copy of the tree and compare with original. If same then symmetric. On Tue, May 22, 2012 at 10:50 AM, algogeek dayanidhi.haris...@gmail.comwrote: How to check if a given binary tree is structurally symmetric ie. the left sub tree should be mirror image of right sub tree and vice-versa. -- 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. -- 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 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] find where the two list connect
start from head of both and as soon as one of the list is empty means you hit null start counting the remaining number of nodes in the other list till that gets empty. Now the number obtained above is the difference in length of the two list prior to the first common node (the red node). Now again traverse the longer list corresponding to the above count and then start traversing the other list .Stop when two nodes become equal. Home!:) On Tue, May 1, 2012 at 7:55 PM, רפי וינר rafiwie...@gmail.com wrote: you have two linked lists that some where combine in to one list. pic attached to illustrate [image: Inline image 1] you need to find where the two list collide. (in the pic the red node) -- 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. -- 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 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. Untitled.png
Re: [algogeeks] Re: find a point closest to other points
Find the centroid
X= (x1 +x2xn)/N
Y=(y1+y2..yn)/N
This will precisely be the point no need to calculate and check with
distance.
On Tue, May 1, 2012 at 1:18 PM, mohit mishra mohit7mis...@gmail.com wrote:
Let me know if there is any bug
/*using centroid of plane */
struct point
{
int x;
int y;
};
typedef struct point Point;
int main()
{
int n,i;
int d,dis;
float sum_x=0,sum_y=0;
Point centroid,final;
//clrcsr();
printf(how many points? );
scanf(%d,n);
Point p[100];
printf(enter X and Y cordinates of %d points\n,n);
for(i=0;in;i++)
scanf(%d%d,p[i].x,p[i].y);
for(i=0;in;i++)
{
sum_x=sum_x+p[i].x;
sum_y=sum_y+p[i].y;
}
centroid.x=(int)sum_x/n;
centroid.y=(int)sum_y/n;
for(i=0;in;i++)
{
dis=distance(centroid,p[i]);
if(disd)
{
d=dis;
final.x=p[i].x;
final.y=p[i].y;
}
}
printf(\n The point is (%3d ,%3d),final.x,final.y);
getch();
return 0;
}
int distance(Point A,Point B)
{
int x,y;
x=(A.x-B.x)*(A.x-B.x);
y=(A.y-B.y)*(A.y-B.y);
return sqrt(x+y);
}
On Mon, Apr 30, 2012 at 4:34 PM, kosgi santosh santoshko...@gmail.comwrote:
how can we find centriod of n points in a plane?
Regards,
Santosh K.
--
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.
--
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 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: find where the two list connect
look at the length before the red node. 3 2 so difference is 1. Now if pointer in longer list has already moved difference lengths before pointer in shorter list is started then they will both take equal time to reach the junction of the list. On Tue, May 1, 2012 at 9:17 PM, rafi rafiwie...@gmail.com wrote: i dont understan if i look in the pic i attached then the length of the first list is 5 and the length of the second list is 6. what should i do now? if i traverse the long list 5,6 nodes i dont get to the red node. what am i missing? On 1 מאי, 18:04, Bhupendra Dubey bhupendra@gmail.com wrote: start from head of both and as soon as one of the list is empty means you hit null start counting the remaining number of nodes in the other list till that gets empty. Now the number obtained above is the difference in length of the two list prior to the first common node (the red node). Now again traverse the longer list corresponding to the above count and then start traversing the other list .Stop when two nodes become equal. Home!:) On Tue, May 1, 2012 at 7:55 PM, רפי וינר rafiwie...@gmail.com wrote: you have two linked lists that some where combine in to one list. pic attached to illustrate [image: Inline image 1] you need to find where the two list collide. (in the pic the red node) -- 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. -- bhupendra dubey Untitled.png 14Kהצגהורדה -- 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. -- 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 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] Longest increasing subsequence
It can be done in O(n) time. int start_index=0, longest_sequence=0 traverse the sequence and increment 't' for every a[i+1]a[i] starting with zero till this holds true. assign 't' to longest_sequence assuming condition evaluates to false for a[k]; repeat the above step but assign 't' to longest_sequence only when tlongest_sequence also change start_index to 'k' do this for the whole array. On Fri, Dec 31, 2010 at 8:20 AM, Prabakaran N prabaf...@gmail.com wrote: You can use binary search On 12/31/10, Anand anandut2...@gmail.com wrote: Anyone know how to find longest increasing subsequence in O(nlogn) complexity? -- 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. -- 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.
Re: [algogeeks] Re: good question
@Dave nice algorithm On Fri, Dec 24, 2010 at 6:59 PM, Dave dave_and_da...@juno.com wrote: @Monty: Use an alternating across and down algorithm: Set the current row = the first row While current row is not the last row Look across the current row for the first false Look down the column containing that first false for a true If no such row is found, break. // current row is the result End While Since you only go to the right and down, you can't take more than m + n steps. Dave On Dec 24, 5:46 am, monty 1987 1986mo...@gmail.com wrote: Given a boolean matrix with all the true elements on left side in the row so that each row can be broken into two parts left part containing only true elements and right part containing only false elements. Find the row with max number of true elements in it. if the size of matrix is m*n then it can be solved in O(m+n) time. Any bettar solution.. -- 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.
Re: [algogeeks] Valid subsets
iam sorry but the problem statment is not clear to me.
how am i supposed to use exclusion rules
some more examples please.
On Wed, Dec 22, 2010 at 8:34 PM, Prims topcode...@gmail.com wrote:
given a set of distinct integers {a1, a2, a3, a4, a5, ...}
and a set of exclusion rules: R = {{a1, a3}, {a2, a4, a10}, ...}
can you print out all the valid subsets?
Example:
what is a valid subset? {a1, a4}
what is an invalid subset? {a1, a2, a4}
--
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.
Re: [algogeeks] Re: difference x
send the data set to the hash table now search for a[i]+x in the table if found for 'k' den a[k] and a[k]+x is the required pair complexity: o(n)(for mapping)+O(n)(for search a[i]+x)=O(n) @Snehal can i see your solution please. On Thu, Dec 23, 2010 at 12:11 AM, Aviral Gupta aviral@gmail.com wrote: use hash map.O(n) or you can use use the binary search for each element O(nlogn) Regards Aviral http://coders-stop.blogspot.com On Dec 22, 3:05 pm, snehal jain learner@gmail.com wrote: How will you find the pair from an sorted array whose difference is x -- 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.
Re: [algogeeks] Re: difference x
@juver:thanx for making me work... please notice this
this also uses the sorted property of the array
i=0,j=1;
while((i!=n-1) or j!=n)
{
/*compare difference of a[j] and a[i]*/
if( (a[j]-[a[i]])x )
i++;
else if( (a[j]-a[i])x)
j++;
else
{
/*SOLUTION*/
return;
}
}
regards
complexity:O(n)
On Thu, Dec 23, 2010 at 12:29 AM, juver++ avpostni...@gmail.com wrote:
Your solution needs extra space and it has only *expected* O(n) time.
There is O(n) inplace solution
--
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.
Re: [algogeeks] Re: celebrity twitters
let S be the set containing n people
int i=0,j=n-1;
while(i!=j)
{
*ask S[i] if he knows S[j]*/
if(YES)
i++;//if yes then S[i] cant be the celebrity take him
out of the equation
else
j--; //if no then S[j] cant be the celebrity so let him
pass
}
S[i] or S[j] gives the celebrity in the set;
Complexity:
(max no of times i can be incremented)+(max no of times j can be
decremented)=n
no of questions=n
so O(n)
Bhupendra Dubey
DELHI COLLEGE OF ENGINEERING
On Tue, Dec 21, 2010 at 9:26 AM, sharat sharath.channaha...@gmail.comwrote:
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.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.
Re: [algogeeks] HP Question
insertion sort On Tue, Dec 21, 2010 at 6:49 PM, Ankur Khurana ankur.kkhur...@gmail.comwrote: insertion sort in IMHO On Tue, Dec 21, 2010 at 5:44 PM, bittu shashank7andr...@gmail.com wrote: Which one is the efficient sorting technique for arranging the books in a library? a) Bubble Sort b) Selection Sort c) Insertion Sort d) Heap Sort 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.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. -- 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.
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.
