given an array of words, how to eliminate the duplicates?

You have a simple tree structure Ⓐ and its clone ⓐ.

Each node in the tree has a pointer to it's parent as well as an array of its children.

Given an original tree's node Ⓑ and cloned tree ⓐ, implement a method that returns ⓑ (the clone of Ⓑ).
(Imagine finding the matching UIButton/UISlider/UIView in a separate cloned view controller.)

Original
Ⓐ
┏━┻━━┓
◯ ◯
┏┻┓ ┏━╋━┓
◯ ◯ ◯ ◯ ◯
┏┻┓ ┃
◯ Ⓑ ◯

Clone
ⓐ
┏━┻━━┓
◯ ◯
┏┻┓ ┏━╋━┓
◯ ◯ ◯ ◯ ◯
┏┻┓ ┃
◯ ⓑ ◯

Question

given an array of words, how to eliminate the duplicates?

You have a simple tree structure Ⓐ and its clone ⓐ.

Each node in the tree has a pointer to it's parent as well as an array of its children.

Given an original tree's node Ⓑ and cloned tree ⓐ, implement a method that returns ⓑ (the clone of Ⓑ).
(Imagine finding the matching UIButton/UISlider/UIView in a separate cloned view controller.)

  Original
    Ⓐ
  ┏━┻━━┓
  ◯    ◯
 ┏┻┓ ┏━╋━┓
 ◯ ◯ ◯ ◯ ◯
  ┏┻┓  ┃
  ◯ Ⓑ  ◯

   Clone
     ⓐ
   ┏━┻━━┓
   ◯    ◯
  ┏┻┓ ┏━╋━┓
  ◯ ◯ ◯ ◯ ◯
   ┏┻┓  ┃
   ◯ ⓑ  ◯

Alex · Accepted Answer

Since nobody answered regarding the UiView tree question, posting my solution that I finished only after the interview:

-(void)originalInput
{
  
  UIView *B = [UIView someViewWithParentAndChildren];    //known subview
  UIView *a = [UIView someViewWithParentAndChildren];    //root of clone view tree
   
  NSMutableArray *indexPaths = [NSMutableArray new];
  
  [self recordIndexPaths:indexPaths fromView:B];    //creating index array
  
  UIView *cloneViewB = [self findViewByIndexes:indexPaths forIndex:0 forView:a];      //recursing through the clone view hierarchy 
  
  NSLog(@"%@", cloneViewB);
}  
  
-(void)recordIndexPaths:(NSMutableArray *)indexPaths fromView:(UIView *)view
{
  if (view.parent == nil){
    return; 
  }else {
    UIView *parent = view.parent;
    int i = [parent.children indexOfObject:view];
    [indexPaths insertObject:i atIndex:0];  //i is not and object, but primitive, should be incapsulated in NSNumber in real life!!
    [self recordIndexPaths:indexPaths fromView:parent];
  }
}
  
-(UIView *)findViewByIndexes:(NSArray *)indexPaths forIndex:(int)i forView:(UIView *)currentView
{
  if (!currentView.children.count) return currentView;
    
  int j = indexPaths[i];  //j is not and object, but primitive, should be incapsulated in NSNumber in real life!!

  UIView *child = currentView.children[j];
  return [self findViewByIndexes:indexPaths forIndex:i+1 forView:child];

}

Carlos Carvalho · Answer

// We just need to find the path to the main top superview on the original view, saving the index of each view based on its superview and then reverse the path and search on the cloned view.


func findView(_ view: UIView, in clonedView: UIView) {
    var path = [Int]()
    var view: UIView? = view
    while view != nil {
        let tmp = view!
        view = view!.superview
        if let idx = view?.subviews.index(of: tmp) {
            path.append(idx)
        }
    }
    
    view = clonedView
    for idx in path.reversed() {
        view = view?.subviews[idx]
    }
    print("Cloned view is: \(view!.tag)")
}

Carlos Carvalho · Answer

func removeDups(words: [String], caseSensitive: Bool = false) -> [String] {
  var hashtable = Dictionary()
  var words2 = [String]()
  
  for word in words {
    let hash =  (caseSensitive ? word : word.uppercased()).hashValue
    hashtable[hash] = (hashtable[hash] ?? 0) + 1
    if hashtable[hash] == 1 {
      words2.append(word)
    }
  }
  
  return words2
}

Anonymous · Answer

I wrote down two different approaches.

NSSet (which doesn't allow duplicate entries, but this also depends on if the implementation is looking at the address of the object or at the contents of the object)

and then using a NSDictionary approach:

    NSMutableDictionary *wordDict = [[NSMutableDictionary alloc] oinit];

    for (eachString in wordArray) {
       NSNumber *numberOfWords = [wordDict objectForKey:eachString];
       if numberOfWords {
           numberOfWords = [NSNumber numberWithInteger: numberOfWords.integerValue+1];
       } else {
           numberOfWords = [NSNumber numberWithInteger:1];
       }
       [wordDict setObject: numberOfWords forKey: eachString];
    }

    return([wordDict allKeys]);
}

I'm guessing I got dinged on the NSDictionary approach because I'm *counting* duplicate entries even though the ultimate result is a unique, non-duplicated set of words.

The answer the interviewer may have been looking for probably involved hashing the word array.

Jeff · Answer

I came up with two interesting solutions (in Swift):

1) Using a set like you mentioned: 

let uniqueWords = Set(["one", "two", "one"])

2) Sorting the strings, then using "reduce" to compare the current value to the last value. I tried to combine this into one line using a ternary operator, but sadly, the compiler complained:

let uniqueWords: [String] = ["one", "two", "one"].sort().reduce([]) {
    if $1 == $0.last {
        return $0
    }
    else {
        return $0 + [$1]
    }
}

Martin Stoufer · Answer

Destroying order:
void dupeStringNoOrder()
{
    NSMutableArray *words = [NSMutableArray arrayWithArray:@[@"one", @"two", @"three", @"dog", @"cat", @"one", @"fox", @"dog", @"One", @"one"]];

    [words sortUsingComparator:^NSComparisonResult(id  _Nonnull obj1, id  _Nonnull obj2) {
        return [obj1 compare:obj2 options:NSLiteralSearch];
    }];

    for (int x=0; x *wordDict = [NSMutableDictionary dictionaryWithCapacity:words.count];
    NSMutableIndexSet *dupes = [NSMutableIndexSet indexSet];

    int index = 0;
    for (NSString *word in words) {
        if (!wordDict[word]) {
            wordDict[word] = @(1);
        } else {
            [dupes addIndex:index];
        }
        index++;
    }
    
    [words removeObjectsAtIndexes:dupes];
    
    NSLog(@"%@", words);
}

Martin Stoufer · Answer

Preserving order:
void dupeStringOrder()
{
    NSMutableArray *words = [NSMutableArray arrayWithArray:@[@"one", @"two", @"three", @"dog", @"cat", @"one", @"fox", @"dog", @"One", @"one"]];
    NSMutableDictionary *wordDict = [NSMutableDictionary dictionaryWithCapacity:words.count];
    NSMutableIndexSet *dupes = [NSMutableIndexSet indexSet];

    int index = 0;
    for (NSString *word in words) {
        if (!wordDict[word]) {
            wordDict[word] = @(1);
        } else {
            [dupes addIndex:index];
        }
        index++;
    }
    
    [words removeObjectsAtIndexes:dupes];
    
    NSLog(@"%@", words);
}

Aviram Ben Moshe · Answer

While I agree that the interviewer probably hoped for a NSDictionary-based solution, it's worth mentioning that you could also do it with key-value coding:

NSArray *originalArray = @[@"hello", @"world", @"yes", @"yes", @"hello"] ;
NSArray *uniqueArray = [originalArray valueForKeyPath:@"@distinctUnionOfObjects.self"];
    NSLog(@"%@", [uniqueArray componentsJoinedByString:@", "]); // will print hello, yes, world

Meta

Meta interview question

Interview Answers

Followed companies

Job searches

Bowls

Want the inside scoop on your own company?