## Facebook Interview Question for Software Engineer / Developers

Team: iOS
Country: United States
Interview Type: In-Person

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

Simply iterate over the array with duplicates and add each element to a HashSet. If the add() method of the HashSet returns true we add the element to the new array, if it returns false we ignore the element.

Time Complexity: O(n)
Space Complexity: O(n)

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

Does the iteration over the HashTable follow the original order of the array? The problem description talked about "keeping the original order of the elements". Not sure if HashTable per se guarantees insertion order during retrieval.

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

@diegum, use LinkedHashMap to retain insert order.

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

@diegum, thanks for pointing it out. My bad.

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

The time complexity is not O(n) becase you have to apply the hash function to each word. The time complexity should be O(kn) where k is the average length of all the words.

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

Hi, Ravio,
Your statement is valid only if hash is O(k). I don't know that for sure.

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

for a,b,c,a,d

if
'char' not exist in hash, insert in hash as well as in new arrary/print in console
else
end

we dont need to print based on hash, but need to print based on the new array which we formed, that is in required order.

PS: question says we need to return new array.

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

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

import java.util.*;
import java.io.*;

public class prac
{
public static void main(String[] args)
{
String[] input = {"dog","dog","cat","horse","horse","cat","mouse"};

for (int i=0;i<input.length ;i++ )
{
String s = input[i];
{
}
}
System.out.println(dictset);
}
}

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

You can use a trie data structure. That is while traversing the array add the string to a trie and if that string already exists in trie then continue else you have to add the element in the trie. At last you have to traverse the trie and get all the strings from it. Advantage:
1. No key collusion as it can be there in a hash.
2. Trie can be traverses in O(m) time where m is the length if the string

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

My approach, in Objective C, uses a Set as auxiliary structure (NSMutableSet in Objective-C). Insertion and retrieval from Set in Objective-C has O(1) because a hash method is applied.
The entire solution has complexity O(n+n+n+n) = O(4n) = O(n): n iterations across the input array, in which each iteration does:
*) 1 check in the set for existence O(1).
*) 1 insertion to the set O(1).
*) 1 insertion to the destination array O(1).

Tests first:

``````#import <XCTest/XCTest.h>
#import "CSPArrayOfUniqueObjectsMaker.h"

@interface CSPArrayOfUniqueObjectsMakerTests : XCTestCase

@end

@implementation CSPArrayOfUniqueObjectsMakerTests

- (void)setUp
{
[super setUp];
// Put setup code here. This method is called before the invocation of each test method in the class.
}

- (void)tearDown
{
// Put teardown code here. This method is called after the invocation of each test method in the class.
[super tearDown];
}

- (void)testHappyPath
{
NSArray* expected = @[@2, @1, @3];
NSArray* actual = [CSPArrayOfUniqueObjectsMaker
arrayOfUniqueObjectsWithArray:@[@2, @1, @3, @1, @2]];
XCTAssertEqualObjects(expected, actual);
}

- (void)testNoDuplicates
{
NSArray* expected = @[ @"January", @"February",
@"March", @"April",
@"May", @"June",
@"July", @"August",
@"September", @"October",
@"November", @"December" ];
NSArray* actual = [CSPArrayOfUniqueObjectsMaker
arrayOfUniqueObjectsWithArray:@[ @"January", @"February",
@"March", @"April",
@"May", @"June",
@"July", @"August",
@"September", @"October",
@"November", @"December" ]];

XCTAssertEqualObjects(expected, actual);
}

- (void)testAllDuplicates
{
NSArray* expected = @[ @3.1416 ];
NSArray* actual = [CSPArrayOfUniqueObjectsMaker
arrayOfUniqueObjectsWithArray:@[ @3.1416, @3.14160,
@3.141600, @3.1416000,
@3.14160000]];

XCTAssertEqualObjects(expected, actual);
}

- (void)testEmptyArray
{
XCTAssertEqualObjects(nil, [CSPArrayOfUniqueObjectsMaker
arrayOfUniqueObjectsWithArray:nil]);

XCTAssertEqualObjects(@[], [CSPArrayOfUniqueObjectsMaker
arrayOfUniqueObjectsWithArray:@[]]);
}

- (void)testDuplicatesAlwaysTogether
{
NSArray* expected = @[ @1, @2, @3, @4, @5, @6, @7, @8, @9, @10,
@20, @21, @22, @23, @24, @25, @26, @27, @28, @29,
@11, @12, @13, @14, @15, @16, @17, @18, @19 ];
NSArray* actual = [CSPArrayOfUniqueObjectsMaker
arrayOfUniqueObjectsWithArray:
@[ @1, @1, @1, @1, @1, @1, @1, @1, @1, @1, @1, @1, @1,
@2, @2,
@3, @4, @5, @6, @7, @8, @9,
@10, @10, @10, @10,
@20, @21, @22,
@23, @23, @23, @23, @23, @23, @23, @23, @23, @23, @23,
@24, @25, @26, @27, @28, @29,
@11, @12, @13, @14,
@15, @15, @15, @15, @15, @15, @15, @15, @15, @15,
@16, @17, @18, @19 ]];

XCTAssertEqualObjects(expected, actual);
}

- (void)testDuplicatesNeverTogether
{
NSArray* expected = @[ @1, @2, @3, @4, @5, @6, @7, @8, @9, @10,
@20, @21, @22, @23, @24, @25, @26, @27, @28, @29,
@11, @12, @13, @14, @15, @16, @17, @18, @19 ];
NSArray* actual = [CSPArrayOfUniqueObjectsMaker
arrayOfUniqueObjectsWithArray:
@[ @1, @2, @3, @4, @5, @6, @7, @8, @9, @10,
@20, @21, @22, @23, @24, @25, @26, @27, @28, @29,
@11, @12, @13, @14, @15, @16, @17, @18, @19,
@1, @2, @3, @4, @5, @6, @7, @8, @9, @10,
@20, @21, @22, @23, @24, @25, @26, @27, @28, @29,
@11, @12, @13, @14, @15, @16, @17, @18, @19,
@1, @2, @3, @4, @5, @6, @7, @8, @9, @10,
@20, @21, @22, @23, @24, @25, @26, @27, @28, @29,
@11, @12, @13, @14, @15, @16, @17, @18, @19,
@1, @2, @3, @4, @5, @6, @7, @8, @9, @10,
@20, @21, @22, @23, @24, @25, @26, @27, @28, @29,
@11, @12, @13, @14, @15, @16, @17, @18, @19,
@1, @2, @3, @4, @5, @6, @7, @8, @9, @10,
@20, @21, @22, @23, @24, @25, @26, @27, @28, @29,
@11, @12, @13, @14, @15, @16, @17, @18, @19,
@1, @2, @3, @4, @5, @6, @7, @8, @9, @10,
@20, @21, @22, @23, @24, @25, @26, @27, @28, @29,
@11, @12, @13, @14, @15, @16, @17, @18, @19,
@1, @2, @3, @4, @5, @6, @7, @8, @9, @10,
@20, @21, @22, @23, @24, @25, @26, @27, @28, @29,
@11, @12, @13, @14, @15, @16, @17, @18, @19,
@1, @2, @3, @4, @5, @6, @7, @8, @9, @10,
@20, @21, @22, @23, @24, @25, @26, @27, @28, @29,
@11, @12, @13, @14, @15, @16, @17, @18, @19,
@1, @2, @3, @4, @5, @6, @7, @8, @9, @10,
@20, @21, @22, @23, @24, @25, @26, @27, @28, @29,
@11, @12, @13, @14, @15, @16, @17, @18, @19 ]];
XCTAssertEqualObjects(expected, actual);
}

@end``````

``````#import <Foundation/Foundation.h>

@interface CSPArrayOfUniqueObjectsMaker : NSObject

/**
* Receives an array, possibly with duplicated elements. Returns an array that
* keeps the order of the original array but only the first occurrence of a
* repeated element is kept.
* @param array an NSArray with possible duplicates.
* @return an array that keeps the order of elements but doesn't include the
* repeated occurrences of duplicated elements. If the input is nil, the output
* is nil as well.
*/
+ (NSArray*)arrayOfUniqueObjectsWithArray:(NSArray*)array;

@end``````

Implementation:

``````#import "CSPArrayOfUniqueObjectsMaker.h"

@implementation CSPArrayOfUniqueObjectsMaker

+ (NSArray*)arrayOfUniqueObjectsWithArray:(NSArray*)array
{
// fail fast: before null input, null answer
if (array == nil) return nil;

// this set will receive objects from the array only once: only if they
// weren't already in the set
NSMutableSet* actualObjects = [NSMutableSet set];
// this array will hold those objects from the array not found in the set
NSMutableArray* retCollection = [NSMutableArray array];

for (const id object in array) {
if (![actualObjects containsObject:object]) {
}
}

return [retCollection copy];
}

@end``````

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

man, you really should stop posting this kind of answers. It's the second answer from you of this kind. 1) here nobody is interested to see the code of your tests (mostly if they're so f*****ng long), 2) if you really have to post so long code (objective-C is frankly crap for this kind of forums) at least be so kind to think twice about your solution and try, please, to write more compact code.
It's really disturbing to be forced to scroll the page for like 3 minutes in order to skip your crap. Thank you.

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

``````Python solution

m = ['a','b','c','d','a','e','b']
n = []

for i in m:
n.append(i) if i not in n else None

print n``````

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

It works, although the complexity seems to be O(n + n*(n-1)/2) = O(n^2).
Explanation, for the original array, n iterations (a whole traversal). In each iteration, you'll have a check for existence in the destination array, which in the first iteration will have 0 elements, in iteration 2 will have 1 element, in iteration 3 will have 2 elements, and in iteration n will have n-1 elements. That checking, then, will have a complexity of O(0+1+2+...+n-1) = O((n-1)*n/2) = O(n^2).

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

``````static string[] a1(string[] a )
{
string [] result = new string[a.Length];
int resultCount = 0;
int count;
for (int i = 0; i < a.Length; i++)
{
count = 0;

for (int j = i+1; j < a.Length ; j++)
{
if (a[i] == a[j])
{
++count;
break;

}

}

if (count == 0)
{
result[resultCount] = a[i];
resultCount++;

}

}

return result;

}
}``````

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

Pythonic Way:
m = ["dog","cat","dog"]
n=[]
j = 0
for i in m:
mydict[j] = i
j++

sortedDict = sorted(mydict)

for i in sortedDict.values():
n.append(i)

The time complexity of this solution should be O(n)

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

No sorting algorithm has linear complexity O(n). Perhaps you assume that because the sorted function is given, you don't need to worry about its complexity. You must because it's your solution.

Another issue is the original order. You should keep it.

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

``````private static String[] removeDupliate(String[] str) {
List<String> list = new ArrayList<String>();
for(String d : str){
if(!list.contains(d))
}
String[] result= new String[list.size()];
int k=0;
for(String st : list){
result[k++] = st;
}
return result;
}``````

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

complexity is O(n)

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

No it is O(n^2), because of the 'If(!list.contains(d))' has to walk the array to determine the if it is contained.

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

public static String[] removeDuplicate(String[] words)
{

for(String word : words)
{
}

String[] result = new String[set.size()];
int index = 0;
Iterator<String> itr = set.iterator();

while(itr.hasNext())
{
result[index] = itr.next();
index++;
}

return result;
}

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

``````import java.util.ArrayList;

public class TestProgram {

static final String[] INPUT_ARRAY = { "dog", "cat", "dog", "fish" };

public static void main(String[] args) {
Object[] array = getDistinctArray();
System.out.print("{ ");
for (int i = 0; i < array.length; i++)
System.out.print(array[i].toString() + " ");
System.out.print(" }");
}

static Object[] getDistinctArray() {
ArrayList<String> array = new ArrayList<String>();
for (int i = 0; i < INPUT_ARRAY.length; i++) {
if (!array.contains(INPUT_ARRAY[i])) {
}
}
return array.toArray();
}
}``````

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

String[] animalArray = {"dog", "cat", "dog", "fish"};

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

Is there any restriction? I mean, is there any requirement or you can use any Foundation classes? if so, we just need NSorderedSet. complexity is not told by apple, but i would say its probably better than o(n), I would say is a o(logN)

``````NSArray *testArray = @[@"dog", @"cat", @"dog", @"fish"];

NSOrderedSet *orderedSet = [NSOrderedSet orderedSetWithArray:testArray];``````

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

we can add all the elements to a hashmap such that keys are the array elements and value is the order i.e for given example key is dog and its value is 1. After one scan the we can add the keys into an array by its values like a[1] where 1 is value for dog key .as keys cannot have duplicates we can get output

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

public string[] MakeUniqueString(string[] arr)
{

string temp=string.Empty;
Array.Sort(arr);
int j;
for(int i=0;i<arr.Length;i++)
{
temp += arr[i] + ",";
j = i + 1;
while (j < arr.Length && arr[j] == arr[i])
j++;
i = j - 1;

}
return temp.Split(',');
}

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

``````from collections import OrderedDict
print(list(OrderedDict.fromkeys(a))}
>>> ['dog', 'cat', 'fishâ€™]``````

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

``````private static String[] removeDuplicate(final String[] values)
{
final List<String> results = new ArrayList<String>(values.length);
for (int i = 0; i < values.length; ++i)
{
if (!results.contains(values[i]))
{
}
}
final String[] resultsArray = new String[results.size()];
results.toArray(resultsArray);
return resultsArray;
}``````

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

``````public static void main(String[] args){

String[] s={"cat","dog","fish","cat"};
solve(s);
}

static void solve(String[]  s){

ArrayList<String> ar =new ArrayList<>();
for(int i=0;i<s.length;i++){
if(!ar.contains(s[i]))
}

Object[] o=ar.toArray();

for(Object c:o){
System.out.println((String)c);
}
}``````

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

My C solution is
void remove_dup(char** list1, char** list2, int len)
{
int i, j, count = 0, to_add;
list2[count++] = list1[0];
for (i = 1; i < len; ++i)
{
for (j = 0; j < count; ++j)
if (0 == strcmp(list1[i], list2[j]))
{
break;
}
list2[count++] = list1[i];
}
}

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

List<String> input;

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

No one asked for an elegant and space-time saved solution.
There are two main purposes for this question:
1. Check if you can find a solution (any)
2. Check if you are understanding the complexity of your solution.

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

#include<iostream>
#include<map>
#include<string>
using namespace std;
int main()
{
char str[100][100]={"cat","cat","god","cat","dog"};
map<string,int> m;
int i;
for(i=0;i<5;i++)
m[str[i]]++;
for(i=0;i<5;i++)
{
if(m[str[i]]>0){
cout<<str[i]<<endl;
m[str[i]]=0;
}
}

}

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

Used Trie to guarantee O(kn)

class Node:
def __init__(self):
self.childs = [None for x in range(26)]
self.matchCount = 0

class CustomTrie:
def __init__(self):
self.rootNode = Node()

if(remainedStr == ""):
aNode.matchCount += 1
return (aNode.matchCount == 1)

idx = self.indexForChar(remainedStr[0])

if(aNode.childs[idx] == None):
aNode.childs[idx] = Node()

def indexForChar(self, aChar:chr):
return ord(aChar)-ord('a')

def getNoDupList(aList:list):
aTrie = CustomTrie()
resultList = []
for aWord in aList:
resultList.append(aWord)
return resultList

print(getNoDupList(['abc', 'abc', 'fea', 'ecb', 'abc', 'suv', 'fea', 'fea', 'ecb']))

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.