1. Intersection

Parameters:

input: two arrays
output: one intersection array (values in both arrays)

Example: [2,4] is the intersection of:

[1,2,3,4,5]
[0,2,4,6,8]

1.1 Naive Solution: Nested Loop - \(O(N*M)\)

arr_a = [1,2,3,4,5]
arr_b = [0,2,4,6,8]
# arr_b = [0,2,2]

intersect_list = []
for chr_a in set(arr_a):        # O(N)
    for chr_b in set(arr_b):    # multiply: O(M)
        # print(chr_a,chr_b)
        if chr_a==chr_b:        # add: O(N)
            intersect_list.append(chr_a)  # total = O(N*M + max(N,M))
            break

intersect_list

[2, 4]

1.2 Dict Solution: Nested Loop - \(O(M+N)\)

arr_a = [1,2,3,4,5]
arr_b = [0,2,4,6,8]

dct_a = {}

for chr_a in set(arr_a):
    dct_a[chr_a]=True

intersect_list = []
for chr_b in set(arr_b):    # O(N) 
    if chr_b in dct_a:      # add: O(M)
        intersect_list.append(chr_b) # O(M+N)

print(intersect_list)

[2, 4]

2. Duplicate

Parameters:

input: an array of strings
output: the first duplicate value it finds.

Example:

input: ["a", "b", "c", "d", "c", "e", "f"]
output: c

2.1 Solution: Psuedo-Code

Check if chr_a of str_a is in dct_a:

true: return chr_a
false: add to dct_a

2.2 Solution: Python-Code

# str_a = "abcdef"
# str_a = "abcdeaf"
str_a = "abcdeff"
dct_a = {}
for chr_a in str_a: #O(N)
    # print(chr_a)
    if chr_a in dct_a: #xO(1)
        print(chr_a)
        break
    else:
        dct_a[chr_a]=True

3. Missing Letter

Parameters:

input: an array of strings of alphabet except 1 letter
output: missing letter

Example:

input: "the quick brown box jumps over a lazy dog"
output: f

3.1 Solution: Python-Code

alphabet = "abcdefghijklmnopqrstuvwxyz" 

input_arr = "the quick brown box jumps over a lazy dog"
input_dct = {}
for ltr_s in set(input_arr.replace(" ", "")):
    input_dct[ltr_s]=True

for alphabet_ltr in alphabet:
    # if not input_dct.get(alphabet_ltr): 
    if alphabet_ltr not in input_dct:
        print(alphabet_ltr)
        break

4. First Non-Duplicated

Parameters:

input: an array of strings
output: first non-duplicated character in string

Example:

input: "minimum"
output: n

4.1 Solution: Psuedo-Code

A. Create letter counter dict: \(O(N)\)

for each letter of input_str, add create key and (add) value by 1

B. Find first letter with only one occurence: \(O(N)\)

for each letter of input_str, find key with value: 1

Time-complexity:

\(O(N+N)=O(2N)=O(N)\)

input_str = "minimum"
ltr_dict = {}

for ltr in input_str: # 4.1.A
    ltr_dict[ltr] = ltr_dict.get(ltr,0)+1

ctr=0
print(f"Input-string: '{input_str}'")
print(f"Letter-counter dictionary: {ltr_dict}")
for ltr in input_str: # 4.1.B
    if ltr_dict[ltr]==1:
        ctr+=1
        print(f"{ctr}: Non-duplicate: '{ltr}' in {input_str}")

Input-string: 'minimum'
Letter-counter dictionary: {'m': 3, 'i': 2, 'n': 1, 'u': 1}
1: Non-duplicate: 'n' in minimum
2: Non-duplicate: 'u' in minimum