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

- rk.rajankalra May 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use bit mask arrays.

- Westlake February 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

fail

- Anonymous March 12, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Anon: What? Why?

- Anonymous March 12, 2014 | Flag
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.

- samuel February 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use a redblack or other type of balanced BST.

- Urik February 17, 2014 | Flag Reply
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.

- glebstepanov1992 February 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- xejgomi February 18, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Tommy March 13, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Tommy March 13, 2014 | Flag
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.

- kr.neerav February 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Ryan February 17, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- kr.neerav February 18, 2014 | Flag
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

- IvgenyNovo February 18, 2014 | Flag Reply
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)

- wangzi11181 April 06, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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)

- shankhs October 10, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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)

- LuborLiu February 27, 2015 | Flag
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 ~
$

- Kiran JG April 30, 2014 | Flag Reply
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.

Please let me know of your thoughts on this.

- Ehsan May 06, 2014 | Flag Reply
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);
	}
}

- kareem.EL.shahawe May 07, 2014 | Flag Reply
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;
}

- Anonymous July 12, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Aj October 10, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Ajay October 10, 2016 | Flag
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;
}

- Anonymous August 30, 2014 | Flag Reply
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

- M A September 04, 2014 | Flag Reply
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)

- Anonymous September 18, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Pavan September 18, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- andrey November 26, 2014 | Flag
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;
}

- kshafiee October 02, 2014 | Flag Reply
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);
	}

}

- Alex November 02, 2014 | Flag Reply
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?

- Eric November 04, 2014 | Flag Reply
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 {
	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();
	}

}

- Sivashankar December 24, 2014 | Flag Reply
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!.

- C++KUKU February 13, 2015 | Flag Reply
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; }

}

}

- MS February 21, 2015 | Flag Reply
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;

- MS February 21, 2015 | Flag Reply
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;

- MS February 21, 2015 | Flag Reply
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; }}} - MS February 21, 2015 | Flag Reply
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.

- MS February 21, 2015 | Flag Reply
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)
		    	{
		    		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;	
	}
}

- naomi.lijing@googlemail.com February 26, 2015 | Flag Reply
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;
}
}
}

- Avik Das March 03, 2015 | Flag Reply
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;
}

- Usha March 26, 2015 | Flag Reply
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;
}

- Usha March 26, 2015 | Flag Reply
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;

}

- Usha March 26, 2015 | Flag Reply
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;
	}

- Usha March 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

- Anonymous March 26, 2015 | Flag Reply
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;

}

- Usha March 26, 2015 | Flag Reply
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;
}

- swaps March 28, 2015 | Flag Reply
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.

- nurgizak June 02, 2015 | Flag Reply
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.

- nurgizak June 02, 2015 | Flag Reply
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.

- nurgizak June 02, 2015 | Flag Reply
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;
	}

- Koushik September 18, 2015 | Flag Reply
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;
	}

- Koushik September 18, 2015 | Flag Reply
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).

- Dhiman December 09, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Object April 01, 2017 | Flag Reply
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.

- sonesh April 13, 2017 | Flag Reply
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.

- ljyanesm December 13, 2017 | Flag Reply
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;
}

- samuel February 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- M A September 04, 2014 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Use bit operation and XOR

- anbmic March 12, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous March 12, 2014 | Flag
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- ctang February 17, 2014 | Flag


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More