## Top view of a binary tree

Given a root of a binary tree, print the top view of a binary tree

This problem is similar to the vertical order traversal of the binary tree. The only catch is here is that , when we are storing the level wise elements in the hashmap , we check if there is already a value exists in the hashmap for that level. If it exists, we wouldn't storing again at that level because as we are coming from the top (root), the first element at each level is what appears in the output.

class TreeNode():
def __init__(self,val):
self.val = val
self.left = None
self.right = None

class solution():
def topview(self,root):
if not root:
return []
hmap ={}
minlevel=2**31-1
maxlevel = -2**31
q = [(root,0)]

while q:
(node,level) = q.pop(0)

if level not in hmap:
hmap[level] = node.val

minlevel = min(minlevel,level)
maxlevel = max(maxlevel,level)

if node.left:
q.append((node.left,level-1))

if node.right:
q.append((node.right,level+1))
res = []

for level in range(minlevel,maxlevel+1):
res.append(hmap[level])

return res

def main():
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(9)
root.left.right = TreeNode(3)
root.left.right.left = TreeNode(4)
root.left.right.left.left = TreeNode(5)
root.right.left = TreeNode(6)
root.right.left.right = TreeNode(7)

print solution().topview(root)

if __name__=='__main__':
main()


## First Non Repeated character in a string

Given a stream of characters, find the first non repeated character. If no such character is found, return -1.

This can be done using a hasmap and queue which takes O(n). The objective of this post is to make it O(1). All we need is a Doubly Linked List and an array of 26 , which points to the node of a character, if at all it exists. A True/False array which will tell whether the char is duplicate or not.

Doibly linked list and storing its nodes as indexes in array , comes in handy for ordering of elements (e.g implementation of ordered dictionary and LRU cache)

class DoubleLL(object):
def __init__(self,val):
self.val = val
self.prev = None
self.next = None

class solution():
def nonRepeatChar(self,elements):

dll_array = [None]*26
visited = [False]*26
res =[]

for elem in elements:
if visited[ord(elem)-ord(‘a’)]==False:
if dll_array[ord(elem)-ord(‘a’)] ==None:
tail.next = DoubleLL(elem)
tail.next.prev = tail
dll_array[ord(elem)-ord(‘a’)] = tail.next
tail = tail.next
else:
node = dll_array[ord(elem)-ord(‘a’)]
if node==tail:
tail=node.prev

prev_node = node.prev
next_node = node.next
if prev_node:
prev_node.next = next_node
if next_node:
next_node.prev = prev_node
dll_array[ord(elem)-ord(‘a’)] = None
visited[ord(elem)-ord(‘a’)] = True

else:
res.append(‘-1’)

return ‘ ‘.join(res)

test_cases = int(input().strip())
for _ in range(test_cases):
n = int(input().strip())
elements = input().strip().split()
sol = solution()
print (sol.nonRepeatChar(elements))


## Running Median of A stream of integers

The problem is to find the running median given a stream of integers. The brute force approach is to sort the array each time an element is inserted, which takes O(n^2 * logn) time. The otherapproach is to maintain two heaps.

Heap1 is a maximum heap of all the minimum elements Heap2 is a minimum heap of all the maximum elements

The approach is to maintain two heaps each of which is almost equal to the half of the array size( We balance two heaps so that the difference in their length is less than 2). The main ideais to treat each half as sorted half of the array.

If the two heaps are of equal size (even number of elements in the array), we return the averageof maximum of first heap and minimum of second heap. if the two heaps are of different sizes(odd number of elements), we will return the top element of the heap that is larger in size.

from heapq import heapify,heappush,heappop
class solution():
heap1 =[]
heap2 =[]
heapify(heap1)
heapify(heap2)
def runningMedian(self,num):
self.insertNum(num)
self.reBalance()
return self.FindMedian()

def insertNum(self,num):
if not self.heap1 or num <= -self.heap1[0]:
heappush(self.heap1,-num)
else:
heappush(self.heap2,num)

def FindMedian(self):

if len(self.heap1)==len(self.heap2):
return (-self.heap1[0] + (self.heap2[0]))//2

else:
if len(self.heap1)>len(self.heap2):
return -self.heap1[0]
else:
return self.heap2[0]

def reBalance(self):
if abs(len(self.heap1)-len(self.heap2))<=1:
return
else:
if len(self.heap1)>len(self.heap2):
heappush(self.heap2,-heappop(self.heap1))
else:
heappush(self.heap1, -heappop(self.heap2))

n = int(input().strip())
sol = solution()
for _ in range(n):
num = int(input().strip())
print (sol.runningMedian(num))