## Yahoo Interview Question for Software Engineer / Developers

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

I think the intent here is that, we have 2 methods.

- Sort the rightmost half and merge (in place). Complexity = n + sqrt(n)log(n)
- Use the insertion sort way . Complexity = n*sqrt(n)

So, 1st method is better than 2nd.

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

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

Sort the last sqrt(n) and do a merge?

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

And what about the elements in between the first and last sqrt(n)?

Say n = 25. Your method only sorted 10 elements. lol.

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

@Anonymous2: What magical elements are there between the first n-sqrt(n) and last sqrt(n)? I am dying to know.

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

I think this works, and the complexity would be: O(sqrt(n)*log(n) + n)

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

i think what is meant was sort the last n - sqrt(n) elements

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

@ lct8712 i am not very sure but complexity should be
O(sqrt(n)*log(sqrt(n) + n) since merge sort for n elements takes O(n*log(n)) so for sqrt(n) elements it should take O(sqrt(n)*log(sqrt(n)) time complexity.

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

does it need sort in place?

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

yeah, dude/miss

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

Just wondering what significance sqrt has in the problem. Sorting the rest and merging them would work with any partition of the array.

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

jagat, there is no significance of sqrt number here, it could be any number of elements from the first element sorted.

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

I think yahoo doesn't want to recruit any more. It seems that they just want to continue interview processes just like that. And they seem to ask really weird questions. Recently a friend of mine faced really weird questions in a yahoo interview.

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

.. they're really weird, since they want you to not have seen them before, thus testing your new-problem-solving ability. They're not allowed to test IQ directly, this is how they do it.

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

start insertion sort from n - sqrt(n) pos.. complexity would be n*sqrt(n)

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

i also feel d same..we can use bucket sort but space complexity will be too high though time complexity can be O(n);

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

take the last sqrt(n) elements and insert them into the n-sqrt(n) using binary search.
time complexity is O(sqrt(n)*logn)

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

You mean insert last n-sqrt(n) elements using binary search in first sqrt(n) elements..

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

Complexity would be O(sqrt(n) * n). no MAGIC exists to insert at an arbitrary location of array without linear complexity to shift.

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

@anon: In-place merge is possible in O(n). So Magic does exist.

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

@anonymous:can u explain hw ur magic works,i mean in-place merge in 0(n)??

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

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

The way the question is framed I would use insertion sort. Its in place and is suitable for nearly sorted input. The array is arranged such that I can skip the first n - sqrt(n) iterations of the algorithm. The complexity would be O(n * sqrt(n)).

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

Most of the elements are already sorted in this array. If n = 25, then sqrt(n) = 5. So the problem already has n-sqrt(n) = 25 - 5 = 20 elements in the array sorted. Inserting sort would be a good idea here since it works well for nearly sorted input. Time complexity = O(n * sqrt(n))

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

I will go with sort the sqrt(n) elements and then merge the elements with n-sqrt(n) elements

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

insertion sort can also be used

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

The complexity is O(n) in the worst case. As given, the n - sqrt(n) elements are sorted. Let's assume (a) we are doing insertion sort and (b) the sqrt(n) elements are the smallest sqrt(n) elements in the entire array. In such a case, each insertion requires shifting of O(n-sqrt(n)) elements. Therefore, the total time to sort would be O (sqrt(n) * (n - sqrt(n) ) ) = O(n).

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

hey..it's O(n*sqrt(n))..according to ur logic..

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

Using Insertion Sort: As maximum of the elements of the array (n - sqrt(n)) are already sorted and only sqrt(n) elements are not sorted, so for a large amount of input, insertion sort would be better. Complexity of the algorithm: O(n * sqrt(n)).

Using Binary Search and Insertion: Suppose an array of 25 elements looks like: 6,7,8,9,10, ....., 25, 5,4,3,2,1. It is the case for the worst case. Just consider the time needed to properly place the last element 1. When it's the turn to insert 1, all other elements are already sorted. So do a binary search on all the (n-1) elements in time log(n-1). Now 1 must be inserted at the front of the array. This insertin needs all the (n-1) elements to move in the right direction. Time complexity: O(n-1). So for a single element to insert properly, the time complexity is: O(n-1) + O(log(n-1)). So for sqrt(n) number of elements this is: O(sqrt(n) * (O(n-1) + O(log(n-1)))). or simply: O(sqrt(n) * n).

It depends on the case which method to use.

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.