Symantec Interview Question for Software Engineer / Developers


Country: United States
Interview Type: Phone Interview




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

I would recommend you first put all odd-position ints in the first half, and then run an in-place sort like heapsort on each half separately.

- Anonymous September 05, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

the even position number should start at len(array)//2.

for the first half. for the int at position i, array[0:i] has been sorted. if i is odd, insertion sort array[i] into array[0:i]. if i is even, swap it with an odd position number in the second half and then do the insertion sort.

then insertion sort the second half.

def sort_even_odd(array):
	l = len(array)
	even_start = l // 2
	even_ptr = even_start
	if even_ptr % 2 == 0: 
		even_ptr += 1
		
	for i in range(even_start):
		if i % 2 == 0:
			assert even_ptr < l, "even_start={0}, even_pr={1}, i = {2}".format(even_start, even_ptr, i)
			array[i], array[even_ptr] = array[even_ptr], array[i]
			even_ptr += 2
			
		for j in range(i - 1, -1, -1):
			if array[j + 1] < array[j]:
				array[j + 1], array[j] = array[j], array[j + 1]
			else:
				break
	for i in range(even_start, l):
		for j in range(i - 1, even_start - 1, -1):
			if array[j + 1] < array[j]:
				array[j + 1], array[j] = array[j], array[j + 1]
			else: 
				break
		
	return array

- gnahzy September 05, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Insertion sort would be very inefficient if the array was very large. Quicksort is better overall; if written iteratively, even better.

- Jack September 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Jack: very true. You could also use heapsort if the degenerate cases of quicksort are not acceptable.

- eugene.yarovoi September 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

@gnahzy ..logic plz..

- saraf2206 September 05, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

// move all odd elements into 1st half, even elements into 2nd half

public static int[] sort(final int[] array) {
        int iter = 1;

        for (iter = 1; iter < (array.length / 2); iter++) {
            if ((iter % 2) > 0) {
                swap(array, iter, (array.length / 2) - 1 + iter);
            }
        }

       // Quicksort(in-place), avg nlogn performance provided by Java
        Arrays.sort(array, 0, (array.length / 2));
        Arrays.sort(array, array.length / 2, array.length);

        return array;
    }

Total running time: O(n + nlogn)

- Jack September 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The fastest we can sort an array of size n is O(nlogn). So in this case also we can sort in O(nlogn) complexity. We can first bring all the odd position array in the first half array and all the even position in the second half of the array. Now the first half a[0..n/2] and second half [n/2+1,n-1] can be independently sorted by two calls to quicksort like given below:

quickSort(a, 0, n/2);
quickSort(a,(n/2)+1, n-1);

void quickSort(int a[], int start, int end)
{
    if (start < end)
    {
        int pivot = start;
        int j = partition(a, start, end, pivot);
        int temp = a[pivot];
        a[pivot] = a[j];
        a[j] = temp;
        quickSort(a, start, j-1);
        quickSort(a, j+1, end);
    }
}

int partition(int a[], int start, int end, int pivot)
{
    static int numTimes = 0;
    while(start < end)
    {
        while(a[start]<=a[pivot] && start < end)
            ++start;
        while(a[end]>a[pivot])
            --end;
        if (start < end)
        {
            int temp = a[start];
            a[start]=a[end];
            a[end] = temp;
        }
    } 

    return end;
}

- Jitendra Singh Bhadoriya September 26, 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