## Groupon Interview Question for Software Developers

Country: United States

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

``````public static void Decode(String str) {
DecodeHelper(str.toCharArray(), 0, str.length(), new StringBuilder());
}

private static void DecodeHelper(char[] str, int index, int len, StringBuilder sb) {
if(index == len) {
System.out.println(sb.toString());
return;
}
int singleDigit = str[index] - '0';
char decodeChar = (char) ('A' + singleDigit - 1);
sb.append(decodeChar);
sb.append(",");
DecodeHelper(str, index + 1, len, sb);
sb.delete(sb.length() - 2, sb.length());
if(index + 1 < len)
{
int doubleDigit = ((str[index] - '0') * 10) + (str[index + 1] - '0');
if(doubleDigit < 26) {
decodeChar = (char) ('A' + doubleDigit - 1);
sb.append(decodeChar);
sb.append(",");
DecodeHelper(str, index + 2, len, sb);
sb.delete(sb.length() - 2, sb.length());
}
}
}``````

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

With a string of length n, you have 2 in power of (n-1) different possible coma delimited strings. You can represent state of coma positions as an array of 0s and 1s, where 1 means that comma is needed at i+1 position. In this example: 123, would have the following:

``````0,0 => 123
0,1 => 12,3
1,0 => 1,23
1,1 => 1,2,3``````

the way you do it is you need introduce a variable of type

``int k;``

and increment it by 1 at each cycle, until

``k<input.length-1``

. To check whether the coma is needed you need to check condition:

``(k>>1)&1==1``

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

The problem is numbers greater than 26 cannot be encoded. Thus 893 can only be encoded as 8,9,3 and no three digit numbers are allowed. I feel like recursion would be useful here as it would allow to not have to check "unallowed" permutations more than once at each level.

``````1,2,2,2
12,2,2
1,22,2
then
12,22
1,2,22``````

Adding a 5th is all of the above encodings plus

``````1,2,2,22
12,2,22
1,22,22``````

which happens to be the 3 digit encodings
6 gives all of the above plus

``````1,2,2,2,22
1,22,2,22
12,2,2,22
1,2,22,22
12,22,22``````

Which once again is all the 4 digit encodings
Thus the number of encodings for a N digit string(where every combination can encoded) is the number of encodings for an n-1 digit string + the number of encodings of a n-2 digit string. Note if every combination is not possible, such as 12,35 then make sure you check that each number is < 26 or else don't count it.
I would definitely use a dynamic programming approach or else this will become exponential in run time like fibonacci.

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

``````public static int findNumberOfDecodeSequences(String sequence) {

if(sequence.length() == 0) {
return 0;
}

int numStringsEndingWithSingleDigit = 1;
int numStringsEndingWithDoubleDigits = 0;

for(int i = 1; i < sequence.length(); i++) {
int doubleDigitVal = (sequence.charAt(i - 1) - '0') * 10 + (sequence.charAt(i) - '0');
if(doubleDigitVal <= 26) {
int temp = numStringsEndingWithDoubleDigits + numStringsEndingWithSingleDigit;
numStringsEndingWithDoubleDigits = numStringsEndingWithSingleDigit;
numStringsEndingWithSingleDigit = temp;
}

else {
numStringsEndingWithSingleDigit = numStringsEndingWithSingleDigit + numStringsEndingWithDoubleDigits;
numStringsEndingWithDoubleDigits = 0;
}
}
return (numStringsEndingWithDoubleDigits + numStringsEndingWithSingleDigit);
}``````

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

``````public static int findNumberOfDecodeSequences(String sequence) {

if(sequence.length() == 0) {
return 0;
}

int numStringsEndingWithSingleDigit = 1;
int numStringsEndingWithDoubleDigits = 0;

for(int i = 1; i < sequence.length(); i++) {
int doubleDigitVal = (sequence.charAt(i - 1) - '0') * 10 + (sequence.charAt(i) - '0');
if(doubleDigitVal <= 26) {
int temp = numStringsEndingWithDoubleDigits + numStringsEndingWithSingleDigit;
numStringsEndingWithDoubleDigits = numStringsEndingWithSingleDigit;
numStringsEndingWithSingleDigit = temp;
}

else {
numStringsEndingWithSingleDigit = numStringsEndingWithSingleDigit + numStringsEndingWithDoubleDigits;
numStringsEndingWithDoubleDigits = 0;
}
}
return (numStringsEndingWithDoubleDigits + numStringsEndingWithSingleDigit);
}``````

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

public static int decodeSeq(String num) {
if (num.length() == 0)
return 0;

int[] f = new int[num.length() + 1];
f[0] = 1;
f[1] = 1;

for (int i = 1; i < num.length(); i++) {
if ((num.charAt(i - 1) - '0') * 10 + (num.charAt(i) - '0') <= 26) {
f[i + 1] = f[i] + f[i - 1];
} else {
f[i + 1] = f[i];
}
}
return f[num.length()];
}

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

public static int decodeSeq(String num) {
if (num.length() == 0)
return 0;

int[] f = new int[num.length() + 1];
f[0] = 1;
f[1] = 1;

for (int i = 1; i < num.length(); i++) {
if ((num.charAt(i - 1) - '0') * 10 + (num.charAt(i) - '0') <= 26) {
f[i + 1] = f[i] + f[i - 1];
} else {
f[i + 1] = f[i];
}
}
return f[num.length()];
}

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

DP

``````package Java;

import java.util.Arrays;

/**
* Author: Nitin Gupta
* Date: 26/04/19
* Description:
*/
public class NumberOfWaysToDecodeDigitSeq {

public static void main(String args[]) {

String s = "1212";

System.out.println(ways(s));
}

private static int ways(String s) {
if (s == null || s.isEmpty())
return 0;

int n = s.length();

int count[] = new int[n + 1];

Arrays.fill(count, 0);

count[0] = 1; //every single character can be transform
count[1] = 1;

char digits[] = s.toCharArray();
for (int i = 2; i <= n; i++) {

if (digits[i - 1] > '0')
count[i] += count[i - 1];

if (digits[i - 2] == '1' || digits[i - 2] == '2' && digits[i - 1] < '7')
count[i] += count[i - 2];
}

return count[n];
}
}``````

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

You can optimise further using Fibonacci numbers; o(logn) time

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.

### 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.