Amazon Interview Question for Software Engineer in Tests

Team: Kindle
Country: United States
Interview Type: Phone Interview

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

If you assume a small set of possible characters, then counting sort will do it.

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

Yes, this is the right answer

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

Agreed. In fact if you assume there are only O(1) possible characters this only uses O(1) extra space (additional to the input and the output).

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

Yep, but...
If the character set is Unicode (what else in 2012?) than the constant on the O(1) is quite huge, to set up a 64K-size array to count is a significant amount of time, allocating and clearing this buffer should not be ignored.

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

public static void sortString(String unsortedString) {
char[] unsortedStringLetters = unsortedString.toCharArray();

int i;
for ( i = 0 ; i < stringToBeSorted.length() ; i++ ) {
chars[stringToBeSortedLetters[i]]++;
}

int j = 0;
for (i = 0 ; i < 256 ; i++ ) {
int count = chars[i];
while ( count > 0 ) {

stringToBeSortedLetters[j] = (char) i;
j++;
count--;
}
}

System.out.println(stringToBeSorted + " : " + String.valueOf(stringToBeSortedLetters));
}

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

This is not a linear solution... goes upto O(n^2).

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

as soon as you use a loop, you are out.

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

I meant nested loops.

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

public static void sortString(String stringToBeSorted) {
char[] stringToBeSortedLetters = stringToBeSorted.toCharArray();

int i;
for ( i = 0 ; i < stringToBeSorted.length() ; i++ ) {
chars[stringToBeSortedLetters[i]]++;
}

int j = 0;
for (i = 0 ; i < 256 ; i++ ) {
int count = chars[i];
while ( count > 0 ) {

stringToBeSortedLetters[j] = (char) i;
j++;
count--;
}
}

System.out.println(stringToBeSorted + " : " + String.valueOf(stringToBeSortedLetters));
}

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

Couting sort and bucket sort can be used.

void CountingSort(int *a, int n, int range) {
using namespace std;

int *b = new int(n);

for (int j =0; j<n; ++j)
b[j] =0;

int *count = new int (range+1);
int i;
for (i =0; i<=range; ++i)
count[i] = 0;

for (i =0; i<n; ++i)
count[a[i]] = count[a[i]] +1;

for (i =1; i<=range; i++)
count[i] = count[i] + count[i-1];

for (i =n-1; i>=0; i--) {
b[count[a[i]]-1] = a[i];
count[a[i]] = count[a[i]]- 1;
}

for (i =0; i<n; ++i)
cout<<b[i]<<" ";
cout<<endl;

}

int main () {
int a[] = {3,2,1,4,2,3,2,2,2,1,4,3,2};
int size = sizeof (a)/ sizeof(*a);
CountingSort(a,size,4);
return 0;
}

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

void sortCharArray(char a[])
{
int b;
int n = 5;
for(int i =0; i<256; i++)
b[i] = 0;
for(int j = 0; j<n; j++)
{
b[a[j]]++;
}
for(int i = 0; i<256; i++)
{
int c = b[i];
for(int j=0; j<c; j++)
{
char ch = i;
cout<<ch;
}
}
}

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

This is not a linear solution.. it goes upto O (n^2).

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

Answer: is not possible if we want to use linear space. If the space is not an issue we can use Counting sort, if the space is indeed an issue then a well optimized QuickSort can get nlogn time, which is almost linear.

Non comparison solutions like Counting and Bucket sort are the only kinds of sort that can guaranty linear time (with a small amount of possible elements), still is not linear space since you need to create a big indexed table, and that will take at the best case 2N of space.

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

I used radix sort. Here is the python code.

m = 10
n = 1
d = 2

for i in xrange(d):
v = [None] * 10

for c in str:
index = (ord(c) % m) / n

if (v[index] == None):
v[index] = []

v[index].append(c)

k = 0

for e in v:
if (e != None):
for item in e:
str[k] = item
k = k + 1

m = m * 10
n = n * 10

return str

Output is ['A', 'C', 'D', 'E', 'F', 'G', 'H', 'J', 'N', 'Q', 'X', 'Z']

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

Counting sort can be used only for Int and with a given range and here it is Char.

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

It's just a question of mapping every Char to an integer key, in such a way that the integer keys preserve the original set's sort order: a < b --> key(a) < key(b)

This is easy to do with chars --- in fact, pre-unicode, "char" generally was just an 8-bit integer (i.e., in C). Unicode and variable-length character encodings make it more complicated, but even then there are only around 110,000 characters, which is still small enough.

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

import java.util.Arrays;

public class SortCharArray {

public static void main( String args[] ) {

char[] a = { 'b', 'f', 'c', 'z', 'a', 'd', 'x', 'h' };

char[] b = charCountingSort( a );

for( int i = 0; i < b.length; i++ ) {
System.out.print( b[i] + " " );
}

}

private static char[] charCountingSort(char[] a) {

int[] count = new int;
char[] b = new char[a.length];

for( int i = 0; i < count.length; i++ ) {
count[i] = 0;
}

for( char c : a ) {
count[c - 'a']++;
}

int current = 0;

for( int i = 0; i < count.length; i++ ) {
if( count[i] != 0 ) {
Arrays.fill( b, current, current + count[i], (char)(i + 'a') );
current++;
}
}

return b;
}
}

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

It's counting sort. The time complexity is (O(n)), given that ACSII ranges from 0 to 255.

public class CountingSort {
public static final int k = 256;
public static String countingSort(String s) {
if (s == null) {
return null;
}

int[] c = new int[k];
char[] b = new char[s.length()];

for (int i = 0; i < c.length; i++) {
c[i] = 0;
}

for (int i = 0; i < s.length(); i++) {
c[s.charAt(i)]++;
}

for (int i = 1; i < k; i++) {
c[i] = c[i] + c[i - 1];
}

for (int i = 0; i < s.length(); i++) {
b[c[s.charAt(i)] - 1] = s.charAt(i);
c[s.charAt(i)]--;
}
return new String(b);
}

public static void main(String[] args) {
System.out.println(countingSort(""));
}
}

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.