Interview Question
Software Engineer / DevelopersCountry: United States
Should we memoize based on the input string str ?
If yes, which is the best one to maintain a hashmap with str as key or maintain array with length of string ?
Maybe I didn't understand your solution, but running your pseudocode for 101 doesn't work:
. First level of recursion x = 0
. Take out "10" from the original string and increment x by one plus the recursive solution of '1' which is 1, so x is now 2.
. Take out "1" and solve recursively for "01", this is an invalid sub-solution so you should prune the recursive branch at this time, however, your algorithm continues the search for '0' and '1' (given that '01' fails to be considered a valid mapping) yielding 3 as the answer to the first level of recursion.
. Since 3 > 2, your algo returns 3 as the answer.
As I mentioned in the problem statement, answer should be 1.
Also, base case should be 1. According to the interviewer the empty string should return 1 as it is by itself a valid mapping.
@meh: Ops, 01 ... 09 are not valid as per question. Need to make adjustments.
@KidOfKop: You can memoize based on i,j indices that point into the overall string.
I should have given that question more of a quick look (I blame being conditioned by the usual CC questions where we are just forced to guess details and solve based on this).
Clarification:
For eg; if the mapping is given as
1: a
0 : a
10:aa
We get aa from 10, but we can do it either 1->a, 0->a or 10->aa. Do we count this as two or one? (i.e. do you count based on the splits, or based on the unique resulting string?)
I don't understand your question, however, I can say that { 0 : a } is an invalid mapping. Therefore "10" can only be mapped as the letter j given that zero maps to no character.
You need to clarify what the mapping can be then. Currently all you say is that we can have a mapping configure like so: <some random example>
Your question as stated does not preclude the example given above.
Please edit the question to exactly define what the mappings could be/could not be. Don't expect people to read your mind.
AND, DID YOU EVEN GET THIS QUESTION IN AN INTERVIEW? WHICH COMPANY WAS IT?
wow, no need to get all crazy with your caps lock dude...
<< watch-out-we-got-a-badass-over-here-meme.png >>
Regarding your question, sorry I assumed everyone is able to "read my mind", that mapping configuration is the only one allowed, but you can definitely complicate the problem more by allowing multiple mappings.
The question is from an actual interview.
DID YOU have this interview???????
Stop saying "from an actual interview." This is ALWAYS true for almost every question.
Assuming you are looking for different split points, rather than resulting string
A dynamic programming algorithm can be written to use the following recursion:
Count[m+1] = Sum_{j=0 to m} IsMapped(j, m+1)*Count[j]
Where IsMapped returns 0 or 1 depending on whether substring from position j to m+1 can be mapped or not (not including j, but including m+1).
Quadratic time, linear space.
If the resulting strings need to be unique, this becomes more complicated.
Btw, this is the recursive approach I used:
count(str):
if empty(str):
return 1
result := 0
if valid_map(str[-1]):
result := result + count(str[:-1])
if str.length > 1 and valid_map(str[-2]):
result := result + count(str[:-2])
return result
Based on this recursive formula, DP can be easily implemented by storing the last two previous solutions for n - 1 and n - 2 (like Fibonacci sequence) so that memory is constant and running time is linear.
Better indentation
count(str):
if empty(str):
return 1
result := 0
if valid_map(str[-1]):
result := result + count(str[:-1])
if str.length > 1 and valid_map(str[-2]):
result := result + count(str[:-2])
return result
Well, you are assuming the mapping is only for 1,2,..., 99.
Why can we have an arbitrary mapping such at
1: a
1000: b
0: c
123213123123: haveyouconsiderthis?
As someone else pointed out, I didn't clearly specify this on the problem statement, sorry about that. The mapping configuration I provided is the only one allowed, but it's definitely more interesting if the problem could allow multiple mappings, will try to adapt my solution for that!
Cheers.
#include <cstdio>
#include <iostream>
#include <map>
#include <vector>
#define DEBUG
//#undef DEBUG
using namespace std;
map<int, char> dic;
bool judgeValid(string code)
{
if(code.size() > 1 && code[0] == '0')
{
return false;
}
int num = atoi(code.c_str());
if(dic.find(num) != dic.end())
{
return true;
}
return false;
}
char getValue(string code)
{
int num = atoi(code.c_str());
return dic[num];
}
void printCode(int cur, vector<char> dcode, string source)
{
if(cur == source.size())
{
for(vector<char>::iterator it = dcode.begin(); it != dcode.end(); ++it)
{
cout << (*it);
}
cout << endl;
return;
}
string tmp;
for(int i = cur; i < source.size(); ++i)
{
tmp.push_back(source[i]);
if(judgeValid(tmp))
{
dcode.push_back(getValue(tmp));
printCode(i + 1, dcode, source);
dcode.pop_back();
}
}
}
#ifdef DEBUG
#endif
#ifdef DEBUG
void testMap()
{
for(map<int, char>::iterator it = dic.begin(); it != dic.end(); ++it)
{
cout << it->first << ", " << it->second << endl;
}
}
void testJudgeValid()
{
bool tmp;
vector<string> tvec;
tvec.push_back(string("10"));
tvec.push_back(string("16"));
tvec.push_back(string("30"));
tvec.push_back(string("01"));
tvec.push_back(string("00"));
tvec.push_back(string("8"));
for(vector<string>::iterator it = tvec.begin(); it != tvec.end(); ++it)
{
tmp = judgeValid(*it);
cout << (tmp ? "True" : "False") << endl;
}
}
void testPrintCode()
{
vector<string> tvec;
tvec.push_back("12632");
tvec.push_back("111");
tvec.push_back("101");
for(vector<string>::iterator it = tvec.begin(); it != tvec.end(); ++it)
{
cout << "Test " << (*it).c_str() << ":" << endl;
printCode(0, vector<char>(), *it);
cout << endl;
}
}
#endif
int main()
{
int i = 0;
for(i = 1; i <= 26; ++i)
{
dic[i] = char('a' + i - 1);
}
#ifdef DEBUG
testMap();
testJudgeValid();
testPrintCode();
#endif
return 0;
}
1. Using recursive method to solve the problem;
2. Using a function to judge if a code is valid dictionary key;
3. Assuming the input string is source, and the last valid key's end position is at cur, cur >= 0 and cur < source.size();
1)From this position,
if string(source[cur], ..., source[cur + i0]) is a valid key,
if string(source[cur], ..., source[cur + i1]) is a valid key,
...
if string(source[cur], ..., source[cur + in]) is a valid key,
2)For each situation,
add the corresponding value into a container, and continue processing it from current end position;
3)If cur == source.size()
Print current contents and return.
private int count=0;
public Calculate() {
noOfWays("" ,"1263256732");
System.out.println(count);
}
private void noOfWays(String B ,String A){
if(A.length()==0){
count++;
System.out.println(B);
return;
}
if(A.length()>1){
char c1 = A.charAt(0);
char c2 = A.charAt(1);
int a1 = c1 -'0';
int a2 = c2 - '0';
if(a1!=0){
char b = (char)('a'+a1-1);
noOfWays(B + b, A.substring(1));
}
if(a1>0 && a1<3 && a2<=6){
char b = (char)('a' + (a1*10 + a2)-1);
noOfWays(B + b, A.substring(2));
}
}else{
char c1 = A.charAt(0);
int a1 = c1 -'0';
noOfWays(B + (char)('a'+a1-1), A.substring(1));
}
}
private void DifferentMapping(string input, string current, int index)
{
if (index == input.Length)
{
Console.WriteLine(current);
//index--;
}
else
{
string intToMap = "";
intToMap = input[index].ToString();
DifferentMapping(input, current + Map(intToMap), index+1);
intToMap = intToMap + input[index];
if (Convert.ToInt32(intToMap) <= 26 && index < input.Length-1)
{
DifferentMapping(input, current + Map(intToMap), index+2);
}
}
}
private char Map(string intToMap){
return (char)(Convert.ToInt32(intToMap) + ((int)'a'));
}
recursive...
Because of overlapping subproblems, memoize to make it DP (top down DP).
- S O U N D W A V E March 23, 2014If you are NOT that nervous in interview, do it bottom up using a table.