Bloomberg LP Interview Question Financial Application Engineers
Country: United States
Interview Type: In-Person
@ 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.
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.
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
#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");
}
#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");
}
#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");
}
#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");
}
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;
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]);
}
}
}
}
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)
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());
}
}
}
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;
}
If we can't sort, then we probably can't change the array in any way.
- Miguel Oliveira October 26, 2013A 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)