Interview Question for Software Engineer / Developers

Country: United States

Comment hidden because of low score. Click to expand.
0
of 0 vote

recursive...

``````function(str) {

If str.length < 1 return 0;

x=0; //number of ways IF we can map first two digits

//if first two characters have a valid mapping, then count the ways into 'x'
If str.length >= 2 and str[1 .. 2] is in range(1,26) {
x = 1 + function(str[2 ... n]);
}

//max of interpreting first 2 digits as valid map OR first digit as valid
return max( x, 1+function(str[1 ... n] );

}``````

Because of overlapping subproblems, memoize to make it DP (top down DP).

If you are NOT that nervous in interview, do it bottom up using a table.

Comment hidden because of low score. Click to expand.
0
of 0 votes

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 ?

Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

Comment hidden because of low score. Click to expand.
0
of 0 votes

@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).

Comment hidden because of low score. Click to expand.
0
of 0 votes

^^^^
Memoize with one index i

Comment hidden because of low score. Click to expand.
0
of 0 vote

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?)

Comment hidden because of low score. Click to expand.
0
of 0 votes

First line should read: Clarfication NEEDED:

Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

Comment hidden because of low score. Click to expand.
0
of 0 votes

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?

Comment hidden because of low score. Click to expand.
0
of 0 votes

Perhaps you understand the question better now.

Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

Comment hidden because of low score. Click to expand.
0
of 0 votes

DID YOU have this interview???????

Stop saying "from an actual interview." This is ALWAYS true for almost every question.

Comment hidden because of low score. Click to expand.
0
of 0 votes

Hi @Meh: Which company was this? Thanks.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 votes

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``````

Comment hidden because of low score. Click to expand.
0
of 0 votes

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?``````

Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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));
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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'));
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

What about this DP solution
Let S contains the given number

``````F(n) = F(n-1) + F(n-2), if S[n-1,n] <= 26
F(n-1),                 if   S[n-1,n] > 26
F(1) = 1
F(2) = 2, if S[1,2] <= 26 else 1``````

Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More