## Bloomberg LP Interview Question for Financial Software Developers

Country: United States
Interview Type: In-Person

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

This problem can be solved in O(n) time.

``````private static void findPairs(int[] a, int n){
//map of the value of an element to the list of indices of elements equal to this one
for (int i=0;i<a.length;i++){
int pair = n-a[i];
if (indices.containsKey(pair) && indices.get(pair).size() > 0){
System.out.println(indices.get(pair).removeFirst() + " " + i);
} else {
if (!indices.containsKey(a[i]))
}
}
}``````

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

HashMap.contains is O(1)

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

``````void sumTwo(int *arr, int size, int sum)
{
int first, second;
for(int i = 0; i < size; i++)
{
if(arr[i] <= sum)
{
first = arr[i];
for(int j = i + 1; j < size; j++)
{
second = arr[j];
if((second + first)==sum)
{
cout << first << " " << arr[j] << endl;
int temp = arr[j];
arr[j] = arr[i+1];
arr[i+1] = temp;
j = size;
//i++;
}
}
}
}
}``````

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

This is O(n^2).. the HashMap solution is O(n)

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

for every element i in aray
For every element i search another element sum-i in array. ( o(n) for searching )

total complexity - o(n^2)
Can be reduced with fast searching algorithms)

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

the interviewer expected for a more efficient way. You can sort it first to be in ascending order. then look at the sum of the first and last element. if greater than the certain value, check the sum of the first element and second to the last element. if smaller, check the sum of 2nd and the last. In this way you need to only go through the sorted array once.

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

User hashset to store the array and check if sum-i exists. However, for the case when sum is 2, and i=1. In that case sum=i+i need to be dealt with,

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

User hashset to store the array and check if sum-i exists. However, for the case when sum is 2, and i=1. In that case sum=i+i need to be dealt with,

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

In case of hash set we also need to deal with case where i=sum/2 in that case sum= i+ i...
I think a custom impl of hashset can solve the problem. Where repeated numberd will chained to the same hashcode.

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

In case of hash set we also need to deal with case where i=sum/2 in that case sum= i+ i...
I think a custom impl of hashset can solve the problem. Where repeated numberd will chained to the same hashcode.

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

In case of hash set we also need to deal with case where i=sum/2 in that case sum= i+ i...
I think a custom impl of hashset can solve the problem. Where repeated numberd will chained to the same hashcode.

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

@echooo : in your approach we have to sort the set the best sorting will take o(nlogn) and again we have compare the sums of the entire sorted set that will take O(n) so swapnil's approach would be better of just finding sum-a[i] th term for every term in array.

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

Take element a[i] from i=1 to n from array and search a created binary tree of sum-a[i]. if a[i] matches we get a match else we add sum-a[i] to the tree.

The worse case complexity will be nlogn + nlogn = O(nlogn)

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

Famous and frequently asked question, the solution can be O(logN) + O(1).

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

Sorry, it can be O(nlogn)+O(n)

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

sort it then traversing from both sides

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

without sorting can we just add the first element to all the elements one by one and store the values in the hash map,and the second with third and soon upto last element.till n-1 elemnts and store the values in the hash table.this hash table may need o(n(n-1)/2) time to construct but than the look up for any sum would be just o(1) times.

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

1 build a BST , O(nlogn)

2. for i to sum, search sum-i, O(nlogn)

so O(nlogn)

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

Here is a Recursive version:

``````...
void FindSumOfPairs( int a[], int n, int sum )
{
if( --n == 0 )
return;
FindSumOfPairs( &a[1], n, sum );
for( int i = 0; i < n; i++ )
{
if( a[0] + a[i+1] == sum )
cout << a[0] << "+" << a[i+1] << "=" << sum << endl;
}
}
...
int a[] = { 9, 6, -2, 1, -3, 7, -5 };
int n = 7;
FindSumOfPairs( &a[0], n, 4 );
...``````

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.