## Bloomberg LP Interview Question for Financial Software Developers

• 1
of 1 vote

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

Use hashing.

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

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

this only works for sorted array

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

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.

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

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).

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

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.

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

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.

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

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

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

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"...

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)

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)

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)

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???

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

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

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.

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)

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

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

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

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

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

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

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

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 ?

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.