Facebook Interview Question
Software Engineer / DevelopersTeam: iOS
Country: United States
Interview Type: In-Person
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.
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.
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
'char' exist in hash, skip to next element in array.
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.
import java.util.*;
import java.io.*;
public class prac
{
public static void main(String[] args)
{
String[] input = {"dog","dog","cat","horse","horse","cat","mouse"};
LinkedHashSet dictset = new LinkedHashSet();
for (int i=0;i<input.length ;i++ )
{
String s = input[i];
if(dictset.add(s))
{
dictset.add(s);
}
}
System.out.println(dictset);
}
}
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
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 access to the original array O(1).
*) 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
Header:
#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]) {
[retCollection addObject:object];
[actualObjects addObject:object];
}
}
return [retCollection copy];
}
@end
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.
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
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).
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;
}
}
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)
private static String[] removeDupliate(String[] str) {
List<String> list = new ArrayList<String>();
for(String d : str){
if(!list.contains(d))
list.add(d);
}
String[] result= new String[list.size()];
int k=0;
for(String st : list){
result[k++] = st;
}
return result;
}
public static String[] removeDuplicate(String[] words)
{
Set<String> set = new LinkedHashSet<String>();
for(String word : words)
{
set.add(word);
}
String[] result = new String[set.size()];
int index = 0;
Iterator<String> itr = set.iterator();
while(itr.hasNext())
{
result[index] = itr.next();
index++;
}
return result;
}
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])) {
array.add(INPUT_ARRAY[i]);
}
}
return array.toArray();
}
}
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];
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
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]))
{
results.add(values[i]);
}
}
final String[] resultsArray = new String[results.size()];
results.toArray(resultsArray);
return resultsArray;
}
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]))
ar.add(s[i]);
}
Object[] o=ar.toArray();
for(Object c:o){
System.out.println((String)c);
}
}
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)
{
to_add = 1;
for (j = 0; j < count; ++j)
if (0 == strcmp(list1[i], list2[j]))
{
to_add = 0;
break;
}
if (to_add)
list2[count++] = list1[i];
}
}
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()
def addStringIfNotExist(self, aNode:Node, remainedStr:str):
if(remainedStr == ""):
aNode.matchCount += 1
return (aNode.matchCount == 1)
idx = self.indexForChar(remainedStr[0])
if(aNode.childs[idx] == None):
aNode.childs[idx] = Node()
return self.addStringIfNotExist(aNode.childs[idx], remainedStr[1:])
def indexForChar(self, aChar:chr):
return ord(aChar)-ord('a')
def getNoDupList(aList:list):
aTrie = CustomTrie()
resultList = []
for aWord in aList:
if(aTrie.addStringIfNotExist(aTrie.rootNode, aWord) == True):
resultList.append(aWord)
return resultList
print(getNoDupList(['abc', 'abc', 'fea', 'ecb', 'abc', 'suv', 'fea', 'fea', 'ecb']))
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.
- teli.vaibhav June 06, 2014Time Complexity: O(n)
Space Complexity: O(n)