Booking.com Interview Question
Software Engineer / DevelopersCountry: Netherlands
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);
}
}
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.
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;
}
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;
}
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)
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;
}
#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);
}
#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);
}
<?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);
<?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);
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]);
}
}
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]);
}
}
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();
}
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;
}
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...
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.
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