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

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

Binary Sub tree sum

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

GitHub – sainadhreddy92

sainadhreddy92