Algorithms-Reference

Arrays and Strings

Class Definition

import sys

Linkedlist Class

class ListNode(object):
    def __init__(self, x=None):
        self.val = x
        self.next = None
        
def printLL(node):
    while node:
        print (node.val, end="->")
        node=node.next

def populateLL(array):
    node= ListNode(0)
    backup=node
    for element in array:
        node.next=ListNode(element)
        node=node.next
    return backup.next

O(n) Sliding Window Algorithm (Single Pointer)

Pseudo algorithm for Ordered Dictionary

Can modify this algorithm to suit any type of problem which involves any kind of sliding window or stream processing.

class OrderedDict(object):
    def __init__(self,capacity):
        self.capacity=capacity
        self.head=ListNode("-inf")
        self.tail=ListNode("-inf")
        self.head.next=self.tail
        self.tail.prev=self.head
        self.dict={}
        
    def addTail(self,key):
        node= ListNode(key)
        node.prev= self.tail.prev
        node.next=self.tail
        self.tail.prev.next=node
        self.tail.prev=node
        self.dict[key]=node
        if len(self.dict)>self.capacity:
            self.removeHead()
        
    def removeNode(self,key):
        node= self.dict[key]
        node.prev.next=node.next
        node.next.prev=node.prev
        del self.dict[key]
        
    def removeHead(self):
        key= self.head.next.val
        self.removeNode(key)
        
obj= OrderedDict(4)
obj.addTail(12)
print(printLL(obj.head))
obj.addTail(13)
obj.addTail(14)
obj.addTail(15)
print(printLL(obj.head))
obj.addTail(16)
print(printLL(obj.head))
obj.removeNode(14)
print(printLL(obj.head))

-inf->12->-inf->None
-inf->12->13->14->15->-inf->None
-inf->13->14->15->16->-inf->None
-inf->13->15->16->-inf->None

O(n) Sliding Window Algorithm (Consecutive Elements)

In sums where we need to compare two windows, we can create and store the window in either a set or dict.

In the example below, we are storing the window in a dict. Make sure that the size of widows remain same at all time. Thus del in the below method.

# 567: Permutation in String On Leetcode
class WindowCompare(object):
    def compareWindow(self, s1, s2):
        if len(s1)>len(s2):
            return False
        
        s1dct = defaultdict(int)
        s2dct = defaultdict(int)

        for elem in s1:
            s1dct[elem]+=1
        for i in xrange(len(s1)):
            s2dct[s2[i]]+=1

        i = 0

        for j in xrange(len(s1), len(s2)):
            if s1dct == s2dct:
                return True 
            s2dct[s2[j]]+=1
            s2dct[s2[i]]-=1
            if s2dct[s2[i]]<=0:
                del s2dct[s2[i]]
            i+=1

        if s1dct == s2dct:
            return True