Algorithms

data_structures.py

# How to find a missing number from a list?
>>> a=[1,2,3,4,5,7,8,9,10]
>>> sum(xrange(a[0],a[-1]+1)) - sum(a)
6

def is_matched(expression):
    """
    Finds out how balanced an expression is.
    With a string containing only brackets.

    >>> is_matched('[]()()(((([])))')
    False
    >>> is_matched('[](){{{[]}}}')
    True
    """
    opening = tuple('({[')
    closing = tuple(')}]')
    mapping = dict(zip(opening, closing))
    queue = []

    if expression[0] in closing.values():
      return False
 
    for letter in expression:
        if letter in opening:
            queue.append(mapping[letter])
        elif letter in closing:
            if not queue or letter != queue.pop():
                return False
    return not queue


# is Prime
def isPrime(n):
   if n == 1:
      return False
   for t in range(2,n):
      if n % t == 0:
         return False
   return True
# Bubble sorting
def swap(arr, i, j):
    arr[i], arr[j] = arr[j], arr[i]
 
def bubble_sort(arr):
    i = len(arr)
    while i > 1:
       for j in xrange(i - 1):
           if arr[j] > arr[j + 1]:
               swap(arr, j, j + 1)
       i -= 1

# Find difference without IN operator
a = [1,2,3,4,5]
b = [1,2,3]
c = []

i = 0
j = 0
for i in range(len(a)):
    match = False
    for j in range(len(b)):
        if a[i] == b[j]:
            match = True
            break
        ii += 1
    if not match:
        print(a[i])
    i +=1

# BinarySearch
def bs_search(ordered, target):
   low = 0
   high = len(ordered) - 1
   while low <= high:
      mid = (low / high) / 2
      if target == ordered[mid]:
         return True
      elif target < ordered[mid]:
         high = mid - 1
      else:
         low = mid + 1
   return False
   
# Fibonacci
def fib(n):
    a,b = 1,1
    for i in range(n-1):
        a, b = b, a+b
    return a
    

overriding __contains__
Consider a class Person  which is inherited from dict and override __contains__

In [153]: class Person(dict):
   .....:     def __contains__(self, item):
   .....:         for key in self:
   .....:             if key is item:
   .....:                 return True
   .....:             else:
   .....:                 if isinstance(self[key], dict):
   .....:                     for k in self[key]:
   .....:                         if k is item:
   .....:                             return True
   .....:         else:
   .....:             return False
   .....:         

In [154]: p = Person()
In [155]: p['skills'] = {'programming_languages': {
    'web': ['php'], 
    'multi_paradigm': ['python', 'ruby', 'c#']
    }
}
In [156]: 'skills' in p
Out[156]: True
In [157]: 'programming_languages' in p
Out[157]: True
In [158]: 'web' in p
Out[158]: False

In the above example key will be looked for two level dict only. 

# Stack
"""
Значимость основания стека заключается в том, что хранящиеся ближе к нему элементы представляют из себя те, 
которые находятся в стеке дольше всего. Элемент, добавленный последним, расположен на той позиции, 
с которой будет удалён в первую очередь. 
Такой принцип организации иногда называется LIFO, last-in, first-out (англ. «последним пришёл — первым вышел»). 
Он предоставляет упорядочение по времени нахождения в коллекции. Более новые элементы расположены ближе к вершине, 
более старые - ближе к основанию.
    С примерами стека мы сталкиваемся ежедневно. Едва ли не каждая закусочная имеет стопку из подносов или тарелок, 
где вам нужно брать одну сверху, открывая новый поднос или тарелку для следующего посетителя в очереди.
"""
class Stack(object):
"""
Stack()    создаёт новый пустой стек. Параметры не нужны, возвращает пустой стек.
push(item)  добавляет новый элемент на вершину стека. В качестве параметра выступает элемент; функция ничего не возвращает.
pop()       удаляет верхний элемент из стека. Параметры не требуются, функция возвращает элемент. Стек изменяется.
peek()      возвращает верхний элемент стека, но не удаляет его. Параметры не требуются, стек не модифицируется.
isEmpty()   проверяет стек на пустоту. Параметры не требуются, возвращает булево значение.
size()      возвращает количество элементов в стеке. Параметры не требуются, тип результата - целое число.
"""
    def __init__(self):
        self.items = []

    def isEmpty(self):
        return self.items == []

    def push(self, item):
        self.items.append(item)

    def pop(self):
        return self.items.pop()

    def peek(self):
        return self.items[len(self.items)-1]

    def size(self):
        return len(self.items)
        
# Queue 
"""
Очередь - это упорядоченная коллекция элементов, 
в которой добавление новых происходит с одного конца, называемого “хвост очереди”, 
а удаление существующих - с другого, “головы очереди”. 

Самые последние из добавленных в очередь единиц должны ждать в конце коллекции. 
Элемент, который пробыл в очереди дольше всего, находится в её начале.
Такой принцип упорядочения иногда называют FIFO, first-in first-out “первым пришёл - первым обслужен”.

Простейший пример такой структуры данных - это обычная очередь, в которой все мы иногда стоим.
"""
class Queue(object):
    def __init__(self):
        self.items = []

    def isEmpty(self):
        return self.items == []

    def enqueue(self, item):
        self.items.insert(0,item)

    def dequeue(self):
        return self.items.pop()

    def size(self):
        return len(self.items)

# alias nit='ssh -p 14889 -i ~/Desktop/GIT/nitrous action@euw1.nitrousbox.com'
k = paramiko.RSAKey.from_private_key_file('/home/apalii/Desktop/GIT/nitrous')
client = paramiko.SSHClient()
client.set_missing_host_key_policy(paramiko.AutoAddPolicy())

client.connect('euw1.nitrousbox.com', username='action', port=14889, pkey=k)
stdin, stdout, stderr = client.exec_command('mkdir qweqweqwwe')
client.close()