Python - Find the first recurring character in a list - 3 Solutions - Google Question

Google Question: Find the first recurring character in the list
Given an array = [2,5,1,2,3,5,1,2,4]:
It should return 2
Given an array = [2,1,1,2,3,5,1,2,4]:
It should return 1
Given an array = [2,3,4,5]:
It should return undefined

By using a new blank list

class Recurring:

def __init__(self, list1):

self.list1 = list1

def first_recurring(self):

print(self.list1)

list2 = []

for n in self.list1:

if n in list2:

return n

else:

list2.append(n)

return None

obj = Recurring([1,2,3,4,1,5])

print(obj.first_recurring())

OUTPUT
[1, 2, 3, 4,1]
1
BIG O
O(n^2) since we are using another list, it iterates through the list to find a value

By expanding existing list

class Recurring:

def __init__(self, list1):

self.list1 = list1

def first_recurring(self):

print(self.list1)

list1_len=len(self.list1)+1

for n in self.list1[0:list1_len]:

if n in self.list1[list1_len:]:

return n

else:

self.list1.append(n)

return None

obj = Recurring([1,2,3,4])

print(obj.first_recurring())

OUTPUT
[1, 2, 3, 4]
None
BIG O
O(n^2) since we are using another list, it iterates through the list to find a value

By checking each element with every other element in sequential order (worst method)

class Recurring:

def __init__(self, list1):

self.list1 = list1

def first_recurring(self):

print(self.list1)

for n in self.list1:

for m in self.list1[n:]:

if n == m:

return n

return None

obj = Recurring([1,2,2,3,4])

print(obj.first_recurring())

OUTPUT
[1, 2, 2, 3, 4]
2
BIG O
O(n^2)

By using Dictionary (Hash Table)

class Recurring:

def __init__(self, list1):

self.list1 = list1

def first_recurring(self):

print(self.list1)

dict1 = {}

i = 0

for n in self.list1:

if n in dict1.values():

return n

else:

i += 1

dict1[i] = n

return None

obj = Recurring([1,2,3,4,4])

print(obj.first_recurring())

OUTPUT
[1, 2, 2, 3, 1, 4, 4]
2
BIG O
O(n) since dictionaries are hash tables and the program doesn't iterate through it but finds the value directly using hash values. This is the most efficient way. BUT, this will give wrong answer in some cases. Like in the case used in the example. 1 is repeated too, but later, so it returns 2 which is repeated first.
By using Dictionary (Hash Table) in such a way that program returns first character that would be repeated

class Recurring:

def __init__(self, list1):

self.list1 = list1

def first_recurring(self):

print(self.list1)

dict1 = {}

i = 0

for n in self.list1:

i += 1

dict1[i] = n

for j in self.list1:

if j in dict1.values():

return j

return None

obj = Recurring([1,2,2,3,1,4,4])

print(obj.first_recurring())

OUTPUT
[1, 2, 2, 3, 1, 4, 4]
1
BIG O
O(n)