CareerCup

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)

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

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

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();
	}
}

String[] animalArray = {"dog", "cat", "dog", "fish"};
Set<String> linkedHashSet = new LinkedHashSet<String>(Arrays.asList(animalArray));
System.out.println(linkedHashSet);

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

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(',');
}

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

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];
}
}

List<String> input;
return new ArrayList<String>(new LinkedHashSet<String>(input));

Please read question carefully.
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.

#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;
}
}

}

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']))