Interview Question for SDE-2s


Country: United States




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

same as above solution without O(n) space and less constant cost in the loop.

unsigned int countNumberOfWaysToDecode(const vector<unsigned char>& arr)
{
	if (arr.size() == 0) return 1; // only interpretation is "empty" or "null"	
	unsigned int dpim2 = arr[0] > 0 ? 1 : 0; // dp[i-2]
	unsigned int dpim1 = arr[0] > 0 && arr[0] < 10 ? 1 : 0; // dp[i-1]
	unsigned int dpi; // dp[i]
	for (size_t i = 1; i < arr.size(); ++i) {
		dpi = (arr[i] > 0 && arr[i] < 10 ? dpim1 : 0) + (arr[i - 1] * 10 + arr[i] < 27 ? dpim2 : 0);
		dpim2 = dpim1;
		dpim1 = dpi;
		dpi = 0;
	}
	return dpim1;
}

- Chris September 26, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

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

- Alex September 27, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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
}

- Chris September 26, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@Netr
1) is the sample input 1322241043, or 132241043? both are listed in your example.
2) you list 132(22)4 and 1322(24) twice, so there should be 10 combinations, not 12. 10 is actually what my code returns, so at least for this case it's not wrong ;-)

- Chris September 26, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Chris September 26, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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];
	}

- sudip.innovates September 27, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

132241043 can only be decoded in 6 ways:
(1)(3)(2)(2)(4)(10)(4)(3)
(13)(2)(2)(4)(10)(4)(3)
(1)(3)(22)(4)(10)(4)(3)
(13)(22)(4)(10)(4)(3)
(1)(3)(2)(24)(10)(4)(3)
(13)(2)(24)(10)(4)(3)

- Alex September 27, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@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

- Chris September 27, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@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

- PenChief September 27, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- md.etemad September 29, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Was this a coding question or a closed analytical question? is an algorithm the required answer or is it a closed equation?

- Alon September 26, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

- audi September 26, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

{{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
}}

- Adi September 26, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

{{
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
}}

- Basmati September 26, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

@ChrisK

Solution doesn't work for 132241043


Total combinations:
132241043
(13)22241043
13(22)241043
132(22)41043
1322(24)1043
(13)(22)241043
(13)2(22)41043
(13)22(24)1043
13(22)(24)1043
132(22)41043
1322(24)1043
(13)(22)(24)1043

- Anonymous September 26, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

@ChrisK

Your solution doesn't work for 132241043


Total combinations:
132241043
(13)22241043
13(22)241043
132(22)41043
1322(24)1043
(13)(22)241043
(13)2(22)41043
(13)22(24)1043
13(22)(24)1043
132(22)41043
1322(24)1043
(13)(22)(24)1043

- Basmati September 26, 2017 | Flag Reply


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