Interview Question for SDE-2s


Country: United States




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

Think about problem as an array of integer with 1,2 or 3 in it that needs
to be sorted in-place, not stable.

1) Use a standard, in-place compare-sort technique that will run
with O(n*lg(n)) time and O1(1) space complexity.

2) implement something like radix sort in place with O(n) time and O(1)
space complexity.

For fun 2) in java

public class SortThreeRadixInPlace {
    public static void sortSpecial(String[] array) {
        if(array == null || array.length <= 1) return;
        for(int p2s = 0, p3s = 0, i = 0; i < array.length; i++) {
            // [0, p2s) marks the range for prio. 1.
            // [p2s, p3s) marks the range for prio. 2.
            // [p3s, i) marks the range for prio 3.
            int prio = getPrio(array[i]); // here one would call the function to get the prio
            if(prio == 1) {
                swap(array, i, p2s);
                swap(array, i, p3s);
                p2s++;
                p3s++;
            } else if(prio == 2) {
                swap(array, i, p3s);
                p3s++;
            }
        }
    }

and the boilerplate to compile and drive

static public void main(String[] args) {
        String[] array = new String[]{"101", "302", "203", "104", "305", "106", "207", "208", "109", "310", "211"};
        sortSpecial(array);
        System.out.println(Arrays.toString(array));
	// output: [101, 104, 106, 109, 207, 208, 203, 211, 305, 310, 302]
    }

    static private int getPrio(String code) {
        // e.g. first character contains the prio 1,2,3
        int prio = code.charAt(0) - '0';
        if(prio >= 1 && prio <= 3) return prio;
        return 3;
    }

    static private <T> void swap(T[] array, int i, int j) {
        T tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
}

- ChrisK May 17, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Easier conceptual approach is to count each priority items and output

- WizardOfCode May 26, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void sortArray(String productCodeArray[]){
		System.out.println(Arrays.toString(productCodeArray));
		int mid=0;
		int low=0;
		int high  = productCodeArray.length-1;
		while(mid<=high){
			int priorityCode = getPriority(productCodeArray[mid]);
			String tmp = null;
			switch(priorityCode){
			case 1:
				tmp = productCodeArray[mid];
				productCodeArray[mid] = productCodeArray[low];
				productCodeArray[low]=tmp;
				mid++;
				low++;
				break;
			case 2:
				mid++;
				break;
			case 3:
				tmp = productCodeArray[mid];
				productCodeArray[mid] = productCodeArray[high];
				productCodeArray[high]=tmp;
				high--;
				break;
			}
		}
		System.out.println("After Sorting: "+Arrays.toString(productCodeArray));
	}

- Ghosh June 10, 2017 | 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