Bloomberg LP Interview Question Financial Software Developers

• 0

Given an array of any length holding integers (a buffer of bytes), write an algorithm to return the first unique element (ie not repeated in rest of the array).

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

mantain a hash table...(element as key and index as value)
mantain another boolean array indicating the whether the element has been detected more than once...intialize it to false..
whnevr we encounter an element search in hash table..if found get it index n mark it as true and also the index of current element as true..
continue this for 1 to n elements in the array..
Then transverse the bool array...1st false indicates the unique no..
i suppose this will b linear n all

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

Assuming it is array of bytes.

public static int firstUniqueElement(byte a[])
{
byte temp[]=new byte[256];

byte b=0;
Arrays.fill(temp, b);

for(int i=0; i<a.length; i++)
{
b=a[i];
temp[b]++;
}
for(int i=0; i<a.length; i++)
{
b=a[i];
if(temp[b]>1)
continue;
else
return b; //first unique element will be returned
}

return -1;
}

The above code can be made more robust. But the general idea is to traverse once and increment the count and again re-traverse till you find the first unique element in the array (by looking up from the temp array).

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

1) First, scan the entire given array & load the hashtable (key = element, value = index). Repeated elements in the array will have hash collision. This takes O(n) to scan the entire array & O(1) for each insertion into the hash table. We will make n insertions into the hashtable.

2) Traverse the given array again for the second time, and, for each element, check in hashtable for repetition or hash collision. If yes, take it's index value and mark as true at the same index in another array of booleans. Else, mark as false at it's index in the boolean array. Again, O(n) overall for this step.

3) Now, traverse the boolean array & the index with the first false is the index in the given array with the first non-repeated unique element. This step will take O(n) worst time.

So, overall complexity comes to O(n).

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

1. Create hashtable: key = element, value = repeat (type: boolean)
2. Scan the entire array.
3. Load each array element into hashtable. Check if the element already exists in hashtable. If it does, check if its value is false. If it is false, then set it to true. If it is true, don't do anything. If the element does not exist then insert it in the hashtable with a value false.
4. Scan the entire array again.
5. The first unique element is the one for which the value in the hashtable entry is false.

This avoids the need for creating an additional boolean array.

Example Java code:

``````Hashtable<Integer, Boolean> positions = new Hashtable<Integer,Boolean>();
int[] elements = {2, 2, 4, 5, 1, 6, 0, 9, 1, 4, 5, 10};
for(int i=0; i<elements.length; i++) {
if(positions.containsKey(elements[i])) {
if(positions.get(elements[i]).booleanValue() == false) {
positions.put(elements[i],true);
}
}
else {
positions.put(elements[i], false);
}
}
for(int j=0; j<elements.length; j++) {
if (positions.get(elements[j]).booleanValue() == false) {
System.out.println("First unique element is: " + elements[j] + " at position " + j);
break;
}
}``````

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

And possibly, a slightly faster version avoiding the containsKey call:

``````Hashtable<Integer, Boolean> positions = new Hashtable<Integer,Boolean>();
int[] elements = {2, 2, 4, 5, 1, 6, 0, 9, 1, 4, 5, 10};
for(int i=0; i<elements.length; i++) {
try {
if(positions.get(elements[i]).booleanValue() == false) {
positions.put(elements[i],true);
}
}
catch (NullPointerException e) {
positions.put(elements[i], false);
}
}
for(int j=0; j<elements.length; j++) {
if (positions.get(elements[j]).booleanValue() == false) {
System.out.println("First unique element is: " + elements[j] + " at position " + j);
break;``````

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

//Sort entire array
//check by this condition
if (a[i]!=a[i+1]&&a[i+1]!=a[i+2]) return a[i+1] as first occurence

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

wont work since sorting will change the order of elements

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

Solutions with with the hashTable, temp[256] etc. have the right idea. But what you want is ideally a hashSet<Integer>. If an element is already exists in the hashSet the add(Integer a) returns false, else true.

Here is the algorithm coded up in java

int firstRepeatedElement(int[] array){
assert(array != null);
hashSet<Integer> myset = new hashSet<Integer>()
for(int i= 0; i<array.length; i++)

}

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

Solutions with with the hashTable, temp[256] etc. have the right idea. But what you want is ideally a hashSet<Integer>. If an element is already exists in the hashSet the add(Integer a) returns false, else true.

Here is the algorithm coded up in java

int firstRepeatedElement(int[] array){
assert(array != null);
hashSet<Integer> myset = new hashSet<Integer>()
for(int i= 0; i<array.length; i++)
return array[i];

return -1;
}

}

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book walking you through every aspect of getting a job at a top tech company, while focuses on software engineering interviews.

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.