Solution For Interview Question: First Duplication | Asked By Google
Find First Duplicate is one of a classic interview question that has been asked by google which you can solve in codesignal. But if you are looking for a different solution than yours, here's how I solved it.
Problem
Given an array a
that contains only numbers in the range from 1
to a.length
, find the first duplicate number for which the second occurrence has the minimal index. In other words, if there are more than 1 duplicated numbers, return the number for which the second occurrence has a smaller index than the second occurrence of the other number does. If there are no such elements, return -1
.
Example
- For
a = [2, 1, 3, 5, 3, 2]
, the output should befirstDuplicate(a) = 3
. - There are
2
duplicates: numbers2
and3
. The second occurrence of3
has a smaller index than the second occurrence of2
does, so the answer is3
. - For
a = [2, 2]
, the output should befirstDuplicate(a) = 2
; - For
a = [2, 4, 3, 5, 1]
, the output should befirstDuplicate(a) = -1
.
Solution
- Create a hash map to store previously visited numbers
- If the current number already exists on the map then this would the first duplicate number we are looking for
Complexity: O(N)
Comments
Leave a comment
You are not LoggedIn but you can comment as an anonymous user which requires manual approval. For better experience please Login.