Month: January 2020

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! 🙂

BFS and DFS are two different ways you can traverse a Tree. BFS is Breadth First Search and DFS is Depth First Search.

To explain this further, consider the following tree:

You can see how BFS traversal works there. Also, you see there are three ways to do DFS traversal:

• pre-order
• in-order
• and post-order.

Depth First Search

class BTnode:
 
	def __init__(self, value):
		self.value = value
		self.left = None
		self.right = None
 
def DFS(node):
	#left
	if node.left:
		DFS(node.left)
	#right
	if node.right:
		DFS(node.right)
	#root
	print(node.value, end=' ') # no new line after print
 
b = BTnode(1)
b.left = BTnode(2)
b.right = BTnode(3)
b.left.left = BTnode(4)
b.left.right = BTnode(5)
b.right.left = BTnode(6)
b.right.right = BTnode(7)
 
DFS(b)
print() #manually adding new line after result

The order of left, right and root can be changed there to convert that into pre-order and in-order.

Breadth First Search

class Queue:
	def __init__(self):
		self.items = []
 
	def put(self, item):
		self.items.append(item)
 
	def get(self):
		if self.items:
			return self.items.pop(0)
 
	def isEmpty(self):
		return self.items == []
 
class BTnode:
 
	def __init__(self, value):
		self.value = value
		self.left = None
		self.right = None
 
def BFS(node):
	q = Queue()
	q.put(node) #enqueue
 
	while not q.isEmpty():
		current = q.get() #dequeue
		print(current.value, end=' ') #prints without adding new line
 
		if current.left:
			q.put(current.left)
		if current.right:
			q.put(current.right)
 
b = BTnode(1)
b.left = BTnode(2)
b.right = BTnode(3)
b.left.left = BTnode(4)
b.left.right = BTnode(5)
b.right.left = BTnode(6)
b.right.right = BTnode(7)
 
BFS(b)
print() #manually adding new line after result

We’ve used a Queue there to implement BFS. Here’s how it works:

1. Add 1
2. Pop 1 and add it’s children 2 and 3
3. Pop 2 and add it’s children 4 and 5
4. Pop 3 and add it’s children 6 and 7
5. Pop all other items (as none have children)

This is illustrated in the image below:

That’s all in this post! 🙂

This is a short post to share python implementation of binary search. What’s binary search you ask? It’s simple.

Imagine you have a list of numbers and you want to check if a particular number exists in it. Normally you’d search it one by one. That’s fine and this approach is called linear search.

The problem with linear search is that if the list of numbers is 1 million, it will take 1 million checks before we can confidently say whether the number exists in it or it doesn’t.

That’s where binary search is helpful. But in order for binary search to work, the list must be sorted.

In binary search, you look at the middle element of a sorted list and see if it is equal to the number we are looking for. If it isn’t, we only look at the first half of the list or the second half. Reducing the list in half at each check.

Thus, if the length of the list is N, binary search will take O(log N) time whereas linear search takes O(N).

Here’s python implementation of binary search:

def binary_search(arr, item):
 
	l = 0
	r = len(arr)-1
 
	while l<=r:
 
		mid = l + (r-l)//2
 
		if item == arr[mid]:
			return True
 
		elif item < arr[mid]:
			r = mid-1
 
		else:
			l = mid+1
 
	return False
 
 
#testing
arr = [2,5,6,9,11,15,18,20]
print(binary_search(arr, 1)) # prints False
print(binary_search(arr, 21)) # prints False
print(binary_search(arr, 20)) # prints True
print(binary_search(arr, 2)) # prints True
print(binary_search(arr, 11)) # prints True

Highlighted lines are really important to remember. We usually make mistakes there. For example, forgetting to return False if we don’t find the item in the given list.

Also, the explanation for mid = r - (r-l)//2 can be found here in a Stack Overflow post which is funny because it is an overflow related issue. This is also addressed in a Google blog here.

The code given below will reverse a Linked List in place. In place means we won’t need additional space for reversing this list.

This will however destroy or modify our original list (so keep this in mind when you’re doing an in-place operation on a given input).

Ok so here’s the code to reverse a given Linked List:

class Node:
	
	def __init__(self, data):
		self.value = data
		self.next = None
 
def reverse_list(head):
 
	current = head
	previous = None
	nextnode = None
 
	while current:
 
		nextnode = current.next
		current.next = previous
 
		previous = current
		current = nextnode
 
	return previous
 
def print_list(head):
	p = head
	while p:
		print(p.value)
		p = p.next
 
# testing
a = Node(1)
b = Node(2)
c = Node(3)
 
a.next = b
b.next = c
 
print_list(a)
newhead = reverse_list(a)
print('after reversing: ')
print_list(newhead)
 
# output
# 1
# 2
# 3
# after reversing: 
# 3
# 2
# 1

The trick here is to maintain three pointers: current, previous, nextnode

And the process can be visualized on paper as follows:

That’s all in this post. Thanks for reading! 🙂

In arrays the size is fixed. This is why we need to know the upper limit of elements we can add.

If we have to add more than that, we’ll need to copy the elements from first array into a bigger array. This resizing of array is expensive.

As an alternative, we can use a Linked List. Here each node can stay anywhere in memory. The items/nodes need not be consecutive because each item/node holds a pointer to the next one. The image below illustrates my point:

To implement such a structure, we’ll make use of something called Node which can be a data structure in its own separate class. Then we’ll use LinkedList class which will set the head and have insert and remove functions.

Here’s how you can visualize a Linked List:

And here’s the full Python implementation:

class Node:
	def __init__(self, data):
		self.value = data
		self.next = None
 
class LinkedList:
	def __init__(self, data=None):
		self.head = data
 
	def printlist(self):
		p = self.head
 
		while p:
			print(p.value)
			p = p.next
 
	def insert(self, data):
		newnode = Node(data)
		newnode.next = self.head
		self.head = newnode
 
	def remove(self, data):
 
		p = self.head
		found = False
 
		if not p:
			return 'Empty List'
 
		if p.value == data:
			self.head = p.next
 
		while p.next:
 
			if p.next.value == data:
				p.next = p.next.next
				found = True
				break
			else: 
				p = p.next
 
		return found
 
# testing
l = LinkedList()
l.insert(1)
l.insert(2)
l.insert(3)
 
l.printlist()
 
for i in range(4):
	item = i+1
	print(l.remove(item))
 
# output:
# 3
# 2
# 1
# True
# True
# False
# Empty List

The code is again self explanatory. But to give you something to visualize, here’s the insertion of item 4 on paper:

And here’s the removal of 2 on paper:

That’s all in this post! 

In this post, let’s have a look at bitwise XOR, bitwise AND and a program that calculates number of 1’s in a given integer’s binary form.

Here’s XOR ^ and AND & operations table:

1. bitwise XOR will return 0 if inputs are same, else it’ll return 1
2. bitwise AND will return 1 if both inputs are 1

Now look at the magic in the code below. To be specific, check out the highlighted line:

def count_ones(z):
 
	count = 0
 
	while z:
		print(z, bin(z))
		count += 1
		z = z & (z-1)
 
	return count
 
print('The number of 1s in 5: ', count_ones(5))
print()
print('The number of 1s in 28: ', count_ones(28))
 
#output
 
# 5 0b101
# 4 0b100
# The number of 1s in 5:  2
 
# 28 0b11100
# 24 0b11000
# 16 0b10000
# The number of 1s in 28:  3

The code above takes an integer, finds out how many 1s are there in its binary form and returns the number of 1s.

This is done using z = z & (z-1) which basically removes the rightmost one from the integer’s binary form.

For example, 28 can be written as 11100. It turns into 11000 in the first pass. 10000 in the second and 00000 in the third pass. Then the loop stops to return the count which is 3.

This can be very useful in calculating hamming distance. What is hamming distance you say? Here’s a quote from Wikipedia:

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

For example, the hamming distance between 1 and 4 is 2:

The simple logic to calculate this is to use bitwise XOR there. In this case 1 ^ 4 will return 5 which is 101 in binary. It has 2 ones in it.

How do we find these 2 ones in there using code? We combine bitwise XOR with bitwise AND as follows:

def hamming(x,y):
 
	count = 0
	z = x ^ y
 
	while z:
		print(z, bin(z))
		count += 1
		z = z & (z-1)
 
 
	return count
 
print(hamming(1,4))
 
#output
# 5 0b101
# 4 0b100
# 2

This is pretty cool right? That’s all I have in this post. See you tomorrow with another interesting CS concept. Thanks for reading!