Adobe Interview Question
Member Technical StaffsCountry: India
Interview Type: In-Person
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;
}
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;
}
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
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
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
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)).
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.
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
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
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.
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;
}
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;
}
The complexity of this algo is not better than n(logn). as the set1.get(value) in the for loop is expensive.
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.
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.
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;
}
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;
}
try running our program on sequence { 1,2,1,2,1,2, 219876534567324567098765423}
How big arrfrew will you allocate ??
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);
}
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.
Sorry there was one mistake number+=(countLower%3)*powerOfTwo;
powerOfTwo*=2;
Plus was missing
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.
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;
}
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);
}
}
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.
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
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;
}
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;
}
}];
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());
}
}
}
}
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));
}
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;
}
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]);
}
}
}
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.
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.
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