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

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``````

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.

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.

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

@gnahzy ..logic plz..

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

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;
}``````

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