Bloomberg LP Interview Question for Financial Software Developers






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

Use hashing.

- amit April 07, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

for each element of an array A, perform a binary search for that element on the other array B. this takes O(lg n) for each element of A, so it takes a total of n*O(lg n) time

- Anonymous May 19, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

this only works for sorted array

- Anonymous September 13, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

for each element of an array A, perform a binary search for that element on the other array B. this takes O(lg n) for each element of A, so it takes a total of n*O(lg n) time

- Anonymous May 19, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

If one array is size n, and the other m, then we can do it in either O(n log m) or O(m log n), depending on which array you choose to do the binary search in.

if m is much larger than n, then O(n log m) would be preferable, So you pick the array with lesser elements and go through each of that and do a binary search on the larger array.

- LOLer May 19, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

The arrays are not sorted as given. So you need to consider in the nlogn and mlogm sorting cost first.
If the arrays are sorted, then an aligned sweep of both arrays will suffice. Complexity is O(n+m).

- danana May 30, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

You are right. I forgot to add the sorting cost.

It is O( (n+m) log n) or O ( (n+m) log m) depending on the array you choose to sort.

So it seems like sorting the smaller array is better.

- LOLer June 05, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

And, if both arrays are sorted...

Using a aligned sweep O(n+m) need not be better. Doing a binary search on the larger array might be better, depending on n and m.

- LOLer June 05, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Ok...this probably is a dumb question...but what does an "aligned sweep" mean here? :-S

- Anonymous July 07, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

By aligned sweep I meant the following:

You have index a into array A and index b into array B.
(Assume A and B are sorted ascending starting with least at 0).

Initially a = b = 0.

Now you compare A[a] with B[b]
if both are equal, add A[a] (or B[b]) to list of common elements and increment a and increment b.
if A[a] < B[b] increment a.
if A[a] > B[b] increment b.

This is what I meant by "aligned sweep"...

- LOLer July 07, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Give A[n] and B[m]:
1. if n>> m, sort B in O(m* log m);
2. remove duplicated in B, Get B[m'], where m' <= m;
3. for each A[i], binary search B* in log m' time;
4. It is n* log m' + m*(1+log m)
5. For m' << n, we can say it is O(n)

- kulang June 04, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

scan Array_1, record in hash table. scan Array_2, look up in Hash table.
time: O(n)

- jaikit October 14, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

for 2 unsorted arrays...
LOLer is Right. O( (n+m) log n)
where m,n are size of 2 arrays, and m > n.

if atleast one is sorted O(mlogn)
if both are sorted O(m+n) (FYI, you could use O(mlogn) too)

- EveryoneLovesMicrosoft November 01, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Suppose size of smaller array is n and size of larger array is m.

If we sort the smaller array first(nlogn) and then (Binary)search for each element in the larger array(Ologn) one by one(Total m elements) in this sorted array then it can be achieved in nlogn+mlogn=m+n(logn)

But what happens if each array have some duplicate elements itself contained inside it????Can someone suggest further or any other good logic???

- KK July 23, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

The running time in the above scenario is (m+n)logn.It was a typing error.

- KK July 23, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

For finding the intersection of the two arrays we will need the concept of hashing and at first, we will insert the array elements of the largest array and then, we will check the elements which are present in the hashset if yes then, they are the array elements which are common to both the arrays.

- swapnilkant11 July 22, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

U can use merge sort... makes sense? and identify the duplicates while merging.... so total time will be O(nlogn)

- Anonymous May 09, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

it can be done in O(n), don't sort it

- Anonymous September 13, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

how are you going to do it in O(n)? you should better explain it mister.

- Anonymous January 03, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

we are not sorting only merging and brush up merge sort merging takes o(m+n) time

- first Anonymous March 03, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Without sorting how can we compare elements ? Is it really possible in O(n) , if so which part of the algorithm are you cutting off the extra cost ?

- Anonymous February 25, 2012 | Flag


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More