CareerCup

Here is the solution in C++. Quite straightforward, and true the stack size would be O(n.size)

First call is PrintStrings("", n, 0, n.size)

const char phonePad[][5] =
{
	{'1', ' ', '\0', '\0', '\0'},
	{'3', 'a', 'b', 'c', '\0'},
	{'3', 'd', 'e', 'f', '\0'},
	{'3', 'g', 'h', 'i', '\0'},
	{'3', 'j', 'k', 'l', '\0'},
	{'3', 'm', 'n', 'o', '\0'},
	{'4', 'p', 'q', 'r', 's'},
	{'3', 't', 'u', 'v', '\0'},
	{'4', 'w', 'x', 'y', 'z'},
	{'1', '+', '\0', '\0', '\0'}
};

static void PrintStrings(std::string prefix, int n[], int startIndex, int size)
{
	const char* optionsStr = &phonePad[n[startIndex]][0];
	int options = atoi(optionsStr);
	for (int optionIndex = 1; optionIndex < 1 + options; ++optionIndex)
	{
		std::string newPrefix = prefix + phonePad[n[startIndex]][optionIndex];
		if (startIndex == size - 1)
		{
			printf("%s\n", newPrefix.c_str());
		}
		else
		{
			PrintStrings(newPrefix, n, startIndex + 1, size);
		}
	}
}

How was it a trick question? If you are recursing, the space complexity is unlikely to be O(1). Is this where you messed up?

That said, I highly doubt you were rejected just because you got that one thing wrong. That's not how interview evaluating works.

Hi Gayle, Thank you for answering on my comment. My mind was really spinning about this question. I answered O(4^n) stack space - but I was sure I was wrong and he said don't you think its too high to claim. I struggled a bit - the correct answer the interviewer told me was O(n).
It really took some time for me to wrap my brain at the end of the interview.

I was looking for some clues in your book - "cracking the coding interview" to strengthen my ability to calculate the stack space for problems like these and other like
What will be the stack space requirement for a BFS on a balanced tree - I would recommend if possible have a small section to orient students like me on this topic a little)

(I consider your book to be my guide, mistakes if any are mine).

But yeah, my solution was correct, I checked it using a IDE if it would worked fine (after the interview) and the interviewer agreed it was correct. He then asked me the iterative solution (just concept - not to code) - I told we can use emulate recursion using a stack. He said OK and nothing else, and I was mistaken here too (I guess?) because this is really sub optimal. The really optimal solution is to iterate through and keep increasing the low value to high value and print number.
I did not mention the optimal solution as he seemed satisfied with my first thought. I could have come to the optimal strategy if he said - "try harder". Probably this was just a communication flow mismatch.

I think this was second mistake - probably enough to reject?

clearly, if length of number is 10, than your recursive program will require a stack no greater than 10 elements. when stack becomes full it prints that combination and pops top chars to make space for next chars in the combination. remember same stack can be used multiple times. so space complexity will be O(n).

nyways, i m curious abt how you manage to print all combinations without using stack with recursive prog..

I believe you were thinking of a backtracking solution by "keep increasing the low value to high value". If it was on your mind, you should have mentioned the idea. Seems a good optimization but could be annoying to program, especially in an interview. You would require a method which takes a string and gives the next string in the sequence. You would also require a smarter data structure to store the phone pad alphabets which would make it easier to query the next alphabet given the previous one.

Same idea as above but way simpler.


#define NUMWIDTH 7

char sary[][5] = {"abc\0","def\0","ghi\0","jkl\0","mno\0", "pqrs", "tuv\0", "wxyz"};
char getChar(int nNum, int nPos)
{
return sary[nNum-2][ nPos];
}
char getLen(int nNum)
{
return strlen(sary[nNum-2]);
}
void telephoneword( int nPos, string s)
{
if ( nPos ==NUMWIDTH)
{
printf("\t %s", s.c_str());
}
else
for ( int i = 2 ; i < 10 ; i++)
{
for ( int j=0; j < getLen(i) ; j++)
telephoneword( nPos + 1, s + getChar(i, j));
}
}

telephoneword( 0, "");

cant this be solved using dp??
ie. if str[i]==str[i-1]&& str[i-2] && str[i]!='7'
ans[i]=ans[i-1]+ans[i-2]+ans[i-3];
else if str[i]==str[i-1]&& str[i-2] && str[i-3] && str[i]=='7'
ans[i]=ans[i-1]+ans[i-2]+ans[i-3]+ans[i-4];
else if str[i]==str[i-1]
ans[i]=ans[i-1]+ans[i-2];
else
ans[i]=ans[i-1];

ans=ans[n-1]

#include <stdio.h>
#include <string.h>
char num[][5] = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
void printchar(char * numstr, char * buf, int pos)
{

if(strlen(numstr))
{

int n = *numstr - 0x30;
char * chars = num[n];

if(strlen(chars))
{
while(*chars)
{
buf[pos] = *chars;
//printf("%c", buf[pos]);
printchar(numstr + 1, buf, pos + 1);
chars ++;
}
}
else
{
printchar(numstr + 1, buf, pos);
}
}
else
{
buf[pos] = '\0';
printf("%s\n",buf);
}
}

void main()
{
char *numstr = "91276";
char *buf = malloc(strlen(numstr));

printchar(numstr, buf, 0);
free(buf);
}

import sys, pdb

def telephone(n,pos,sz,ans):
    global trans, cnt

    if sz==0:
        cnt+=1
        print cnt,''.join(ans)
        return
        
    C=trans[n[pos]]
    for c in C:
        ans[pos]=c
        telephone(n,pos+1,sz-1,ans)

if __name__=='__main__':
    trans={'0':"",'1':"abc",'2':"def",'3':"ghi",'4':"jkl",'5':"mno",'6':"pqr",'7':"stu",'8':"vwx",'9':"yz"}
    
    num='12345600'
    cnt=0
    telephone(num,0,len(num),['']*len(num))