Amazon Interview Question for SDE-2s


Country: India
Interview Type: In-Person




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

public static Set<String> decode(String code){
		return decode("", code);
	}
	
	private static Set<String> decode(String prefix, String code) {
		Set<String> set = new HashSet<String>();
		if (code.length() == 0) {
			set.add(prefix);
			return set;
		}
		if (code.charAt(0) == '0'){
			return set;
		}
	
		set.addAll(decode(prefix + (char) (code.charAt(0) - '1' + 'a'), code.substring(1)));
		
		if (code.length() >= 2 && code.charAt(0) == '1') {
			set.addAll(decode(prefix + (char) (10 + code.charAt(1) - '1' + 'a'), code.substring(2)));
		}
		if (code.length() >= 2 && code.charAt(0) == '2' && code.charAt(1) <= '6') {
			set.addAll(decode(prefix + (char) (20 + code.charAt(1) - '1' + 'a'), code.substring(2)));
		}
		return set;
	}

- Adnan Ahmad March 15, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

C++, implementation, O(log n)

int numberAlphabetCombination(int n, map<int, int>& cache) {
	map<int, int>::iterator it;
	int count;

	if (n <= 0) return 1;

	it = cache.find(n);
	if (it != cache.end()) {
		return it->second;
	}

	count = numberAlphabetCombination(n / 10, cache);
	if ((n % 100) >= 10 && (n % 100) <= 26) {
		count += numberAlphabetCombination(n / 100, cache);
	}

	cache.insert(make_pair(n, count));
	
	return count;
}

int solve(int n) {
	map<int, int> cache;

	return numberAlphabetCombination(n, cache);
}

- kyduke March 14, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class StringDecoder {

    public static void main(final String[] args) {

        final Map<String, String> codes = new HashMap<>();
        codes.put("0", "+");
        codes.put("1", "A");
        codes.put("2", "B");
        codes.put("3", "C");
        codes.put("4", "D");
        codes.put("5", "E");
        codes.put("6", "F");
        codes.put("7", "G");
        codes.put("8", "H");
        codes.put("9", "I");
        codes.put("10", "J");
        codes.put("11", "K");
        codes.put("12", "L");
        codes.put("13", "M");
        codes.put("14", "N");
        codes.put("15", "O");
        codes.put("16", "P");
        codes.put("17", "Q");
        codes.put("18", "R");
        codes.put("19", "S");
        codes.put("20", "T");
        codes.put("21", "U");
        codes.put("22", "V");
        codes.put("23", "W");
        codes.put("24", "X");
        codes.put("25", "Y");
        codes.put("26", "Z");

        System.out.println(decode("1123", codes));
    }

    private static List<StringBuilder> decode(final String string, final Map<String, String> codes) {
        List<StringBuilder> result = new ArrayList<StringBuilder>();
        final Map<StringBuilder, Integer> indexMap = new HashMap<>();
        char currentChar, nextChar = 0;
        for (int i = 0; i < string.length(); i++) {
            currentChar = string.charAt(i);
            if (i < string.length() - 1) {
                nextChar = string.charAt(i + 1);
            } else {
                nextChar = 0;
            }

            if (currentChar == '1' || (currentChar == '2' && nextChar >= '0' && nextChar <= '6')) {
                final String code1 = codes.get("" + currentChar);
                final String code2 = codes.get("" + currentChar + nextChar);
                result = addToResult(code1, code2, i, result, indexMap);
            } else {
                final String code = codes.get("" + currentChar);
                result = addToResult(code, result, i, indexMap);
            }


        }
        return result;

    }

    private static List<StringBuilder> addToResult(final String code1, final String code2, final int index,
            final List<StringBuilder> result, final Map<StringBuilder, Integer> indexMap) {
        final List<StringBuilder> resultStringbuilder = new ArrayList<StringBuilder>();
        if (result.isEmpty()) {
            final StringBuilder decodeString1 = new StringBuilder(code1);
            final StringBuilder decodeString2 = new StringBuilder(code2);
            resultStringbuilder.add(decodeString1);
            resultStringbuilder.add(decodeString2);
            indexMap.put(decodeString1, index);
            indexMap.put(decodeString2, index + 1);

        } else {
            for (final StringBuilder decodedString : result) {
                final int indexForDeocdedString = indexMap.get(decodedString);
                if (indexForDeocdedString < index) {
                    final StringBuilder newDecodedString = new StringBuilder(decodedString).append(code1);
                    resultStringbuilder.add(newDecodedString);
                    indexMap.put(newDecodedString, index);
                    final StringBuilder newDecodedString2 = new StringBuilder(decodedString).append(code2);
                    resultStringbuilder.add(newDecodedString2);
                    indexMap.put(newDecodedString2, index + 1);
                } else {
                    resultStringbuilder.add(decodedString);
                }
            }
        }
        return resultStringbuilder;
    }

    private static List<StringBuilder> addToResult(final String code, final List<StringBuilder> result,
            final int index, final Map<StringBuilder, Integer> indexMap) {
        final List<StringBuilder> resultStringbuilder = new ArrayList<StringBuilder>();
        if (result.isEmpty()) {
            resultStringbuilder.add(new StringBuilder(code));
        } else {
            for (final StringBuilder decodedString : result) {
                final int indexForDeocdedString = indexMap.get(decodedString);
                if (indexForDeocdedString < index) {
                    final StringBuilder newDecodedString = new StringBuilder(decodedString).append(code);
                    resultStringbuilder.add(newDecodedString);
                    indexMap.put(newDecodedString, index);
                } else {
                    resultStringbuilder.add(decodedString);
                }
            }
        }
        return resultStringbuilder;
    }

}

- sid March 14, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class StringDecoder {

    public static void main(final String[] args) {

        final Map<String, String> codes = new HashMap<>();
        codes.put("0", "+");
        codes.put("1", "A");
        codes.put("2", "B");
        codes.put("3", "C");
        codes.put("4", "D");
        codes.put("5", "E");
        codes.put("6", "F");
        codes.put("7", "G");
        codes.put("8", "H");
        codes.put("9", "I");
        codes.put("10", "J");
        codes.put("11", "K");
        codes.put("12", "L");
        codes.put("13", "M");
        codes.put("14", "N");
        codes.put("15", "O");
        codes.put("16", "P");
        codes.put("17", "Q");
        codes.put("18", "R");
        codes.put("19", "S");
        codes.put("20", "T");
        codes.put("21", "U");
        codes.put("22", "V");
        codes.put("23", "W");
        codes.put("24", "X");
        codes.put("25", "Y");
        codes.put("26", "Z");

        System.out.println(decode("1123", codes));
    }

    private static List<StringBuilder> decode(final String string, final Map<String, String> codes) {
        List<StringBuilder> result = new ArrayList<StringBuilder>();
        final Map<StringBuilder, Integer> indexMap = new HashMap<>();
        char currentChar, nextChar = 0;
        for (int i = 0; i < string.length(); i++) {
            currentChar = string.charAt(i);
            if (i < string.length() - 1) {
                nextChar = string.charAt(i + 1);
            } else {
                nextChar = 0;
            }

            if (currentChar == '1' || (currentChar == '2' && nextChar >= '0' && nextChar <= '6')) {
                final String code1 = codes.get("" + currentChar);
                final String code2 = codes.get("" + currentChar + nextChar);
                result = addToResult(code1, code2, i, result, indexMap);
            } else {
                final String code = codes.get("" + currentChar);
                result = addToResult(code, result, i, indexMap);
            }


        }
        return result;

    }

    private static List<StringBuilder> addToResult(final String code1, final String code2, final int index,
            final List<StringBuilder> result, final Map<StringBuilder, Integer> indexMap) {
        final List<StringBuilder> resultStringbuilder = new ArrayList<StringBuilder>();
        if (result.isEmpty()) {
            final StringBuilder decodeString1 = new StringBuilder(code1);
            final StringBuilder decodeString2 = new StringBuilder(code2);
            resultStringbuilder.add(decodeString1);
            resultStringbuilder.add(decodeString2);
            indexMap.put(decodeString1, index);
            indexMap.put(decodeString2, index + 1);

        } else {
            for (final StringBuilder decodedString : result) {
                final int indexForDeocdedString = indexMap.get(decodedString);
                if (indexForDeocdedString < index) {
                    final StringBuilder newDecodedString = new StringBuilder(decodedString).append(code1);
                    resultStringbuilder.add(newDecodedString);
                    indexMap.put(newDecodedString, index);
                    final StringBuilder newDecodedString2 = new StringBuilder(decodedString).append(code2);
                    resultStringbuilder.add(newDecodedString2);
                    indexMap.put(newDecodedString2, index + 1);
                } else {
                    resultStringbuilder.add(decodedString);
                }
            }
        }
        return resultStringbuilder;
    }

    private static List<StringBuilder> addToResult(final String code, final List<StringBuilder> result,
            final int index, final Map<StringBuilder, Integer> indexMap) {
        final List<StringBuilder> resultStringbuilder = new ArrayList<StringBuilder>();
        if (result.isEmpty()) {
            resultStringbuilder.add(new StringBuilder(code));
        } else {
            for (final StringBuilder decodedString : result) {
                final int indexForDeocdedString = indexMap.get(decodedString);
                if (indexForDeocdedString < index) {
                    final StringBuilder newDecodedString = new StringBuilder(decodedString).append(code);
                    resultStringbuilder.add(newDecodedString);
                    indexMap.put(newDecodedString, index);
                } else {
                    resultStringbuilder.add(decodedString);
                }
            }
        }
        return resultStringbuilder;
    }

}

- sid March 14, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is a Dinamic Propramming question, if we just want to know the number of combinations:

public int GetNumCombinations(string s)
{
    int[] dp = new int[s.Length];

    dp[0] = IsValid(ToInt(s[0])) ? 1 : 0;
    for (int i=1; i < s.Length; i++)
    {
        dp[i] = dp[i - 1];
        if (IsValid(ToInt(s[i-1]), ToInt(s[i])))
        {
            int j = i > 2 ? i - 2 : 0;
            dp[i] += dp[j];
        }
    }

    return dp[s.Length -1];
}

private bool IsValid(int first)
{
    return IsValid(first, null);
}

private bool IsValid(int first, int? second)
{
    if (first == 0)
        return false;

    if (second.HasValue)
    {
        if (first > 2)
            return false;
        if (first == 2 && second.Value > 6)
            return false;
    }

    return true;
}

private int ToInt(char c)
{
    return (int)(c - '0');
}

- hnatsu March 14, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

int numPermutations(int num)
{
  if (num < 10) {
    return 1;
  }

  int lastTwo = num % 100;

  if (lastTwo <= 26) {
    return numPermutations(num / 100) + numPermutations(num / 10);
  } else {
    return numPermutations(num / 10);
  }
}

- Mani March 14, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public void numPermutations(int num, String result) {
        if(num < 1) {
            System.out.println(result);
            return;
        }

        if (num < 10) {
            System.out.println(codes().get(num) + result);
            return;
        }

        int lastTwo = num % 100;

        if (lastTwo <= 26) {
            numPermutations(num / 10, codes().get(lastTwo % 10) + result);
            numPermutations(num / 100, codes().get(lastTwo) + result);
        } else {
            numPermutations(num / 100, result);
        }
    }

    public static Map<Integer, String> codes() {
        final Map<Integer, String> codes = new HashMap<>();
        codes.put(0, "+");
        codes.put(1, "A");
        codes.put(2, "B");
        codes.put(3, "C");
        codes.put(4, "D");
        codes.put(5, "E");
        codes.put(6, "F");
        codes.put(7, "G");
        codes.put(8, "H");
        codes.put(9, "I");
        codes.put(10, "J");
        codes.put(11, "K");
        codes.put(12, "L");
        codes.put(13, "M");
        codes.put(14, "N");
        codes.put(15, "O");
        codes.put(16, "P");
        codes.put(17, "Q");
        codes.put(18, "R");
        codes.put(19, "S");
        codes.put(20, "T");
        codes.put(21, "U");
        codes.put(22, "V");
        codes.put(23, "W");
        codes.put(24, "X");
        codes.put(25, "Y");
        codes.put(26, "Z");
        return codes;
    }

- Srikanth March 15, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

If we need to return all the strings we can use recursion and a string builder but is really inefficient, This is based on a DP solution you just check the current and last chars according to that update the lists; I used list of integers instead of string builders is more easy to do the operations/comparations.

public List<string> GetCombinations(string s)
{
    var result = new List<string>();
    if (string.IsNullOrEmpty(s))
        return result;

    int i = 0;
    var list = new List<List<int>>();

    // Add the first valid element to the first list
    while (!IsValid(s[i]))
        i++;

    if (i < s.Length)
    {
        var newList = new List<int>();
        newList.Add(ToInt(s[i]));
        list.Add(newList);
        i++;
    }

    while (i < s.Length)
    {
        // If is valid update the existing list.
        if (IsValid(s[i]))
        {
            int n1 = ToInt(s[i]);
            foreach (var item in list)
                item.Add(n1);
        }

        // If the current and previus numbers form a valid letter add new lists.
        if (IsValid(s[i - 1], s[i]))
        {
            int n1 = ToInt(s[i - 1]);
            int n2 = ToInt(s[i]);
            int n = (n1 * 10) + n2;
            var list2 = new List<List<int>>();
            foreach (var item in list)
            {
                int m = -1;
                // Special case when n2 == 0, the 0 is not in the item list and there is only one eleent
                if (n2 == 0 && item.Count > 0 && item[item.Count - 1] == n1)
                    m = item.Count - 1;
                else if (item.Count > 1 && item[item.Count - 2] == n1 && (n2 == 0 || item[item.Count - 1] == n2))
                    m = item.Count - 2;

                if (m == -1)
                    continue;

                var newList = new List<int>();
                for (int j = 0; j < m; j++)
                    newList.Add(item[j]);
                newList.Add(n);
                list2.Add(newList);
            }
            list.AddRange(list2);
        }

        i++;
    }
            
    // Parse int values to char
    foreach (var item in list)
        result.Add(ToString(item));

    return result;
}

private bool IsValid(char c)
{
    return IsValid(c, null);
}
private bool IsValid(char c1, char? c2)
{
    int n1 = ToInt(c1);
    if (n1 == 0 || n1 > 9)
        return false;

    if (c2.HasValue)
    {
        int n2 = ToInt(c2.Value);
        if (n1 > 2)
            return false;
        if (n1 == 2 && n2 > 26)
            return false;
    }

    return true;
}

private int ToInt(char c)
{
    return (int)(c - '0');
}
private char ToChar(int n)
{
    return (char)((int)'A' + n - 1);
}

private string ToString(List<int> list)
{
    var sb = new StringBuilder();
    foreach (var item in list)
        sb.Append(ToChar(item));
    return sb.ToString();
}

public void Test(object sender, EventArgs e)
{
    var s = "1123";
    //var s = "134524";
    //var s = "1203";
    var list = GetCombinations(s);

    foreach (var item in list)
        Console.WriteLine(item);
}

- hnatsu March 15, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Same as
question?id=19300678

- Adnan Ahmad March 15, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

var input = [1,1,2,3];

function equals(a, b){
  if(a.length != b.length) return false;
  for(let i = 0; i < a.length; i++){
    if(a[i] != b[i]) return false;         
  }
  return true;
}

function found(r,m){
  for(let arr of r){
     if(equals(arr,m)) return true;         
  }  
  return false;
}

function find(input, results = []){
  if(!found(results, input))results.push(input);
  for(let i = 0; i < input.length -1; i++){
    if(input[i+1]>=10 && input[i] != 0) continue;
    let m = input[i]*10 +input[i+1];    
    if(m <27){
      let tmp = input.slice();
      tmp.splice(i,2,m);
      find(tmp,results,i);
    }
  }
  return results.length;
}


var r = [];
find(input,r);

for(let x of r){
  console.log(x);
}

console.log('length: ',r.length);

- asdf March 18, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int numCombination(int num) {
		Map<Integer, Integer> memo = new HashMap<>();
		return numCombinationHelper(num, memo);
	}

	int numCombinationHelper(int num, Map<Integer, Integer> memo) {
		if (num < 10) {
			return 1;
		}
		if (memo.get(num) == null) {
			if (num % 100 < 27) {
				memo.put(num, numCombinationHelper(num/10, memo) + numCombinationHelper(num/100, memo));
			} else {
				memo.put(num, numCombinationHelper(num/10, memo));
			}
		}
		return memo.get(num);
	}

- Johnny March 19, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

size_t getDigNum(int inp) {
    vector<short> digs;
    while(inp > 0) {
        digs.push_back(inp % 10);
        inp /= 10;
    }

    for(size_t i = 0; i < digs.size() / 2; ++i) {
        swap(digs[i], digs[digs.size() - i - 1]);
    }

    size_t prev = 1;
    size_t cur = 1;
    for (size_t i = 1; i < digs.size(); ++i) {
        if (digs[i-1] < 2 || (digs[i-1] == 2 && digs[i] < 7)) {
            size_t tmp = cur;
            cur += prev;
            prev = tmp;
        } else {
            prev = cur;
        }
    }

    return cur;
}

- Anonymous March 26, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

A simple recursive solution

private static final Map<String, String> map = new HashMap<>();

    public static void main(String[] args) {

        map.put("1", "A");
        map.put("2", "B");
        map.put("3", "C");
        map.put("11", "J");
        map.put("23", "W");

        combinations("1123", "");
    }

    private static void combinations(String str, String result) {

        for (int i = 1; i <= str.length(); i++) {

            String prefix = str.substring(0, i);

            if (map.containsKey(prefix)) {

                if (i == str.length()) {
                    System.out.println(result + map.get(prefix));
                }
                
                combinations(str.substring(i, str.length()), result + map.get(prefix) + "");
            }

        }
    }

- Vishal Mehta March 29, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Combinations {
	
	public static void main(String[] args) {
		String number = "0123";
		System.out.println("\nNumber: "+findCombinations(number,0,number.length()));
	}

	private static int findCombinations(String number,int index, int maxIndex) {
		int sum =0;
		if(index>=maxIndex){
			System.out.println(number);
			return 1;
		}else{
			if(index+1<=maxIndex){
				String remainingString ="";
				if(index+1<maxIndex){
					remainingString = number.substring(index+1);
				}
				 sum = sum + findCombinations(number.substring(0, index)+convertNumberToString(number.substring(index, index+1)) + remainingString,
										index+1, number.length());
			}
			if(index+2<=maxIndex){
				String remainingString ="";
				if(index+2<maxIndex){
					remainingString = number.substring(index+2);
				}
				 sum =sum +findCombinations(number.substring(0, index)+convertNumberToString(number.substring(index, index+2))+ remainingString, index+1, number.length()-1);
			}
		}
		return sum;
	}

	private static String convertNumberToString(String charAt) {
		int intVal = Integer.valueOf(charAt);
		if(intVal==0){
			return "+";
		}
		char a = (char)(intVal + 64);
		return a+"";
	}

}

- CodeDemon March 31, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Combinations {
	
	public static void main(String[] args) {
		String number = "0123";
		System.out.println("\nNumber: "+findCombinations(number,0,number.length()));
	}

	private static int findCombinations(String number,int index, int maxIndex) {
		int sum =0;
		if(index>=maxIndex){
			System.out.println(number);
			return 1;
		}else{
			if(index+1<=maxIndex){
				String remainingString ="";
				if(index+1<maxIndex){
					remainingString = number.substring(index+1);
				}
				 sum = sum + findCombinations(number.substring(0, index)+convertNumberToString(number.substring(index, index+1)) + remainingString,
										index+1, number.length());
			}
			if(index+2<=maxIndex){
				String remainingString ="";
				if(index+2<maxIndex){
					remainingString = number.substring(index+2);
				}
				 sum =sum +findCombinations(number.substring(0, index)+convertNumberToString(number.substring(index, index+2))+ remainingString, index+1, number.length()-1);
			}
		}
		return sum;
	}

	private static String convertNumberToString(String charAt) {
		int intVal = Integer.valueOf(charAt);
		if(intVal==0){
			return "+";
		}
		char a = (char)(intVal + 64);
		return a+"";
	}

}

- codedemon March 31, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class NumberCombinations {
public static void main(String[] args) {
String number = "1123";
int count = 0;
int nextCount =0;
for(int i=0;i<=number.length()-2;i++) {
nextCount =0;
String Substring = number.substring(i, i+2);
if(Integer.parseInt(Substring)<27){
if(Substring.charAt(0) !='0'){
count++;
}
}
for(int j=number.lastIndexOf(Substring)+2;j<=number.length()-2;j++){

String Substring2 = number.substring(j, j+2);
if(Integer.parseInt(Substring2)<27){
if(Substring2.charAt(0) !='0'){
nextCount++;
}
}
}
if(nextCount>0){
count++;
}
}
System.out.println(count+1);
}
}

- Maheshbabu B April 01, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class NumberCombinations {

	public static void main(String[] args) {
		String number = "1123";
		int count = 0;
		int nextCount =0;
		for(int i=0;i<=number.length()-2;i++) {
					nextCount =0;
			    	   String Substring = number.substring(i, i+2);			    	   
			    	   if(Integer.parseInt(Substring)<27){
			    		   if(Substring.charAt(0) !='0'){
			    		   count++;
			    	   }
			    	   }
			    	   for(int j=number.lastIndexOf(Substring)+2;j<=number.length()-2;j++){
			    		   
			    		   String Substring2 = number.substring(j, j+2);				    	   
				    	   if(Integer.parseInt(Substring2)<27){
				    		   if(Substring2.charAt(0) !='0'){
				    		   nextCount++;
				    		   }
				    	   }
			    	   }
			    		   if(nextCount>0){
			    				   count++;
			    	   }
			    	   }
		System.out.println(count+1);
		}	
	
}

- Maheshbabu B April 01, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

# Pure string version.





def ci(x):
	return chr(int(x) + ord('A') - 1)

def cc(x):
	return chr(ord(x) + ord('A') - 1)

myChr = [ x for x in "1123"]

# --- print all the onesies 
for i in myChr: print ci(i), 
print 
myTwos = [ int(myChr[i])*10 + int(myChr[i+1]) for i in range(0,len(myChr),2)]
for x in myTwos: 
	if x < 27: 
		print ci(x), 
print 
for j in range(len(myChr)-1):
	i = j
	while i < len(myChr):
		k = 0; 
		while k <= (j-1):
			print ci(myChr[k]), 
			k = k + 1
		print  ci(10*int(myChr[j])+int(myChr[j+1])),
		if j == i: i = i + 1
		k = j+2;
		while k < len(myChr):
			print ci(myChr[k]),
			k = k + 1; 
			i = i + 1
		print 
		i = i + 1

- kbhusain April 26, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<iostream>
#include<deque>
#include<vector>
#include<list>

using namespace std;

void displayq (deque<vector<int> > &d) {

for(int i=0; i<d.size(); i++) {
vector<int> v = d[i];
for(int j=0; j<v.size(); j++) {
cout << v[j] << " ";
}
for(int j=0; j<v.size(); j++) {
cout << char('A' + v[j] -1) ;
}
cout << endl;
}
}

int main() {
int arr[] = {1,1,2,3};
int n = sizeof(arr)/sizeof(arr[0]);
int i=0;

deque<vector<int> > dqlstint;
vector <int> v ;

for(int i=0; i<n; i++)
v.push_back(arr[i]);
dqlstint.push_back(v);

while(i<dqlstint.size() ) {
vector<int> front = dqlstint[i];
int temp=0;
for(int j=0; j<front.size()-1; j++) {
vector<int> front2 = front;
if( (temp = ((front[j]*10)+front[j+1])) <= 26 && front[j] < 10 && front[j+1] < 10 ) {
front2[j] = temp;
front2.erase(front2.begin() + j +1);
int k=0;
while(k<dqlstint.size() ) {
if(dqlstint[k] == front2)
break;
k++;
}
if(k == dqlstint.size() )
dqlstint.push_back(front2);
}
}
i++;
}

displayq(dqlstint);
return 0;
}

- kbkunalb May 04, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<iostream>
#include<string>
using namespace std;
int PrintValidCombinations(string s, int i){
if(i == s.length()-1){
return 1;
}else if (i == s.length()-2){
int number = (s[i]-'0')*10 + (s[i+1]-'0');
if(number>26){
return 1;
}else{
return 2;
}
}
int number = (s[i]-'0')*10 + (s[i+1]-'0');
if(number > 26){
return 1+PrintValidCombinations(s,i+2);
}else{
return PrintValidCombinations(s,i+1)+PrintValidCombinations(s,i+2);;
}
}
int main(){
std::string s;
cin>>s;
std::cout<<PrintValidCombinations(s,0)<<endl;

- Srinivas May 05, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<iostream>
#include<string>
using namespace std;
int PrintValidCombinations(string s, int i){
	if(i == s.length()-1){
		return 1;
	}else if (i == s.length()-2){
		int number = (s[i]-'0')*10 + (s[i+1]-'0');
		if(number>26){
			return 1;
		}else{
			return 2;
		}
	}
	int number = (s[i]-'0')*10 + (s[i+1]-'0');
	if(number > 26){
		return 1+PrintValidCombinations(s,i+2);
	}else{
		return  PrintValidCombinations(s,i+1)+PrintValidCombinations(s,i+2);;
	}
}
int main(){
	std::string s;
	cin>>s;
	std::cout<<PrintValidCombinations(s,0)<<endl;

- Srinivas May 05, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<iostream>
#include<string>
using namespace std;
int PrintValidCombinations(string s, int i){
	if(i == s.length()-1){
		return 1;
	}else if (i == s.length()-2){
		int number = (s[i]-'0')*10 + (s[i+1]-'0');
		if(number>26){
			return 1;
		}else{
			return 2;
		}
	}
	int number = (s[i]-'0')*10 + (s[i+1]-'0');
	if(number > 26){
		return 1+PrintValidCombinations(s,i+2);
	}else{
		return  PrintValidCombinations(s,i+1)+PrintValidCombinations(s,i+2);;
	}
}
int main(){
	std::string s;
	cin>>s;
	std::cout<<PrintValidCombinations(s,0)<<endl;

- sreenu.javvadi May 05, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

static int ways(String s) {
	if (s.length() == 1) {
		return 1;
	}
	int i = 0;

	int k = 1;
	int j = 1;

	while (i < s.length()-1) {
		int temp = j;
		if (is2Decodable(s, i)) {
			j += k;
		}
		k = temp;
		i++;
	}

	return j;
}

static boolean is2Decodable(String s, int i) {
	if (i > s.length() - 2) {
		return false;
	}

	return s.charAt(i) == '1' || (s.charAt(i) == '2' && s.charAt(i+1) >= '0' && s.charAt(i+1) <= '6');
}

- Misha May 24, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Non-recursive, O(n) by time, O(1) by space:

static int ways(String s) {
	if (s.length() == 1) {
		return 1;
	}
	int i = 0;

	int k = 1;
	int j = 1;

	while (i < s.length()-1) {
		int temp = j;
		if (is2Decodable(s, i)) {
			j += k;
		}
		k = temp;
		i++;
	}

	return j;
}

static boolean is2Decodable(String s, int i) {
	if (i > s.length() - 2) {
		return false;
	}

	return s.charAt(i) == '1' || (s.charAt(i) == '2' && s.charAt(i+1) >= '0' && s.charAt(i+1) <= '6');
}

- Borodin.Mik May 24, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

static HashMap<Integer, Character> map;
	static {
		map = new HashMap<Integer,Character>();
		map.put(1, 'A');
		map.put(2, 'B');
		map.put(3, 'C');
		map.put(4, 'D');
		map.put(5, 'E');
		map.put(6, 'F');
		map.put(7, 'G');
		map.put(8, 'H');
		map.put(9, 'I');
		map.put(10, 'J');
		map.put(11, 'K');
		map.put(12, 'L');
		map.put(13, 'M');
		map.put(14, 'N');
		map.put(15, 'O');
		map.put(16, 'P');
		map.put(17, 'Q');
		map.put(18, 'R');
		map.put(19, 'S');
		map.put(20, 'T');
		map.put(21, 'U');
		map.put(22, 'V');
		map.put(23, 'W');
		map.put(24, 'X');
		map.put(25, 'Y');
		map.put(26, 'Z');
	}
	
	public static Set<String> getCombinations(String input){
		return getCombinations("", input);
	}
	
	public static Set<String> getCombinations(String prefix, String suffix ){
		Set<String> combinations = new HashSet<String>();
		if(suffix.length() == 0){
			combinations.add(prefix);
			return combinations;
		}
		if(suffix.length() == 1){
			combinations.add(prefix + map.get(Integer.valueOf(suffix.substring(0,1))));
			return combinations;
		}
		
		combinations.addAll(getCombinations(prefix + map.get(Integer.valueOf(suffix.substring(0,1))), suffix.substring(1)));
		if(suffix.length() > 1 && suffix.charAt(0) == '1'){
			combinations.addAll(getCombinations(prefix + map.get(Integer.valueOf(suffix.substring(0,2))), suffix.substring(2)));	
		}
		if(suffix.length() > 1 && suffix.charAt(0) == '2' && (Integer.valueOf(suffix.substring(0,2)) <= 26)){
			combinations.addAll(getCombinations(prefix + map.get(Integer.valueOf(suffix.substring(0,2))), suffix.substring(2)));	
		}
		return combinations;
	}
	
	public static void main(String ... args){
		Set<String> combinations = getCombinations("1123");
		for(String s : combinations){
			System.out.println(s);
		}
	}

- Héctor June 05, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

static HashMap<Integer, Character> map;
	static {
		map = new HashMap<Integer,Character>();
		map.put(1, 'A');
		map.put(2, 'B');
		map.put(3, 'C');
		map.put(4, 'D');
		map.put(5, 'E');
		map.put(6, 'F');
		map.put(7, 'G');
		map.put(8, 'H');
		map.put(9, 'I');
		map.put(10, 'J');
		map.put(11, 'K');
		map.put(12, 'L');
		map.put(13, 'M');
		map.put(14, 'N');
		map.put(15, 'O');
		map.put(16, 'P');
		map.put(17, 'Q');
		map.put(18, 'R');
		map.put(19, 'S');
		map.put(20, 'T');
		map.put(21, 'U');
		map.put(22, 'V');
		map.put(23, 'W');
		map.put(24, 'X');
		map.put(25, 'Y');
		map.put(26, 'Z');
	}
	
	public static Set<String> getCombinations(String input){
		return getCombinations("", input);
	}
	
	public static Set<String> getCombinations(String prefix, String suffix ){
		Set<String> combinations = new HashSet<String>();
		if(suffix.length() == 0){
			combinations.add(prefix);
			return combinations;
		}
		if(suffix.length() == 1){
			combinations.add(prefix + map.get(Integer.valueOf(suffix.substring(0,1))));
			return combinations;
		}
		
		combinations.addAll(getCombinations(prefix + map.get(Integer.valueOf(suffix.substring(0,1))), suffix.substring(1)));
		if(suffix.length() > 1 && suffix.charAt(0) == '1'){
			combinations.addAll(getCombinations(prefix + map.get(Integer.valueOf(suffix.substring(0,2))), suffix.substring(2)));	
		}
		if(suffix.length() > 1 && suffix.charAt(0) == '2' && (Integer.valueOf(suffix.substring(0,2)) <= 26)){
			combinations.addAll(getCombinations(prefix + map.get(Integer.valueOf(suffix.substring(0,2))), suffix.substring(2)));	
		}
		return combinations;
	}
	
	public static void main(String ... args){
		Set<String> combinations = getCombinations("1123");
		for(String s : combinations){
			System.out.println(s);
		}
	}

- Héctor June 05, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class NumberCombination {
    private HashMap<Integer, String> codes;

    public NumberCombination() {
        codes = new HashMap<>();
        codes.put(0, "+");
        codes.put(1, "A");
        codes.put(2, "B");
        codes.put(3, "C");
        codes.put(4, "D");
        codes.put(5, "E");
        codes.put(6, "F");
        codes.put(7, "G");
        codes.put(8, "H");
        codes.put(9, "I");
        codes.put(10, "J");
        codes.put(11, "K");
        codes.put(12, "L");
        codes.put(13, "M");
        codes.put(14, "N");
        codes.put(15, "O");
        codes.put(16, "P");
        codes.put(17, "Q");
        codes.put(18, "R");
        codes.put(19, "S");
        codes.put(20, "T");
        codes.put(21, "U");
        codes.put(22, "V");
        codes.put(23, "W");
        codes.put(24, "X");
        codes.put(25, "Y");
        codes.put(26, "Z");

    }

    public List<String> createCombinations(int num) {
        List<String> results = new ArrayList<>();
        if (num <= 9 && num >= 0) {
            results.add(codes.get(num));
        } if(num <=26 && num >= 10) {
            results.add(codes.get(num));
            int lastNum = num % 10;
            if(num/10 > 0) {
                List<String> tempResult = createCombinations(num / 10);
                tempResult.forEach((s) -> {
                    results.add(s + codes.get(lastNum));
                });
            }
        } else {
            int lastNum = num % 10;
            int lastTwoNum = num % 100;
            if(num/10 > 0) {
                List<String> tempResult = createCombinations(num / 10);
                tempResult.forEach((s) -> {
                    results.add(s + codes.get(lastNum));
                });
            }
            if(num/100 > 0) {
                List<String> tempResult2 = createCombinations(num / 100);
                tempResult2.forEach((s) -> {
                    results.add(s + codes.get(lastTwoNum));
                });
            }
        }
        return results;
    }

    public static void main(String[] args) {
        NumberCombination numberCombination = new NumberCombination();
        List<String> results = numberCombination.createCombinations(1123);
        results.forEach(System.out::println);
    }
}

- shashank.neo June 19, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package geek.random;

public class PrintCombinaton {
	private String getChar(String i){
		return ""+ (char)(Integer.parseInt(i)+64);
	}
	
	private void printValues(String str, int i, int len, String res){
		if(i >=len){
			System.out.println(res);
			return;
		}
		if(i+1<=len){
			String toAdd1 = getChar(str.substring(i, i+1));
			printValues(str, i+1, len, res+toAdd1);
		}
		if(i+2<=len){
			String toAdd2 = getChar(str.substring(i,i+2));
			printValues(str, i+2, len, res+toAdd2);
		}
	}
public static void main(String[] args) {
	int i=1;
	PrintCombinaton printCombinaton = new PrintCombinaton();
	printCombinaton.printValues("1123", 0, 4, "");
}
}

- Vinay Sahu September 08, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Java working code

package geek.random;

public class PrintCombinaton {
	private String getChar(String i){
		return ""+ (char)(Integer.parseInt(i)+64);
	}
	
	private void printValues(String str, int i, int len, String res){
		if(i >=len){
			System.out.println(res);
			return;
		}
		if(i+1<=len){
			String toAdd1 = getChar(str.substring(i, i+1));
			printValues(str, i+1, len, res+toAdd1);
		}
		if(i+2<=len){
			String toAdd2 = getChar(str.substring(i,i+2));
			printValues(str, i+2, len, res+toAdd2);
		}
	}
public static void main(String[] args) {
	int i=1;
	PrintCombinaton printCombinaton = new PrintCombinaton();
	printCombinaton.printValues("1123", 0, 4, "");
}
}

- Vinay Sahu September 08, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

#include <stdio.h>
static unsigned int combos;
void alpha_combos(unsigned int);

int main(void)
{
    unsigned int input = 0;
    
    printf("Please Provide Input \n");
    scanf("%d",&input);
    alpha_combos(input);
    printf("combos = %d",combos);
    return 0;
}

void alpha_combos(unsigned int num)
{
    unsigned int rem_2digit = 0, rem_1digit = 0;
    
    rem_2digit = num%100;
    rem_1digit = num%10;
    
    num = num/100;
    
    if(num!=0)
        alpha_combos(num);
    
    if(rem_2digit <= 26)
    {
        if(combos != 0)
        {
            combos++;
        }
        combos++;
    }
    
    if (rem_1digit != 0)
    {
        combos++;
    }

}

- godzilathakur March 14, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

I don't understand why there are 5 combinations for 1123, can you please explain?

Here are some combos that I can extract (there are more though)

1,1,2,3
1,1,3,2
1,2,1,3
1,2,3,1
1,3,1,2
2,1,1,3
2,1,3,1
2,3,1,1
23,11
11,23
21,13
... and so on

- Peter March 14, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

That's permutation, not combination.

- Anonymous March 20, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

That's permutation, not combination.

- anon March 20, 2016 | Flag


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