CS Mumbai

Today let’s look at a python program that will help us check whether there’s a cycle in a given linked list.

The above example illustrates a cycle in Linked List. The best way to check whether it has a cycle is to have two markers (or runners).

The first runner takes one step at a time. The second one takes two steps at a time. With this setup, if there is a cycle, both runners will come to the same place eventually.

You can imagine this happening for runners running around a lake with one person running slow and the other one running fast. The faster runner will eventually complete a round and pass by the slower runner. If this happens, we know there is a cycle.

The code below does exactly that by using two markers.

# Problem: Finding cycle in linked list
# Logic: Maintain two markers, one that moves 2 steps faster
# If markers meet at the end, there's a cycle

def cycle_check(node):
    
    marker1 = node
    marker2 = node
    
    while marker2 != None and marker2.next != None:
        
        marker1 = marker1.next
        marker2 = marker2.next.next
        
        if marker2 == marker1:
            return True
        
    return False

# Testing the result

a = Node(1)
b = Node(2)
c = Node(3)
d = Node(4)

a.next = b
b.next = c
c.next = d
d.next = c

cycle_check(a)

Since we’re making marker2 take two steps at a time, we want to run the while loop till marker2’s current value and its next value doesn’t equal to None. If it is, we stop and return False.

Today let’s look at a bracket validator program. This will accept an input string that contains a bunch of brackets. It’ll check whether they are correctly opened and closed (in the right order).

The examples below will give a better idea of valid and invalid inputs:

s1 = ['(((}})))']
bracket_validator(s1) # returns False

s2 = '[](([[{{}}]]))'
bracket_validator(s2) # returns True

Now let’s have a look at the code:

# Problem: Bracket validator (balanced vs unbalanced) (using Stack)

def bracket_validator(s):
    
    if len(s)%2 != 0:
        return False
    
    openers_to_closers = {
        '(' : ')',
        '{' : '}',
        '[' : ']'
    }
    
    openers = openers_to_closers.keys()
    closers = openers_to_closers.values()
    
    openers_stack = []
    
    for char in s:
        
        if char in openers:
            openers_stack.append(char)
        elif char in closers:
            if not openers_stack:
                return False
            else:
                last_unclosed_opener = openers_stack.pop()
                if openers_to_closers[last_unclosed_opener] != char:
                    return False
    
    if len(openers_stack) == 0:
        return True
        

s1 = ['(((}})))']
bracket_validator(s1) # returns False

s2 = '[](([[{{}}]]))'
bracket_validator(s2) # returns True

The very first thing we do is check the input is odd or even in length. If it is odd, return False.

Next we maintain a dictionary of openers to closers and turn those into sets of openers and closers. We also maintain a openers_stack as a list.

We then run a for loop going through each character in the input string. If the character is in opener, add it to the openers stack.

If we find a closer and openers stack doesn’t is empty, return False. If openers stack is not empty, pop the top element from the openers stack and check whether our current closer is the correct closing pair for the top element in the stack (last unclosed opener).

For example, if our closer is ] and the last unclosed opener is [ then we’re good. If not, we return False.

At the very end if length of openers_stack is zero, return True.

Today I’m sharing a simple python program that accepts an input string and reverses it.

def reverse_word(word):
    
    letters = list(word)
    start = 0
    end = len(letters)-1
    
    while start < end:
        letters[start], letters[end] = letters[end], letters[start]
        start+=1
        end-=1
        
    return ''.join(letters)

reverse_word('Nice work') #output: krow eciN

The program starts by accepting a string word, converts it to a list type in letters, sets the start to 0 and end index to length of the input string minus one.

Next a while loop runs from while start and end pointers don’t cross each other. In each iteration, we swap the characters at start and end index and also increment and decrement the start and end pointers respectively.

The end result gets us a reversed version of input string. For example: “Nice work” gets turned into “krow eciN”.

In one of the next posts I’ll write about “sentence” reversal. For example: “Nice work” will be turned into “work Nice”.

Here’s Google’s definition of an Anagram: a word, phrase, or name formed by rearranging the letters of another, such as spar, formed from rasp.

Let’s see how we can write a program in Python to check whether the given input strings s1 and s2 are anagrams of each other.

def anagram1(s1, s2):
    
    # remove spaces and lowercase every letter
    s1 = s1.replace(' ', '').lower()
    s2 = s2.replace(' ', '').lower()
    
    return sorted(s1) == sorted(s2)

anagram1('clint eastwood', 'old west action') # True

That’s done using in-built python functions called replace, lower and sorted where we replace all the spaces with nothing and transform the strings to lowercase before comparing them to each other using the “sorted” function.

That works just fine but let’s see how we can do this manually without using the “sorted” in-built function.

def anagram2(s1, s2):
    
    # remove spaces and lowercase every letter
    s1 = s1.replace(' ', '').lower()
    s2 = s2.replace(' ', '').lower()
    
    # Edge case check
    if len(s1) != len(s2):
        return False
    
    # maintain a dict of letters
    # and count occurrence of each letter
    
    count = {}
    
    for letter in s1:
        if letter in count:
            count[letter] += 1
        else:
            count[letter] = 1
    
    for letter in s2:
        if letter in count:
            count[letter] -= 1
        else:
            count[letter] = 1
            
    for letter in count:
        if count[letter] != 0:
            return False
    
    return True

anagram2('clint eastwood', 'old west action') # True

Here we replace spaces and transform the strings to lower case (same as before). Next we run an edge case check to see if length of those strings are not equal. If they aren’t, we stop!

If they are equal, we use dictionary to track the count of each letter. When we check the first string, we increment the count. When we check the second string, we decrement it.

Finally we check if count isn’t zero. If it isn’t, we stop. Else we return True. And that is how we check for Anagrams manually 🙂

Before going to the recursive solution, let’s check the iterative one given below:

def fibo(n):
 
	prev = 0
	current = 1
	result = 0
 
	while result <= n:
 
		result = prev+current
		prev = current
		current = result
 
	return result
 
print(fibo(5))

Here’s a hand drawn explanation of how the Fibonacci numbers are calculated:

This makes us store the last two values as prev and current to calculate the current result. After which we will move prev and current or update them to calculate the next result.

Now here’s the recursive solution:

def fibo(n):
 
	if n==0 or n==1:
		return n
 
	return fibo(n-1) + fibo(n-2)
 
print(fibo(7))

It will print the 7th Fibonacci number as follows:

The problem with recursive solution is that it gets huge and repeats itself as follows:

The time spent on calls in the highlighted area can be saved by storing the results and then returning the stored results instead of calculating them again. This is called Memoization.

Here’s memoized recursive solution for Fibonacci:

class Fibrec:
 
	def __init__(self):
		self.memo = {} #creates dict 
 
	def fibo(self, n):
 
		if n < 0: raise ValueError("incorrect value")
 
		elif n in [0,1]: 
			return n
 
		if n in self.memo:
			return self.memo[n]
 
		result = self.fibo(n-1) + self.fibo(n-2)
 
		self.memo[n] = result # store result in dict
 
		return result
 
f = Fibrec()
print(f.fibo(8)) # prints 21

That’s all in this post 🙂

Here’s a simple code for checking if a given number is prime:

def isPrime(n):
 
	for i in range(2, n):
		if n%i == 0:
			return False
	return True
 
print(isPrime(2)) # true
print(isPrime(3)) # true
print(isPrime(11)) # true
print(isPrime(8)) # false

For the input 2 you may be wondering how it returns True. This is because we never enter the for loop for that input. Notice the range becomes 2,2. Since the range goes from “first argument” to “second argument – 1”, it will go from 2 to 1 which doesn’t make sense. Which is why we never enter the for loop.

It has a worst case complexity of O(n) because the for loop will run from 2 to n in worst case.

Can we do better than that? Yes, we can. We only need to check till square root of the given number. Using this logic we re-write the code as follows:

import math
 
def isPrime2(n):
 
	n2 = int(math.sqrt(n))
 
	for i in range(2,n2+1):
		if n%i == 0:
			return False
	return True
 
print(isPrime2(2)) # true
print(isPrime2(3)) # true
print(isPrime2(8)) # false

You may be wondering why we changed the range to (2,n2+1). This is because if we were to use (2,n), the input 8 wouldn’t return the correct result.

The square root of 8 is 2.82 but it would be returned as 2. The for loop would not be entered in this case and the output would be True which is incorrect for input 8. This is fixed by making it n2+1.

The worst case time complexity here would be O(sqrt(n)).

Today I want to share a cool thing that you can install on your computer that can help you write documents with live code. It’s called Jupyter Notebook.

I discovered it while I was watching a Python tutorial on Udemy. Since then I have always used it to jot down study notes and keep them all in one place.

My previous approach was to write in-line comments in my code. It worked but it was very limiting. With Jupyter Notebook, I can write rich text just like Google docs but with the ability to embed live code and see its output.

Here’s an example of what that looks like:

I, of course, use it very naively. There’s a lot more that can be done and you can read all about it at https://jupyter.org/

If you’re interested, you can get it from here. Once installed, it can be run via terminal by typing in jupyter notebook. That’s it! 🙂