Pages

Saturday, September 28, 2013

[Amazon interview question] A character array of arbitary length with 'R', 'B', 'W' is needed to be sorted in that order.

There is char array of n length. Array can have elements only from of any order R, B, W. You need to sort array so that order should R,B,W i.e. all R will come first followed by B and then W.
Constraints: Time complexity is O(n) and space complexity should be O(1)
Assumption: You can assume one swap method is given with signature swap(int index1, int index2) that swaps number in unit time.
method given to implement: public sort(char[]array);
    public static void sort(char[] arr){
        int rIndex = 0, wIndex = arr.length -1;
        for (int i = 0 ; i <= wIndex; ){
            if ( arr[i] == 'R' ){
                swap(arr, i , rIndex ++ );
                i ++ ;
            } else if (arr[i] == 'W' ){
                swap(arr, i , wIndex -- );
            }else{
             i ++;
            }
        }
    }
    //a dummy implementation just for testing sake
    private static void swap(char[] arr, int index1, int index2){
        char temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }

Please leave your comments and suggestions that improves the logic above.

No comments:

Post a Comment