Booking.com Interview Question for Software Engineer / Developers


Country: Netherlands




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

If you are asked this, try to make your first answer as simple as possible: "I would use a set to keep track of integers that I already encountered." Then engage the interviewer in dialog. Does she have any special constraints? Is time scarce, storage scarce, or both? Also, make sure that the interviewer knows that you know the difference between interface and implementation. There are a zillion ways to implement a set, but the most important feature of a set is that you can put a value into it, and the set will remember that it's part of the, um, set. The actual implementation can be based on a hash, but be clear that it's an implementation detail.

- showell30@yahoo.com February 22, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

LinkedHashSet

- Anonymous February 21, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

public static void main(String args[])
{
List<Integer> list = new ArrayList<Integer>();

list.add(new Integer(1));
list.add(new Integer(2));
list.add(new Integer(2));
list.add(new Integer(3));
list.add(new Integer(3));
list.add(new Integer(2));
list.add(new Integer(5));
list.add(new Integer(4));
list.add(new Integer(4));

Set<Integer> withoutRepetition = new HashSet<Integer>();

List<Integer> finalList = new ArrayList<Integer>();

for(Integer intNum: list)
{
if(!withoutRepetition.contains(intNum))
{
withoutRepetition.add(intNum);
finalList.add(intNum);
}
}

for(Integer intNum: finalList)
System.out.println(intNum);
}
}

- Kris February 21, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

withoutRepetition is necessary? you are not using it

- duygu.kahramann February 08, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use a hashset?

- Jialiang February 20, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

HashSet does not preserve the Order.

- Vijay February 21, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

We have to use LinkedHashSet

- Anonymous February 21, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Or just start with an empty HashSet, and for each element of the array, check to see if it's already in the hashset. If yes, don't print it or do anything else; if no, add it to the hashset and print it. This way each element will be printed the first time it occurs.

- eugene.yarovoi February 21, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

-@eugene.yarovoi: I think the answer is perfectly fine.

- Rahul February 21, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Rahul: The original answer ("Use a hashset?") doesn't describe in what way a HashSet would be used. I was not disputing the correctness of the LinkedHashSet comment, only offering another possible approach.

- eugene.yarovoi February 22, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use TreeSet. Compare by index and value, while traversing array. If values are different, sort by index. If values are equal, discard dup.  Overall running time is O(nlogn)

- Jack February 21, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

We can use OrderedSet STL (CPP).

- rahul.kushwaha February 21, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void remove_repetitions(int* a, unsigned& size)
{
set<int> s;
unsigned removeIndex = 0;
for (unsigned i=0; i<size; i++)
{
if (s.find(a[i]) != s.end()){
if (removeIndex == 0) removeIndex = i;
} else if (removeIndex>0) {
a[removeIndex++] = a[i];
}
s.insert(a[i]);
}
if (removeIndex>0) size = removeIndex;
}

- SD February 21, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void remove_repetitions(int* a, unsigned& size)
{
        if (size<2) return;
        set<int> s;
        unsigned removeIndex = 0;
        for (unsigned i=0; i<size; i++)
        {
                if (s.find(a[i]) != s.end()){
                        if (removeIndex == 0) removeIndex = i;
                } else if (removeIndex>0) {
                        a[removeIndex++] = a[i];
                }
                s.insert(a[i]);
        }
        if (removeIndex>0) size = removeIndex;
}

- SD February 21, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Q + hasset should solve the problem

- hint February 21, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

scala> def rmDuplicates(a: Array[Int]): Array[Int] = a match {
     |  case Array() => Array()
     |  case Array(e,tail@_*) => e +: rmDuplicates(tail.filterNot(x => e == x).toArray)
     | }
rmDuplicates: (a: Array[Int])Array[Int]

scala> rmDuplicates(Array(1,1,2,3,4,4,5,6,7,7,7))
res15: Array[Int] = Array(1, 2, 3, 4, 5, 6, 7)

- rbsomeg February 21, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void Remove(int arr[],int size)
{
map<int,int> mymap;
map<int,int> :: iterator it;
int start=0;
for(int i=0;i<size;i++)
{
it=mymap.find(arr[i]);
if(it==mymap.end())
{
mymap.insert(pair<int,int>(arr[i],i));
swap(arr[i],arr[start++]);
}
}
memset(arr+start,0,sizeof(int)*(size-start));
}

- Anonymous February 21, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I give a neat answer.

List<Integer> removeDuplicates(List<Integer> intList) {
    Set<Integer> occurrences = new HashSet<Integer>();
   
    for (int i = 0; i < intList.size(); i++) {
        if (occurrences.contains(intList.get(i))) {
            intList.remove(i);
            i--;  // adjust the index to counter the removed effect
        } else {
            occurrences.add(intList.get(i));
        }
    }

    return intList;
}

- Danny Sun February 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#!/usr/bin/python

input = [4, 5, 6, 3, 3, 4, 5, 1, 2, 2, 5];

result = [];

for x in input:
        if input.count(x) > 1 and result.count(x) == 0:
                result.append(x);
                
print result

- PT May 01, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char *argv[]) {
        int arr[] = {4,5,6,3,3,4,5,1,2,2,2,5};

        int htable[10] = {0};

        int len = sizeof(arr)/sizeof(arr[0]);
        int *result;

        //Loop to figure out extras for allocating space for
        //result array.
        int i, count=0;
        for(i=0;i<len;i++) {
                if(htable[arr[i]] > 0) {
                        count++;
                }
                htable[arr[i]]++;
        }

        result = (int *) malloc((len-count) * sizeof(int));

        int j=0;
        for(i=0;i<len;i++) {
                //zero the hit the first pass
                if(htable[arr[i]] > 0) {
                        htable[arr[i]] = 0;
                        result[j++] = arr[i];
                        printf("%d", result[j-1]);
                }
        }
        printf("\n");

        free(result);
        return(0);
}

- PT June 12, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char *argv[]) {
        int arr[] = {4,5,6,3,3,4,5,1,2,2,2,5};

        int htable[10] = {0};

        int len = sizeof(arr)/sizeof(arr[0]);
        int *result;

        //Loop to figure out extras for allocating space for
        //result array.
        int i, count=0;
        for(i=0;i<len;i++) {
                if(htable[arr[i]] > 0) {
                        count++;
                }
                htable[arr[i]]++;
        }

        result = (int *) malloc((len-count) * sizeof(int));

        int j=0;
        for(i=0;i<len;i++) {
                //zero the hit the first pass
                if(htable[arr[i]] > 0) {
                        htable[arr[i]] = 0;
                        result[j++] = arr[i];
                        printf("%d", result[j-1]);
                }
        }
        printf("\n");

        free(result);
        return(0);
}

- PT June 12, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

<?php
# Same order or exactly same position. Its not the same question/answer
$arr = [1, 1, 2, 2, 3, 4, 5, 10, 1, 7];
print_r(array_unique($arr));

# Keeping only the same order
$res = [];
foreach($arr as $v) {
    if(!in_array($v, $res)) $res[] = $v;
}
print_r($res);

# Keeping the same position
$res = [];
foreach($arr as $i => $v) {
    if(!in_array($v, $res)) $res[$i] = $v;
}
print_r($res);

- Lucas July 08, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

<?php
# Same order or exactly same position. Its not the same question/answer
$arr = [1, 1, 2, 2, 3, 4, 5, 10, 1, 7];
print_r(array_unique($arr));

# Keeping only the same order
$res = [];
foreach($arr as $v) {
    if(!in_array($v, $res)) $res[] = $v;
}
print_r($res);

# Keeping the same position
$res = [];
foreach($arr as $i => $v) {
    if(!in_array($v, $res)) $res[$i] = $v;
}
print_r($res);

- Lucas July 08, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

NSArray *initialArray = @[@(10),@(20),@(30),@(10),@(30),@(20)];

    NSMutableArray *newArray = [NSMutableArray new];
    
    for (NSNumber *number in initialArray)
    {
        if (![newArray containsObject:number])
        {
            [newArray addObject:number];
        }
    }

- Anonymous September 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Swift implementation.

import UIKit

var numbers = [7, 7, 7, 1, 1, 1, 2, 3, 4, 4, 5, 5, 6, 7, 7, 8, 8]
var filter = NSMutableArray()

for number in numbers {
    if !filter.containsObject(number) {
        filter.addObject(number)
    }
}

println(filter)

- hebertialmeida September 24, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#!/usr/bin/perl

use strict;
use warnings;

my @arr = (1,2,3,6,7,2,3,4,5,6,5,6);
my @newarr = ();

foreach my $element(@arr){
push @newarr, $element if (join('',@newarr) !~ m!$element!);
}
print @arr,"\n\n";
print @newarr;

- Disha April 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#!/usr/bin/perl

my @arr = (1,2,3,6,7,2,3,4,5,6,5,6);
my %aux;
my @newarr = grep { ++$aux{$_} == 1 } @arr;
print join ', ', @newarr; print "\n";

- EvilCartman May 04, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Ruby

values= [0,0,0,2,1,3,4,1,2,3,4,6,-1]
unique = []
existing = {}
values.each do |value|
	if !existing.has_key?(value)
		unique << value
	end
	existing[value] = true
end
print "#{unique.inspect}\n"

- Camilo May 14, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

What about using a stack?

public static void main(String args[]){
		int[] inputArr = {1,2,2,7,7,7,6,5,4,4,2};
		Stack<Integer> st = new Stack<Integer>();
		st.push(inputArr[0]);
		for(int i=1;i<inputArr.length;i++){
			if(st.peek()!=inputArr[i])
				st.push(inputArr[i]);
		}
		System.out.println(st);
	}

- bugibugi October 16, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use LinkedHashSet

public static void main(String[] args) {
		int a [] = {1,2,4,5,7,8,9,9,4,1,1};
		
		LinkedHashSet<Integer> set = new LinkedHashSet<>();
		for (int i = 0; i < a.length; i ++ ) {
			set.add(a[i]);
		}
		
		for (Integer integer : set) {
			System.out.println(integer);
		}

}

- tasneem March 15, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

const a = [5, 2, 2, 4, 1, 4, 5, 1, 3, 4, 4];

let hmap = {};
let b = [];
for(let i=0; i<a.length; i++){
    if(!hmap[a[i]]){
        b.push(a[i]);    
    }    
    hmap[a[i]] = a[i];    
}
console.log(b);

- Saiful April 23, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public void removeDuplicateValueInArrayWithOutSet(Integer[] n){
int sizeOfArray = n.length;
for(int i=0;i<sizeOfArray;i++){
for(int j=i+1;j<sizeOfArray;j++){
if(n[i] == n[j]){
//remove duplicate
int shiftLeft = j;
for(int k=j+1;k<sizeOfArray;k++,shiftLeft++){
n[shiftLeft] = n[k];
}
--j;
--sizeOfArray;
}
}

}
for (int i=0; i<sizeOfArray;i++){
System.out.println(n[i]);
}
}

- Nelson June 27, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public void removeDuplicateValueInArrayWithOutSet(Integer[] n){
int sizeOfArray = n.length;
for(int i=0;i<sizeOfArray;i++){
for(int j=i+1;j<sizeOfArray;j++){
if(n[i] == n[j]){
//remove duplicate
int shiftLeft = j;
for(int k=j+1;k<sizeOfArray;k++,shiftLeft++){
n[shiftLeft] = n[k];
}
--j;
--sizeOfArray;
}
}

}
for (int i=0; i<sizeOfArray;i++){
System.out.println(n[i]);
}
}

- Nelson June 27, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int[] RemoveDuplicatesInOrder(int[] array)
        {
            //List<T> in .Net maintains the insertion order
            List<int> result = new List<int>();

            HashSet<int> set = new HashSet<int>();

            for(int i=0;i<array.Length;i++)
            {
                if(!set.Contains(array[i]))
                {
                    set.Add(array[i]);
                    result.Add(array[i]);
                }
            }

            return result.ToArray();
        }

- SiddharthSingh March 13, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

List<Integer> removeDuplicates(List<Integer> values) {
		Set<Integer> withoutRepetition = new HashSet<Integer>(values);
		List<Integer> ret = new ArrayList<Integer>();
		for(Integer val : values) {
			if(withoutRepetition.remove(val)) {
				ret.add(val);
			}
		}
		return ret;
	}

- helpless February 21, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This solution does not preserve original order.

- Jack February 21, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

sort array by using merge sort which is stable. the next steps are obvious..insert the 1st item in the resulting array, for each next item insert it in the resulting array if the key is not equal to the key of the previous value in the sorted array...

- S.Abakumoff February 21, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Review the definition of "stable sort". A "stable" sort does not preserve the order of all elements, only elements with equal sorting keys. Since we just have an array of integers here, whether or not we use a stable sort is irrelevant. Any sort will destroy the order of elements and therefore not satisfy the requirements of this problem.

- eugene.yarovoi February 21, 2013 | Flag


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