Amazon Interview Question
Quality Assurance EngineersTeam: Kindle
Country: India
Interview Type: In-Person
How is the space O(n)?? Because it depends on the number in the array right.
Say if n=10, and largest element in the array is m~99999999. Array which we have to create should be of length m.
If there is any other to get the hashmap please explain
Use AVL trees to store elements and search in it...like STL hashmaps....logn for searching n inserting...so space is 0(n) n is number of nodes and time is n logn n...even if we search in hash maps they internally uses red black tres.
or
0(m) space..as above mentioned comment
thnx
You don't need a HashMap. A Set would work and require less space.
public Integer getDuplicate(int[] numbers) {
Set<Integer> freq = new HashSet<Integer>();
for (int i = 0; i < numbers.length; i++) {
if (!freq.contains(numbers[i])) {
freq.put(numbers[i]);
} else {
return number[i];
}
}
return null;
}
import java.util.HashMap;
public class FirstDupicate {
public static void main(String []args)
{
int []arr= {4,3,5,6,5,7,8,4};
int duplicate=-1;
HashMap<Integer,Integer> hm=new HashMap<Integer, Integer>();
for(int i:arr){
System.out.print(i+",");
if(null==hm.get(i))
{
hm.put(i,i);
}
else{
duplicate=i;
break;
}
}
System.out.println(duplicate);
}
}
This is my C++ version with O(n) time, O(n) space.
#include <iostream>
#include <unordered_set>
#include <vector>
template <typename T>
typename std::vector<T>::iterator find_first_duplicate(std::vector<T>& arr) {
std::unordered_set<T> set;
for (auto it = arr.begin(); it != arr.end(); it++) {
const T& elem = *it;
if (set.count(elem))
return it;
set.insert(elem);
}
return arr.end();
}
int main() {
std::vector<int> arr{4,3,1,2,5,9,5,4};
auto it = find_first_duplicate(arr);
if (it != arr.end())
std::cout << "first duplicate: " << *it << std::endl;
return 0;
}
Time O(n) Space(n). Finding a number which have Closest duplicate. Below method will return 5 as answer not 4 since 5 has closest duplicate then 4.
public static int FindClosestDuplicate(int[] arr)
{
if (arr == null) return -1;
Dictionary<int, int> elePos = new Dictionary<int, int>();
int minDiff = int.MaxValue;
int duplicate = -1;
for (int i = 0; i < arr.Length; i++)
{
if (elePos.ContainsKey(arr[i]))
{
int pos = elePos[arr[i]];
int diff = i - pos;
if (diff < minDiff)
{
minDiff = diff;
duplicate = arr[i];
}
}
else
elePos.Add(arr[i], i);
}
return duplicate;
}
}
public class FindingFirstDuplicateElement {
/**
* @param args
*/
public static void main(String[] args) {
int[] data = { 4, 3, 1, 2, 5, 9, 5, 4 };
Map<Integer, Integer> lookup = new HashMap<Integer, Integer>();
for (int temp : data) {
if (lookup.containsKey(temp)) {
System.out.println(temp);
} else {
lookup.put(temp, 1);
}
}
}
}}
I agree that hashset should be used since it also has a method that returns false if the element being added is duplicate.Moreover for Performance both hashmap and hashset are same,but this code makes it much simpler.
import java.util.HashSet;
public class FirstDupicate {
//Use hashset because it has a function that can be used for finding the duplicates (public boolean add(obj) )
public static void main(String []args)
{
int []arr= {4,3,5,6,5,7,8,4};
int duplicate=-1;
HashSet<Integer> hs=new HashSet<Integer>();
boolean isUnique=false;
for(int i:arr){
isUnique=hs.add(i);
if(!isUnique)
{
duplicate=i;
break;
}
}
System.out.println(duplicate);
}
}
For simplicity, assume that the values of the array A are all positive integers and A has length N (In the general case, hash the values of A into the positive integers). Now, count sort the values A[i] of A, starting from i=0, noting that the first bin to obtain two elements will be the first duplicate.
Let B = array of length max{ A[i] }
for i=0, i < B.length, i++
B[i]=0
for i=0, i < N, i++
if B[A[i]] //returns true when B[A[i]]=1, aka A[i] has already appeared
return i //index of the first duplicate
B[A[i]]++
Since we begin with i=0, we are assured to return the first duplicate.
Recursive version
int getDuplicateElement(int[] numbers, int j, int dupElement, int difference)
{
if(j + 1 == numbers.length)
{
return dupElement;
}
for(int i = j + 1; i < numbers.length; i++)
{
if(numbers[j] == numbers[i] && difference > (i - j))
{
dupElement = numbers[i];
difference = i - j;
break;
}
}
return getDuplicateElement(numbers, j + 1, dupElement, difference);
}
Here is the C++ code:
//!!!Finding first duplicate element in the array
string strArr = "43125954";
int cPntr = 0;
int lPntr = 0;
for (int i = 0; i < strArr.length(); i++)
{
for (int j = (i+1); j < strArr.length(); j++)
{
if (strArr[i] == strArr[j])
{
cPntr = j;
}
}
if ( cPntr < lPntr)
lPntr = cPntr;
else
lPntr = cPntr;
}
cout << strArr[lPntr] << " is the first duplicate elements in the string";
cout << endl;
public static void fPrintDuplicate(int []arr) {
//Time complexity is more, as all elements till end needs to be worked
int asum=0;
int n = arr.length;
int esum = n*(n+1)/2; //expected sum;
for(int i=0;i<arr.length;i++)
asum += arr[i];
System.out.println("esum="+esum); //expected sum;
System.out.println("asum="+asum); //actual sum
int missing = n - (asum+1 - esum) ;
System.out.println("Missing number = "+missing);
int duplicate = missing - 1;
System.out.println("Duplicate number = "+duplicate);
}
int firstDup(int[] str) {
int len = str.length;
Map map = new HashMap();
int loc = len;
int lastValue = 0;
for (int i = 0; i < len; i++) {
for (int j = i + 1; j < len; j++) {
if (str[i] == str[j]) {
if (loc > j) {
loc = j;
}
}
}
}
return str[loc];
}
Time: O(n) Space: O(n)
- Shikhar November 23, 2013Use hashMap to mark every element encountered so far. The first element that is already in map is the output, print that number and return.