Amazon Interview Question
Software Engineer InternsCountry: United States
Interview Type: Phone Interview
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.
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.
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.
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.
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.
<?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);
?>
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);
}
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;
}
}
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);
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)));
}
}
}
The problem over here is whether the '1' or '2' belongs to a two digit representation or a single digit representation.
- Anon July 21, 2014We 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.