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):
head = DoubleLL(0)
tail = head
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
if head.next:
res.append(head.next.val)
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))
```

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))
```

Given a binary tree and a sum, return the subtree’s root whose sum is equal to the given sum.

I initially came up with O(n^2) solution and an O(n) time and O(n) space complexity solution, until I figured out that I have been missing on an easy simple O(n) solution.

The catch here is to do a post order traversal, where you call left and right subtrees before coming to the current node.

class solution():

```
def max_sum_subtree(self,root):
res_node = [None]
max_sum = [-2**31]
self.helper(root,max_sum,res_node)
return res_node[0]
def helper(self,root,max_sum,res_node):
if not root:
return 0
subtreesum = self.helper(root.left,max_sum,res_node)+self.helper(root.right,max_sum,res_node)+root.val
if subtreesum>=max_sum[0]:
max_sum[0] = subtreesum
res_node[0] = root
return subtreesum
```

e. g: 3

```
-12 1
```

2 4 7

output: 1

Q 2: Convert a binary tree to its sum tree.

e. g: 3

```
-12 1
```

2 4 7

should become

```
2( 2+4+-12+7+1)
6(2+4) 7
```

0 0 0

class solution():

```
def max_sum_subtree(self,root):
self.helper(root)
return root
def helper(self,root):
if not root:
return 0
treesum = self.helper(root.left)+self.helper(root.right)
tmp = root.val
root.val = treesum
return treesum + tmp
```