## A9 Interview Question for abcs

Country: United States
Interview Type: In-Person

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

``````//Quick Sort gives you O(n log n)
public class QuickSort {
int ArrLength;
int[] arr = {9,6,3,7,2,1,8,10,5,4};
static int count = 0;

private void sort(int[] arr){
if(arr == null || arr.length == 0){
return;
}
ArrLength = arr.length;
quicksortAlgo(0,ArrLength-1);

}

private void quicksortAlgo(int low, int high){

int i = low;
int j = high;
int pivot = ComputePivot(low, high);

count++;

while(arr[i] < arr[pivot]){
i++;
}

while(arr[j] > arr[pivot]){
j--;
}

if(i<=j){
swap(i,j);
i++;
j--;
}

if(i<high){
quicksortAlgo(i, high);
}

if(j>low){
quicksortAlgo(low, j);
}

}

private int ComputePivot(int low, int high){

return (new Random().nextInt(high - low +1) + low);

}

private void swap(int i, int j){

int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}

}``````

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

Merge sort can be inplace with O(n log n) and is stable.

``````#include <iostream>

using namespace std;

void print(int *a, int len) {
for (int i=0; i<len; i++)
cout << a[i];

cout << "\n";

}

void merge(int *a, int *b, int len1, int len2) {

int c[len1+len2];
int i=0, j=0, k=0;

while (i<len1 && j<len2) {
if (a[i] < b[j]) {
c[k++] = a[i++];
} else {
c[k++] = b[j++];
}
}

while (i<len1) {
c[k++] = a[i++];
}

while (j<len2) {
c[k++] = b[j++];
}

for(i=0; i<(len1+len2); i++) {

a[i] = c[i];
}
}

void sort(int *a, int start, int end) {

if (end <= start) return;

int len = end - start;

// ERROR: Must offset with index start to do inplace msort!
int mid = start + len/2;
if (len < 2) {

cout << "start " << start << ": " << a[start] << ", end " << end << ": " << a[end] << "\n";
if (a[start] > a[end]) {

int tmp = a[start];
a[start] = a[end];
a[end] = tmp;
}
} else {

cout << "start " << start << ": " << a[start] << ", mid " << mid << ": " << a[mid] << ", end " << end << ": " << a[end] << "\n";
sort(a, start, mid);
sort(a, mid+1, end);
merge(&a[start], &a[mid+1], (mid-start+1), (end-mid));
cout << "merge result: \n"; //  << start << ": " << a[start] << ", mid " << mid << ": " << a[mid] << ," end " << end << ": " << a[end] << "\n";
print(&a[start], end-start + 1);
}
}

void msort(int *a, int len) {

sort(a, 0, len-1);
}

int main() {

int a[] = {3,2,1};
print(a, 3);
msort(a, 3);
print(a, 3);

int b[] = {9,0,1, 5, 2, 7, 2,3};
print(b, 8);
msort(b, 8);
print(b, 8);

return 0;``````

}

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.

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