Interview Question
SDE-2sCountry: United States
int WaysCount(string const &s, int alphabet_size, int idx = 0)
{
if (idx < 0 ||
idx > s.size())
{
return 0;
}
if (idx == s.size()) {
return s.empty() ? 0 : 1;
}
if (s[idx] == '0') {
return 0;
}
int count = 0;
for (int i = idx; i < s.size(); ++i) {
if (stoi(s.substr(idx, i - idx + 1)) > alphabet_size) {
break;
}
count += WaysCount(s, alphabet_size, i + 1);
}
return count;
}
assumption: "01" is not valid and does not mean "1"
I don't see a combinatorics approach that will lead to success, but it can be written as recursion:
dp(i) = sum[
dp(i-1) if 0 < arr[i] < 10
dp(i-2) if i > 0 and 0 < (arr[i-1] * 10 + arr[i]) < 27
0 if arr[i] == 0 || (i > 0 && arr[i-1] * 10 + arr[i] > 26)
0 if i < -1
1 if i == -1
]
with a functional programming language that would be it.
With an imperative language, this can be implemented in O(n) time complexity and O(1) space complexity. Below the simplified version with O(n) time and O(n) space.
#include <vector>
#include <iostream>
using namespace std;
int countNumberOfWaysToDecode(const vector<unsigned char>& arr)
{
if (arr.size() == 0) return 1; // only interpretation is "empty" or "null"
vector<unsigned int> dp(arr.size(), 0);
// note the repeated comparisons for i > 0, i > 1 could be simplified by
// extracting the base case from the loop (which would be nicer, but less compact)
for (size_t i = 0; i < arr.size(); ++i) {
if (arr[i] > 0 && arr[i] < 10) {
dp[i] = (i > 0) ? dp[i - 1] : 1;
}
if (i > 0 && arr[i - 1] > 0 && (arr[i - 1] * 10 + arr[i]) < 27) {
dp[i] += (i > 1) ? dp[i - 2] : 1;
}
}
return dp.back();
}
// some test cases
int main()
{
cout << (countNumberOfWaysToDecode({ 2,6,2,6 }) == 4) << endl; // 2,6,2,6; 26,2,6; 26,26; 2,6,26
cout << (countNumberOfWaysToDecode({ 0,1,1 }) == 0) << endl; // invalid
cout << (countNumberOfWaysToDecode({ 1,1 }) == 2) << endl; // 1,1; 11
cout << (countNumberOfWaysToDecode({ }) == 1) << endl; // null
cout << (countNumberOfWaysToDecode({ 2,7 }) == 1) << endl; // 2,7;
cout << (countNumberOfWaysToDecode({ 2,1,1,1 }) == 5) << endl; // 2,1,1,1; 21,1,1; 21,11; 2,11,1; 2,1,11
}
@Netr: Do I interpret nCn-v right if I assume you mean nC(n-v) = "choose (n-v) from n"
for "1010" it has two valid groups, so it's 4C(4-2), which is 6 (type 4 choose 2 into wolfram alpha...). this is hard to understand, same is with "1111" where the interpretations are (11)11; 1(11)1; 11(11); 1111 which are 4.
Two things I don't understand from your proposal,
1) "1010" can't be treated the same way as "1111"
2) the formula in general seems not complete, because you don't choose 2 from 4, you choose 0,2 or 4 from 4 but not exactly, because you can't choose any 2 only index 0,1 or index 2,0 ... I don't understand how you come up with the nC(n-v).
Actually there would be 18 combinations for '132241043'
132241043
[1]
[1,3][13]
[1,3,2][13,2]
[1,3,2,2][1,3,22][13,2,2][13,22]
[1,3,2,2,4][1,3,2,24][1,3,22,4][13,2,2,4][13,2,24][13,22,4]
[1,3,2,2,4,1][1,3,2,24,1][1,3,22,4,1][13,2,2,4,1][13,2,24,1][13,22,4,1]
[1,3,2,2,4,1,0][1,3,2,2,4,10][1,3,2,24,1,0][1,3,2,24,10][1,3,22,4,1,0][1,3,22,4,10][13,2,2,4,1,0][13,2,2,4,10][13,2,24,1,0][13,2,24,10][13,22,4,1,0][13,22,4,10]
[1,3,2,2,4,1,0,4][1,3,2,2,4,1,04][1,3,2,2,4,10,4][1,3,2,24,1,0,4][1,3,2,24,1,04][1,3,2,24,10,4][1,3,22,4,1,0,4][1,3,22,4,1,04][1,3,22,4,10,4][13,2,2,4,1,0,4][13,2,2,4,1,04][13,2,2,4,10,4][13,2,24,1,0,4][13,2,24,1,04][13,2,24,10,4][13,22,4,1,0,4][13,22,4,1,04][13,22,4,10,4]
public static void main(String[] args) {
String str = "132241043";
int n = combinations(str);
System.out.println(n);
}
/**
* A message containing letters from A-Z is being encoded to numbers using
* the following mapping:
*
* 'A' -> 1 'B' -> 2 ... 'Z' -> 26 Given an encoded message containing
* digits, determine the total number of ways to decode it.
*
* For example, Given encoded message "12", it could be decoded as "AB" (1
* 2) or "L" (12).
*/
public static int combinations(String str) {
int n = str.length();
int[] dp = new int[n];
dp[0] = 1;
char[] ch = str.toCharArray();
boolean multiply = true;
for (int i = 1; i < n; i++) {
String s = String.valueOf(String.valueOf(ch[i - 1]) + String.valueOf(ch[i]));
if (multiply && Integer.parseInt(s) <= 26){
dp[i] = dp[i - 1] * 2;
multiply = false;
}else if(!multiply && Integer.parseInt(s) <= 26){
dp[i] = (dp[i - 1]/2) + (dp[i - 1]/2) * 2;
multiply = true;
}else{
multiply = true;
dp[i] = dp[i - 1];
}
}
return dp[n - 1];
}
@Alex, that's correct, Netr added an extra "2" in between in the list. For the "132241043" pattern I agree, 6 combinations, for "1322241043" there are 10.
@studip.innovations: I think you are supposed to interprete the whole string, and count after that "132241043" definitely can't be interpreted as "1" unless you skip all following characters. "0" alone is no valid character, as the "0" comes from "10" and the range is 1..26 not 0..25
@ChrisK Yes, I am aware that my initial code was wrong, I deleted as soon I posted it (this site does not delete it immediately, this is why you were able to view it)
Here is a working solution that also print the groups found in a more human readable form which uses queue:
int countDecodingOptions(const std::vector<int>& numbers)
{
// The result
int options = 0;
// For visualization, we also keep track of the prefix this is why I use here std::pair
std::queue<std::pair<std::vector<int>, std::string> > q;
q.push(std::make_pair(numbers, ""));
while(!q.empty()) {
std::pair<std::vector<int>, std::string> e = q.front();
std::vector<int> v = e.first;
std::string prefix = e.second;
q.pop();
if(v.empty()) {
// All numbers processed successfully, increase the options counter and print the group found
++options;
std::cout << prefix << std::endl;
continue;
}
int n0 = v[0];
if(n0 != 0) {
// Single digit branch
v.erase(v.begin());
q.push(std::make_pair(v, prefix + std::to_string(n0) + " "));
if(!v.empty()) {
int n1 = v[0];
int tmp = (n0 * 10 + n1);
if(tmp < 27) {
// Two digit branch
v.erase(v.begin());
q.push(std::make_pair(v, prefix + std::to_string(tmp) + " "));
}
}
}
}
return options;
}
Example execution:
countDecodingOptions({ 1, 2, 2, 1 });
12 21
1 2 21
1 22 1
12 2 1
1 2 2 1
countDecodingOptions({ 2, 1, 1, 1 });
21 11
2 1 11
2 11 1
21 1 1
2 1 1 1
#include <iostream>
using namespace std;
char Codes[27];
void Print(const string& code, string result, int pos)
{
if(pos == code.length())
{
cout << result << endl;
return;
}
Print(code, result + Codes[code[pos] - '0'], pos+1);
if(pos == (code.length()-1))
return;
short index = (code[pos]-'0')*10+code[pos+1]-'0';
if(index <= 26)
Print(code, result + Codes[index], pos+2);
}
int main()
{
for (short i = 1; i <= 26 ; i++)
Codes[i] = 'A' + i - 1;
string code = "121345161718";
Print(code, "", 0);
return 0;
}
You need to write code to just count a few things, and the rest is mathematics,
First write simple code count the number of possible valid two digit groups [10 -> 26]
Next,If
valid groups = v
message length = n
number of possible ways you can decode with one group is nCn-2+1 = nCn1
number of possible ways you can decode with two groups is nCn-4+2 = nCn-2
....
number of possible ways you can decode with "v" groups is nCn-2*v+v = nCn-v
{{nCn-v}}
{{You need write code just to count the number of valid groups, rest is mathematics.
Count all the valid two digit groups, [10 -> 26]
If v is the number of valid groups,
n is the length of the message,
Then number of ways we can decode the message with one group = nCn-2+1 = nCn-1
Then number of ways we can decode the message with two groups = nCn-4+2 = nCn-2
Then number of ways we can decode the message with "v" groups = nCn-2*v+v = nCn-v
Calculate nCn-v
}}
{{
You need write code just to count the number of valid groups, rest is math,
Count all the valid two digit groups, [10 -> 26]
If v is the number of valid groups,
n is the length of the message,
Then number of ways we can decode the message with one group = nCn-2+1 = nCn-1
Then number of ways we can decode the message with two groups = nCn-4+2 = nCn-2
Then number of ways we can decode the message with "v" groups = nCn-2*v+v = nCn-v
Calculate nCn-v
}}
same as above solution without O(n) space and less constant cost in the loop.
- Chris September 26, 2017