# Unique Characters

Problem: Implement an algorithm to determine if a string has all unique characters. What if you cannot use additional data structures?

```def isUniqueChars(str):
#first sort the string O(nlgn)
sortedStr = "".join(sorted(str))

isUnique = True

#compare the consecutive characters O(n)
for i in range(len(sortedStr)-1):
if sortedStr[i] == sortedStr[i+1]:
isUnique = False

return isUnique

print isUniqueChars("Amber".lower())

def isUniqueChars2(str):
#considering the characters are ascii characters building an array for 256 characters acting as a hash table
arr = *256
for c in str:
asciiValue = ord(c)
arr[asciiValue] += 1

isUnique = True

#checking for repeated characters O(1)
for entries in str:
if arr[ord(entries)] > 1:
isUnique = False
return isUnique

print isUniqueChars2("Amber".lower())

```

# Trees

Hi! If you are thinking where have you arrived and have no clue of whats going on then visit this page.

Here is the lecture on general trees and binary trees by Prof Naveen Garg.

Some very important properties of a binary tree assuming that the height of the tree is h are:

1. The maximum number of nodes at each level of a binary tree is: 2l where l is the level number.

2. The number of nodes n in a full binary tree are: 2h+1-1
This is because a binary tree of height h has h levels. So we add the number of nodes at each level
(20+21+22…2h)

3. The number of leaf nodes in a full binary tree is: 2h

Here is the python implementation of a binary tree:

```class BinaryTree:
#binary tree constructor
def __init__(self, root):
self.root = root
self.leftChild = None #initializing left child of a binary tree
self.rightChild = None #initializing right child of a binary tree

#method for setting the root of a binary tree
def setRoot(self, root):
self.root = root

#method for getting the root of a binary tree
def getRoot(self):
return self.root

#method for getting the left child of the binary tree
def getLeftChild(self):
return self.leftChild

#method for getting the right child of the binary tree
def getRightChild(self):
return self.rightChild

#method for inserting the left child of the binary tree
def insertLeftChild(self, newNode):
if self.leftChild == None:
self.leftChild = BinaryTree(newNode)
else:
t = BinaryTree(newNode)
t.leftChild = self.leftChild
self.leftChild = t

#method for inserting the right child of the binary tree
def insertRightChild(self, newNode):
if self.rightChild == None:
self.rightChild = BinaryTree(newNode)
else:
t = BinaryTree(newNode)
t.rightChild = self.rightChild
self.rightChild = t
```

Hi! If you are thinking where have you arrived and have no clue of whats going on then visit this page.

Here is the lecture on queues and linked lists by Prof Naveen Garg.

Learn Linked Lists in 10 minutes from the following video:

This video is also a very good source:

A singly link list consists of one or more nodes with each node having a next pointer that points to the next node.

A very simple Node with all the operations might look like this in Python:

```#node of a Singly Linked List
class Node:
#constructor
def __init__(self):
self.data = None
self.next = None

#method for setting the data field of the node
def setData(self,data):
self.data = data

#method for getting the data field of the node
def getData(self):
return self.data

#method for setting the next field of the node
def setNext(self,next):
self.next = next

#method for getting the next field of the node
def getNext(self):
return self.next
```

Now that we have dealt with the nodes. Lets deal with the actual Linked List that contain these nodes.

The basic operations in a singly linked list are:

2. Inserting an element in the Linked List
3. Deleting an element in the Linked List

The code for implementing a Singly Linked List is as follows:

```

#constructor
def __init__(self):
self.length = 0

#method for inserting a new node at the beginning of the Linked List (at the head)
def insertAtBeg(self,data):
newNode = Node()
newNode.setData(data)
if self.length == 0:
else:
self.length += 1

#method for inserting a new node at the end of a Linked List
def insertAtEnd(self,data):
newNode = Node()
newNode.setData(data)

while current.getNext() != None:
current = current.getNext()

current.setNext(newNode)
self.length += 1

#method for inserting a new node at any position in a Linked List
def insertAtPos(self,pos,data):
if pos > self.length or pos < 0:
return None
else:
if pos == 0:
self.insertAtBeg(data)
else:
if pos == self.length:
self.insertAtEnd(data)
else:
newNode = Node()
newNode.setData(data)
count = 0
while count < pos-1:
count += 1
current = current.getNext()

newNode.setNext(current.getNext())
current.setNext(newNode)
self.length += 1

#method for traversing and printing the Linked List
def printList(self):
while current != None:
print current.getData()
current = current.getNext()

#method for deleting a node having a certain data
def delete(self,data):

else:
while (current.getData() != data):
previous = current
current = current.getNext()

if current.getData() == data:
previous.setNext(current.getNext())
else:
return None

if __name__ == "__main__":
ll.insertAtBeg(1)

ll.insertAtBeg(2)
ll.insertAtEnd(3)
ll.insertAtPos(0, 4)
ll.insertAtPos(4,5)
ll.insertAtPos(2,9)

ll.printList()

ll.delete(9)

ll.printList()

print "Deleting the last element"
ll.delete(5)
ll.printList()

```

A node in a doubly linked list can be defined using a class. It might look as follows:

```class Node:
#constructor
def __init__(self):
self.data = 0
self.next = None
self.previous = None

#method for setting the value of a node
def setValue(self,value):
self.data = value

#method for getting the value of a node
def getValue(self):
return self.data

#method for setting the next node of a node
def setNext(self,next):
self.next = next

#method for getting the next node of a node
def getNext(self):
return self.next

#method for setting the previous node of a node
def setPrevious(self,previous):
self.previous = previous

#method for getting the previous node of a node
def getPrevious(self):
return self.previous
```

The basic operations in a Doubly Linked List is again
1. Insertion
2. Deletion
3. Traversal

The class for Doubly Linked List along with its operations is defined as follows:

```class DoublyLinkedList:
#constructor
def __init__(self):
self.length = 0 #length of the list

#method for inserting at the beginning of the list
def insertAtBeg(self,value):
newNode = Node()
newNode.setValue(value)
newNode.setNext(None)
newNode.setPrevious(None)
if self.length == 0:
self.length += 1
else:
self.length += 1

#method for inserting a node at the end
def insertAtEnd(self,value):
newNode = Node()
newNode.setValue(value)

while(current.getNext() != None):
current = current.getNext()

newNode.setNext(current.getNext())
newNode.setPrevious(current)
current.setNext(newNode)
self.length += 1

#method for inserting a node at the middle
def insertAtMid(self,pos,value):
newNode = Node()
newNode.setValue(value)
count = 0
while(count < pos-1):
current = current.getNext()
count += 1

current.getNext().setPrevious(newNode)
newNode.setNext(current.getNext())
current.setNext(newNode)
newNode.setPrevious(current)
self.length += 1

#method for traversing and printing the list
def printList(self):
while current != None:
print current.getValue()
current = current.getNext()

```

Here is a list of problems related to Linked Lists.

# Stacks

Hi! If you are thinking where have you arrived and have no clue of whats going on then visit this page.
Here is the lecture on stacks by Prof Naveen Garg.

A very simple implementation of a Stack in Python is explained below.

```
#class for defining a stack
class Stack:
def __init__(self):
self.items = []

#method for pushing an item on a stack
def push(self,item):
self.items.append(item)

#method for popping an item from a stack
def pop(self):
return self.items.pop()

#method to check whether the stack is empty or not
def isEmpty(self):
return (self.items == [])

#method to get the top of the stack
def topOfStack(self):
return len(self.items)

def __str__(self):
return str(self.items)

if __name__ == "__main__":
stck = Stack()

stck.push(5)
stck.push(10)
stck.push(15)
stck.push(20)

print stck
#Output = [5, 10, 15, 20]

stck.pop()

print stck
#Output = [5, 10, 15]

print stck.topOfStack()
#Output = 3
```

We will learn about how to implement stacks using Linked Lists later, when we cover Linked Lists. At this moment we will use the stack created above for solving most of the problems related to Stacks.

1. Write a code for showing how stacks can be used for checking balancing of symbols.

Sample Input: “([)]”
Sample Output: False

Sample Input : “{{([][])}()}”
Sample Output : True

Soln: The algorithm is as follows:
Step 1. Create a stack.
Step 2. Scan the input and while the end is not reached perform the following steps:
Step 2a. If the character read is not a symbol to be balanced then ignore it.
Step 2b. If the character is an opening symbol like “(,{ or [” then push it onto the stack.
Step 2c. If the character is a closing symbol like “), } or ]” then if the stack is empty then return that the given input is unbalanced, else pop the symbol from the top of the stack.
Step 2d. If the symbol popped is not the corresponding opening symbol of the closing symbol currently being scanned then return that the given input is unbalanced.

The Python program implementing the problem is as follows:

```class Stack:
def __init__(self):
self.items = []

#method for pushing an item on a stack
def push(self,item):
self.items.append(item)

#method for popping an item from a stack
def pop(self):
return self.items.pop()

#method to check whether the stack is empty or not
def isEmpty(self):
return (self.items == [])

#method to get the top of the stack
def topOfStack(self):
return len(self.items)

def __str__(self):
return str(self.items)

def matches(top,symbol):
openingSymbols = "({["
closingSymbols = ")}]"

return openingSymbols.index(top) == closingSymbols.index(symbol)

def checkBalance(input):
symbolstack = Stack()
balanced = False
for symbols in input:
if symbols in ["(","{","["]:
symbolstack.push(symbols)
else:
if symbolstack.isEmpty():
balanced = False
else:
topSymbol = symbolstack.pop()
if not matches(topSymbol,symbols):
balanced = False
else:
balanced = True

return balanced

print checkBalance("([)]")
'''Output: False'''

print checkBalance("{{([][])}()}")
'''Output: True'''
```

2. Convert a decimal number into the number of a particular given base.

Sample Input: decimal = 25 base = 2
Sample Output: 11001
Soln:

```class Stack:
def __init__(self):
self.items = []

#method for pushing an item on a stack
def push(self,item):
self.items.append(item)

#method for popping an item from a stack
def pop(self):
return self.items.pop()

#method to check whether the stack is empty or not
def isEmpty(self):
return (self.items == [])

#method to get the top of the stack
def topOfStack(self):
return len(self.items)

def __str__(self):
return str(self.items)

def baseConversion(decimalNum,base):
digits = "0123456789ABCDEF"

remainderStack = Stack()

while (decimalNum > 0):
remainderStack.push(decimalNum % base)
decimalNum //= base

convertedString = ""
while not remainderStack.isEmpty():
convertedString = convertedString + digits[remainderStack.pop()]

return convertedString

print baseConversion(25,2)
'''Output 11001'''

print baseConversion(1000,16)
'''Output 3E8'''

```

3. Check whether a given string is a palindrome or not?

Sample Output: True

Soln:

```class Stack:
def __init__(self):
self.items = []

#method for pushing an item on a stack
def push(self,item):
self.items.append(item)

#method for popping an item from a stack
def pop(self):
return self.items.pop()

#method to check whether the stack is empty or not
def isEmpty(self):
return (self.items == [])

#method to get the top of the stack
def topOfStack(self):
return len(self.items)

def __str__(self):
return str(self.items)

def isPalindrome(str):
strStack = Stack()
palindrome = False

for char in str:
strStack.push(char)

for char in str:
if char == strStack.pop():
palindrome = True
else:
palindrome = False

return palindrome

```

# Data Structures and Algorithms

Hi! Everyone,

This blog is an effort from my side to be in touch with Data Structures and Algorithms and practice questions that are often asked in coding interviews. People might not find anything very new in this blog, but they will certainly find the topics related to data structures and algorithms organized in a sequential manner, where we start from the basics and explore the concepts to solve various problems. This blog would certainly be helpful for those who are preparing for interviews.

Almost all the codes would be written in Python. This is because thats’ the language I am most comfortable with. I am sorry if you don’t know the language as most people prefer C++ or Java. If you want to learn Python, you can easily do so and it should not take more than a week. Its very close to writing Pseudo Codes. I learnt it for the first time from here. Try it out. Most of the big companies don’t mind what you code in. Infact Google uses python a lot. So does the other companies. Most importantly Python is used by Data Scientists, and Data Science is regarded as the sexiest job of the 21st century. Check out this article by Harvard Business Review: http://hbr.org/2012/10/data-scientist-the-sexiest-job-of-the-21st-century/ar/1. Fortunately, I am also into data science and belong to the same breed of people often known as Data Scientists. I will soon start a new blog that would showcase my works on Data Science.

I am a big fan of IIT (Indian Institute of Technology) and also a big fan of IIT-Delhi. 🙂 I am biased about this as my fiance is a IITD grad. But I genuinely feel that Prof Naveen Gargs’ lectures on Data Structure and Algorithms are very easy to follow and can be a solid foundation for anyone who is interested to learn them. So I would be providing links to his lectures, every time I cover a topic. A full list of his lectures can be found over here.

Regarding the programming problems related to a topic I would like to follow this book (Coding Interview Questions by Narasimha Karumanchi). This book might not be a great book. But surely it has good problems to start with. I totally believe that the problems in this book would help anyone to be clear with the basic data structure and algorithm problems that are asked by interviewers. Trust me on this. I mostly have a good experience with the book.

I have sketched out the topics below. As soon as I start adding materials to the topic, each of them would become clickable and will lead you to the various blog posts related to the topic. Don’t hesitate, just click, read and give suggestions, provide better solutions. After all, I am always open for them.

So lets sketch out the outline of the topics that we will cover:

1. Introduction to Data Structures and Algorithms
2. Stacks
4. Dictionaries
5. Hashing
6. Trees
7. Tree Walks / Traversals
8. Ordered Dictionaries
9. Deletion
10. Quick Sort
11. AVL Trees
12. AVL Trees
13. Trees
14. Red Black Trees
15. Insertion in Red Black Trees
16. Disk Based Data Structures
17. Case Study: Searching for Patterns
18. Tries
19. Data Compression
20. Priority Queues
21. Binary Heaps
22. Why Sorting
23. More Sorting
24. Graphs
25. Data Structures for Graphs
26. Two Applications of Breadth First Search
27. Depth First Search
28. Applications of DFS
29. DFS in Directed Graphs
30. Applications of DFS in Directed Graphs
31. Minimum Spanning Trees
32. The Union
33. Prims Algorithm for Minimum Spanning Trees
34. Single Source Shortest Paths
35. Correctness of Dijkstras Algorithm
36. Single Source Shortest Paths

# Introduction to Data Structures and Algorithms

Hi! If you are thinking where have you arrived and have no clue of whats going on then visit this page.

I would not dive into a lot of coding in this blog. Prof Naveen Gargs’ lectures are enough for this blog post. Have a go at the lecture:

The transcript of the lecture can be found over here:
http://textofvideo.nptel.iitm.ac.in/1074/lec1.pdf

For the Python code of the Insertion Sort algorithm, please refer to my blog post on Insertion Sort.
https://codeatsociallywired.wordpress.com/2013/07/06/insertion-sort-and-shell-sort-the-two-brothers/

# Identical Binary Trees

```class BinaryTree:
def __init__(self, root):
self.root = root
self.leftChild = None
self.rightChild = None

def setRoot(self, root):
self.root = root

def getRoot(self):
return self.root

def getLeftChild(self):
return self.leftChild

def getRightChild(self):
return self.rightChild

def insertLeftChild(self, newNode):
if self.leftChild == None:
self.leftChild = BinaryTree(newNode)
else:
t = BinaryTree(newNode)
t.leftChild = self.leftChild
self.leftChild = t

def insertRightChild(self, newNode):
if self.rightChild == None:
self.rightChild = BinaryTree(newNode)
else:
t = BinaryTree(newNode)
t.rightChild = self.rightChild
self.rightChild = t

def isStructurallyIdentical(tree1,tree2):
if tree1 == None and tree2 == None:
return True
if tree1 == None or tree2 == None:
return False

return (tree1.root == tree2.root and isStructurallyIdentical(tree1.getLeftChild(), tree2.getLeftChild()) and isStructurallyIdentical(tree1.getRightChild(), tree2.getRightChild()) )

if __name__ == "__main__":

r = BinaryTree(5)
r.insertLeftChild(6)
r.insertRightChild(7)
r.leftChild.insertLeftChild(12)
r.leftChild.insertRightChild(54)
r.rightChild.insertRightChild(63)

t = BinaryTree(5)
t.insertLeftChild(6)
t.insertRightChild(7)
t.leftChild.insertLeftChild(12)
t.leftChild.insertRightChild(54)
t.rightChild.insertRightChild(63)

print isStructurallyIdentical(t,r)
```

# Number of Leaves, Non Leaf Nodes and Nodes having one Child of a Binary Tree

```
class BinaryTree:
def __init__(self, root):
self.root = root
self.leftChild = None
self.rightChild = None

def setRoot(self, root):
self.root = root

def getRoot(self):
return self.root

def getLeftChild(self):
return self.leftChild

def getRightChild(self):
return self.rightChild

def insertLeftChild(self, newNode):
if self.leftChild == None:
self.leftChild = BinaryTree(newNode)
else:
t = BinaryTree(newNode)
t.leftChild = self.leftChild
self.leftChild = t

def insertRightChild(self, newNode):
if self.rightChild == None:
self.rightChild = BinaryTree(newNode)
else:
t = BinaryTree(newNode)
t.rightChild = self.rightChild
self.rightChild = t

def getNumberOfLeavesIterative(tree):
queue = []
leafCount = 0
queue.append(tree)

if tree == None:
return 0

while (queue != []):
temp = queue.pop(0)
if temp.getLeftChild() == None and temp.getRightChild() == None:
leafCount += 1

if temp.getLeftChild():
queue.append(temp.getLeftChild())

if temp.getRightChild():
queue.append(temp.getRightChild())

return leafCount

def getNumberOfNonLeafNodesIterative(tree):
queue = []
nonleafCount = 0
queue.append(tree)

if tree == None:
return 0

while (queue != []):
temp = queue.pop(0)
if temp.getLeftChild() != None and temp.getRightChild() != None:
nonleafCount += 1

if temp.getLeftChild():
queue.append(temp.getLeftChild())

if temp.getRightChild():
queue.append(temp.getRightChild())

return nonleafCount

def getNumberOfNodesHavingOneChild(tree):
queue = []
oneChildCount = 0
queue.append(tree)

if tree == None:
return 0

while (queue != []):
temp = queue.pop(0)
if (temp.getLeftChild() == None and temp.getRightChild() != None) or(temp.getLeftChild() != None and temp.getRightChild() == None) :
oneChildCount += 1

if temp.getLeftChild():
queue.append(temp.getLeftChild())

if temp.getRightChild():
queue.append(temp.getRightChild())

return oneChildCount

if __name__ == "__main__":

r = BinaryTree(5)
r.insertLeftChild(6)
r.insertRightChild(7)
r.leftChild.insertLeftChild(12)
r.leftChild.insertRightChild(54)
r.rightChild.insertRightChild(63)

print "The number of leaf nodes of the binary tree are:",getNumberOfNonLeafNodesIterative(r)
print "\n\n"

print "The number of non-leaf nodes of the binary tree are:", getNumberOfNonLeafNodesIterative(r)
print "\n\n"

print "The number of nodes having just one child are:", getNumberOfNodesHavingOneChild(r)
print "\n\n"

```

# Level Order Traversal of Binary Tree and Reverse Level Order Traversal

```class BinaryTree:
def __init__(self, root):
self.root = root
self.leftChild = None
self.rightChild = None

def setRoot(self, root):
self.root = root

def getRoot(self):
return self.root

def getLeftChild(self):
return self.leftChild

def getRightChild(self):
return self.rightChild

def insertLeftChild(self, newNode):
if self.leftChild == None:
self.leftChild = BinaryTree(newNode)
else:
t = BinaryTree(newNode)
t.leftChild = self.leftChild
self.leftChild = t

def insertRightChild(self, newNode):
if self.rightChild == None:
self.rightChild = BinaryTree(newNode)
else:
t = BinaryTree(newNode)
t.rightChild = self.rightChild
self.rightChild = t

'''Iterative Level Order Traversal of a Binary Tree'''
def iterativeLevelOrderTraversal(tree):
current = tree
queue = []
queue.append(current)
while (queue != []):
temp = queue.pop(0)
print temp.root
if temp.getLeftChild():
queue.append(temp.getLeftChild())
if temp.getRightChild():
queue.append(temp.getRightChild())

'''Printing Level Order Traversal in a reverse way'''
def printingLevelOrderReverse(tree):
stack = []
if tree == None:
return 0
else:
queue = []

queue.append(tree)
while(queue != []):
temp = queue.pop(0)
stack.append(temp.root)
if temp.getLeftChild():
queue.append(temp.getLeftChild())
if temp.getRightChild():
queue.append(temp.getRightChild())

if stack != []:
for i in range(len(stack)):
print stack.pop()
else:
return 0

if __name__ == "__main__":

r = BinaryTree(5)
r.insertLeftChild(6)
r.insertRightChild(7)
r.leftChild.insertLeftChild(12)
r.leftChild.insertRightChild(54)
r.rightChild.insertRightChild(63)

print "Levelorder traversal of the tree is:", iterativeLevelOrderTraversal(r)
print "\n\n"

print "Printing level order in a reverse way:", printingLevelOrderReverse(r)
print "\n\n"

```

# Size and Height of a Binary Tree

```class BinaryTree:
def __init__(self, root):
self.root = root
self.leftChild = None
self.rightChild = None

def setRoot(self, root):
self.root = root

def getRoot(self):
return self.root

def getLeftChild(self):
return self.leftChild

def getRightChild(self):
return self.rightChild

def insertLeftChild(self, newNode):
if self.leftChild == None:
self.leftChild = BinaryTree(newNode)
else:
t = BinaryTree(newNode)
t.leftChild = self.leftChild
self.leftChild = t

def insertRightChild(self, newNode):
if self.rightChild == None:
self.rightChild = BinaryTree(newNode)
else:
t = BinaryTree(newNode)
t.rightChild = self.rightChild
self.rightChild = t

'''recursive process for finding height of a binary tree'''
def height(tree):
if tree == None:
return 0
else:
return max(height(tree.leftChild),height(tree.rightChild)) + 1

'''iterative process for finding height of a binary tree'''
def heightIterative(tree):
height = 0
if tree == None:
return 0

queue = []
queue.append(tree)
queue.append("NULL")

while ( queue != []):
root = queue.pop(0)
if root == "NULL":
if queue != []:
queue.append("NULL")
height += 1
else:
if root.getLeftChild():
queue.append(root.getLeftChild())
if root.getRightChild():
queue.append(root.getRightChild())

return height

'''recursive process for finding size of a binary tree'''
def size(tree):
if tree == None:
return 0
else:
return size(tree.getLeftChild()) + 1+ size(tree.getRightChild())

if __name__ == "__main__":

r = BinaryTree(5)
r.insertLeftChild(6)
r.insertRightChild(7)
r.leftChild.insertLeftChild(12)
r.leftChild.insertRightChild(54)
r.rightChild.insertRightChild(63)

print "Height of the tree is:", height(r)
print "\n\n"

print "size of the tree is:", size(r)
print "\n\n"

print "height of the tree is:", heightIterative(r)
print "\n\n"

```