## Expedia Interview Question for Principal Software Engineers

Country: India
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
2
of 4 vote

Use a set instead. For hashmap, it will need <key,value> pairs. Instead set will serve the purpose. Use contains method to find if the value is already inserted in the set. If yes, print the element.

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

The HashMap/HashSet are only used to detect duplicates. The order is kept by iterating over the array and storing the duplicates in another array or simply printing them out as we go.

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

Set is a better option here. Add array element to the set and check the return value of set.add() which returns true if this set did not already contain the specified element. There is no need of calling contains() to check if the value is already present.

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

I have solve it using count sort.I will create one more array of size K where K is the range of numbers it can have.Now suppose N numbers are there than the time complexity is
O(K * N)
let say numbers are 3,5,5,8,4,7,8,2,7,9,6,6
then another array will be of size 9 as numbers varies from 1-9
now in this array i will put the count of numbers at index = number , so
index 1 2 3 4 5 6 7 8 9
count 0 1 1 1 2 2 2 2 1

I will finally traverse the new array and any index with count > 1 means it is duplicate.

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

Time complexity of this algorithm is O(N), I do not think K will play any role, whereas it is possible for shorter arrays space complexity will be quite huge... Consider following array
1, 123456

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

Also, what if your array comprises negative integers? It seems you might need an additional step...

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

And how you get the same order. While traversing through the array you will loose the order.

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

Create one hash map and start putting array elements one by one. Before putting elements in hash map just check whether it's already present in hash map or not. If already present in hash map then it's duplicate and print it.
Time Complexity = O(n)
Space Complexity = O(n)

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

This answer is incorrect as hashmap does not preserve the insertion order, for that we can used LinkedHashMap but then we can use it if space is not a constraint.

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

Let me explain by this by example. Lets say we array
{3,1,2,3,1,5,6,9,8,6}
Now 3 , 1 ,6 will be present in hash map already so it will print it in correct seqenece
3 , 1, 6 as i am iterating the array

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

@Avinash :
1) HashMap is a map based on hashing of the keys. It supports O(1) get/put operations. Keys must have consistent implementations of hashCode() and equals() for this to work.

2) LinkedHashMap is very similar to HashMap, but it adds awareness to the order at which items are added (or accessed), so the iteration order is the same as insertion order (or access order, depending on construction parameters).

There is no guarantee that hash map will preserve the order in which it is inserted.Hence although we will find out the duplicates using hash map but the order will get change.

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

I agree to your points but my point is I am not dependent on hashMap insertion order to check the duplicates. Order will be maintained by array iteration order.

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

#include<stdio.h>
int main(){
int arr[50];
int *p;
int i,j,k,size,n;
printf("\nEnter size of the array: ");
scanf("%d",&n);
printf("\nEnter %d elements into the array: ",n);
for(i=0;i<n;i++)
scanf("%d",&arr[i]);
size=n;
p=arr;
for(i=0;i<size;i++){
for(j=0;j<size;j++){
if(i==j){
continue;
}
else if(*(p+i)==*(p+j)){
k=j;
size--;
while(k < size){
*(p+k)=*(p+k+1);
k++;
}
j=0;
}
}
}
printf("\nThe array after removing duplicates is: ");
for(i=0;i < size;i++){
printf(" %d",arr[i]);
}
return 0;
}

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

O(n) solution but need additional space.
create and int asciiArray[256]. This will act as the ascii incrementer.
for each value in the given list:
find its ascii value and increment the corresponding int in the asciiArray.

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

``````int[] n={1,1,5,0,-2,33,343,8,29,-2};
List<Integer> duplicates = new ArrayList<Integer>();
List<Integer> all = new ArrayList<Integer>();
for(int i:n) {
if(all.contains(i)) {
} else {
}
}
System.out.println(duplicates);``````

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

``````// Time Complexity is O(n) and space complexity is (n)
void findDuplicates(int[] arr) {

Map<Integer, Integer> hashMap = new HashMap<Integer, Integer>();
Set<Integer> duplicates = new HashSet<Integer>();

for (int index = 0; index < arr.length; index++) {

if (null != hashMap.get(arr[index])) {
} else {
hashMap.put(arr[index], 1);
}
}

for (Integer duplicate : duplicates) {
System.out.println(duplicate);
}

}``````

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

public static List<int> FindDuplicates(int[] arr)
{
List<int> duplicates = new List<int>();
Dictionary<int, int> iDict = new Dictionary<int, int>();

foreach(int i in arr)
{
if(!iDict.ContainsKey(i))
{
}
else
{
iDict[i]++;
}
}

foreach(KeyValuePair<int,int> keyvalue in iDict)
{
if(keyvalue.Value>1)
{
}
}
return duplicates;
}

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

There are 4 Approaches for this solution:
Approach 1: If input element is lying certain number range and upper limit of range is not too high.
Than apply counting sort approach
Approach 2: Using hash map, input array number is key for the element,hence when we insert element in hashmap check key exist or not, if now than add key with frequency 1 as value, otherwise increase frequency by 1.

Appraoch 3: Build BST from given number at any node , node having four filed, value, frequncy , left and right reference.

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.