Facebook Interview Question
iOS DevelopersTeam: iOS
Country: United States
Interview Type: Phone Interview
You can even use HashSet to store the elements, because you don't need to store any value under the key. In this task only presence is important.
@anonymous
That's true. Awwww I feel for you man. To solve that problem I'd suggest you expose yourself to more languages to become more eclectic. Try perl, python, bash/sh scripting, lisp/scheme, and best of all a metalanguage called "write pedagogical pseudo-code so as get your point across."
Is it not that obvious that h.exists() and h.insert() make it clear that we need a hash table which at minimum has some boolean nature internally?
The operations define the required D.S.
The Issue with the solution is that the order is not maintained. Hashtable does not store elements in any specific order.
@CookieMonster thank you for the suggestion, of course I'm trying some other languages, but anyway you are working with your main instrument whole the day :)
Comments upvoting - it's not possible to up/downvote your own comments, it's the rule of this portal, so it's not me. How do people voting here is a separate topic, sometimes very strange.
anonymous, someone named "com" is upvoting your comments
specifically the ones which "debate" me
could be your fan or someone who is both aligned strongly with your debate points and is also following your activity on short time frames
doesn't matter at all to me
What is my main instrument? Your point about "only one hammer see nail yada yada" is actually a point against people who think in one or few languages.
In other words, using "hash table" covers many hammers, while using "HashSet" is the few hammer approach.
Why are you arguing main instrument and blah blah over 1 min. coding exercises?
@CookieMonster hey man, are you crazy? I believe you should stop to watch films about "conspiracy theory".
I didn't understand your last reply at all.
> "What is my main instrument? Your point about "only one hammer see nail yada yada" is actually a point against people who think in one or few languages."
I wrote about me, that my main instrument influenced me to the first comment, because "Hashtable" is a specific data structure in Java, after that I realized where I was wrong. That's all. I thought is was clear and what are you talking about in the last comment I have no idea.
> "Why are you arguing main instrument and blah blah over 1 min. coding exercises?"
This portal is created for the communication about any questions, what I'm actually doing. If you don't have anything to reply - your right is to be silent (or downvote).
I hope this debate is over, because it's already off top of actual coding question.
@anonymous
You need to buzz off dude. I'm reading my post and its repliesbecause I love teaching/talking about problems (hope to be a prof. some day) so I'm checking replies to it.
The guy who uses an anonymous handle and who was up-voting himself with an alternate account and was dropping corny jokes for no reason (that sounded like insults because he used "you/your") now claiming the high ground of staying on topic and keeping careercup pure.
"Oh all I was doing is making fun of myself over and over as replies to your code, didn't you notice?"
"Hey stop, we need to keep this on topic."
# Python
array = ["@2", "@1", "@3", "@1", "@2"]
result = []
for item in array:
if item not in result:
result.append(item)
print result
I don't think this line is good enough "if item not in result". This line costs O(n) time where n is the length of array. A set is good instead.
s = set()
for item in array:
if item not in s:
result.append(item)
s.add(item)
In most real world code, this would be true (for instance, getting unique IP addresses in their order of access), but I think it's good to note too that the overhead of a set is not always good. For instance
from random import randint
from datetime import datetime
long = 100000
short = 10
tests = [["********** Long list of lots of values **********", long, long],
["********** Long list of not many values **********", short, long],
["********** Short list of lots of values **********", long, short],
["********** Short list of lots of values **********", short, short]]
for test in tests:
print test[0]
items = ["".join(["@", str(randint(0,test[1]))]) for value in range(test[2])]
results = []
start = datetime.now()
result = []
for item in items:
if item not in result:
result.append(item)
results.append(result)
difference = datetime.now() - start
method1 = difference.microseconds/1000000.0
print "Method 1", method1
start = datetime.now()
result = []
values = set()
for item in items:
if item not in values:
result.append(item)
values.add(item)
results.append(result)
difference = datetime.now() - start
method2 = difference.microseconds/1000000.0
print "Method 2", method2
assert results[0] == results[1]
print "%s is faster!" % ("Method 1" if method1 < method2 else "Method 2")
Generates:
********** Long list of lots of values **********
Method 1 0.831988
Method 2 0.070339
Method 2 is faster!
********** Long list of not many values **********
Method 1 0.031872
Method 2 0.025667
Method 2 is faster!
********** Short list of lots of values **********
Method 1 8.4e-05
Method 2 3e-05
Method 2 is faster!
********** Short list of lots of values **********
Method 1 1.9e-05
Method 2 2.1e-05
Method 1 is faster!
Note that with a short list with not many values, (for instance, maybe an internal list of IP addresses on a forum or something), method 1 is faster. Just something to think about!.
public void removeDup(int[] a)
{
int N =a.length;
int r=0;
ArrayList<Integer> arrayList = new ArrayList<Integer>();
for(int i =0;i<N;i++)
{
if((r&(1<<a[i]))==(1<<a[i])) continue;
r+=(1<<a[i]);
arrayList.add(a[i]);
}
System.out.println(arrayList);
}
One way to solve it in java: 1. go through all the items in the list. 2. Check if the item is in a hashmap or set, if it's true, ignore it. Otherwise, put the item to the map and append it to an ArrayList
import java.util.List;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
public class Duplicator {
public static List<Integer> uniqueArray(int[] list) {
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
List<Integer> array = new ArrayList<Integer>();
for(int i = 0; i < list.length; i++) {
if(!map.containsKey(list[i])) {
map.put(list[i], 0);
array.add(list[i]);
}
}
return array;
}
public static void main(String[] args) {
int[] list = {1, 2, 3, 2, 3, 5, 4, 1};
List<Integer> array = uniqueArray(list);
for(Integer item: array) {
System.out.print(item + " ");
}
}
}
#include<iostream>
#include<conio.h>
#include<math.h>
#include<stdlib.h>
using namespace std;
int removeDuplicate(int arr[],int len){
long positive = 0L;
long negative = 0L;
int i, j =0;
for(i=0;i<len;i++){
if(arr[i]>=0){
if(positive&1<<arr[i])
continue;
arr[j++]=arr[i];
positive=positive|1<<arr[i];
}else{
if(negative&1<<arr[i])
continue;
arr[j++]=arr[i];
negative=negative|1<<arr[i];
}
}
return j;
}
int main(){
int arr[]={1,2,3,0,0,-1,-2,-3,-4,0,0,1,2,3,4,5,6,7,-1,-2,-3,-4,-5,-6,-7,4,5,6,7,8,-1,-2,-3,-4,-5,-6,-7,0,0,0,0,1,2,3,4,5,6,7,-1,-2,-3,-4,-5,-6,-7};
int len = sizeof(arr)/sizeof(arr[0]);
int arrlen = removeDuplicate(arr,len);
for(int i =0; i <arrlen; i++)
cout<<arr[i]<<" ";
return 0;
}
#include<iostream>
#include<conio.h>
#include<math.h>
#include<stdlib.h>
using namespace std;
int removeDuplicate(int arr[],int len){
long positive = 0L;
long negative = 0L;
int i, j =0;
for(i=0;i<len;i++){
if(arr[i]>=0){
if(positive&1<<arr[i])
continue;
arr[j++]=arr[i];
positive=positive|1<<arr[i];
}else{
if(negative&1<<arr[i])
continue;
arr[j++]=arr[i];
negative=negative|1<<arr[i];
}
}
return j;
}
int main(){
int arr[]={1,2,3,0,0,-1,-2,-3,-4,0,0,1,2,3,4,5,6,7,-1,-2,-3,-4,-5,-6,-7,4,5,6,7,8,-1,-2,-3,-4,-5,-6,-7,0,0,0,0,1,2,3,4,5,6,7,-1,-2,-3,-4,-5,-6,-7};
int len = sizeof(arr)/sizeof(arr[0]);
int arrlen = removeDuplicate(arr,len);
for(int i =0; i <arrlen; i++)
cout<<arr[i]<<" ";
return 0;
}
class Program
{
static void Main(string[] args)
{
string[] arr = { "@2", "@1", "@3", "@1", "@2" };
string[] arr2 = iQ.myFunction(arr);
foreach (string str in arr2)
Console.Write("[" + str + "]");
Console.ReadLine();
}
}
public string[] myFunction(string[] strArr) {
List<string> strList = new List<string>();
string[] tempStr = {};
for (int i = 0; i < strArr.Length; i++) {
for (int j = i; j < strArr.Length; j++) {
if(!strList.Contains(strArr[j]))
strList.Add(strArr[j]);
}
}
tempStr = strList.ToArray();
return tempStr;
}
- (NSMutableString *) removeDuplicates:(NSString *) string
if(string && [string length] > 1){
NSMutableString *stringMutable = [string mutableCopy];
CFMutableBitVectorRef charExists = CFBitVectorCreateMutable(kCFAllocatorDefault,0);
unsigned int index = 0;
while( index < [stringMutable length])
{
if(CFBitVectorGetBitAtIndex(charExists,[stringMutable characterAtIndex:index]) == 0){
CFBitVectorFlipBitAtIndex(charExists,[stringMutable characterAtIndex:index]);
index++;
} else {
[stringMutable deleteCharactersInRange:NSMakeRange(index,1)];
}
}
NSLog(@"%@",stringMutable);
} else {
return string;
NSLog(@"Nothing to be done here");
}
}
Java:
public static void main(String args[]) {
ArrayList<String> list = new ArrayList<String>();
list.add("A");
list.add("B");
list.add("A");
list.add("C");
list.add("B");
ArrayList<String> newList = new ArrayList<String>();
for(String string : list){
if(!newList.contains(string)){
newList.add(string);
}
}
System.out.println(newList);
}
<?php
function removeDup (array $list)
{
for($i = 0;$i < count($list); $i++)
{
$tmp[$list[$i]]++;
}
foreach($tmp as $k=>$v)
{
$output[] = $k;
}
return $output;
}
//Main
echo"Array (space btw elements)-> ";
$line = trim(fgets(STDIN));
echo"Result-> ".implode(",",removeDup(explode(" ",$line)))."\n";
?>
<?php
function removeDup (array $list)
{
for($i = 0;$i < count($list); $i++)
{
$tmp[$list[$i]]++;
}
foreach($tmp as $k=>$v)
{
$output[] = $k;
}
return $output;
}
//Main
echo"Array (space btw elements)-> ";
$line = trim(fgets(STDIN));
echo"Result-> ".implode(",",removeDup(explode(" ",$line)))."\n";
?>
<?php
function removeDup (array $list)
{
for($i = 0;$i < count($list); $i++)
{
$tmp[$list[$i]]++;
}
foreach($tmp as $k=>$v)
{
$output[] = $k;
}
return $output;
}
//Main
echo"Array (space btw elements)-> ";
$line = trim(fgets(STDIN));
echo"Result-> ".implode(",",removeDup(explode(" ",$line)))."\n";
?>
#include <stdio.h>
#include <unordered_set>
#include <list>
using namespace std;
void removeDups(list<int> & values)
{
unordered_set<int> seenValues;
list<int>::iterator iter = values.begin();
while(iter != values.end())
{
if(seenValues.find(*iter) == seenValues.end())
{
seenValues.insert(*iter);
iter ++;
}
else
{
iter = values.erase(iter);
}
}
}
int main()
{
list<int> values;
values.push_back(1);
values.push_back(1);
values.push_back(4);
values.push_back(6);
values.push_back(5);
values.push_back(4);
values.push_back(5);
values.push_back(0);
values.push_back(6);
values.push_back(7);
values.push_back(7);
values.push_back(7);
removeDups(values);
for(list<int>::iterator iter = values.begin(); iter != values.end(); iter ++)
{
printf("%d ",*iter);
}
return 0;
}
This is a one-liner in Python.
from collections import OrderedDict
def dedupe(lst):
return OrderedDict((x, 1) for x in lst).keys()
If you're not allowed imports, you can just iterate over the list, updating a normal dictionary as you go and for items not seen before you copy them into a separate list, which you return at the end.
Since I did not see a scala solution, thought I would add one :-)
I use a Set to determine what has already been seen, a list to collect what has been seen, and a recursion to solve the problem.
type ilist = List[Int]
def removeDups(l:ilist, sofar:ilist, seen:Set[Int]):ilist = {
l match {
case h::t => if (seen.contains(h)) removeDups(t, sofar, seen)
else removeDups(t,h :: sofar, seen + h)
case List() => sofar.reverse
}
}
Execution on the provided data:
scala> val vals = List(2,1,3,1,2)
vals: List[Int] = List(2, 1, 3, 1, 2)
scala> removeDups(vals, Nil, Set.empty[Int])
res2: ilist = List(2, 1, 3)
Since I did not see a scala solution, thought I would add one :-)
I use a Set to determine what has already been seen, a list to collect what has been seen, and a recursion to solve the problem.
type ilist = List[Int]
def removeDups(l:ilist, sofar:ilist, seen:Set[Int]):ilist = {
l match {
case h::t => if (seen.contains(h)) removeDups(t, sofar, seen)
else removeDups(t,h :: sofar, seen + h)
case List() => sofar.reverse
}
}
Execution on the provided data:
scala> val vals = List(2,1,3,1,2)
vals: List[Int] = List(2, 1, 3, 1, 2)
scala> removeDups(vals, Nil, Set.empty[Int])
res2: ilist = List(2, 1, 3)
-(NSArray *)removeDuplicates:(NSArray *)uncheckedArray{
NSMutableSet *checkList = [NSMutableSet set];
NSMutableArray *uniqueArray = [NSMutableArray array];
for (id object in uncheckedArray) {
BOOL isDuplicate = [checkList containsObject:object];
if (!isDuplicate) {
[checkList addObject:object];
[uniqueArray addObject:object];
}
}
return [uniqueArray copy];
}
int k=0,i=0;
a[k++]=a[i];
while(i<n)
{
if((a[i]!=a[i+1])&&(notcomesbefore()))
a[k++]=a[i+1];
i++;
}
notcomesbefore()
{
use hash table ..........//hash table is initialised to zero
if(hash array has value 1) //this value is already taken
return 0;
else
return 1;
}
based on my this solution ..code in c is...
assumption: array elements are single digit ...for anything else u can make a suitable hash function
#include<stdio.h>
#include<conio.h>
int hash[10];
main()
{
int i,modifiedlength;
int x;
int arr[7]={0,8,9,8,0,2,0};
modifiedlength=removedup(arr,7);
for(i=0;i<modifiedlength-1;i++)
printf("%d ",arr[i]);
getch();
}
int removedup(int a[],int n)
{
int i,k;
i=0;k=0;
hash[a[0]]=1;
a[k++]=a[i];
while(i<n)
{
if((a[i]!=a[i+1])&&(hash[a[i+1]]==0))
{
a[k++]=a[i+1];
hash[a[i+1]]=1;
}
i++;
}
return k;
}
I would like to use LinkedHashMap to hold values from array one by one, this way, no dups will be stored, while order will be maintained:
public void removeDup(String[] strArr){
LinkedHashMap<String, Integer> linkedhmap = new LinkedHashMap<String, Integer>();
for (int i=0; i<strArr.length; i++){
linkedhmap.put(strArr[i], 1);
}
Iterator iter = linkedhmap.keyset().iterator();
while (iter.hasNext()){
System.out.println(iter.next());
}
}
void RemoveDuplicate(int *a)
{
if(a==NULL)
return;
int *q=a;
n=sizeof(a)/sizeof(a[0]);
int *tb=new int[n+1];
memset(t,0,sizeof(int)*(n+1));
vector<int>vec;
int cnt=0;
while(cnt<n)
{
if(t[*q]==0)
{
t[*q]=1;
vec.push_back(*q);
}
q++;
cnt++;
}
vector<int>::iterator p=vec.begin();
while(p!=vec.end())
cout<<*p++<<"\t";
cout<<endl;
delete [] t;
}
+(NSArray*)removeDuplicateNumbers
{
NSArray *array = @[@"2",@"1",@"3",@"1",@"2"];
NSMutableOrderedSet *set = [[NSMutableOrderedSet alloc]init];
for (NSString *str in array) {
if (![set containsObject:str]) {
[set addObject:str];
}
}
return [set array];
}
This can be achieved using Hashset for example in C#, add items to HashSet from beginning to end and print them using either foreach loop or HashSet.elementAt():
for example:
for(int i = 0; i < HashSet.Count; i++){
print(HashSet.elementAt(i));
}
I can think of 4 solutions as of now:
Solution 1: Time O(nlogn) Space O(1)
Sort the array using quicksort. Traverse the array if the consecutive values are same then remove it and keep shifting the corresponding further values.
Solution 2: Time O(n) Space O(n)
Use hashmap to store the value while traversing the array. If value is already present then remove the element,
Solution3: Time O(n2) Space O(1)
Use two for loops (Brute force method)
Solution 4: Time O(n) Space O(Max value in an array)
Find the largest element in the array ( considering @ can be ignored since its constant for all the values).
Create an array of that size. Iterate the given array and mark the corresponding index in the new array as visited. If value is already marked visited then it is the duplicate.
Solution 1 doesn`t work. You need to preserve the order and by sorting you`ll destroy it.
I think your fourth solution will only work for positive integers, I like your solution 1, solution 3 wont work in interview, solution 2 is good but better still is hashset.
Nice discussion folks (forced some thinking).
I am trying to salvage is 1 to 4 list:
S.Dev's solution #1)
----------------------------
I think we can do it with O(n) extra space.
Declare class/struct like this:
struct {
Type or Type* item; //store or point to element in array
unsigned int index; //index of item in original;
};
Then fill out a linked list (or array list) of structures like defined above to mirror the array.
Now we can
a) Sort on the indices (doesn't need to be stable)
b) Stable sort on the item's (so can't use quicksort because it is unstable)
Now we traverse the list and remove duplicate links.
Then
c) We sort it on indices again.
We should have the result in the linked list (or array list) now.
Confirm please.
His solution #4) {This assumes integer items though}
----------------------
a) On first pass find max and also min.
b) then declare:
bool tab[max - min + 1] ={0};
c) then use this no-collision hash:
#define h(x) ((x)-min)
d) then run regular hash scheme:
for(to=from=0; from < a.length; from++) {
if( tab[ h(a[from]) ] ) continue;
else tab[ h(a[from]) ]=true, a[to++] = a[from];
}
a.length=to;
Space is O(range) though, but no pain in the neck % and collisions.
Off by one errors? :)
For #4:
If you know you`ll only have single digits no need to parse the input at all just us characters[10]. If you can have single digits and single chars supposing ASCII characters you`ll need to use characters[256]. If the input is not single digit/char then a hash is required and using just an array might be problematic: imagine a case were the input is @2,@3,@2,@65535 -> you`ll allocate a giant array for 2 values.
Manually like this.
Whenever you think of "have I seen it before" problems, think "hash tables."
h is hash table for elements in your array.
Should work.
- Urik's twin Cookie Monster (dead now) October 29, 2013