Amazon Interview Question for SDE1s


Country: United States




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

Java Code:
code is simple,effective and easy to understand.

public class Encrypt {
public static void main(String[] args) {
String string="aaaabbccdd";
StringBuffer sb=new StringBuffer("");
int count=0;
char str=string.charAt(0);
for(int i=0;i<string.length();i++)
{
if(str==string.charAt(i))
{
count++;
}
else
{
sb=sb.append(str);
str=string.charAt(i);
sb.append(count);
count=1;
}
}
System.out.println(sb);

}

}

- sksantoshkumar090 January 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

When I wrote the same thing in Python, it won't append the last characters because of the end case on your if statement.

At the end of the iteration, I added the last character to the final string

def encodeString(s):
char = s[0]
count = 1
final = ""
for c in s:
if char == c:
count += 1
else:
final += char
final += str(count)
count = 1
char = c
final += char
final += str(count)
return final


print encodeString("aaabbcccdd")

- stelles January 10, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Is it for contiguous characters only? For eg : What should happen for strings like aabbaaccaa? Should it be a2b2a2c2a2 OR a6b2c2?

- Anonymous January 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Good observation. The former one that you mentioned.

- lks January 09, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Did the interviewer allow to use extra space to store the result?
If input string array should be used for output,
abc would expand to a1b1c1 so that the input string array would be not enough.

- Mark January 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

U can omit that condition. No character of frequency 1 exists

- lks January 09, 2014 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 votes

If you omit this condition, the problem becomes very simple. I guess, later or sooner the interviewer would ask you to add this condition as well.

- Dharam January 09, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

string getStringFromNumber(int i)
{
	ostringstream ss;
	ss << i;
	return ss.str();
}
void printFormattedString1(string iStr)
{
	string finalStr = "";
	//int counter = 0;
	int characters[256] = {0};
	int totalChars = iStr.length();
	for(int i = 0; i < totalChars; ++i)
	{
		counter++;
		characters[int(iStr[i])]++;
	}

	for(int j = 0; j < 256; ++j)
	{
		counter++;
		if(characters[j])
		{
			finalStr += char(j);
			finalStr += getStringFromNumber(characters[j]);
		}
	}

	//cout<<endl<<counter;
	cout<< endl << finalStr;
}

- Anonymous January 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

i forgot to comment the two couter++ statements. Please ignore.

- Anonymous January 09, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

this is the solution to the latter one.

- Anonymous January 09, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Solution to the former one :

void printFormattedString(string iStr)
{
	string finalStr = "";
	char currChar = iStr[0];
	int ctr = 0;
	//int counter = 0;
	int totalChars = iStr.length();
	for(int i = 0; i <= totalChars; ++i)
	{
		char newChar = ' ';
		//counter++;
		if( i < totalChars )
		{
			newChar = iStr[i];
		}
		if(newChar == currChar)
		{
			ctr++;
		}
		else
		{
			finalStr += currChar;
			finalStr += getStringFromNumber(ctr);
			ctr = 1;
			currChar = newChar;
		}
	}
	//cout<<endl<<counter;
	cout<< endl << finalStr;
}

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

Java Code:

public class StringCompApp {

public static String StringComp(String str) {

int tail=0;
int count=1;
String compStr = "";

for (int j=1; j<str.length(); j++) {
if(str.charAt(j) == str.charAt(tail)) {
tail++;
count++;
}
else {
compStr = compStr + str.charAt(tail) + count;
System.out.println("compStr: " + compStr);
tail++;
count = 1;
}
}
//for the last character count
compStr = compStr + str.charAt(tail) + count;

return compStr;
}
public static void main(String[] args) {

String str1 = "aaaabbcccdefgg";
String compstr1;

compstr1 = StringComp(str1);

System.out.println("Compressed Str: " + compstr1);

}

}

- sreekanth_77@yahoo.com January 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Do a single scan of the string and collect and print the data as below. Space complexity is constant, time is linear:

#include <stdio.h>

void enc(const char* buf, int size)
{
	if (NULL == buf)
		return;
	
	int cnt = 0;
	char pc = 0;
	
	for (int i = 0; i < size; i++)
	{
		if (pc == buf[i])
		{
			cnt++;
		}
		else
		{
			// process the previous char
			if(pc)
				printf("%c%d", pc, cnt);
			
			pc = buf[i];
			cnt = 1;
		}
	}
	
	// process the final char(s)
	if (cnt)
		printf("%c%d", pc, cnt);
}


int main(int argc, char* argv[])
{
	char buf[] = "aaaabbccdd";
	int size = strlen(buf);
	enc(buf, size);
	return 0;
}

- ashot madatyan January 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void encodeString(String input)
{
char[] inputArray = input.toCharArray();
int charCounter = 1;
int arrayIndex = 0;
char tmpChar = inputArray[0];
String encodeString="";

System.out.println("Method 1:");
for (int i = 1; i < inputArray.length; i++) {
if(tmpChar == inputArray[i])
charCounter++;
else
{
// 1. You can just go on printing new string as and when you find it. In this case in the end you wont have it stored anywhere.
// 2. We copy encoded string to new string. So space increases
// 3. You can modify your current char array with encoded string. When encoding is over you can insert special char to mark the end.
// The catch here is there should be no such char which occurs only once since then you will exceed char array limit. Ex abc -> a1b1c1 which goes beyond limit of char array.
System.out.print(tmpChar+Integer.toString(charCounter));
encodeString=encodeString+tmpChar+ Integer.toString(charCounter);
inputArray[arrayIndex]=tmpChar;
arrayIndex++;
if(((String)Integer.toString(charCounter)).toCharArray().length>1)
{
char[] charCounterArray = ((String)Integer.toString(charCounter)).toCharArray();
for (int j = 0; j < charCounterArray.length; j++) {
inputArray[arrayIndex]=charCounterArray[j];
arrayIndex++;
}
}
else
{
inputArray[arrayIndex]=((String)Integer.toString(charCounter)).charAt(0);
arrayIndex++;
}

tmpChar = inputArray[i];
charCounter =1;

}
}
// collecting final char
System.out.print(tmpChar+Integer.toString(charCounter));
System.out.println();

encodeString = encodeString+tmpChar+charCounter;
System.out.println("Method 2: "+encodeString);

inputArray[arrayIndex]=tmpChar;
arrayIndex++;
if(((String)Integer.toString(charCounter)).toCharArray().length>1)
{
char[] charCounterArray = ((String)Integer.toString(charCounter)).toCharArray();
for (int j = 0; j < charCounterArray.length; j++) {
inputArray[arrayIndex]=charCounterArray[j];
arrayIndex++;
}
}
else
{
inputArray[arrayIndex]=((String)Integer.toString(charCounter)).charAt(0);
arrayIndex++;
}
// Marking end of collection in original array
inputArray[arrayIndex]='*';

System.out.println("Method 3: ");
for (int i = 0; i < inputArray.length; i++) {
if(inputArray[i]=='*')
break;
System.out.print(inputArray[i]);
}
System.out.println();

}

- loveCoding January 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <stdio.h>
#include <string>

int main(){
	std::string input = "abbeeecccd";
	char lastChar = input[0];
	int count = 0;
	for (auto x : input){
		if (lastChar != x){
			printf("%c%d", lastChar, count);
			count = 0;
			lastChar = x;
		}
		count++;
	}
	printf("%c%d", lastChar, count);
}

- GK January 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.StringBuilder;

public class Encoding {

	protected static StringBuilder encodedStr = new StringBuilder();

	private static void encodeStr(char[] c, int start) {
		int count = 1;

		if (start > c.size -1) {
			return;
		}

		encodedStr.add(c[start]);

		while (c[count + start - 1] == c[count + start]) {
			count++;
		}
		encodedStr.add(count);

		encodeStr(c, start+count);
	}

	public static String encodeStr(String str) {
		encodeStr(str.toCharArray(), 0);
		return encodedStr.toString();
	}
}

- GSheld January 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void main(String args[]){
	         String str = "aaaabbbbcccddddefgh";
	         StringBuilder sbr = new StringBuilder("");
	         int count=0;
	         for(int i=0;i<str.length();){
	             count=1;
	             sbr.append(str.charAt(i));
	             while(i<str.length() && (i+1)<str.length() && str.charAt(i)==str.charAt(i+1)){
	                 count++;
	                 i++;
	             }
	            sbr.append(count);
	            i++;
	         }
	         
	         System.out.println(sbr);
	                
	    }

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

import java.util.Scanner;
public class Encript {


public static void main(String [] arg){
int count=1;
String s1="",s2="";
Scanner in=new Scanner(System.in);
s1=in.nextLine();

System.out.print("The encripted stirng is....");
for(int i=0;i<s1.length()-1;i++)
{ if(s1.charAt(i)==s1.charAt(i+1))
count++;
else
{
System.out.print(s1.charAt(i));
System.out.print(count);
count=1;
}
}
System.out.print(s1.charAt(s1.length()-1));
System.out.print(count);
}
}

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

what if continous aaa... array will be more than 256?

- glebstepanov1992 January 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

<pre class="language-java">
public static void Encrypt(){
String in="aaaabbbcccccccdddgggggg";
StringBuilder sb=new StringBuilder("");
int count=0;
char c=in.charAt(0);
for (int i = 0; i < in.length(); i++) {
if(c==in.charAt(i)) count++;
else {
sb=sb.append(c);
sb.append(count);
c=in.charAt(i);
count=1;
}
}
sb.append(c);
sb.append(count);
System.out.println(sb.toString());
}
</pre>

- TerrorGeek January 15, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void Encrypt(){ 
String in="aaaabbbcccccccdddgggggg"; 
StringBuilder sb=new StringBuilder(""); 
int count=0; 
char c=in.charAt(0); 
for (int i = 0; i < in.length(); i++) { 
if(c==in.charAt(i)) count++; 
else { 
sb=sb.append(c); 
sb.append(count); 
c=in.charAt(i); 
count=1; 
} 
} 
sb.append(c); 
sb.append(count); 
System.out.println(sb.toString()); 
}

- TerrorGeek January 15, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This one could use a little more optimization. encode function will not reallocate string buffer. I used strdup in main to avoid access violations.

#include <stdio.h>
#include <string.h>

char* encode(char* arr);
int main (int argc, char * argv[]){
        if (argc > 1){
                printf ("\'%s\' > %s\n",argv[1], encode(strdup(argv[1])));
        }
}

char* encode(char* arr){
        char * orig = arr;
        unsigned short int count = 1;
        char * ref = arr;
        char * wrt = arr;
        while (*arr != '\0'){
                if (*ref == *arr && arr > ref){
                        ++count;
                }else if (*ref != *arr && arr > ref){
                        if (count >= 2){
                                int pc = sprintf(++wrt,"%d",count);
                                wrt += pc;
                        }
                        *(wrt) = *arr;
                        ref = arr;
                        count = 1;
                }else
                        count = 1;
                arr ++;
        }
        if (count >= 2){
                int pc = sprintf(++wrt,"%d",count);
                wrt += pc;
        }

        return orig;
}

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

public String encodeString( String s ){
		if ( s == null || s.isEmpty()) return "";
		char curChar = s.charAt(0);
		int counter = 0;
		for ( int i = 0; i < s.length; i += 1){
			char newChar = s.charAt(i);
			if ( newChar == curChar ) counter += 1;
			else{
				s.replaceFirst(""+curChar+"+",""+curChar+counter);
				curChar = newChar;
				counter = 0;
			}		
		}
	}

- tango January 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>
#include<string.h>

void Encode(char ch[], int size)
{
char abc[10]="",abd[10]="";
int i,j,flag=0,size1;
for(i=0;i<size-1;i++)
{
flag=ch[i]-97;

if(abc[flag]>0)
{
abc[flag]++;
}
else
{
abc[flag]=1;
abd[flag]=ch[i];
}
}
size1=strlen(abc);
for(j=0;j<size1;j++)
printf("%c%d",abd[j],abc[j]);

}

int main()
{
char buf[] = "aaaabadbaccdbd";
int size = sizeof(buf)/sizeof(buf[0]);

Encode(buf, size);
return 0;
}

- Rajeev February 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

char ch;
     char arr[3]="\0";
     int count = 0;
     char input[] = "aaaabbccdddddeeee";
     char result[50] = "\0";
     int i;
     ch = input[0];
     for ( i = 0 ; input[i] != '\0'; i++ )
     {
        if( input[i] == ch )
        {
           count++;
           continue;
        }
        else
        {
           ch = input[i];
           snprintf( arr,sizeof(arr),"%c%d", input[i-1], count);
           strcat( result, arr);
           count = 1;
           continue;
        }
     }
    printf("%s\n", result);

- Dhananjaya February 12, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

How about this? create a HashMap<String, Integer>, for a given string length check each character in the hash map If(!Map.containsKey(key)) Map.put("character", count) else
Map.put("character", count+1).

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

public class EncodeString {

public static void main(String[] args) {

String s = "aaaabbccdd";
char a[] = s.toCharArray();
StringBuilder sb = new StringBuilder();
int count = 1;
TreeMap<Character, Integer> map = new TreeMap();
for (int i = 0; i < a.length; i++) {
if (map.containsKey(a[i])) {
count = map.get(a[i]);
count++;
map.put(a[i], count);
} else
map.put(a[i], 1);
}
for (Object key : map.keySet()) {
System.out.print(key.toString() + map.get(key).toString());
}

}

}

- yash.varshney05 April 08, 2014 | 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