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.

- fwiffo October 17, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yes, this is the right answer

- wqhrock October 18, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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).

- Anonymous October 18, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Selmeczy, P├ęter October 19, 2012 | Flag
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));
}

- belligerentCoder October 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- jeanclaude October 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- visitor June 16, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I meant nested loops.

- visitor June 16, 2014 | Flag
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));
}

- belligerentCoder October 18, 2012 | Flag Reply
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;
}

- crystal.rishi2 October 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void sortCharArray(char a[])
{
   int b[256];
    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;
            }
    }  
}

- Manikanta October 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- jeanclaude October 19, 2012 | Flag
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.

- rahvii October 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I used radix sort. Here is the python code.

def radixsort (str):
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

print radixsort(['A','N','F','J','D','H','C','G','Z','E','X','Q'])


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

- Anonymous November 08, 2012 | Flag Reply
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.

- hint January 03, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- fwiffo January 03, 2013 | Flag
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[26];
		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;
	}
}

- howardkhl January 15, 2013 | Flag Reply
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(""));
  }
}

- Yue March 27, 2013 | 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