Skip to main content

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)

Comments

Popular posts from this blog

Python - Mathematical Functions - Hexadecimal, Binary, Exponential, Absolute, Round

🐍 Some mathematical functions are in-built in python. Here are some of them. Convert Decimal to Hexadecimal hex(246) Output: '0xf6' hex(512) Output: '0x200' 0x is prefix to all hexadecimal numbers in output. The number after 0x is the hexadecimal value. Convert Decimal to Binary bin(1234) Output: '0b10011010010' bin(246) Output: '0b11110110' bin(512) Output: '0b1000000000' Exponential Function pow() function is similar to num1**num2, but it comes useful when you want to execute (num1**num2)%num3. Passing three arguments to pow(), does this. pow(3,4) Output: 81 This works just like 3**4 pow(3,4,5) Output: 1 But this, works equivalent to (3**4)%5. Either of the two ways can be used. At this point I feel (3**4)%5 is better, as anybody reading the code will understand what is being done immediately. While with pow(2,3,4), the person may have to refer to documentation to understand how this function works. Absolute Value The function abs() is used ...

Two Ways of rendering in React Examples

Two Ways of rendering in React Examples 1 - Render twice HTML < div id = "p1" ></ div > < div id = "p2" ></ div > CSS . person { display : inline - block ; margin : 10px ; border : 1px solid # eee ; box - shadow : 0 2px 2px # ccc ; } JAVASCRIPT (Babel) function Person ( props ) { return ( < div className = ' person "> < h1 >{ props . name }</ h1 > < p > Age :{ props . age }</ p > </ div > ); } ReactDOM . render (< Person name = "VK" age = "29" />, document . querySselector ( '#p1' )); ReactDOM . render (< Person name = "HK" age = "28" />, document . querySselector ( '#p2' )); 2 Render all at once HTML < div id = "app" ></ div > CSS . person { display : inline - block ; margin : 1...

Binary Tree Traversal in Python - In Order, Pre Order, Post Order

Binary Tree Traversal in Python - In Order, Pre Order, Post Order Run the code here to see output:  https://repl.it/@VinitKhandelwal/iterative-traversal-of-binary-tree # Node Class to Create Object of Nodes class Node (): def __init__ ( self , value , left= None , right= None ): self .value = value self .left = left self .right = right # Creation of a Binary Tree class BinaryTree (): def __init__ ( self , mylist ): self .mylist = mylist self .root=Node ( None ) for value in self .mylist : self .curr= self .root self ._add ( value ) def _add ( self , value ): if self .curr.value == None : self .curr.value = value else : if self .curr.value > value : if self .curr.left == None : self .curr.left = Node ( value ) else : self .curr = self .curr.left self ._add ( value ) else : if self...