0

Topological Sort

Sometimes you might need to traverse the graph in a bit different way. (not DFS or BFS)

Suppose each tree node represent a course. Each course has some prerequisites .

Eg: For taking Android course you need to have taken Java course.

If you want to print the dependency of all nodes in sequential way, you can perform `Topological sort`.

         /- Algorithms \
 Maths ->                \-> Java -> Android developement
         \- Datastructure/

We can traverse in Maths, Algo, DS, Java, Android dev.

Concept:
Similar to Depth first search, we add a node to the output list only after we have traversed through all it’s childrens.
Note: Such a sorting is not possible if the graph cyclic. (Deadlock).

Here is the python implementation:

'''
Topological Sort
'''

from collections import deque
from collections import defaultdict

def topo_sort(adj_list, nodes):
	visited = set()
	stack = deque()
	for each_node in range(nodes):
		if each_node not in visited:
			dfs_search(each_node, visited, stack, adj_list)

	return list(stack) 

def dfs_search(current_node,visited, stack, adj_list):
	visited.add(current_node)

	for each_neighbour in adj_list[current_node]:
		if each_neighbour not in visited:
			dfs_search(each_neighbour, visited, stack, adj_list)

	stack.appendleft(current_node)

class Graph:
    def __init__(self,vertices):
        self.graph = defaultdict(list)
        self.V = vertices 

    def addEdge(self,u,v):
        self.graph[u].append(v)

g = Graph(6)
g.addEdge(5, 2);
g.addEdge(5, 0);
g.addEdge(4, 0);
g.addEdge(4, 1);
g.addEdge(2, 3);
g.addEdge(3, 1);

print topo_sort(g.graph, g.V)
0

Merge Sort

Concept: Divide and conquer using PMI.

Assume we have  a magical function merge_sort(arr, i, j) which sorts array from i index to j index.

If we call merge_sort(arr, i, (i + j)/2) : This will sort left half of the array.

If we call merge_sort(arr, (i+j)/2 + 1, j) : This will sort the right half of the array.

 

Now we have array sorted from i to (i+j)/2 and (i+j)/2 + 1 to j.

We can merge both array in O(n) time and space.

 

Here is the simple implementation in Python.

 

def merge_sort(arr, l, r):
	if l < r:
		mid = (l + r) /2 

		merge_sort(arr, l, mid)
		merge_sort(arr,mid + 1, r)
		merge(arr, l, mid, r)


def merge(arr, l, m, r):
	temp = []

	i = l
	j = m+1
	index = l

	while i <=m and j <= r:
		if arr[i] < arr[j]:
			temp.append(arr[i])
			i += 1
		else:
			temp.append(arr[j])
			j += 1
		index += 1

	temp.extend(arr[i:m+1])
	temp.extend(arr[j:r+1])

	arr[l:r + 1] = temp	

arr = [5,6,2,1,0]

merge_sort(arr, 0, len(arr) - 1)
print arr 

 

0

Roman to Integer

Let’s say that the given roman number is roman = 'ABC' where A is a variable for some integer. Eg: X -> 10, M -> 1000.

The algorithm to calculate integer value is pretty simple. Lets start parsing it from the left (index = 0).

if roman[index + 1] > roman[index]:

add the value roman[index+1] – roman[index] and move ahead by 2 indices.

else:

Just add the numeric value of roman[index] to the result.

Here is the code:


hash_map = {'X':10,'I':1,'V':5,'L':50,'C':100,'D':500,'M':1000}
sample_input = 'MXI'
def roman_to_integer(A, hash_map):
	i = 0
	result = 0
	while i < len(A):

		if i + 1  hash_map[A[i]]:
			result += hash_map[A[i+1]] - hash_map[A[i]]
			i+=2
		else:
			result += hash_map[A[i]]
			i+=1

	return result
print roman_to_integer(sample_input, hash_map)
0

Tries

They can be used to store words and search for words with prefix.

It’s basically a n-ary tree. Each node contains two attribute.
1. isEnd (boolean) : marks if it’s the end of the word.
2. links (list): List of all n nodes it’s connected to.

search_prefix() function is interesting. This is how it works:

1. Iterate through all the nodes of prefix characters.

2. Start DFS search from the next node and keep track of the characters you are traversing through. When you reach the end of the word (`isEnd == True`), add it to the output list.


class Trie:
	def __init__(self):
		self.root = Node()

	def add_word(self, word):
		current_node = self.root 

		for each_char in word:
			if current_node.has_char(each_char) == False:
				current_node.create_link(each_char)
			current_node = current_node.get_link(each_char)

		current_node.is_end = True	

	def search_word(self, word):
		current_node = self.root
		for each_char in word:
			if current_node.has_char(each_char) == False:
				return False
			current_node = current_node.get_link(each_char)
		if current_node.is_end == True:
			return True

		return False

	def search_prefix(self, prefix):
		current_node = self.root
		for each_char in prefix:
			current_node = current_node.get_link(each_char)
		output = []
		self._dfs_search(prefix, current_node, '', output)
		return output

	def _dfs_search(self, prefix, current_node, current_word, output):
		if current_node.is_end:
			output.append(prefix + current_word )
		if current_node == None:
			return 

		for i, each_link in enumerate(current_node.links):
			if each_link != None:
				self._dfs_search(prefix, each_link , current_word + chr(ord('a') + i), output)

my_trie = Trie()
my_trie.add_word('yask')
my_trie.add_word('yak')
my_trie.add_word('alan')

print my_trie.search_prefix('ya')