Bloomberg LP Interview Question
Financial Software DevelopersCountry: United States
* 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
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.
ok but, if you do radix sort , won`t you lose the order ?
( because the question asks the first unique in an unsorted array )
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.
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.
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:)
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
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)
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)
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.
Please let me know of your thoughts on this.
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);
}
}
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
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)
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
import java.util.LinkedHashMap;
import java.util.Map.Entry;
import java.util.Scanner;
public class Solution {
private LinkedHashMap<Integer, Integer> freqCounter = new LinkedHashMap<Integer, Integer>(0);
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) {
Scanner reader = new Scanner(System.in);
int n = reader.nextInt();
int[] A = new int[n];
for (int i = 0; i < n; i++) {
A[i] = reader.nextInt();
}
Solution sol = new Solution();
System.out.println(sol.solution(A));
reader.close();
}
}
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; }
}
}
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;
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.
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.
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.
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.
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.
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;
}
#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;
}
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;
}
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);
}
}
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;
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)
{
myset.add(index);
myset.add(i);
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;
}
}
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;
}
}
}
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;
}
- Kiran JG April 30, 2014