Adobe Interview Question for Member Technical Staffs


Country: India
Interview Type: In-Person




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

The idea is to for every bit position count the number of 1's mod 3. The resulting number will be the answer.It is possible to do it in O(n) using bitwise operations. Will provide code soon.

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

This will return element which is present different number of times than recurringElementCount i.e. if all elements are present for 5 number of times and there is a single element which is not present 5 number of times (either 1,2,3,4,6,7,8 etc) that element will be returned

static int findUnique (int[] input, int recurringElementCount) {
		int result = 0;
		for (int bit = 0; bit < 32; bit++) {
			int mask = 1 << bit;
			int setCount = 0;
			for (int i = 0; i < input.length; i++) {
				if ((input[i] & mask) != 0) {
					setCount++;
					setCount = setCount % recurringElementCount;
				}
			}
			if (setCount > 0) {
				result = result | mask;
			}
		}
		return result;
	}

- saurabh November 20, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

isn't this this nlog(n) algorithms

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

use of O(n) space would give time complexity O(n). using map it can be done easily.
check below solution in c++

#include<iostream>
#include<map>
using namespace std;
int main() {
	int a[] = {2,3,5,1,2,2,5,3,5,3};
	int size = sizeof(a) / sizeof(a[0]);
	map < int, int > m;
	map < int, int >::iterator it;
	for( int i=0; i< size; i++) m[a[i]]++;
	for( it=m.begin(); it!=m.end(); it++) {
		if ( it->second ==1 ) 
			cout << "Unique Element is = " << it->first << endl;
	}
	return 0;
}

- NEO December 14, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 3 vote

O(n) solution using O(1) space

def unique(lst):
    # For every bit we need to store a 2-bit counter
    # 00 01 10 are its possible values.
    # Lower bit of each counter
    counter_lower = 0
    # Higher bit of each counter
    counter_higher = 0
    for number in lst:
        # f(high_bit, low_bit, number_bit) = new_high_bit, new_low_bit
        # Just note that we don't have to do anything if number_bit isn't set
        new_counter_lower = counter_lower
        new_counter_higher = counter_higher

        # f(00, 1) = 01
        # Bits which are set and both counters bits are zero
        both_zero = number & (~counter_lower & ~counter_higher)
        new_counter_lower |= both_zero

        # f(01, 1) = 10
        # Bits for which only lower counter is set
        lower_set = number & counter_lower
        # unset lower bit
        new_counter_lower &= (~lower_set)
        # set higher bit
        new_counter_higher |= lower_set

        # f(10, 1) = 00
        # Bits for which only higher counter is set
        higher_set = number & counter_higher
        # Drop high counter to 0
        new_counter_higher &= (~higher_set)

        counter_lower = new_counter_lower
        counter_higher = new_counter_higher
        # just a sanity check that each counter is ok
        assert counter_lower & counter_higher == 0
    # since we've taken number of bits mod 3, the lower counter will have our unique number.
    assert counter_higher == 0, "incorrect input"
    return new_counter_lower

assert unique([3,19,2,2,2,2,2,2,3,3]) == 19
assert unique([3,19,19,19,8,2,2,2,2,2,2,3,3]) == 8

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

This looks geat. Would you please elaborate the logic. I'm struggling to get it.

- Anonymous November 03, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Let's count the number of 1's on each position in binary representation.
So if the numbers are
3 5 3 3
which is
011 101 011 011
in binary
The corresponding counters will be
{1, 3, 4}
Every number repeats 3 times, so let's take each counter modulo 3 to clean the 3-times-repeating elements.
{1, 0, 1}
this is the number which is unique.

Now what we have to do is just count the number of 1's at each position modulo 3

We need a 2-bit counter for every bit position that will increment every time it meets a number with the corresponding bit is set.
It increments like this: 00 -> 01 -> 10 -> 00 (since we need modulo 3)

We store lower bit and higher bit of counters in counter_lower and counter_higher

Then we just do the following
For every bit position where number bit is set and both counter bits are 0, change the lower counter from 0 to 1 (this is 00 -> 01 transition
For every bit position where number bit is set and lower counter is set, set the lower counter bit to zero and higher counter bit to 1 (01 -> 10 transition)
For ... where higher counter bit is set, just unset the higher counter bit (10 -> 00 transition)

That's all, after we've processed all numbers, we will have our unique number in lower counter.

This is the same logic for "find a unique element in array where every other element is met twice" - here when we xor, our accumulator is 1-bit counter. In this problem we just switch from 1-bit counters to 2-bit counters

- bowl November 03, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Nice solution. but it is O(n log n) because for each number you have to do an action for each bit.

Now, if for example each number is 4 byte (let say like int in Java) then the complexity is at least O(32 * n). So, if the length of the array is smaller than 2^32 (which normally is, otherwise you need 2^32 * 4 byte = 14 GB memory for the array) than the complexity is larger than O(n * log n) because log n is smaller than 32

- Mohammad November 04, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 votes

It's up to conventions, whether we count bitwise operation of two numbers as O(1) or O(log(b)) where b is the number of bits in number.
It's commonly assumed that if we add two int32 it's O(1) and if we iterate over bits of int32 it's O(log(b)).

- bowl November 04, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think we can achieve this solution by counting number of set bits mod 3. at last convert the binary to number..

e.q. 1,2,2,3,1,4,1,2,3,3 so there will be {1,6,6,} number of ones. If you took mod with 3 this will reduce to {1,0,0} which is nothing but our answer..

Please let me know if i am missing any use case.

- mil November 09, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

very good, but here's a simpler version (it works by implementing binary addition logic 00->01->10->11 and then zeroing any value of 3 [11]):

def mod3(l):
  low_bits = 0
  high_bits = 0

  for v in l:
    new_low = low_bits ^ v
    new_high = high_bits ^ (v & low_bits)
    both_bits = new_low & new_high
    low_bits = new_low ^ both_bits
    high_bits = new_high ^ both_bits

  return low_bits

- gen-y-s November 11, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 6 vote

In O(N) with python

def find_num(L):
	counts = {}
	for l in L:
		if counts.get(l):
			counts[l] += 1
		else:
			counts[l] = 1
	
	for el in counts:
		if counts[el] == 1:
			return el

- yoavzimmerman November 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I actually quite like this solution, don't understand why it was down-voted. Assuming a Python dictionary is implemented as a hashmap, it's a very concise way of implementing the "hashmap with a count" idea.

- merlinme November 07, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Try this :

Average case: O(n)
Worst case: O(n2)

==================================

#include <iostream>
#include <unordered_map>

using namespace std;

int main(){

unordered_map<int, int> numberFrequencyHolder;
unordered_map<int, int>::iterator itr;

int arr[]={2,3,5,1,1,1,5,3,5,3};
for (int i=0; i<sizeof(arr)/sizeof(int); ++i){
if ( (itr = numberFrequencyHolder.find(arr[i])) != numberFrequencyHolder.end() ){
itr->second++;
}else{
numberFrequencyHolder.insert( {arr[i], 1} );
}
}

bool found = false;
for(itr = numberFrequencyHolder.begin(); itr != numberFrequencyHolder.end(); ++itr){
if ( itr->second == 1 ){
cout << "Number with frequency 1 is: " << itr->first << endl;
found = true;
break;
}
}

if(!found){
cout << "No Such Element Found !" << endl;
}
return 0;
}

- ashishcse99 November 12, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

private int findOneValue(int[] arr){
		
		int maxValue = Integer.MIN_VALUE;
		for( int value : arr ){
			maxValue = Math.max(value, maxValue);
		}
		
		BitSet set1 = new BitSet(maxValue+1);
		BitSet set2 = new BitSet(maxValue+1);
		
		for( int value : arr ){
			if( ! set1.get(value) ){
				set1.set(value);
			}
			else {
				set2.set(value);
			}
		}
		
		set1.xor(set2);
		
		return set1.length()-1;
	}

- m@}{ November 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

The complexity of this algo is not better than n(logn). as the set1.get(value) in the for loop is expensive.

- ahj November 03, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

set1.get(value) is O(1) according to time complexity.

- m@}{ November 04, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I'm not a Java person but I think this could work, as long as you had enough memory. If the data input is 1, 2147483647, 1, 1 then there's going to be a wee bit of unused memory, but if my calculations are correct then you're not going to run out on a modern system. It would almost certainly run out of memory if using large 64 bit integers though, so I'm not sure it's my preferred solution.

- merlinme November 05, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It's worth pointing out that there is a cost to having what are potentially two huge BitSets. The constructor must initialise the bits to 0 or this solution won't work. Assuming this is implemented as something like a memset of the values in an array to 0 then I would expect this to be lightning fast, as initialising memory to 0 is something computers do very well. The other issue is that you may have to compare 2147483647 bits when doing the xor, when you only actually set two of them. Again, comparing bits is something computers do very quickly, and compilers may be able to optimise, so I'm not sure this is a genuine issue. Running out of memory in a 64 bit world seems a more significant problem to me.

- merlinme November 06, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Count every bit of the element in this array, after Count, then mode 3, so the left bit should be the element which appear once.

int GetSingleNumber(vector<int>& irvector)
{
	vector<int> lvBitCount;
	for(int i = 0; i< irvector.size(); i++)
	{
		int Cur = irvector[i];
		int BitC = 0;
		while(Cur)
		{
			if(Cur & 1)
			{
				while(BitC >= lvBitCount.size())
				{
					lvBitCount.push_back(0);
				}
				lvBitCount[BitC] += 1;
			}
			Cur = Cur >> 1;
			BitC ++;
		}
	}

	reverse(lvBitCount.begin(), lvBitCount.end());
	int result = 0;
	for(int i = 0; i< lvBitCount.size(); i++)
	{
		lvBitCount[i] = lvBitCount[i] % 3;
		result = (result << 1) + lvBitCount[i];
	}
	return result;
}

- suwei19870312 November 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

we can do this in O(n).. by frequency measuring... just note the frequencies of all the elemnts.. this can be done in O(n) time and then check the whole array if the frequency is 1 or not.. O(n) time.. thus checked!

for(i=0;i<n;i++)
{
arrfreq[arrnumbrs[i]]++;
}
for(i=0;i<rangeofnumbers;i++)
{
if(arrfreq[i]==1)
printf("i");
break;
}

- ayushsethi22031992 November 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

try running our program on sequence { 1,2,1,2,1,2, 219876534567324567098765423}

How big arrfrew will you allocate ??

- Vifi November 04, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

you have to allocate ceil(n/3) length map to measure frequency.

- Anon November 04, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void main(String[] args) {
		int[] a=new int[]{2,3,3,3};
		int number=0;
		int powerOfTwo=1;
		boolean flag=true;
		while(flag){
			flag=false;
			int countLower=0;
			for(int i=0;i<a.length;i++){
				if((a[i]&1)==1){
					countLower++;
				}
				a[i]=a[i]>>1;
				if(a[i]!=0)
					flag=true;
			}
			number+=(countLower%3)*powerOfTwo;
			powerOfTwo*=2;
			
		}
		System.out.println(number);

}

- Yasir Mukhtar November 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

When i tried to executed your code it worked fine with the array you it. But if we change the array it is returning wrong results.

- Manidhar November 04, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sorry there was one mistake number+=(countLower%3)*powerOfTwo;
powerOfTwo*=2;

Plus was missing

- Yasir Mukhtar November 04, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Could you explain how this code works please, as I don't understand it. What does "a[i]&;1" do? I don't recognise that syntax. Is it Java specific?

- merlinme November 06, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is a really great answer.

One could argue it is in fact O(n Log(n)) as there will be log(n) bits but it is close enough to O(1) as far as I am concerned.

The interesting thing is to think about this solution why it worked and be ready to apply the same brilliant thinking to other problems. I wonder if there is a name for this kind of thing.

- DR A.D.M November 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I believe this is linear time O(n), as lookup, insert, delete using hashmaps without collisions should be O(1). Works to find any unique values, it's not necessary that all multiple examples are in threes. It's assumed there is only one number which only appears once, but it's trivial to show multiple examples using a loop through "candidates" at the end.

int main()
{
    std::unordered_set<int> candidates;
    std::unordered_map<int,int> previously_seen;
    const int TEST_SIZE = 10;
    int test_data[TEST_SIZE] = { 2,3,5,1,2,2,5,3,5,3 };
    std::unordered_map<int, int>::iterator iter;

    for( int idx = 0; idx < TEST_SIZE; ++idx )
    {
        iter = previously_seen.find( test_data[idx] );
        if( iter != previously_seen.end() )
        {
            if( ++(iter->second) == 2 )
            {
                // if this is the second occurrence,
                // erase from candidates
                candidates.erase( iter->first );
            }
        }
        else
        {
            previously_seen.insert( std::make_pair(test_data[idx], 1) );
            candidates.insert( test_data[idx] );
        }
    }
    if( candidates.size() == 1 )
    {
        std::cout << "Answer is: " << *candidates.begin() << std::endl;
    }

    return 0;
}

- merlinme November 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

C# O(n), using linq.single as a shortcut at the end.

using System.IO;
using System;
using System.Linq;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
       int[] inputs = { 2,3,5,1,2,2,5,3,5,3,6,6,103,6,7,7,7,1,1,18,18,18 };
       IDictionary<int, int> hash = new Dictionary<int,int>();
       
       foreach(var i in inputs)
       {
           if (!hash.ContainsKey(i))
           {
                hash.Add(i, 0);
           }
           hash[i]++;
       }
       
       var singleOccur = hash.Single(h => h.Value == 1).Key;
       Console.WriteLine(singleOccur);
    }
}

- matt.korwel November 05, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Interesting. Your final hash will be one third + 1 of the size of the input. My solution adds and then erases 1/3 of the input from my "candidates" hashmap, which is not ideal. So your solution does look more efficient than mine. My only other comment would be that I don't think hash.Single is helpful. Single must presumably iterate through the entire hashmap; hashmaps are not sorted by value, so how else can Single know that there is one and only one entry with value == 1? If you know that there can only be one value == 1 then rather than iterating through the entire hashmap you might as well stop iterating when you find the one example. Or you can iterate through the entire hashmap and report if there is more than value == 1, without having to handle the exception which Single would throw.

- merlinme November 05, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

this solution can work for negative numbers as well.. while storing negative number in hash we can take hash of that number, because according to the problem there is only unique number, so hash value should be either 1 or 4....
we will just need one loop 'n' times extra which will tell whether number is +ve or -ve

- shubhamnov November 06, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Hey guys, check it out. The idea is to make a bitwise sum of all the numbers modulo 3 (I mean, every i-th bit of the result is a sum modulo 3 of i-th bit across all the numbers). Since we have no such an operation, let's emulate it using bitwise operations. Let us have 2 words, representing our sum modulo 3 (one word is for lower bit of the sums, and one word for higher bit). All we need to do is to implement an operation (x + y) mod 3, where x is a 2-bit number, and y is a 1-bit number. And we want to do it in O(1) using bitwise operaions. If you know how computer adders/counters work, it is pretty much it (check Half_adder and Counter on wikipedia).

Here is the code of a function:

template<typename T>
T getUniqueNumber(const T *begin, const T *end) {
    T low = 0, high = 0;
    for (; begin + 1 <= end; ++begin) {
        high ^= low & *begin;
        low ^= *begin;
        const T overflow = high & low;
        low ^= overflow;
        high ^= overflow;
    }
    return low;
}

- Pavel Kalinnikov November 12, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Also this solution can be easily generalized to solve the whole family of problems "N numbers appear exactly K times, and 1 number appears M times (M != K)", and the complexity will be O(N log K) with O(log K) additional memory.

- Pavel Kalinnikov November 12, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Objective C solution to this problem,
    NSArray *threeTimesArray = @[@2,@3,@5,@1,@2,@2,@5,@3,@5,@3];
    __block NSNumber *uniqueNumer ;
    [threeTimesArray enumerateObjectsUsingBlock:^(id obj, NSUInteger idx, BOOL *stop) {
        NSMutableArray *remainingArray = [[NSMutableArray alloc]initWithArray:threeTimesArray];
        [remainingArray removeObjectAtIndex:idx];
        if (![remainingArray containsObject:obj]) {
            uniqueNumer = obj;
        }
    }];

- deepak.hebbar November 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int findUniqueNum(int A[], int times){
		int N = A.length;
		
		Arrays.sort(A);
		for (int j = 0 ; j < N ; j++)
		System.out.print(A[j] + " ");
		System.out.println();
		int i = 0 ;
		for ( ; i < N-1 ; i+=times ){
			if (A[i] == A[i+1]){
				continue;
			}
			else {
				break;
			}
		}
		return A[i];
	}

- amit December 18, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package test;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;


public class Hashtest {
	public static void main(String [] args)
	{
		String str = null;
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		try {
			str=br.readLine();
		} catch (IOException e) {
			e.printStackTrace();
		}
		String [] tokens;
		tokens=str.split(" ");
		Map<String, Integer> hmap = new HashMap<String, Integer>();
		for (String string : tokens) {
			if(hmap.containsKey(string))
			{
				int i=hmap.get(string).intValue();
				hmap.put(string, i+1);
			}
			else
			{
				hmap.put(string, 1);
			}
		}
		for(Entry<String, Integer> e:hmap.entrySet())
		{
			if(e.getValue().equals(1))
			{
				System.out.println(e.getKey());
			}
		}
		
	}
}

- sudeep91soni January 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Count Sort is best :)
complexity : O(cn) ... c is some constant time ..

- Ishwar chandwani March 03, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

sum all of them and do mod 3
time complexity -> O(n)
space complexity -> O(1)

- Akshat May 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

if the input numbers are positive integers then the following is a solution in O(n). if negative is involved there can be a bit of search involved at the end.

unsigned return_unique_num(const std::vector<unsigned>& input)
{
    std::unordered_set<unsigned> unique_input;
    for (auto i : input)
      unique_input.insert(i);
    long long input_mult = 1;
    long long unique_input_mult = 1;
    std::for_each(input.begin(), input.end(), [&](unsigned i) {input_mult *= i; });
    std::for_each(unique_input.begin(), unique_input.end(), [&](unsigned i) {unique_input_mult *= i; });

    long long cube_unique_input_mult = unique_input_mult * unique_input_mult * unique_input_mult;

    return static_cast<unsigned>(sqrt(cube_unique_input_mult / input_mult));
}

- ahj November 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

integer overflow

- bowl November 03, 2014 | Flag
Comment hidden because of low score. Click to expand.
-2
of 2 vote

Version with handling zero's and negative numbers as well as positives.

#include <vector>
#include <unordered_set>
#include <algorithm>
#include <cmath>

unsigned return_unique_num(const std::vector<int>& input)
{
  int zeros = std::count(input.begin(), input.end(), 0);
  if (zeros == 1)
    return 0;

    std::unordered_set<int> unique_input;
    for (auto i : input)
      unique_input.insert(i);
    long long input_mult = 1;
    long long unique_input_mult = 1;
    std::for_each(input.begin(), input.end(), [&](int i) {if(i) input_mult *= i; });
    std::for_each(unique_input.begin(), unique_input.end(), [&](int i) {if(i) unique_input_mult *= i; });

    long long cube_unique_input_mult = unique_input_mult * unique_input_mult * unique_input_mult;



    int ret = static_cast<int>(sqrt(cube_unique_input_mult / input_mult));
    if (std::count(input.begin(), input.end(), ret) == 1)
      return ret;
    return -ret;
}

- ahj November 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

using System;
using System.Collections.Generic;
class SingularityFinder
{
    static void Main()
    {
        int[] arr = {2,3,5,1,2,2,5,3,5,3 };
        List<int> entries = new List<int>();
        bool bl = false;
        for (int i = 0; i < arr.Length - 1; i++)
        {
            bl = false;
            if (!entries.Contains(arr[i]))
            {
                entries.Add(arr[i]);
                for (int j = i + 1; j < arr.Length; j++)
                {
                    if (arr[i] == arr[j])
                    {
                        bl = true;
                        break;
                    }
                }
                if (!bl)
                {
                    Console.WriteLine(arr[i]);
                    bl = true;
                    break;
                }
            }
        }
        if (!bl)
        {
            Console.WriteLine(arr[arr.Length - 1]);
        }
    }

}

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

That will work, but it has an inner loop, so I think it's quadratic complexity, O(N^2). Also, unless the elements of the List are sorted as they are inserted, how is "Contains" implemented? According to the documentation I could find, "The List interface provides two methods to search for a specified object. From a performance standpoint, these methods should be used with caution. In many implementations they will perform costly linear searches." So for each element in the input you are potentially doing a linear search of the entries List to confirm it does not exist. If you think about the worst case, where you get input of the format 1,2,3,1,2,3,1,2,3,4, then you are doing a linear search for every single item in the input, and on top of that, you're comparing the first 1/3 of the input items to all later items in the input. For input of 10 items you'd be performing 3 * 3 comparisons; for input of 1,000,000 items you'd be performing 333,333 * 333,333 comparisons. Input size has gone up by 100,000 times, but worst case number of comparisons is 12,345,654,321 greater.

- merlinme November 06, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Unfortunately that doesn't work, JustSteppedIn. Try it with the input 1, 2, 3, 5, 2, 2, 5, 3, 5, 3. The last element added to entries will be 5, not 1. That was why in my solution I kept track of "previously_seen" entries and potential "candidates" in separate unordered maps, adding entries to candidates but then deleting them if I saw them more than once. However matt.korwel pointed out that I didn't need to keep them in separate maps, I just needed to keep a count of how many times each one appeared and then iterate through to find the answer which only appears once at the end. Number of operations will increase linearly. In answer to the question 'Any other option without using "Contains"?', yes: use a container optimised for lookup, which is probably a hashmap. In C#, matt.korwel used a Dictionary, which checking the documentation appears to be implemented as a hashmap behind the scenes.

- merlinme November 07, 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