## Bloomberg LP Interview Question for Financial Software Developers

Country: United States

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

* Sort the array, takes O(nlogn)

* Taking two variables i & j starting from 0 and i+1 respectively, with one counter variable as 0

if i==j then
increment j by 1 and counter by 1, until the equality fails then increment i by (counter + 1)
else if i != j && counter>0
i <- j and j <- i+1 and counter = 0
else
we have found the number at i

Step 2 takes O(n) time. In gross the program should take O(nlogn) time. Correct me if I am going wrong somewhere

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

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

fail

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

@Anon: What? Why?

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

if there is no time complexity requirement, we can just use two layers loops.

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

Use a redblack or other type of balanced BST.

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

Use radix sort. And then find first a[i] != a[i + 1]. Complexity is O(n * k) where K = 32. Actually if all numbers are positive it can be done in constant memory.

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

ok but, if you do radix sort , won`t you lose the order ?
( because the question asks the first unique in an unsorted array )

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

Actually, you have to save the positions in another array and use radix sort as if the original array contains the keys and the position array contains the values. Then, the first element that is not equal to its adjacent gives you the key to its position in the original array.

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

I'm sorry I made a mistake. You should not use the "first" element that is not equal to its adjacent but the one with the "minimum position value". IvgenyNovo has given this solution in this thread more concisely.

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

There is one algorithm which will work in linear time but it is probabilistic.

1) Create a bloom filter (BF1) and add each element to it ( O(1) space and O(N) complexity)
2) If any element is already present then add it to a separate bloom filter (BF2) (O(1) space and O(N) complexity)
3) Once scanning the array is done. Start with the first element and use bloom filter BF2 to check if its present in it or not. The first element that you find that is not present in BF2 is the answer.

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

I think bloom filter would work, but you need to take care of the fact that if an element appears in a bloom filter, this just says that there is a chance of the element being encountered before. You could miss this way the first element that is unique:)

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

You are right, thats why mentioned it as a probabilistic approach :)

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

1. Create an array of pairs with the form (value,index) where value = input_array[index] for every index in the input array.
2. Sort the pairs array according to "value" using Radix Sort.
3. Iterate over the sorted pairs array and find the minimum index of unique elements (because the pairs are sorted according to "value", the final step can be done in a single pass).

The assumption that the array values are 32 bit numbers means that Radix Sort is done with O(n) worst case complexity. Space complexity is also O(n).

Code: snipt.org/Gghgd5

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

My thought is:

first, sort the array and store the sorted one in another array
then, iterate the sorted array to get all the unique numbers stored in a set
At last, iterate the original array to pick the first element in the array that is in the unique set.

The time complexity is O(nlogn + n + n)=O(nlogn)

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

Wont you need two loop, one to iterate the original array and for every element in this array another loop to iterate the unique set to find the first unique number? The time complexity will then become O(n^2)

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

after sorting the array, we can use binary search to find if the element is unique in the sorting array, so the final worst time complexity would be O(nlogn)+O(nlogn)=O(nlogn)

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

``````GLC@GLC-Butterfly ~
\$ cat a.cpp
#include<iostream>
#include<stdio.h>

using namespace std;

int main(){

int ele[]={4,8,8,8,8};

int size=sizeof(ele)/sizeof(int);

for(int i=0;i<size;i++)
{

int j;
for(j=0;j<size;j++)
{
if(i==j) continue;
if( (ele[i] ^ ele[j]) == 0)
{
break;
}
}
if(j==size) {cout<<"\nWe found the element: " << ele[i];
break;}
}

return 0;
}

GLC@GLC-Butterfly ~
\$ g++ a.cpp

GLC@GLC-Butterfly ~
\$ ./a.exe

We found the element: 4
GLC@GLC-Butterfly ~
\$``````

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

Given that you were told numbers are 32-bit integers, they were probably looking for some bit-level magic, or a probabilistic approach as explained above.

I decided to choose a different approach just for fun and run a divide and conquer code. I can argue that the complexity is at worst O(N^2) but on average O(N log(N)). It uses stack memory for recursion so O(log(N)) memory. I am also assuming I can modify the elements of array and that all elements are positive.

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

bool exists(int, int[], int, int);

bool firstUnique(int[], int, int, int&);

int main() {
int a[10] = { 1, 3, 5, 2, 5, 10, 3, 1, 9, 2 };
int pos = -1;
firstUnique(a, 0, 10, pos);
cout << a[pos] << endl;
getc(stdin);

}

bool firstUnique(int a[], int start, int end, int& pos) {
if (end - start == 1) {
pos = a[start] > 0 ? start : pos;
return a[start] > 0;
}

if (firstUnique(a, start, (start + end) / 2, pos)) {
if (!exists(a[pos], a, (start + end) / 2, end)) return true; // found it
else {
a[pos] = -a[pos];
return firstUnique(a, pos + 1, end, pos);
}
}
else {
return firstUnique(a, (start + end) / 2, end, pos);
}
}

bool exists(int num, int arr[], int start, int end) {
bool found = false;
for (int i = start; i < end; i++) if (num == arr[i]) {
arr[i] = -arr[i];
found = true;
}
return found;
}``````

IDEA: Divide into two halfs. Find the first unique element in first half and verify if it happens in the second half.
If not, return true and the corresponding index.
If yes, then mark all occurrences as "seen" (i.e., negate numbers) and solve the problem for the smaller array [pos + 1, end] where pos was the index of the unique element in first half.

At worse, the size is decreased by one every time which leads to O(n^2). Average performance, I believe, is much faster.

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

HI All, I managed to write solution with 0(N)LogN comlixty I assume.

``````public class CodingChellenge1 {
// First Unique number is 77
private static final int numbers[] = { 5, 2, 5, 2, 9, 5, 9, 3, 77, 6, 3, 8,
8, 6, 11, 0, 0, 0, 3 };

public static void main(String[] args) {
for (int i = 0; i < numbers.length; i++) {
{
if (check(0, numbers[i], i)) {
System.out.println(numbers[i]);
}

}

}

}

public static final boolean check(int currentIndex, final int currentNmber,
final int numberIndex) {
if (currentNmber == numbers[currentIndex]
&& numberIndex != currentIndex) {
return false;
} else if (currentIndex == numbers.length - 1
&& (currentIndex == numberIndex || currentNmber != numbers[currentIndex])) {
return true;
}
return check(++currentIndex, currentNmber, numberIndex);
}
}``````

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

#include <iostream>
#include <math.h>

using namespace std;

int main() {

int a[] = {1,2,3,4,5,1,2,3,4,10,5,6,6,6,6};
int n = sizeof(a)/sizeof(int);
int result = 0;

for(int i= 0; i<n; i++)
{

result = result ^ a[i];

}

cout << result;

return 0;
}

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

Wont work if there are more than one non-repeating numbers

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

Wont work if there are more than one non-repeating numbers

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

int find_first_unique(int A[], int n) {
int residx=-1;
if (n<1) return residx;
for(int i=0;i<n;i++) {
bool uniq=true;
for(int j=i+1;j<n-1;j++) {
if(A[i]==A[j] {
uniq=false;
break;
}
}
if(uniq) {
residx=i;
break;
}
}
return residx;
}

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

Right solution is to use a bit-vector based algorithm in 1 pass.
1. Make a bit vector of size 2^32 - 1 and another freq bit-vector of size 2^32 -1
2. Iterate through array, and each element is used to set the position in bitvector corresponding to the value of current array element.
2.1 Set the freq-bitvector as well at the same position.
2.2 If the element is found in bitvector #1, then reset the freq-bitvector.
3. First unset bit position in the freq bit-vector corresponds to the unique element

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

Construct a binary Search Tree (Lets assume its balanced) with 2 additional fields in the node along with the key value- count and order. count will be the number of times the key has been inserted into the tree and order will be the order in which this element was inserted into the tree. Now do a in-order traversal on the tree. Ignore elements with count >1. while traversing using the simple algorithm of finding the largest/smallest number in a list, find the first unique element using the order field. ( Node with the lowest value of 'order' was the one inserted first into the tree.

Complexity of building tree would be O(nlog n) and in-order traversal in O(n) yielding a final result of O(n)

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

I am unable to edit my original answer. So adding correction here.

Overall complexity is O(nlogn) and not O(n) as mentioned in my answer

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

the array of counters is prohibited. i guess tree with counters is also prohibited.

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

In C++:

``````#include <iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main() {
int array[] = {2,6,1,5,34,24,6,12,2,1};
int sorted_array[sizeof(array)/sizeof(array[0])];
int count = 0;
vector<int> myvector (array, array + sizeof(array)/sizeof(array[0]));
sort (myvector.begin(), myvector.end());
for (vector<int>::iterator it=myvector.begin(); it!=myvector.end(); ++it)	sorted_array[count++] = *it;

int i;
for(i = 0;i < sizeof(sorted_array)/sizeof(sorted_array[0]);i++){
int start = 0, end = sizeof(sorted_array)/sizeof(sorted_array[0]) - 1, mid = (start + end) / 2, value = sorted_array[i];
while(sorted_array[start] != sorted_array[end]){
if(value <= sorted_array[(start + end) / 2])	end = (start + end) / 2;
if(value > sorted_array[(start + end) / 2])	start = (start + end) / 2 + 1;
}
if(sorted_array[start] != sorted_array[start + 1]){
cout << sorted_array[start] << endl;
break;
}
}

return 0;
}``````

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

``````package alex;

import java.util.Arrays;

public class FirstUniqueNumber {

/*
* Cannot use hashtable or arrays w/ counters
*/
public static void firstUnique(int[] a) {
if (a == null || a.length == 1 ) {
return;
}

// sort array
Arrays.sort(a);

// compare elements w/ look backs
boolean duplicate = false;

for (int i = 1; i < a.length; i++) {
if (a[i] == a[i-1]) {
duplicate = true;
} else {
if (!duplicate) {
System.out.println(a[i-1]);
return;
}

duplicate = false;
}
}
}

public static void main(String[] args) {
int[] a = {2, 4, 3, 4, 1, 3, 9, 10, 1, 2};

FirstUniqueNumber.firstUnique(a);
}

}``````

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

What about sort the array into another container and then find the first unique from the original array?

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

``````import java.util.LinkedHashMap;
import java.util.Map.Entry;
import java.util.Scanner;

public class Solution {

public Solution() {
}

public int solution(int[] A) {
int firstUniqueNumber = -1;
for (int i : A) {
Integer j = freqCounter.get(i);
if(j == null) {
j = 1;
}	else {
j = j + 1;
}
freqCounter.put(i, j);
}
for(Entry<Integer,Integer> entry : freqCounter.entrySet()){
if(entry.getValue().intValue() == 1){
firstUniqueNumber = entry.getKey();
break;
}
}
return firstUniqueNumber;
}

public static void main(String[] args) {

int[] A = new int[n];
for (int i = 0; i < n; i++) {
}
Solution sol = new Solution();
System.out.println(sol.solution(A));
}

}``````

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

given its 32bit number, please AND first element with the second and so on , if AND result is same as first number please proceed down in the array or else that is the first unique number in the array ...kaboom!.

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

The idea is to iterate trough array, skipping array elements known NOT to be unique by keeping track of known duplicates indexes in bit array structure.

int A[size]; unsorted array
int x;
std::bitset<size> index_set;

for (int i 0; i < size; ++i) {
if(index_set.test(i)) continue; // element @ i not unique

x = a[I];

for(int j = i + 1; true; ++j) {
if(j == size) return x; // reached the end of array so x is unique
if(index_set.test(j)) continue; // element @ j not unique
if(x == A[j]) { index_set.set(j); break; }

}

}

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

The idea is to iterate trough array, skipping array elements known NOT to be unique by keeping track of known duplicates indexes in bit array structure.

``````int getUniqueIndex(int A[], int size)
{
int x;
std::bitset<size> index_set;

for (int i 0; i < size; ++i) {
if(index_set.test(i)) continue; // element @ i not unique

x = a[I];

for(int j = i + 1; true; ++j) {
if(j == size) return j; // reached the end of array so x is unique
if(index_set.test(j)) continue; // element @ j not unique
if(x == A[j]) { index_set.set(j); break; }

}
}

return -1;``````

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

The idea is to iterate trough array, skipping array elements known NOT to be unique by keeping track of known duplicates indexes in bit array structure.

``````int getUniqueIndex(int A[], int size)
{
int x;
std::bitset<size> index_set;

for (int i 0; i < size; ++i) {
if(index_set.test(i)) continue; // element @ i not unique

x = a[I];

for(int j = i + 1; true; ++j) {
if(j == size) return j; // reached the end of array so x is unique
if(index_set.test(j)) continue; // element @ j not unique
if(x == A[j]) { index_set.set(j); break; }

}
}

return -1;``````

Comment hidden because of low score. Click to expand.
0
of 0 vote
The idea is to iterate trough array, skipping array elements known NOT to be unique by keeping track of known duplicates indexes in bit array structure. int getUniqueIndex(int A[], int size) { {{ int x; std::bitset<size> index_set; for (int i 0; i < size; ++i) {{{ if(index_set.test(i)) continue; // element @ i not unique x = a[I]; for(int j = i + 1; true; ++j) {{{ if(j == size) return j; // reached the end of array so x is unique if(index_set.test(j)) continue; // element @ j not unique if(x == A[j]) {{{ index_set.set(j); break; }} } }}} }}} return -1; }}}
Comment hidden because of low score. Click to expand.
0
of 0 vote

The idea is to iterate trough array, skipping array elements known NOT to be unique by keeping track of known duplicates indexes in bit array structure.

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

``````class Ideone
{
public static void main (String[] args) throws java.lang.Exception
{
int[] arr = {23,45,43,43,23,45,32};
System.out.print(findUnique(arr,7));
}

public static int findUnique(int[] arr,int size)
{
int unique = arr[0], index = 0;
HashSet<Integer> myset = new HashSet<Integer>();

for(int i = 0; i < size; i++)
{
System.out.println(i);
if(i!=index && arr[i]==unique)
{
if(index < size-1)
{
index++;
while(myset.contains(index))
{
index++;
}
if(index <= size -1)
{
unique = arr[index];
i=1;
while(myset.contains(i))
{
i++;
}

if(i>=size)
return -1;

i--;
}
else
return -1;
}
else
return -1;
}
}
return unique;
}
}``````

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

public static void firstunique(int[]arr){
int[] visit= new int[arr.length];
for(int i=0;i<arr.length-1;i++){
boolean found=false;
if(visit[i]==1){continue;}
for(int j=i+1;j<arr.length;j++){
if(arr[i]==arr[j]){
visit[j]=1;
found=true;
}
}
if(!found){
System.out.print(arr[i]);
break;
}
}
}

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

public int duplicateNumWithNoHash(int[] a){
int result = 0;
Set<Integer> s = new TreeSet<Integer>();
for(int i=0; i<a.length; i++) {
if(s.contains(a[i])) {
result = a[i];
break;
} else {
}
}
return result;
}

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

public int duplicateNumWithNoHash(int[] a){
int result = 0;
Set<Integer> s = new TreeSet<Integer>();
for(int i=0; i<a.length; i++) {
if(s.contains(a[i])) {
result = a[i];
break;
} else {
}
}
return result;
}

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

``````public int duplicateNumWithNoHash(int[] a){
int result = 0;
Set<Integer> s = new TreeSet<Integer>();
for(int i=0; i<a.length; i++) {
if(s.contains(a[i])) {
result = a[i];
break;
} else {
}
}
return result;``````

}

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

``````public int duplicateNumWithNoHash(int[] a){
int result = 0;
Set<Integer> s = new TreeSet<Integer>();
for(int i=0; i<a.length; i++) {
if(s.contains(a[i])) {
result = a[i];
break;
} else {
}
}
return result;
}``````

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

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

``public int duplicateNumWithNoHash(int[] a){``

``int result = 0;``

``Set<Integer> s = new TreeSet<Integer>();``

``for(int i=0; i<a.length; i++) {``

``if(s.contains(a[i])) {``

``result = a[i];``

``break;``

``} else {``

``s.add(a[i]);``

}

}

``return result;``

``}``

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

public int Solve(int []arr)
{
// this solution is in C#
int ret = int.MinValue;
for (int i = 0; i < arr.Length; ++i)
{
int val = arr[i];
bool matchfound = false;

for (int j = 0; j < arr.Length; ++j)
{
int val2 = arr[j];

if(i==j)
continue;

if (val2 == val)
{
arr[j] = int.MinValue;
matchfound = true;
}
} // end of for(j)

if (true == matchfound)
arr[i] = int.MinValue;
else
{
ret = val;
break;
}

} // end of for(i)
return ret;
}

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

I think you have to create one additional integer array that can store as many values as max value of integer.
In cells it will store the number of times the number denoted by given index was encountered in the sequence.
When processing the array you will increment number in the additional array every time you encounter it.
After first traversal you have to go through the array the second time in order to find the fist number with value one in additional array.

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

I think you have to create one additional integer array that can store as many values as max value of integer.
In cells it will store the number of times the number denoted by given index was encountered in the sequence.
When processing the array you will increment number in the additional array every time you encounter it.
After first traversal you have to go through the array the second time in order to find the fist number with value one in additional array.

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

I think you have to create one additional integer array that can store as many values as max value of integer.
In cells it will store the number of times the number denoted by given index was encountered in the sequence.
When processing the array you will increment number in the additional array every time you encounter it.
After first traversal you have to go through the array the second time in order to find the fist number with value one in additional array.

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

``````public int solution(int[] A) {
boolean flag = true;

for (int i = 0; i < A.length; i++) {
for (int j = 0; j < A.length; j++)
if (i != j) {
if (A[i] == A[j]) {
flag = false;
break;
}
}
if (flag == true) {
return A[i];
}
flag = true;
}
return -1;
}``````

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

``````public int solution(int[] A) {
boolean flag = true;

for (int i = 0; i < A.length; i++) {
for (int j = 0; j < A.length; j++)
if (i != j) {
if (A[i] == A[j]) {
flag = false;
break;
}
}
if (flag == true) {
return A[i];
}
flag = true;
}
return -1;
}``````

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

Use a BST of Unique Elements. Keep adding, return the first value that is NOT insert-able.
it is likely that you'd hit the first duplicate very soon. Worst case complexity O(n^2), though average case is just log(n).

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

Perform an O(nlogn) sort. Traverse linear. Find the unique.

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

The partition method of the quick sort will give you your required answer. use three pointers i, j , k, where start to i-1 will be the array containing elements smaller then pivot element, j to end will be containing bigger then pivot and i to j-1 will be containing equal to pivot element, and if i == j then, we found our a unique element. now we will check if we can find unique in left subarray, then that would be first, if not, we will check the current pivot and if that is also not hold true, we will check in the right side.

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

If the array is extremely large, sort first, then look for it. O(n log n).

If you don't care using O(2n) bits of memory, create a bitmap the size of the original array. If the second bit is not active and an element is present 1 time activate the first bit, if present a second time activate the second bit.

Go through the bitmap and print the element in the position of the first bit pair with no bits active. O(n) time complexity.

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

something like the following code:

``````int find_first_unique(int A[], int n) {
int residx=-1;
for(int i=0;i<n;i++) {
bool uniq=true;
for(int j=0;j<n;j++) {
if(A[i]==A[j] && i!=j) {
uniq=false;
break;
}
}
if(uniq) {
residx=i;
break;
}
}
return residx;
}``````

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

Your solution is O(n^2), assuming the details are correct, but your inner loop should start at j=i+1.

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

Use bit operation and XOR

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

really do no know why you use bit operation and XOR.... please read questions carefully.....

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

if the sequence is 1,3,3,3， then your method will fail.

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.