Amazon Interview Question
Software Engineer in TestsTeam: Kindle
Country: United States
Interview Type: Phone Interview
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).
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));
}
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));
}
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;
}
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;
}
}
}
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.
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']
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.
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;
}
}
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(""));
}
}
If you assume a small set of possible characters, then counting sort will do it.
- fwiffo October 17, 2012