## Facebook Interview Question for Software Engineer Interns

Country: United States
Interview Type: Phone Interview

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

QuickSort with findMedium to find the pivot. Use findMax on left side of pivot and findMin on right side of pivot until findMax > pivot and findMin < pivot ?

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

what is the time complexity in this case

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

I think it should be a Merge sort:

static int [] mergeSort()
{
if(ar == null || ar.length < 2)
{
return ar;
}
int min = findMin(ar, 0, ar.length);
int max= findMax(ar,0, ar.length);
return mergeSortHelper(ar, min, max);
}

static int []mergeSortHelper(int []ar, int min, int max)
{
min > end return ar;
min = findMin(ar);
max= findMax(ar);
int pivot = findMedium(min, max);
int []left = mergeSortHelper(min,mid);
int []right = mergeSortHelper(mid+1, max);
merge(left,right);

}

static int []merge((int []left, int []right))
{
int []res = new int[left.length + right.length];
int len = Math.min(left.length, right.length);
int i=o;
int leftIndex, rightIndex;
while(i < len)
{

if(left[leftIndex]< right[rightIndex)
{
res[i++] = (left[leftIndex++];
}
else
{
res[i++] = (right[right dex++];
}
}
int k = len;
if(left.length > k)
{
while( k < left.length)
{
res[i++] = (left[k++];
}
}
else
{

while( k < left.length)
{
res[++] = (right[k++];
}
}

}

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

Mergesort would be better than quicksort because the worst case run-time is still O(nLogn), and in quicksort, the pivot choice using findMedium may be a bad choice.

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

calling this function in the entire array will always resolve to the same numbers so
If it would be possible to specify a starting index on each of these functions
Then you could sort the array only using findMin(int i).
// finds Min from index i to array.length.

pseudocode:

``````public static void sortArray(int a[]) {

for (int i - 0; i < a.length; i++) {
int min = findMin(a.length, i);
if (min != a[i]) {
swap(a, min, i);
}
}

}``````

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

def sort(qslist):

if len(qslist) < 2:
return qslist

pivot = findMin(qslist)
small = [x for x in qslist if x < pivot]
equal = [x for x in qslist if x == pivot]
big = [x for x in qslist if x > pivot]

return sort(small) + equal + sort(big)

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

@ Mary are you sure that is findMin()?
I think you were thinking findMedium. Or is that intentional instead?

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

``````fnSort(int arr[],l,r)
{
for(int i=0,j=r;i<j;i++,j--)
{
var maxi=fnMax(arr,i,j);
var mini=fnMax(arr,i,j);
if(maxi!=j)
swap(arr,maxi,j);
if(mini!=i)
swap(arr,mini,i);
}
}``````

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

@VV, I will explain why I down-voted your question, please be wise and don't retaliate. Also, if you will correct the issue with problem statement, not only I will revert my down-vote, but will also up-vote this.

Any existing sorting method can use these 3 methods in addition to the algorithm. It is obvious that problem statement is incomplete and is also stating WHAT YOU CANNOT UTILIZE --->

OR: It potentially says that these 3 methods can complete with certain magical time complexity and now having such, come up with better time complexity for the sorting.

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

Not clear what the exact problem statement is.
- I am assuming that we cannot iterate the array?
- No swap method is given (which internally swaps two integer based at an index )?
- The only way I can assume this can be solved is given these APIs return index instead of value.

In which case (not handling off by one errors)

``````int begin = 0;
int end = getMedian() * 2 -1;

while(begin < end)
{
Swap(A, getMin(), begin);
Swap(B, getMax(), end);
begin += 1;
end - =1;
}``````

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

I am gonna assume that findMax, findMin, and findMedium all takes array A and its length as parameters and return the results in O(1) time.

If that is the case, I would use counting sort to sort the integer in O(N) time.

Any critics will be welcomed.

``````int* CountingSort(int* A, int len)
{
int max = findMax(A, len);
int min = findMin(A, len);
int clen = max - min +1;
int *c = new int[clen];
int *B = new int[len];
int i;

for (i = 0; i <clen; i++)
c[i] = 0;
for(i = 0; i <len; i++)
c[A[i]-min] += 1;
for (i = 0; i <clen; i++)
{
if (i >0)
c[i] = c[i-1]+c[i];
}

for (i = len-1; i >=0; i--)
{
B[c[A[i]-min]-1] = A[i];
c[A[i]-min] -=1;
}
delete [] c;
return B;
}``````

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

Pseudocode:

``````//p and r are the starting and end index of array A.
SORT(A, p, r):
if r > p + 2:	// more than 3 elements
q = PARTITION(A, p, r)
SORT(A, p, q-1)
SORT(A, q+1, r)
elif r == p + 2:	// 3 elements
min = findMin(A[p to r])
mid = findMedium(A[p to r])
max = fincMax(A[p to r])
A[p] = min
A[p + 1] = mid
A[r] = max
elif r == p + 1:	// 2 elements
min = findMin(A[p to r])
max = findMax(A[p to r])
A[p] = min
A[q] = max

PARTITION(A, p, r):
x = findMedium(A[p to r])
i = p - 1
for j = p to r:
if A[j] <= x:
i += 1
Swap A[i] with A[j]
return i``````

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

If most of the elements are distinct it should run in

``nlgn``

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

``````Does the question really ask people to sort the array? If not, then we can just maintain four heap data structure. One for max, one for min. and two for medium.

Run time, Log n.``````

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

Never mind, I misunderstand the question.

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

``````void sortMMM(vector<int>& values) {
int start = 0;
int end = values.size()-1;
while (start < end) {
int min = findMin(values, start, end);
swap(values[min], values[start]);
if (end-start+1 > 2) {
int max = findMax(values, start, end);
swap(values[max], values[end]);
int half = start + (end - start) / 2;
int mid = findMedium(values, start, end);
swap(values[mid], values[half]);
}
start = start+1;
end = end-1;
}
}``````

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

``````void sortMMM(vector<int>& values) {
int start = 0;
int end = values.size()-1;
while (start < end) {
int min = findMin(values, start, end);
swap(values[min], values[start]);
if (end-start+1 > 2) {
int max = findMax(values, start, end);
swap(values[max], values[end]);
int half = start + (end - start) / 2;
int mid = findMedium(values, start, end);
swap(values[mid], values[half]);
}
start = start+1;
end = end-1;
}
}``````

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.