## Bloomberg LP Interview Question for Financial Application Engineers

Country: United States
Interview Type: In-Person

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

If we can't sort, then we probably can't change the array in any way.

A possible approach would be to use a min-heap of size k.
- Insert the first k numbers into the heap
- for each number insert it in the heap if it is larger than the current minimum and pop the minimum

The runtime will be O(n log k) with extra O(k) space.
Im my opinion, I expect 'k' to be much smaller than 'n'. Thus this approach ends up being better in practice than other approaches that run in O(n) but need to either
a) change it (it seems we're forbidden to change the array)
b) or use extra O(n) memory (remember the "enormous" word)

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

@ Miguel

It doesn't say that you can't change the array in anyway. Median of Medians is a valid solution given the no-sort condition.

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

lol hahahaha
that's technically correct actually

even if some randommethod() sorts the array and finds the largest k numbers in O(1) time {hypothetical}, we can always wrap it with:

``````newmethod( )
{
randomethod(), then save largest k;
swap two elements (so array isn't sorted anymore);
return largest k
}``````

:)
But assuming we can't trample the original array, let's fork off different answers based on that too.

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

Miguel's answer is the one I'd give for the "no trampling original array, n is huge."
n is huge sort of implies that k isn't.

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

The (in) famous median of median based partitioning algorithm.
Running Time : O(n)

Or its simpler cousin. Simple Selection Algorithm
Running Time :O(n) Expected

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

If we can't sort, then we probably can't change the array in any way and those methods require that.

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

``````#include<iostream>
using namespace std;

#define MIN_ -999999;

void replace_with_smallest(int * k_large_number,int k,int current)
{

int small=k_large_number[0];
int stor_i=0;

for(int i=0;i<k; i++)
if(small>k_large_number[i])
{
small=k_large_number[i];
stor_i=i;
}

if(small<current)
k_large_number[stor_i]=current;

}

void main()
{
int size=0;
cout<<"Enter the size of array:";
cin>>size;

int * arr=new int [size];

for(int i=0; i<size;i++)
{
cout<<"Enter values:";
cin>>arr[i];
}

cout<<"Enter the value of K::";

int k=0;
cin>>k;

int * k_large_number=new int [k];

for(int j=0; j<k; j++)
k_large_number[j]=MIN_;

int current=arr[0];

for(int print=0; print<k; print++)
cout<<k_large_number[print]<<",";
cout<<endl;

system("pause");
}``````

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

``````#include<iostream>
using namespace std;

#define MIN_ -999999;

void replace_with_smallest(int * k_large_number,int k,int current)
{

int small=k_large_number[0];
int stor_i=0;

for(int i=0;i<k; i++)
if(small>k_large_number[i])
{
small=k_large_number[i];
stor_i=i;
}

if(small<current)
k_large_number[stor_i]=current;

}

void main()
{
int size=0;
cout<<"Enter the size of array:";
cin>>size;

int * arr=new int [size];

for(int i=0; i<size;i++)
{
cout<<"Enter values:";
cin>>arr[i];
}

cout<<"Enter the value of K::";

int k=0;
cin>>k;

int * k_large_number=new int [k];

for(int j=0; j<k; j++)
k_large_number[j]=MIN_;

int current=arr[0];

for(int print=0; print<k; print++)
cout<<k_large_number[print]<<",";
cout<<endl;

system("pause");
}``````

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

``````#include<iostream>
using namespace std;

#define MIN_ -999999;

void replace_with_smallest(int * k_large_number,int k,int current)
{

int small=k_large_number[0];
int stor_i=0;

for(int i=0;i<k; i++)
if(small>k_large_number[i])
{
small=k_large_number[i];
stor_i=i;
}

if(small<current)
k_large_number[stor_i]=current;

}

void main()
{
int size=0;
cout<<"Enter the size of array:";
cin>>size;

int * arr=new int [size];

for(int i=0; i<size;i++)
{
cout<<"Enter values:";
cin>>arr[i];
}

cout<<"Enter the value of K::";

int k=0;
cin>>k;

int * k_large_number=new int [k];

for(int j=0; j<k; j++)
k_large_number[j]=MIN_;

int current=arr[0];

for(int print=0; print<k; print++)
cout<<k_large_number[print]<<",";
cout<<endl;

system("pause");
}``````

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

``````#include<iostream>
using namespace std;

#define MIN_ -999999;

void replace_with_smallest(int * k_large_number,int k,int current)
{

int small=k_large_number[0];
int stor_i=0;

for(int i=0;i<k; i++)
if(small>k_large_number[i])
{
small=k_large_number[i];
stor_i=i;
}

if(small<current)
k_large_number[stor_i]=current;

}

void main()
{
int size=0;
cout<<"Enter the size of array:";
cin>>size;

int * arr=new int [size];

for(int i=0; i<size;i++)
{
cout<<"Enter values:";
cin>>arr[i];
}

cout<<"Enter the value of K::";

int k=0;
cin>>k;

int * k_large_number=new int [k];

for(int j=0; j<k; j++)
k_large_number[j]=MIN_;

int current=arr[0];

for(int i=0; i<size ; i++ )
{
current=arr[i];
replace_with_smallest(k_large_number,k,current);

}

for(int print=0; print<k; print++)
cout<<k_large_number[print]<<",";
cout<<endl;

system("pause");
}``````

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

``````for(i=0;i<k;i++)
heap.push(a[i]);
for(i=k;i<n;i++)
{
if(a[i]>heap.top())
{
heap.pop();
heap.push(a[i]);
}
}
while(!heap.empty())
{
cout<<heap.top()<<"\t";
heap.pop();
}
cout<<endl;``````

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

I forgot to include the following:

``priority_queue<int,vector<int>,greater<int,int>>heap;``

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

Using a min-heap of k elements
First build the heap with the first k elements. As you advance the array, check if the current number is greater than the root of the heap. IFF it is greater, add it to the heap.

``````largest_elem(int a[], int k)
{
minheap hp;
int size=0;
for(int i=0;i<a.length;i++)
{
if(size<k)
{
hp.insert(a[i]);
} size++;
else
{
if(a[i]>hp.peek())
{
hp.extract-min();
hp.insert(a[i]);
}
}
}
}``````

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

Random select a number from the array, used it as pivot, then the numbers smaller than this goes to the left, the numbers larger than this goes to the right. Check the location of this pivot (m), if it is larger than k, then do this recursively to the left part, if it is smaller than k, then store the left part to the answer, and do this recursively to the right part, with k=k-m;

Time is O(N)

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

why is the time O(N)

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

After each iteration, you only need to do the recursion for either the left part or the right part. T(n) = T(n/2) + n
which means the total time is n + n/2 + n/4......= 2n, which is O(n)

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

``````import java.util.Comparator;
import java.util.Map;
import java.util.TreeMap;

class ReverseComparator implements Comparator<Comparable<Object>> {
@Override
public int compare(Comparable<Object> o1, Comparable<Object> o2) {
return o2.compareTo( o1 );
}
}

public class TopK {

public static void main(String[] args) {
int[] numbers = {1,3,2,6,7,5,9,10,13,12};
findTop5(numbers);
}

static void findTop5(int[] numbers) {
Comparator reverseComparator = new ReverseComparator();

Map<Integer, Integer> entries = new TreeMap<Integer, Integer>(reverseComparator);
for(int i : numbers) {
entries.put(i, i);
}

for(Map.Entry<Integer, Integer> entry : entries.entrySet()) {
System.out.println(entry.getKey()+" : "+entry.getValue());
}

}

}``````

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

Here is a solution without heap. The same thing can be done in an array.
If we need to find 'k' largest numbers, we take an array of size 'k' populated with first k items from the main data source. Now, keep on reading an item, and place it in the result array, if it has a place.

``````public static void largestkNumbers() {
int k = 4;    // find 4 largest numbers
int[] arr = {4,90,7,10,-5,34,98,1,2};
int[] result = new int[k];

//initial formation of elems
for (int i = 0; i < k; ++i) {
result[i] = arr[i];
}
Arrays.sort(result);

for ( int i = k; i < arr.length; ++i ) {
int index = binarySearch(result, arr[i]);
if (index > 0) {
// insert arr[i] at result[index] and remove result[0]
insertInBetweenArray(result, index, arr[i]);
}
}
}

public static void insertInBetweenArray(int[] arr, int index, int num) {
// insert num at arr[index] and remove arr[0]
for ( int i = 0 ; i < index; ++i ) {
arr[i] = arr[i+1];
}
arr[index-1] = num;
}

public static int binarySearch(int[] arr, int num) {

int lo = 0;
int hi = arr.length - 1;
int mid = -1;

while( lo <= hi ) {
mid = (lo+hi)/2;
if ( arr[mid] > num ) {
hi = mid-1;
} else if ( arr[mid] < num ) {
lo = mid+1;
} else {
return mid;
}
}
return mid;
}``````

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

I believe you cannot use sort anyway

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

Whether using a Heap, or just keeping a sorted array with the k largest numbers, any updates to this collection will take O(log(k) ) time. For a large k (let's say 1 million) this will become relatively slow. Does anyone want to provide a solution where the insert is O(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.