Interview Question

  • 1
    of 1 vote
    9
    Answers

    1 represent A, 2 rep B etc and 26 rep Z. Given a number, find number of possible decoding for this number. No need to consider number starts with zero. Eg: input – 1234, output – 3(ABCD, AWD, LCD)

    - koustav.adorable on July 24, 2014 in United States Report Duplicate | Flag
    Algorithm

Country: United States


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

/*
1 represent A, 2 rep B etc and 26 rep Z. Given a number, find number of
possible decoding for this number. No need to consider number starts with zero.
Eg: input – 1234, output – 3(ABCD, AWD, LCD)
*/

import java.util.*;

class Decoder {

    static final char[] CHARY;
    static {
        CHARY = ((String)"ABCDEFGHIJKLMNOPQRSTUVWXYZ").toCharArray();
    }
    private String numStr;
    Decoder(String numStr) {
        this.numStr = numStr;
    }
    void printWords() {
        recurse("", numStr);
    }
    void recurse(String ltrStr, String numStr) {
        int len = numStr.length();
        if (len == 0 && ltrStr.length() > 0) {
            System.out.println(ltrStr);
            return;
        } else if (len > 2) {
            len = 2;
        }
        // Try valid 1 and 2 digit encodings.
        for (int i = 1; i <= len; i++) {
            int n = Integer.parseInt(numStr.substring(0, i));
            if (n >= 1 && n <= 26)
                recurse(ltrStr + CHARY[n - 1], numStr.substring(i));
        }
    }
}
public class WordDecoder {
    // Usage: java WordDecoder 1234
    // Output:
    //   ABCD
    //   AWD
    //   LCD
    public static void main(String[] args) {
        try {
            // Validate input.
            int n = Integer.parseInt(args[0]);
            if (n <= 0)
                throw new NumberFormatException();
        } catch (NumberFormatException e) {
            System.out.println("Error: " + args[0] + " is not a positive, base-10 numeric string.");
            return;
        }
        Decoder decoder = new Decoder(args[0]);
        decoder.printWords();
    }
}
// vim:ts=4:sw=4:et:tw=78

- Brett Pershing Stahlman on July 24, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Please provide the solution using dp.

- Anonymous on July 24, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

What are you looking for exactly?

- Brett Pershing Stahlman on July 24, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

DP formula:
if s[i] == 0, dp[i] = 0
else if s[i] <= 2 && s[i+1] <= 6, dp[i] = dp[i+1] + dp[i+2]
else dp[i] = dp[i+1]
Code in C++:

int getWaysToDecode(const string& text){
        //check if head decodable
        if(text.empty() || text[0] == '0') return 0;
        //if single character
        if(text.size() == 1) return 1;
        
        int len = text.size(), i;
        int* dp = new int[len + 1];
        //check if memory allocation failed
        if(dp == NULL) return -1;
        dp[len] = 1;
        dp[len-1] = text[len-1] > '0';
        for(i = len-2; i >= 0; --i){
            if(text[i] > '0'){
                //we can decode text[i] as a one-code word
                dp[i] = dp[i+1];
                //try to decode text[i,i+1] as a two-code word
                if(text[i] <= '2' && text[i+1] <= '6') dp[i] += dp[i+2];
            }
            else dp[i] = 0;
        }
        //free memory before return
        len = dp[0];
        delete[] dp;
        return len;
    }

- uuuouou on July 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

What are you trying to achieve ?
I don't get this.

- Anonymous on July 25, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Anonymous, it's to figure out how many ways there are to decode the number string into a legal letter string.

- uuuouou on July 25, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

1, Check the last two digits before the letter. Add all the possible array to a stack.
2, Poll one item from the stack and repeat step 1.
3, If the pulled item has no letter, put it in the result.

- Allen on July 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

one example for the 1st step, the last two digits for 1234 is 34. Since 34 is larger than 26. So the only possible array is 123D.

- Allen on July 25, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

if you need print the letters

void decode(const char* number, char* letters, int n, int idxN = 0, int idxL = 0)
{
    if (idxN == n)
	{
		printf("%s\n", letters);
        return;
	}

	if (number[idxN] != '0')
	{
		letters[idxL] = number[idxN] - '0' - 1 + 'a';
		letters[idxL + 1] = '\0';
		decode(number, letters, n, idxN+1, idxL + 1);
	}
	
	if (idxN+1 < n && (number[idxN]-'0')*10 + number[idxN+1]-'0' <= 26)
	{
		letters[idxL] = (number[idxN]-'0')*10 + number[idxN+1]-'0' - 1 + 'a';
		letters[idxL + 1] = '\0';
		decode(number, letters, n, idxN+2, idxL + 1);
	}

}

if not, use memorization to avoid recompute the same solutions again

int count(const char* number, int* numWays, int n, int idxN)
{
    if (idxN == n)
    {
        return 1;
	}
    else if (idxN > n) return 0;
    else if (numWays[idxN] != -1) return numWays[idxN];
    else{
        numWays[idxN] = 0;
    	if (number[idxN] != '0')
    	{
    		numWays[idxN] += count(number, numWays, n, idxN+1);
    	}
    	
    	if (idxN+1 < n && (number[idxN]-'0')*10 + number[idxN+1]-'0' <= 26)
    	{
    		numWays[idxN] += count(number, numWays, n, idxN+2);
    	}
        
        printf("numWays[%d] = %d\n", idxN, numWays[idxN]);
        return numWays[idxN];
    }

}

- Anonymous on July 26, 2014 | Flag Reply


Add a Comment
Name:

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

Books

is a comprehensive book walking you through 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