Re: [algogeeks] Re: Facebook Interview Question from glassdoor
@sravan, What i meant was get the jth digit in the representation of i to the base NUM_PER_DIGIT. ie 3rd digit of (2137)8 which is 2.. 7 is the 0th digit, 3 being 1st digit, 1 being 2nd digit and 2 being 3rd digit.Here 2137 is a base 8 representation. Thanks, Immanuel On Tue, May 24, 2011 at 6:37 PM, sravanreddy001 wrote: > @Immanuel: > In the iteretive approach, can you tell me what you meant by this function. > A code is not required, but, how are we going to calculate? the method name > is little confusing. > > The recursive is good.. but.. I'm looking at the iterative approach. > > ---> getJthDigitinItotheBaseNumPerDigit(NUM_PER_DIGIT,i,j); > > Thanks > Sravan. > > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Facebook Interview Question from glassdoor
@Immanuel: In the iteretive approach, can you tell me what you meant by this function. A code is not required, but, how are we going to calculate? the method name is little confusing. The recursive is good.. but.. I'm looking at the iterative approach. ---> getJthDigitinItotheBaseNumPerDigit(NUM_PER_DIGIT,i,j); Thanks Sravan. -- 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: Facebook Interview Question from glassdoor
@Anuj, true.This will optimise the solution by reducing the amount of stack space used for recursion. NUM_PER_DIGIT = 3 char c[][NUM_PER_DIGIT] = {"abc","def",...}; char n[] = 2156169 (number is pressed); int k=7; char * s = (char *) malloc(sizeof(char) * k); void printAllCombinations (int k, char *s, int count) { if (count >= k - 1) { s[k] = '\0'; print (s); } else { for (i =0; i< NUM_PER_DIGIT; i++) { s[i] = c[n[count]][i]; printAllCombinations(k,s, count+1); } } } printAllCombinations (k,s,0); Thanks, Immanuel On Mon, May 23, 2011 at 10:41 PM, anuj agarwal wrote: > Immanuel, > We can keep c and n arrays as global variable as they are not part of state > of the recursion. > > Anuj Agarwal > Engineering is the art of making what you want from things you can get. > > > > On Mon, May 23, 2011 at 10:04 PM, immanuel kingston < > kingston.imman...@gmail.com> wrote: > >> small correction >> >> On Mon, May 23, 2011 at 9:46 PM, immanuel kingston < >> kingston.imman...@gmail.com> wrote: >> >>> A Recursive soln: >>> >>> >>> NUM_PER_DIGIT = 3 >>> char c[][NUM_PER_DIGIT] = {"abc","def",...}; >>> >>> char n[] = 2156169 (number is pressed); >>> int k=7; >>> char * s = (char *) malloc(sizeof(char) * k); >>> >>> void printAllCombinations (char c[][], char n[], int k, char *s, int >>> count) { >>> if (count >= k - 1) { >>> s[k] = '\0'; >>> print (s); >>> } else { >>> for (i =0; i< NUM_PER_DIGIT; i++) { >>> *s[i] = c[n[count]][i];* >>> >>> printAllCombinations(c,n,k,s, count+1); >>> } >>> } >>> } >>> printAllCombinations (c,n,k,s,0); >>> >>> Please correct me if my understanding is wrong. >>> >>> Thanks, >>> Immanuel >>> >>> >>> On Mon, May 23, 2011 at 9:33 PM, immanuel kingston < >>> kingston.imman...@gmail.com> wrote: >>> Extending the above soln: NUM_PER_DIGIT = 3 char c[][NUM_PER_DIGIT] = {"abc","def",...}; char n[] = 2156169 (number is pressed); int k=7; for i <-- 0 to NUM_PER_DIGIT ^ k String s=""; for j <-- 0 to k int index = getJthDigitinItotheBaseNumPerDigit(NUM_PER_DIGIT,i,j); // ie get 1st digit in (022)3 returns 2 s += c[n[j]][index]; print(s); Time Complexity: O((NUM_PER_DIGIT^k)*k^2); On Mon, May 23, 2011 at 7:32 PM, anshu mishra < anshumishra6...@gmail.com> wrote: > the same question i have asked in microsoft interview. (if it is the > same :P) > > for 12 perutation are (ad, ae, af, bd, be, bf, cd, ce ,cf); > i have given them 3 solution(recusrsive, stack based) and the last one > what they wanted. > > take a tertiary number(n) = 3^(number of digits) in case of 12 it is > equals to 2; > > i m solving the save problem. assuming on every key there are only 2 > alphabets. > > char c[][2] = {ab , cd, ..}; > > char n[] = 2156169 (number is pressed); > so k = 7; > for (i = 0; i < (1< string s = ""; > for (j = 0; j < k; j++){ > s += c[n[j]][i & (1< } > print(s); > } > > same logic u can use for tertiary too. > > -- > You received this message because you are subscribed to the Google > Groups "Algorithm Geeks" group. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > >>> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to algogeeks@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com. >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Facebook Interview Question from glassdoor
Immanuel, We can keep c and n arrays as global variable as they are not part of state of the recursion. Anuj Agarwal Engineering is the art of making what you want from things you can get. On Mon, May 23, 2011 at 10:04 PM, immanuel kingston < kingston.imman...@gmail.com> wrote: > small correction > > On Mon, May 23, 2011 at 9:46 PM, immanuel kingston < > kingston.imman...@gmail.com> wrote: > >> A Recursive soln: >> >> >> NUM_PER_DIGIT = 3 >> char c[][NUM_PER_DIGIT] = {"abc","def",...}; >> >> char n[] = 2156169 (number is pressed); >> int k=7; >> char * s = (char *) malloc(sizeof(char) * k); >> >> void printAllCombinations (char c[][], char n[], int k, char *s, int >> count) { >> if (count >= k - 1) { >> s[k] = '\0'; >> print (s); >> } else { >> for (i =0; i< NUM_PER_DIGIT; i++) { >> *s[i] = c[n[count]][i];* >> >> printAllCombinations(c,n,k,s, count+1); >> } >> } >> } >> printAllCombinations (c,n,k,s,0); >> >> Please correct me if my understanding is wrong. >> >> Thanks, >> Immanuel >> >> >> On Mon, May 23, 2011 at 9:33 PM, immanuel kingston < >> kingston.imman...@gmail.com> wrote: >> >>> Extending the above soln: >>> >>> NUM_PER_DIGIT = 3 >>> char c[][NUM_PER_DIGIT] = {"abc","def",...}; >>> >>> char n[] = 2156169 (number is pressed); >>> int k=7; >>> >>> for i <-- 0 to NUM_PER_DIGIT ^ k >>> String s=""; >>> for j <-- 0 to k >>> int index = >>> getJthDigitinItotheBaseNumPerDigit(NUM_PER_DIGIT,i,j); // ie get 1st digit >>> in (022)3 returns 2 >>> s += c[n[j]][index]; >>> print(s); >>> >>> >>> Time Complexity: O((NUM_PER_DIGIT^k)*k^2); >>> >>> >>> On Mon, May 23, 2011 at 7:32 PM, anshu mishra >> > wrote: >>> the same question i have asked in microsoft interview. (if it is the same :P) for 12 perutation are (ad, ae, af, bd, be, bf, cd, ce ,cf); i have given them 3 solution(recusrsive, stack based) and the last one what they wanted. take a tertiary number(n) = 3^(number of digits) in case of 12 it is equals to 2; i m solving the save problem. assuming on every key there are only 2 alphabets. char c[][2] = {ab , cd, ..}; char n[] = 2156169 (number is pressed); so k = 7; for (i = 0; i < (1<>>> string s = ""; for (j = 0; j < k; j++){ s += c[n[j]][i & (1<>>> } print(s); } same logic u can use for tertiary too. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. >>> >>> >> > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Facebook Interview Question from glassdoor
small correction On Mon, May 23, 2011 at 9:46 PM, immanuel kingston < kingston.imman...@gmail.com> wrote: > A Recursive soln: > > > NUM_PER_DIGIT = 3 > char c[][NUM_PER_DIGIT] = {"abc","def",...}; > > char n[] = 2156169 (number is pressed); > int k=7; > char * s = (char *) malloc(sizeof(char) * k); > > void printAllCombinations (char c[][], char n[], int k, char *s, int count) > { > if (count >= k - 1) { > s[k] = '\0'; > print (s); > } else { > for (i =0; i< NUM_PER_DIGIT; i++) { > *s[i] = c[n[count]][i];* > printAllCombinations(c,n,k,s, count+1); > } > } > } > printAllCombinations (c,n,k,s,0); > > Please correct me if my understanding is wrong. > > Thanks, > Immanuel > > > On Mon, May 23, 2011 at 9:33 PM, immanuel kingston < > kingston.imman...@gmail.com> wrote: > >> Extending the above soln: >> >> NUM_PER_DIGIT = 3 >> char c[][NUM_PER_DIGIT] = {"abc","def",...}; >> >> char n[] = 2156169 (number is pressed); >> int k=7; >> >> for i <-- 0 to NUM_PER_DIGIT ^ k >> String s=""; >> for j <-- 0 to k >> int index = getJthDigitinItotheBaseNumPerDigit(NUM_PER_DIGIT,i,j); >> // ie get 1st digit in (022)3 returns 2 >> s += c[n[j]][index]; >> print(s); >> >> >> Time Complexity: O((NUM_PER_DIGIT^k)*k^2); >> >> >> On Mon, May 23, 2011 at 7:32 PM, anshu mishra >> wrote: >> >>> the same question i have asked in microsoft interview. (if it is the same >>> :P) >>> >>> for 12 perutation are (ad, ae, af, bd, be, bf, cd, ce ,cf); >>> i have given them 3 solution(recusrsive, stack based) and the last one >>> what they wanted. >>> >>> take a tertiary number(n) = 3^(number of digits) in case of 12 it is >>> equals to 2; >>> >>> i m solving the save problem. assuming on every key there are only 2 >>> alphabets. >>> >>> char c[][2] = {ab , cd, ..}; >>> >>> char n[] = 2156169 (number is pressed); >>> so k = 7; >>> for (i = 0; i < (1<>> string s = ""; >>> for (j = 0; j < k; j++){ >>> s += c[n[j]][i & (1<>> } >>> print(s); >>> } >>> >>> same logic u can use for tertiary too. >>> >>> -- >>> You received this message because you are subscribed to the Google Groups >>> "Algorithm Geeks" group. >>> To post to this group, send email to algogeeks@googlegroups.com. >>> To unsubscribe from this group, send email to >>> algogeeks+unsubscr...@googlegroups.com. >>> For more options, visit this group at >>> http://groups.google.com/group/algogeeks?hl=en. >>> >> >> > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Facebook Interview Question from glassdoor
A Recursive soln: NUM_PER_DIGIT = 3 char c[][NUM_PER_DIGIT] = {"abc","def",...}; char n[] = 2156169 (number is pressed); int k=7; char * s = (char *) malloc(sizeof(char) * k); void printAllCombinations (char c[][], char n[], int k, char *s, int count) { if (count >= k - 1) { s[k] = '\0'; print (s); } else { for (i =0; i< NUM_PER_DIGIT; i++) { s[i] = c[count][i]; printAllCombinations(c,n,k,s, count+1); } } } printAllCombinations (c,n,k,s,0); Please correct me if my understanding is wrong. Thanks, Immanuel On Mon, May 23, 2011 at 9:33 PM, immanuel kingston < kingston.imman...@gmail.com> wrote: > Extending the above soln: > > NUM_PER_DIGIT = 3 > char c[][NUM_PER_DIGIT] = {"abc","def",...}; > > char n[] = 2156169 (number is pressed); > int k=7; > > for i <-- 0 to NUM_PER_DIGIT ^ k > String s=""; > for j <-- 0 to k > int index = getJthDigitinItotheBaseNumPerDigit(NUM_PER_DIGIT,i,j); > // ie get 1st digit in (022)3 returns 2 > s += c[n[j]][index]; > print(s); > > > Time Complexity: O((NUM_PER_DIGIT^k)*k^2); > > > On Mon, May 23, 2011 at 7:32 PM, anshu mishra > wrote: > >> the same question i have asked in microsoft interview. (if it is the same >> :P) >> >> for 12 perutation are (ad, ae, af, bd, be, bf, cd, ce ,cf); >> i have given them 3 solution(recusrsive, stack based) and the last one >> what they wanted. >> >> take a tertiary number(n) = 3^(number of digits) in case of 12 it is >> equals to 2; >> >> i m solving the save problem. assuming on every key there are only 2 >> alphabets. >> >> char c[][2] = {ab , cd, ..}; >> >> char n[] = 2156169 (number is pressed); >> so k = 7; >> for (i = 0; i < (1<> string s = ""; >> for (j = 0; j < k; j++){ >> s += c[n[j]][i & (1<> } >> print(s); >> } >> >> same logic u can use for tertiary too. >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to algogeeks@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com. >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Facebook Interview Question from glassdoor
Extending the above soln: NUM_PER_DIGIT = 3 char c[][NUM_PER_DIGIT] = {"abc","def",...}; char n[] = 2156169 (number is pressed); int k=7; for i <-- 0 to NUM_PER_DIGIT ^ k String s=""; for j <-- 0 to k int index = getJthDigitinItotheBaseNumPerDigit(NUM_PER_DIGIT,i,j); // ie get 1st digit in (022)3 returns 2 s += c[n[j]][index]; print(s); Time Complexity: O((NUM_PER_DIGIT^k)*k^2); On Mon, May 23, 2011 at 7:32 PM, anshu mishra wrote: > the same question i have asked in microsoft interview. (if it is the same > :P) > > for 12 perutation are (ad, ae, af, bd, be, bf, cd, ce ,cf); > i have given them 3 solution(recusrsive, stack based) and the last one what > they wanted. > > take a tertiary number(n) = 3^(number of digits) in case of 12 it is equals > to 2; > > i m solving the save problem. assuming on every key there are only 2 > alphabets. > > char c[][2] = {ab , cd, ..}; > > char n[] = 2156169 (number is pressed); > so k = 7; > for (i = 0; i < (1< string s = ""; > for (j = 0; j < k; j++){ > s += c[n[j]][i & (1< } > print(s); > } > > same logic u can use for tertiary too. > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Facebook Interview Question from glassdoor
the same question i have asked in microsoft interview. (if it is the same :P) for 12 perutation are (ad, ae, af, bd, be, bf, cd, ce ,cf); i have given them 3 solution(recusrsive, stack based) and the last one what they wanted. take a tertiary number(n) = 3^(number of digits) in case of 12 it is equals to 2; i m solving the save problem. assuming on every key there are only 2 alphabets. char c[][2] = {ab , cd, ..}; char n[] = 2156169 (number is pressed); so k = 7; for (i = 0; i < (1
[algogeeks] Re: Facebook Interview Question from glassdoor
I didn't get the question actually. I have copied the post(the question). but i dont think for 12, 36 can be the answer. We have to go for the permutation of the telephone number i guess after substituting for each number the corresponding set of alphabets. The question given is - "Given a telephone number, find all the permutations of the letters assuming 1=abc, 2=def, etc." and the solution given is - Standard "find all permutations" of XYZ, except for each XYZ, you include permutations for each X0...Xn, Y0...Yn, etc On May 23, 5:51 pm, anshu mishra wrote: > 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.