## Adobe Interview Question for Member Technical Staffs

• 2

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.

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

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) {
}
}
return result;
}``````

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

isn't this this nlog(n) algorithms

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

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;
}``````

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``````

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

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

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

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

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

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

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

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

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.

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``````

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``````

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

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.

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

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;
}

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;
}``````

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

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

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

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

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

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.

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

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.

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;
}``````

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;
}

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

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

How big arrfrew will you allocate ??

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

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

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);``````

}

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

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.

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

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

Plus was missing

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

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?

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.

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;
}``````

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[i]++;
}

var singleOccur = hash.Single(h => h.Value == 1).Key;
Console.WriteLine(singleOccur);
}
}``````

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

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.

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

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

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;
}``````

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

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.

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;
}
}];``````

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];
}``````

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

``````package test;

import java.io.IOException;
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;
try {
} 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());
}
}

}
}``````

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 ..

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)

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));
}``````

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

integer overflow

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;
}``````

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]))
{
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]);
}
}``````

}

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

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.

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

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.

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.

### 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.