[algogeeks] Facebook Interview Question
There are K pegs. Each peg can hold discs in decreasing order of radius when looked from bottom to top of the peg. There are N discs which have radius 1 to N; Given the initial configuration of the pegs and the final configuration of the pegs, output the moves required to transform from the initial to final configuration. You are required to do the transformations in minimal number of moves. A move consists of picking the topmost disc of any one of the pegs and placing it on top of anyother peg. At anypoint of time, the decreasing radius property of all the pegs must be maintained. Constraints: 1= N=8 3= K=5 Input Format: N K 2nd line contains N integers. Each integer in the second line is in the range 1 to K where the i-th integer denotes the peg to which disc of radius i is present in the initial configuration. 3rd line denotes the final configuration in a format similar to the initial configuration. Output Format: The first line contains M - The minimal number of moves required to complete the transformation. The following M lines describe a move, by a peg number to pick from and a peg number to place on. If there are more than one solutions, it's sufficient to output any one of them. You can assume, there is always a solution with less than 7 moves and the initial confirguration will not be same as the final one. Sample Input #00: 2 3 1 1 2 2 Sample Output #00: 3 1 3 1 2 3 2 Sample Input #01: 6 4 4 2 4 3 1 1 1 1 1 1 1 1 Sample Output #01: 5 3 1 4 3 4 1 2 1 3 1 -- *Regards* Mahendra Pratap Singh Sengar B-tech 4/4 NIT Warangal. Facebook ID http://www.facebook.com/mkingmahi -- 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] Facebook Interview Question
There are K pegs. Each peg can hold discs in decreasing order of radius when looked from bottom to top of the peg. There are N discs which have radius 1 to N; Given the initial configuration of the pegs and the final configuration of the pegs, output the moves required to transform from the initial to final configuration. You are required to do the transformations in minimal number of moves. A move consists of picking the topmost disc of any one of the pegs and placing it on top of anyother peg. At anypoint of time, the decreasing radius property of all the pegs must be maintained. Constraints: 1= N=8 3= K=5 Input Format: N K 2nd line contains N integers. Each integer in the second line is in the range 1 to K where the i-th integer denotes the peg to which disc of radius i is present in the initial configuration. 3rd line denotes the final configuration in a format similar to the initial configuration. Output Format: The first line contains M - The minimal number of moves required to complete the transformation. The following M lines describe a move, by a peg number to pick from and a peg number to place on. If there are more than one solutions, it's sufficient to output any one of them. You can assume, there is always a solution with less than 7 moves and the initial confirguration will not be same as the final one. Sample Input #00: 2 3 1 1 2 2 Sample Output #00: 3 1 3 1 2 3 2 Sample Input #01: 6 4 4 2 4 3 1 1 1 1 1 1 1 1 Sample Output #01: 5 3 1 4 3 4 1 2 1 3 1 -- 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/-/wR-n5NDKpoQJ. 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] Facebook interview question.
does this work if array elements are negative??? -- 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] Facebook interview question.
@Piyush : yes it works ... please check the link again ..Lucifer has added more details to the same post for better explanation. follow that link and if you have any queries post your queries on that old link. On Mon, Jan 9, 2012 at 1:04 PM, Piyush Grover piyush4u.iit...@gmail.comwrote: Hi Atul Yes, I posted it earlier but couldn't keep track of it, thanks for the link. I still have a doubt, does it give all the maximal subsets or all the subsets. I couldn't get it from the algo posted by Lucifer. On Mon, Jan 9, 2012 at 9:45 AM, atul anand atul.87fri...@gmail.comwrote: @Piyush : you are re-posting same problem which you had posted on 5 dec 2011. check this link :- http://groups.google.com/group/algogeeks/browse_thread/thread/8a58ea05c96f811b/ee74f8a4d7b68561?lnk=gstq=Maximal+possible+subsets+Algorithm#ee74f8a4d7b68561 On Mon, Jan 9, 2012 at 3:27 AM, Piyush Grover piyush4u.iit...@gmail.comwrote: Given a set S, find all the maximal subsets whose sum = k. For example, if S = {1, 2, 3, 4, 5} and k = 7 Output is: {1, 2, 3} {1, 2, 4} {1, 5} {2, 5} {3, 4} Hint: - Output doesn't contain any set which is a subset of other. - If X = {1, 2, 3} is one of the solution then all the subsets of X {1} {2} {3} {1, 2} {1, 3} {2, 3} are omitted. - Lexicographic ordering may be used to solve it -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Facebook interview question.
Given a set S, find all the maximal subsets whose sum = k. For example, if S = {1, 2, 3, 4, 5} and k = 7 Output is: {1, 2, 3} {1, 2, 4} {1, 5} {2, 5} {3, 4} Hint: - Output doesn't contain any set which is a subset of other. - If X = {1, 2, 3} is one of the solution then all the subsets of X {1} {2} {3} {1, 2} {1, 3} {2, 3} are omitted. - Lexicographic ordering may be used to solve it -- 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] Facebook interview question.
@Piyush : you are re-posting same problem which you had posted on 5 dec 2011. check this link :- http://groups.google.com/group/algogeeks/browse_thread/thread/8a58ea05c96f811b/ee74f8a4d7b68561?lnk=gstq=Maximal+possible+subsets+Algorithm#ee74f8a4d7b68561 On Mon, Jan 9, 2012 at 3:27 AM, Piyush Grover piyush4u.iit...@gmail.comwrote: Given a set S, find all the maximal subsets whose sum = k. For example, if S = {1, 2, 3, 4, 5} and k = 7 Output is: {1, 2, 3} {1, 2, 4} {1, 5} {2, 5} {3, 4} Hint: - Output doesn't contain any set which is a subset of other. - If X = {1, 2, 3} is one of the solution then all the subsets of X {1} {2} {3} {1, 2} {1, 3} {2, 3} are omitted. - Lexicographic ordering may be used to solve it -- 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] Facebook interview question.
Hi Atul Yes, I posted it earlier but couldn't keep track of it, thanks for the link. I still have a doubt, does it give all the maximal subsets or all the subsets. I couldn't get it from the algo posted by Lucifer. On Mon, Jan 9, 2012 at 9:45 AM, atul anand atul.87fri...@gmail.com wrote: @Piyush : you are re-posting same problem which you had posted on 5 dec 2011. check this link :- http://groups.google.com/group/algogeeks/browse_thread/thread/8a58ea05c96f811b/ee74f8a4d7b68561?lnk=gstq=Maximal+possible+subsets+Algorithm#ee74f8a4d7b68561 On Mon, Jan 9, 2012 at 3:27 AM, Piyush Grover piyush4u.iit...@gmail.comwrote: Given a set S, find all the maximal subsets whose sum = k. For example, if S = {1, 2, 3, 4, 5} and k = 7 Output is: {1, 2, 3} {1, 2, 4} {1, 5} {2, 5} {3, 4} Hint: - Output doesn't contain any set which is a subset of other. - If X = {1, 2, 3} is one of the solution then all the subsets of X {1} {2} {3} {1, 2} {1, 3} {2, 3} are omitted. - Lexicographic ordering may be used to solve it -- 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] facebook interview question
refer algorithms by cormen for this On Mon, Nov 28, 2011 at 9:56 PM, Nitin Garg nitin.garg.i...@gmail.comwrote: Find the min and max in an array. Now do it in less than 2n comparisons. (they were looking for the solution that finds both max and min in about 3/2 n comparisons). -- Nitin Garg Personality can open doors, but only Character can keep them open -- 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] facebook interview question
Greetings! The strategy should be to process the elements in pairs - and compare the larger element with current maximum, and smaller element with current minimum. loop runs upto n in steps of 2, and in each iteration, there are 3 comparisons: - between (i)th and (i+1)th element - between min(i, i+1) and current_min - between max(i, i+1) and current_max That gives 3n/2 comparisons. Instead of doing 2 comparisons for every element (with min and max), now you're doing 3 comparisons for every pair - which makes it effectively 1.5 comparisons for each element. That's how the n/2 comparisons are saved. I hope the idea is clear. On Sun, Dec 4, 2011 at 11:32 AM, Anika Jain anika.jai...@gmail.com wrote: refer algorithms by cormen for this On Mon, Nov 28, 2011 at 9:56 PM, Nitin Garg nitin.garg.i...@gmail.comwrote: Find the min and max in an array. Now do it in less than 2n comparisons. (they were looking for the solution that finds both max and min in about 3/2 n comparisons). -- Nitin Garg Personality can open doors, but only Character can keep them open -- 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. -- Best Regards, Deepak -- 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] facebook interview question
Find the min and max in an array. Now do it in less than 2n comparisons. (they were looking for the solution that finds both max and min in about 3/2 n comparisons). -- Nitin Garg Personality can open doors, but only Character can keep them open -- 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] facebook interview question
Take numbers in pair of 2, compare with each other and then compare the maximum among them with max (maximum element so far) and minimum among them with min (minimum element so far) , In this way you will be able to find max, min in 3 comparisons for each 2 integers. Hence 3n/2 comparisons needed for finding min and max simultaneously in an array. On Mon, Nov 28, 2011 at 9:56 PM, Nitin Garg nitin.garg.i...@gmail.comwrote: Find the min and max in an array. Now do it in less than 2n comparisons. (they were looking for the solution that finds both max and min in about 3/2 n comparisons). -- Nitin Garg Personality can open doors, but only Character can keep them open -- 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. -- Aamir Khan | 3rd Year | Computer Science Engineering | IIT 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] Facebook Interview question at NIT Warangal
Hi The solution in the link is of complexity (n*2^n)) Does anyone know any better solution ? Regards Ankur On Tue, Jul 26, 2011 at 11:10 PM, rajeev bharshetty rajeevr...@gmail.comwrote: @Ankur The link does has a very good explanation. Nice solution :) On Tue, Jul 26, 2011 at 10:47 PM, Kunal Patil kp101...@gmail.com wrote: @Ankur Garg: Nice explanation at the link given by u... On Tue, Jul 26, 2011 at 10:35 PM, Ankur Garg ankurga...@gmail.comwrote: Check this http://codesam.blogspot.com/2011/03/find-all-subsets-of-given-set.html On Tue, Jul 26, 2011 at 9:41 PM, Vishal Thanki vishaltha...@gmail.comwrote: Here is the working code.. #include stdio.h #include stdlib.h int a[] = {1,2,3,4,5}; #define ARRLEN(a) (sizeof(a)/sizeof(a[0])) void print_comb(int len) { int tlen = len; int i, j, k; int al = ARRLEN(a); for (i = 0; i al; i++) { for (j=i+len-1; jal;j++) { for (k = i; k i+len-1; k++) { printf(%d , a[k]); } printf(%d\n, a[j]); } } } int main(int argc, char *argv[]) { int len = atoi(argv[1]); print_comb(len); return 0; } On Tue, Jul 26, 2011 at 5:18 PM, praneethn praneeth...@gmail.com wrote: check this link: *http://www.stefan-pochmann.info/spots/tutorials/sets_subsets/* On Tue, Jul 26, 2011 at 11:59 AM, sumit sumitispar...@gmail.com wrote: Given an array of size n, print all the possible subset of array of size k. eg:- input: a[]={1,2,3,4}, k = 2 output: 1,2 1,3 1,4 2,3 2,4 3,4 -- 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. -- 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 Rajeev N B http://www.opensourcemania.co.cc -- 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] Facebook Interview question at NIT Warangal
Given an array of size n, print all the possible subset of array of size k. eg:- input: a[]={1,2,3,4}, k = 2 output: 1,2 1,3 1,4 2,3 2,4 3,4 -- 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] Facebook Interview question at NIT Warangal
Hi Dont u think the subsets will also be {2,1} {3,1} {3,2} {4,1} {4,2} {4,3} On Tue, Jul 26, 2011 at 11:59 AM, sumit sumitispar...@gmail.com wrote: Given an array of size n, print all the possible subset of array of size k. eg:- input: a[]={1,2,3,4}, k = 2 output: 1,2 1,3 1,4 2,3 2,4 3,4 -- 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] Facebook Interview question at NIT Warangal
@ankur, i think 1,2 and 2,1 would be same as set theory.. CMMIW. following is the code.. #include stdio.h #include stdlib.h void print_comb(int *a, int len) { int tlen = len; int i, j, k; for (i=0;i5;i++) { for (j=i+1; j4;j++) { printf(%d , a[i]); k=j; while(tlen-1 0) { printf(%d , a[k]); k++; tlen--; } printf(\n); tlen = len; } } } int main(int argc, char *argv[]) { int len = atoi(argv[1]); int arr[] = {1,2,3,4}; print_comb(arr, len); return 0; } On Tue, Jul 26, 2011 at 1:01 PM, Ankur Garg ankurga...@gmail.com wrote: Hi Dont u think the subsets will also be {2,1} {3,1} {3,2} {4,1} {4,2} {4,3} On Tue, Jul 26, 2011 at 11:59 AM, sumit sumitispar...@gmail.com wrote: Given an array of size n, print all the possible subset of array of size k. eg:- input: a[]={1,2,3,4}, k = 2 output: 1,2 1,3 1,4 2,3 2,4 3,4 -- 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] Facebook Interview question at NIT Warangal
anyway, the code i posted is buggy.. doesn't work for k=3.. don't use it :) On Tue, Jul 26, 2011 at 1:02 PM, Vishal Thanki vishaltha...@gmail.com wrote: @ankur, i think 1,2 and 2,1 would be same as set theory.. CMMIW. following is the code.. #include stdio.h #include stdlib.h void print_comb(int *a, int len) { int tlen = len; int i, j, k; for (i=0;i5;i++) { for (j=i+1; j4;j++) { printf(%d , a[i]); k=j; while(tlen-1 0) { printf(%d , a[k]); k++; tlen--; } printf(\n); tlen = len; } } } int main(int argc, char *argv[]) { int len = atoi(argv[1]); int arr[] = {1,2,3,4}; print_comb(arr, len); return 0; } On Tue, Jul 26, 2011 at 1:01 PM, Ankur Garg ankurga...@gmail.com wrote: Hi Dont u think the subsets will also be {2,1} {3,1} {3,2} {4,1} {4,2} {4,3} On Tue, Jul 26, 2011 at 11:59 AM, sumit sumitispar...@gmail.com wrote: Given an array of size n, print all the possible subset of array of size k. eg:- input: a[]={1,2,3,4}, k = 2 output: 1,2 1,3 1,4 2,3 2,4 3,4 -- 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] Facebook Interview question at NIT Warangal
#include bitset #include iostream #include math.h #include vector int main() { using namespace std; int arr[] = {1,2,3,4}; int k = 2; int n = sizeof(arr)/sizeof(int); vectorint v(arr, arr+n); int l = pow(2.0, n); for (int i = 0; i l; ++i) { bitset32 b(i); if (b.count() != k) continue; for (int j = 0; j n; ++j) { if (b[j]) cout arr[j] ; } cout endl; } return 0; } On Tue, Jul 26, 2011 at 11:59 AM, sumit sumitispar...@gmail.com wrote: Given an array of size n, print all the possible subset of array of size k. eg:- input: a[]={1,2,3,4}, k = 2 output: 1,2 1,3 1,4 2,3 2,4 3,4 -- 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] Facebook Interview question at NIT Warangal
int main() { buildsubsets(0,0,); } void buildsubsets(int i,int j,String subset) { if(j==k) { coutsubset+ ; return ; } for(;in;++i) buildsubsets(i+1,j+1,subset+arr[i]); } assume that given arr[] is a character array i.e. arr[]={'1','2','3'}. for any value of k it works On Tue, Jul 26, 2011 at 11:59 AM, sumit sumitispar...@gmail.com wrote: Given an array of size n, print all the possible subset of array of size k. eg:- input: a[]={1,2,3,4}, k = 2 output: 1,2 1,3 1,4 2,3 2,4 3,4 -- 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] Facebook Interview question at NIT Warangal
check this link: *http://www.stefan-pochmann.info/spots/tutorials/sets_subsets/* On Tue, Jul 26, 2011 at 11:59 AM, sumit sumitispar...@gmail.com wrote: Given an array of size n, print all the possible subset of array of size k. eg:- input: a[]={1,2,3,4}, k = 2 output: 1,2 1,3 1,4 2,3 2,4 3,4 -- 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] Facebook Interview question at NIT Warangal
Here is the working code.. #include stdio.h #include stdlib.h int a[] = {1,2,3,4,5}; #define ARRLEN(a) (sizeof(a)/sizeof(a[0])) void print_comb(int len) { int tlen = len; int i, j, k; int al = ARRLEN(a); for (i = 0; i al; i++) { for (j=i+len-1; jal;j++) { for (k = i; k i+len-1; k++) { printf(%d , a[k]); } printf(%d\n, a[j]); } } } int main(int argc, char *argv[]) { int len = atoi(argv[1]); print_comb(len); return 0; } On Tue, Jul 26, 2011 at 5:18 PM, praneethn praneeth...@gmail.com wrote: check this link: *http://www.stefan-pochmann.info/spots/tutorials/sets_subsets/* On Tue, Jul 26, 2011 at 11:59 AM, sumit sumitispar...@gmail.com wrote: Given an array of size n, print all the possible subset of array of size k. eg:- input: a[]={1,2,3,4}, k = 2 output: 1,2 1,3 1,4 2,3 2,4 3,4 -- 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] Facebook Interview question at NIT Warangal
Check this http://codesam.blogspot.com/2011/03/find-all-subsets-of-given-set.html On Tue, Jul 26, 2011 at 9:41 PM, Vishal Thanki vishaltha...@gmail.comwrote: Here is the working code.. #include stdio.h #include stdlib.h int a[] = {1,2,3,4,5}; #define ARRLEN(a) (sizeof(a)/sizeof(a[0])) void print_comb(int len) { int tlen = len; int i, j, k; int al = ARRLEN(a); for (i = 0; i al; i++) { for (j=i+len-1; jal;j++) { for (k = i; k i+len-1; k++) { printf(%d , a[k]); } printf(%d\n, a[j]); } } } int main(int argc, char *argv[]) { int len = atoi(argv[1]); print_comb(len); return 0; } On Tue, Jul 26, 2011 at 5:18 PM, praneethn praneeth...@gmail.com wrote: check this link: *http://www.stefan-pochmann.info/spots/tutorials/sets_subsets/* On Tue, Jul 26, 2011 at 11:59 AM, sumit sumitispar...@gmail.com wrote: Given an array of size n, print all the possible subset of array of size k. eg:- input: a[]={1,2,3,4}, k = 2 output: 1,2 1,3 1,4 2,3 2,4 3,4 -- 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] Facebook Interview question at NIT Warangal
@Ankur Garg: Nice explanation at the link given by u... On Tue, Jul 26, 2011 at 10:35 PM, Ankur Garg ankurga...@gmail.com wrote: Check this http://codesam.blogspot.com/2011/03/find-all-subsets-of-given-set.html On Tue, Jul 26, 2011 at 9:41 PM, Vishal Thanki vishaltha...@gmail.comwrote: Here is the working code.. #include stdio.h #include stdlib.h int a[] = {1,2,3,4,5}; #define ARRLEN(a) (sizeof(a)/sizeof(a[0])) void print_comb(int len) { int tlen = len; int i, j, k; int al = ARRLEN(a); for (i = 0; i al; i++) { for (j=i+len-1; jal;j++) { for (k = i; k i+len-1; k++) { printf(%d , a[k]); } printf(%d\n, a[j]); } } } int main(int argc, char *argv[]) { int len = atoi(argv[1]); print_comb(len); return 0; } On Tue, Jul 26, 2011 at 5:18 PM, praneethn praneeth...@gmail.com wrote: check this link: *http://www.stefan-pochmann.info/spots/tutorials/sets_subsets/* On Tue, Jul 26, 2011 at 11:59 AM, sumit sumitispar...@gmail.com wrote: Given an array of size n, print all the possible subset of array of size k. eg:- input: a[]={1,2,3,4}, k = 2 output: 1,2 1,3 1,4 2,3 2,4 3,4 -- 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. -- 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] Facebook Interview question at NIT Warangal
@Ankur The link does has a very good explanation. Nice solution :) On Tue, Jul 26, 2011 at 10:47 PM, Kunal Patil kp101...@gmail.com wrote: @Ankur Garg: Nice explanation at the link given by u... On Tue, Jul 26, 2011 at 10:35 PM, Ankur Garg ankurga...@gmail.com wrote: Check this http://codesam.blogspot.com/2011/03/find-all-subsets-of-given-set.html On Tue, Jul 26, 2011 at 9:41 PM, Vishal Thanki vishaltha...@gmail.comwrote: Here is the working code.. #include stdio.h #include stdlib.h int a[] = {1,2,3,4,5}; #define ARRLEN(a) (sizeof(a)/sizeof(a[0])) void print_comb(int len) { int tlen = len; int i, j, k; int al = ARRLEN(a); for (i = 0; i al; i++) { for (j=i+len-1; jal;j++) { for (k = i; k i+len-1; k++) { printf(%d , a[k]); } printf(%d\n, a[j]); } } } int main(int argc, char *argv[]) { int len = atoi(argv[1]); print_comb(len); return 0; } On Tue, Jul 26, 2011 at 5:18 PM, praneethn praneeth...@gmail.com wrote: check this link: *http://www.stefan-pochmann.info/spots/tutorials/sets_subsets/* On Tue, Jul 26, 2011 at 11:59 AM, sumit sumitispar...@gmail.com wrote: Given an array of size n, print all the possible subset of array of size k. eg:- input: a[]={1,2,3,4}, k = 2 output: 1,2 1,3 1,4 2,3 2,4 3,4 -- 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. -- 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 Rajeev N B http://www.opensourcemania.co.cc -- 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] Facebook Interview Question from glassdoor
for 12 answer will be 36? is it ur question? -- 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] Facebook Interview Question....Heavy Number
Hi Geeks, One of The My Friend had This Question in His Technical Round of Facebook, I m going to share with you.lest see how geek approach this...Plz don't make this post spam..by discussing whats ur friend name, wich colge, etc etc..just share your approach, think solve the question, even Google search wont give you correct efficient approach ,answer for this question..so think your self.. O(n^2) Solution is Obvious ..but .it wont work for 10 million as a limit so not a good solution we have to solve it using best approach algo..as we have so here is the question...From Facebook... /* A non-negative integer is called heavy if the average value of its digits in decimal representation exceeds 7. Assume that 0 has average value of its digits equal to 0. For example the number 8698 is heavy, because the average value of its digits equal to (8+6+9+8)/4 = 7.75. The number 53141 has the average value of its digits equal to (5+3+1+4+1)/5 = 2.6, so it is not heavy. Write a function int heavy_decimal_count(int a,int b); that given two non-negative integers A and B returns the number of heavy integers in the interval [A..B] (both ends included). Assume that 0 =A = B = 200,000,000 Range Given ..It Really Matters Your Program should not give time out memory error For example, given A=8,675 and B=8,689 the function should return 5, because there are 5 heavy integers in range [8,675..8,689]: 8675 avg=6.5 8676 avg=6.75 8677 avg=7 8678 avg=7.25HEAVY 8679 avg=7.5 HEAVY 8680 avg=5.5 8681 avg=5.75 8682 avg=6 8683 avg=6.25 8684 avg=6.5 8685 avg=6.75 8686 avg=7 8687 avg=7.25HEAVY 8688 avg=7.5 HEAVY 8689 avg=7.75HEAVY you have to keep in mind for given range e.g given B=2 Billion Its Man Thing so what happen when A=1 Billion B=2 Billion */ Go Ahead Thanks Regards Shashank Mani Cell 9740852296 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Facebook Interview Question....Heavy Number
I am not sure if I can explain the general approach as efficiently as by explaining with an example: for the example you have give , say to find for A= 1,000,000,000 - 2,000,000,000 first two billion is not heavy. So finding from 1,000,000,000 - 1,999,999,999 It is:( 1 + sigma (x) ) 70 , where sigma( x ) is the sum of the rest of the nine integers. so, sigma(x) 69. so its now a problem of finding the sum of 9 digits to exceed the sum 69. If someone could work this permutation problem please put it up, I am trying to come up with an accurate formula for this. Generalizing, split the range into units that can be brought into this workable form and apply the formula. On Mon, Apr 4, 2011 at 8:52 AM, bittu shashank7andr...@gmail.com wrote: Hi Geeks, One of The My Friend had This Question in His Technical Round of Facebook, I m going to share with you.lest see how geek approach this...Plz don't make this post spam..by discussing whats ur friend name, wich colge, etc etc..just share your approach, think solve the question, even Google search wont give you correct efficient approach ,answer for this question..so think your self.. O(n^2) Solution is Obvious ..but .it wont work for 10 million as a limit so not a good solution we have to solve it using best approach algo..as we have so here is the question...From Facebook... /* A non-negative integer is called heavy if the average value of its digits in decimal representation exceeds 7. Assume that 0 has average value of its digits equal to 0. For example the number 8698 is heavy, because the average value of its digits equal to (8+6+9+8)/4 = 7.75. The number 53141 has the average value of its digits equal to (5+3+1+4+1)/5 = 2.6, so it is not heavy. Write a function int heavy_decimal_count(int a,int b); that given two non-negative integers A and B returns the number of heavy integers in the interval [A..B] (both ends included). Assume that 0 =A = B = 200,000,000 Range Given ..It Really Matters Your Program should not give time out memory error For example, given A=8,675 and B=8,689 the function should return 5, because there are 5 heavy integers in range [8,675..8,689]: 8675 avg=6.5 8676 avg=6.75 8677 avg=7 8678 avg=7.25 HEAVY 8679 avg=7.5 HEAVY 8680 avg=5.5 8681 avg=5.75 8682 avg=6 8683 avg=6.25 8684 avg=6.5 8685 avg=6.75 8686 avg=7 8687 avg=7.25 HEAVY 8688 avg=7.5 HEAVY 8689 avg=7.75 HEAVY you have to keep in mind for given range e.g given B=2 Billion Its Man Thing so what happen when A=1 Billion B=2 Billion */ Go Ahead Thanks Regards Shashank Mani Cell 9740852296 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Best, T Anand Karthik, Contact number: +91-9571552652 -- 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.