## student student Interview Question for Students Students

• 0

Country: India
Interview Type: In-Person

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

If k is small, you can use a heap (which I suppose fits in the memory).

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

This solution is preferable to external sorting if the heap can fit into memory. Something like external sorting (or Quickselect) will be needed if can't, however.

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

External sorting algorithm, which sorts chunks that each fit in RAM, then merges the sorted chunks together. For example, for sorting 900 megabytes of data using only 100 megabytes of RAM:

Read 100 MB of the data in main memory and sort by some conventional method, like quicksort.
Write the sorted data to disk.
Repeat steps 1 and 2 until all of the data is in sorted 100 MB chunks (there are 900MB / 100MB = 9 chunks), which now need to be merged into one single output file.
Read the first 10 MB (= 100MB / (9 chunks + 1)) of each sorted chunk into input buffers in main memory and allocate the remaining 10 MB for an output buffer. (In practice, it might provide better performance to make the output buffer larger and the input buffers slightly smaller.)
Perform a 9-way merge and store the result in the output buffer. If the output buffer is full, write it to the final sorted file, and empty it. If any of the 9 input buffers gets empty, fill it with the next 10 MB of its associated 100 MB sorted chunk until no more data from the chunk is available. This is the key step that makes external merge sort work externally -- because the merge algorithm only makes one pass sequentially through each of the chunks, each chunk does not have to be loaded completely; rather, sequential parts of the chunk can be loaded as needed.

courtesy :- wikipedia (en.wikipedia.org/wiki/External_sorting )

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

use external sorting.

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

``````public static int getKthSmallest(int[] input,int k)
{
// post condition: This function returns kth smallest element
// Algorithm: selection algorithm:
// complexity: O(N)
// Assumption: All values in input are distinct.However, you can change this function a
// little bit to accommodate with non-distinct values
// Notes: I ignore the memory limitation. You can also optimize that in this function.

int pivotValue=input[(input.length-1)/2];
int [] rearrangement=new int[input.length];
int smaller=0,bigger=input.length-1;
for(int i=0;i<input.length;i++)
{
if(i!=((input.length-1)/2))
{
if(input[i]<pivotValue)
{
rearrangement[smaller]=input[i];
smaller++;
}
else if(input[i]>pivotValue)
{
rearrangement[bigger]=input[i];
bigger--;
}
}
}
if(smaller==k-1)
{
return pivotValue;
}
else if(smaller<k-1)
{
int [] nextInput=new int[input.length-smaller-1];
for(int i=0;i<input.length-smaller-1;i++)
{
nextInput[i]=rearrangement[i+smaller+1];
}
return getKthSmallest(nextInput,k-smaller-1);
}
else
{
int [] nextInput=new int[smaller];
for(int i=0;i<smaller;i++)
{
nextInput[i]=rearrangement[i];
}
return getKthSmallest(nextInput,k);
}
}
public static void printFirstKthSmallestElements(int [] input,int k)
{
int KthValue=getKthSmallest(input,k);
for(int i=0;i<input.length;i++)
{
if(input[i]<KthValue)
System.out.print(input[i]+",");
}
System.out.print(KthValue);
}``````

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

It's perhaps worth noting this algorithm has degenerate cases that are O(n^2). It is not worst-case O(n). With some randomization, the degenerate cases can be made extremely improbable.

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

External sorting is also a good solution for this question. The time complexity is NlogN, but the solution takes the memory limitation into account.

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

Heap will work perfectly if the K is a constant. If k is equal to half size of the array.The time complexity will be NlogN

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

Correct answer, I believe heap is the correct solution in majority of the cases.

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

Why NlogN? Maybe NlogK?

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

Use Merge sort.

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

This comment has been deleted.

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

Selection sort is O(n^2) in the best, worst, and average case.

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

1) Run insertion sort on the first k elements on array m of size k
2) For next element K, if K= > m[k-1], then discard
3) Else find first element m[i] such that K<m[i]. Move all elements m[i...k-1] to the right and m[i]=K; if any elements fall beyond the array, discard them.

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.