## Yahoo Interview Question for Software Engineer / Developers

Team: Ad
Country: United States
Interview Type: In-Person

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

This can be done using a Set. We will put one element from the array at a time in the Set. If the add operation returns false then it means that element was already present in the Set and thus is a duplicate.

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

o(n) runtime and O(1) space complexity

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

Is there actually a solution can be done by O(N) time and O(1) space?

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

With the question as it is, no. You would need to know more about the data in the array to be able to do it in O(n) time and O(1) space.

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

Either a set or a Hash Table. Someone already mentioned how to use a set, but you could create a hash table, w/ boolean value true during inserts. If there's a collision -> return true. There are a bunch of ways to simplify the hash table.

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

``````a = [1,2,34,545,334,53,534,56,7,4,3,1]
def findDup():

d = {}
for i in a:
print d
try:
d[i] = d[i] + 1
if d[i] > 1:
return True
else:
continue
except:
d[i] = 1
continue
else:
continue
return False

print findDup()``````

Comment hidden because of low score. Click to expand.
0
of 0 votes
If you are doing it in Python, might as well do it in Pythonic way :P (Use collections.Counter) {{{ import collections def findDup(a): d = collections.Counter(a) for key, value in d.items(): if value > 1: return True return False a = [1, 2, 34, 545, 334, 53, 534, 56, 7, 4, 3, 1] print findDup(a)
Comment hidden because of low score. Click to expand.
0
of 0 votes

If you are doing it in Python, might as well do it in Pythonic way :P
(Use collections.Counter)

``````import collections

def findDup(a):
d = collections.Counter(a)
for key, value in d.items():
if value > 1:
return True
return False

a = [1, 2, 34, 545, 334, 53, 534, 56, 7, 4, 3, 1]
print findDup(a)``````

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

``````a = [1,2,34,545,334,53,534,56,7,4,3,1]
def findDup():

d = {}
for i in a:
print d
try:
d[i] = d[i] + 1
if d[i] > 1:
return True
else:
continue
except:
d[i] = 1
continue
else:
continue
return False

print findDup()``````

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

``````var findDuplicatedItems = (function() {
var obj = {}, result = [],
len = 0;

return {
getDup: function(arrData) {
len = arrData.length;
for(var i = 0; i < len; i++) {
if (obj[arrData[i]]) result.push(arrData[i]);
else obj[arrData[i]] = true;
}
console.log(result);
}
};
})();

var arr = [1, 2, 3, 4, 77, 54, 3, 57, 2, 99, 54];
findDuplicatedItems.getDup(arr);``````

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

For a Set or HashMap there is space complexity and without them it is impossible to do it in O(n) time complexity and O(1) space complexity unless you are exploiting any data specific properties.

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

If the array has exactly 0 or 1 duplicate then it can be found in O(N) time and O(1) space complexity if it is an array of char or int.

Step1 : Sum the array .If it is char array convert to ascii no and sum the array up.
Step 2: XOR the array and compare this value with sum from step 1.
if (sum from step1 == sum from step2) {
return no duplicates
}
else {
return ascii (step1 - step2)/2;
}

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

How about using a BloomFilter..

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