Amazon Interview Question for Software Engineer Interns


Country: United States
Interview Type: Phone Interview




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

The problem over here is whether the '1' or '2' belongs to a two digit representation or a single digit representation.
We can change the number scheme to the following,
A-3 B-4 C-5 D-6 E-7 F-8 G-9 H-10 I-11 J-12 K-13 L-14 M-15 N-16 O-17 P-18 Q-19 R-20 S-21 T-22 U-23 V-24 W-25 X-26 Y-27 Z-28

Now, whenever there is a '1' or '2' in the encrypted string, one knows it is a 2digit character representation and can decode properly.
I think, the interviewer was looking for different approach to the same problem.
In this algorithm, the number of digits approximately remains the same, except for few odd scenario's.

- Anon July 21, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

if problem allows you to store 3 for 'A' then why not to simply use ASCII code

- Aalekh Neema July 24, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Yes, using ASCII is another possible solution, but it will tend to increase the size of encrypted text since each character will be 2digit string.
This solution will produce much compressed string without any conflicts.

- Anon July 24, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Your solution is actually good but I guess objective is to store A as 1 and decode it in the same way as far as I could conclude from the question.

- Aalekh Neema July 26, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

The encrypted msg can be decrypt and wont give the unique solution.

- goforgold July 21, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

if we start decrypting say "12352625118" then it wont have a unique decryption string. for unique decryption, metadata or some conventions are required.
each character is either represented by one integer character or two integer character. It can be changed to have two integer character representation like 01 for A, 02 for B and so on.

- hinax July 21, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

i gave a solution to interviewer,but he not satisfied.
i add

'\0'

with each character and when we decrypt msg then skip

'\0'

and we can get a original msg..but main problem is that if there 2 digit exits for single character then it gives different msg.for example 26 for Z,25 for Y but it gives me 2 for B,6 for F,2 for B,5 for E.

- rajat sadh July 21, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Add 9 to all encrypted values and store, example A-10,B-11....so on, prefix 0 to single digit numbers also works but not strong encryption.

- kanna July 21, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Store all the alphabets in a array. Encrypt the original file data using array location. Use charAt() and replace using java. Complexity rises based on length of data. If longer then use classes in java.util such as ArrayList.

- Coider July 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You don't have to store the alphabet in an array. Have a variable for an integer and a variable for a character. Read the first character into the character variable and then subtract it by 64. Now, set the integer variable to equal the subtracted character variable and send it to the output file.

- me July 22, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Store all the alphabets in a array. Encrypt the original file data using array location. Use charAt() and replace using java. Complexity rises based on length of data. If longer then use classes in java.util such as ArrayList.

- Coder July 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

<?php

$text = "ABCEZYAR";
$encryptText = "12352625118";

$dictonary = array();

$dictonary['A'] = 1;
$dictonary['B'] = 2; 
$dictonary['C'] = 3; 
$dictonary['D'] = 4; 
$dictonary['E'] = 5; 
$dictonary['F'] = 6; 
$dictonary['G'] = 7; 
$dictonary['H'] = 8; 
$dictonary['I'] = 9; 
$dictonary['J'] = 10; 
$dictonary['K'] = 11; 
$dictonary['L'] = 12; 
$dictonary['M'] = 13; 
$dictonary['N'] = 14; 
$dictonary['O'] = 15; 
$dictonary['P'] = 16; 
$dictonary['Q'] = 17; 
$dictonary['R'] = 18; 
$dictonary['S'] = 19; 
$dictonary['T'] = 20; 
$dictonary['U'] = 21; 
$dictonary['V'] = 22;
$dictonary['W'] = 23;
$dictonary['X'] = 24; 
$dictonary['Y'] = 25;
$dictonary['Z'] = 26;

$i= 0;
for($k = 0; $k <strlen($text); $k++) {
    $encrypted[$i] = $dictonary[$text[$k]];
    $i++;
}

echo implode('',$encrypted);
?>

- JP July 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Try decrypting the same text in php code.
There will be no unique solution from your code.

- Anon July 23, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

In this situation, you will develop your own encryption key and use that key for decryption. I have develop a simple encryption key. So, at time of encryption, you will generate output and key and use that output and key, you simply decrypt the data. code may be like below:

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

static string Encrypt(string input, out string encriptionKey)
        {
            string decript = string.Empty;
            encriptionKey = string.Empty;
            int encryptPart;
            foreach (char part in input.ToArray())
            {
                encryptPart = digit.FirstOrDefault(x => x.Value == part.ToString()).Key;
                decript = decript + encryptPart.ToString();
                if (encryptPart >= 10)
                    encriptionKey = encriptionKey + "1";
                else
                    encriptionKey = encriptionKey + "0";
            }

            return decript;
        }

static string Decrpt(string input, string key)
        {
            string outPut = string.Empty;
            int keyPart;
            foreach(char part in key.ToArray())
            {
                if(part == '0')
                {
                    keyPart = Convert.ToInt32(input.Substring(0, 1));
                    input = input.Substring(1);
                }
                else
                {
                    keyPart = Convert.ToInt32(input.Substring(0, 2));
                    input = input.Substring(2);
                }
                outPut = outPut + digit[keyPart];
            }

            return outPut;
        }

static void Main(string[] args)
        {
            string input = "ABCEZYAR";
            string key;
            string output = Encrypt(input, out key);
            string inputReturn = Decrpt(output, key);
      }

- Rajesh Kumar July 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Take a bit/boolean array to keep track of the characters that come after 'K'(mapping to a double digit number) while encrypting. While decryption, use this boolean array to check if the next character is mapped to a double digit number.If so, get the original character by decrypting 2 adjacent digits instead of 1 or else use just use single digit number.

import java.util.HashMap;
import java.util.Map;
import java.util.Set;

/**
 * 
 */

/**
 * @author Amish
 *
 */
public class Encryptior {

	static Map<Character, Integer> map = new HashMap<Character, Integer>();
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		map.put('A', 1);
	    map.put('B', 2);
	    map.put('C', 3);
	    map.put('D', 4);
	    map.put('E', 5);
	    map.put('F', 6);
	    map.put('G', 7);
	    map.put('H', 8);
	    map.put('I', 9);
	    map.put('J', 10);
	    map.put('K', 11);
	    map.put('L', 12);
	    map.put('M', 13);
	    map.put('N', 14);
	    map.put('O', 15);
	    map.put('P', 16);
	    map.put('Q', 17);
	    map.put('R', 18);
	    map.put('S', 19);
	    map.put('T', 20);
	    map.put('U', 21);
	    map.put('V', 22);
	    map.put('W', 23);
	    map.put('X', 24);
	    map.put('Y', 25);
	    map.put('Z', 26);
	    String str = "ABCEZYAR";
	    boolean[] isAfterK = new boolean[str.length()];
	    System.out.println(encrypt(str, isAfterK));
	    System.out.println(decrypt("12352625118", isAfterK));

	}
	private static String encrypt(String str, boolean[] isAfterK){
		char[] chars = str.toCharArray();
		String encrypted = "";
		for(int i = 0 ; i < chars.length ; i++){
			if(map.get(chars[i]) > 9)
				isAfterK[i]=true;
			encrypted += map.get(chars[i]);
		}
		return encrypted;
	}
	private static String decrypt(String encrypted, boolean[] isAfterK){
		String decrypted = "";
		int charIndex = 0;
		for(int i = 0 ; i < encrypted.length();){
			if(isAfterK[charIndex]){
				decrypted += getKey(map, Integer.parseInt(encrypted.substring(i, i+2)));
				i += 2;
				charIndex ++;
			}
			else{
				decrypted += getKey(map, Integer.parseInt(encrypted.substring(i, i+1)));
				i++;
				charIndex++;
			}
		}
		return decrypted;
	}
	private static char getKey(Map<Character, Integer> map, int value){
		Set<Map.Entry<Character, Integer>> entrySet = map.entrySet();
		for(Map.Entry<Character, Integer> entry : entrySet){
			if(entry.getValue() == value)
				return entry.getKey();
		}
		return 0;
	}

}

- Amish July 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

string s = "ABCEZYAR";
            StringBuilder decode = new StringBuilder();
            StringBuilder b = new StringBuilder();
            StringBuilder c = new StringBuilder();
            foreach (int a in s.ToLower())
            {
                b.Append(a + ",");
                c.Append(a - 96);
            }
            Console.WriteLine(c);
            foreach (string a in b.ToString().Split(','))
            {
                int a1;
                int.TryParse(a,out a1);
                decode.Append((char)a1);
            }
            Console.WriteLine(decode);

- Deepti July 27, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class EnciptAndDcript {

/**
* @param args
*/
public static void main(String[] args) {
String s = "ABCEZYAR";
for(int j=0;j<s.length();j++)
{
System.out.print(Character.getNumericValue(s.charAt(j))-9);

}
}

}

- Anonymous August 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;


public class StringEncript {

/**
* @param args
*/
public static void main(String args[])
{
String s = "ABCEZYAR";
List<Character>al= new ArrayList<Character>();
HashMap<Character,Integer> map = new HashMap<Character,Integer>();
for(int i=64;i<91;i++)
{
al.add((char)i);

}
for(int i=1;i<al.size();i++)
{
map.put( al.get(i),i);
}
for(int j=0;j<s.length();j++)
{
System.out.print(map.get(s.charAt(j)));
}

}
}

- Anonymous August 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Is there any requirement for encrypting and descrypting other letters not in "ABCEZYAR".
If just need to get an unique decryption and there's no HEAD AND TAIL. What about using dictionary :
"A"=>1,"B"=>2, "C"=>3,"E"=>52,"Z"=>62,"Y"=>51,"R"=>8.

- Echo February 18, 2015 | 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