DATA STRUCTURES

Trees and Graphs are covered in a separate notebook.
This link contains a lot more algorithms to review before the interview, especially those I haven't reviewed yet - DP, number theory, bit manipulation, some interesting string / array algos!

BIG O NOTATION

Big Omega - lower bound (best case); Big Theta - average bound; Big O - max bound

Big-O notation describes how quickly runtime will grow relative to the input as the input gets arbitrarily large. Big-O notation is a relative representation of the complexity of an algorithm

relative: you can't compare multiplication to sorting directly, but comparison of two sorts is meaningful;
representation: Big-O reduces comparison to single var through observations or assumptions, e.g. sorting is compared on comparison operations (expensive)
complexity: one second to sort 10,000 elements, how long to sort one million? Complexity = relative measure to something else.

We compare how quickly runtime grows, not exact runtimes (can vary depending on hardware).
We compare for a variety of input sizes - relative to the input => use n for notation.
We only worry about terms that grow the fastest as n gets large => Big-O is asymptotic analysis

Asymptotic behavior = limiting behavior (theory of limits). Asymptote (/ˈæsɪmptoʊt/) of a curve is a line such that the distance between the curve and the line approaches zero as one or both x or y tends to infinity

THEORY

Order of magnitude

Time complexity != exact # times the code runs, but shows the order of magnitude. E.g. if the code is executed 3n, n+5 and n/2 times, time complexity is the same = O(n)

Phases

If algo has consecutive phases, total time complexity = time complexity of the largest single phase.
Reason - slowest phase is usually the bottleneck. E.g. if the code consists of three phases O(1), O(n), and O(n^2) => total time complexity = O(n^2)

Several variables

Sometimes time complexity depends on several factors. If two nested loops, 1 through n & 1 through m, time complexity = O(nm):
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {// code}
}

Recursion

Time complexity of recursive f(x) = # calls X time complexity of each call
For example - n function calls, each w/complexity of O(1) = total time complexity of O(n):

void f(int n) {
if (n == 1) return;
f(n-1);
}

Another example:

void g(int n) {
if (n == 1) return;
g(n-1);
g(n-1);
}

Each call generates two more calls, except for n = 1:

Big-O	Name
1	Constant
log(n)	Logarithmic
n	Linear
nlog(n)	Log Linear
n^2	Quadratic
n^3	Cubic
2^n	Exponential

Complexity classes

From "Competitive Programmer’s Handbook" - very interesting book: terse and to the point

O(1) constant-time algo - no dependency on input size. E.g. formula calculating an answer OR list[idx].
O(logn) algo halves / reduces input size at each step. Logarithmic because (log2 n) = # times to divide n by 2 to get 1.
O(sqrt(n)) slower than O(logn), but faster than O(n); sqrt(n) = sqrt(n) / n, so sqrt(n) lies in the middle of input.
O(n) iteration over the input - accessing each input element at least once before reporting the answer.
O(nlogn) often indicates that algo sorts the input OR algo uses data structure where each operation takes O(logn) time.
O(n^2) two nested loops
O(n^3) three nested loops.
O(2^n) algo iterates through all subsets of input elements. E.g. subsets of {1,2,3}: {1}, {2}, {3}, {1,2}, {1,3}, {2,3} and {1,2,3}.
O(n!) algo iterates through all permutations of input elements. E.g. permutations of {1,2,3}: (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2) and (3,2,1). Polynomial algo - time complexity of O(n^k) where k is const; if k small - algo efficient. All above except O(2^n) and O(n!) are polynomial.

There are many important problems with no known polynomial (=efficient) algo, e.g. NP-hard problems

Python

from math import log
import numpy as np
import matplotlib.pyplot as plt
%matplotlib inline
plt.style.use('bmh')

# Set up runtime comparisons
n = np.linspace(1,10,1000)
labels = ['Constant','Logarithmic','Linear','Log Linear','Quadratic','Cubic','Exponential']
big_o = [np.ones(n.shape),np.log(n),n,n*np.log(n),n**2,n**3,2**n]

# Plot setup
plt.figure(figsize=(10,8))
plt.ylim(0,50)

for i in range(len(big_o)):
    plt.plot(n,big_o[i],label = labels[i])


plt.legend(loc=0)
plt.ylabel('Relative Runtime')
plt.xlabel('n')

Output

Text(0.5, 0, 'n')

Output

Stay away from any exponential, quadratic, or cubic behavior!

Lists

Common list operations and their Big O values:

Operation	Big-O Efficiency
index []	O(1)
index assignment	O(1)
append	O(1)
pop()	O(1)
pop(i)	O(n)
insert(i,item)	O(n)
del operator	O(n)
iteration	O(n)
contains (in)	O(n)
get slice [x:y]	O(k)
del slice	O(n)
set slice	O(n+k)
reverse	O(n)
concatenate	O(k)
sort	O(n log n)
multiply	O(nk)

Dictionaries

Use hash tables - get and set items = O(1)! (Hash tables - one of the most important data structures). Common dictionary operations:

Operation	Big-O Efficiency
copy	O(n)
iteration	O(n)
get item	O(1)
set item	O(1)
delete item	O(1)
contains (in)	O(1)

Big-O Cheatsheet

Big O Examples

O(1) Constant

Python

def func_constant(values):
    '''
    Prints first item in a list of values.
    '''
    print values[0]
    
func_constant([1,2,3])

For any list, get 1 value list[index] and print it regardless of the list size

O(n) Linear

Python

def func_lin(lst):
    '''
    Takes in list and prints out all values
    '''
    for val in lst:
        print(val, end=' ')
        
func_lin([1,2,3])

O(n) (linear time) - number of operations scales linearly with n (list of 100 values will print 100 times, a list of 10,000 values will print 10,000 times, and a list of n values will print n times).

O(log n) Logarithmic time

Algorithm often halves the input size at each step. Running time = logarithmic, because log2 n = # times n must be divided by 2 to get 1.

Running time grows in proportion to the logarithm of the input size - more elements during less time, proportional to the number of digits in n. Find a name in the phone book - divide-and-conquer by looking based on where the name is alphabetically. Any d&q is logarithmic time.

Common attributes of log f(x): * Choice of the next element on which to perform some action - one of several AND only one will be picked
or * elements on which the action is performed are digits of n

O(n log n) Loglinear or linearithmic time

Logarithmic f(x) run n times e.g. reducing the size of a list n times (mergesort). If outer loop iterates through a list O(n), and an inner loop is cutting/reducing data on each iteration O(log n) => overall complexity is O(n log n)

O(n^2) Quadratic

Python

def func_quad(lst):
    '''
    Prints pairs for every item in list.
    '''
    for item_1 in lst:
        for item_2 in lst:
            print(item_1, item_2, end=', ')
            
lst = [0, 1, 2, 3]

func_quad(lst)

Two nested loops - list of n items will perform n x n operations (n^2)
If there are k nested loops, it's O(n^k)

O(n**a) Polynomial Time Generalized

O(n), O(n2) etc. are all polynomial time. Some problems cannot be solved in polynomial time: Public Key Cryptography - computationally hard to find two prime factors of a very large number

O(n!) Factorial or combinatorial complexity

The Traveling Salesman

There are n towns, each linked to 1 or more other towns by a road of a certain distance. Find the shortest tour that visits every town.

3 towns - 3 possibilities
4 towns - 12 possibilities
5 - 60
6 - 360
5! = 5 × 4 × 3 × 2 × 1 = 120
6! = 6 × 5 × 4 × 3 × 2 × 1 = 720
7! = 7 × 6 × 5 × 4 × 3 × 2 × 1 = 5040 …
50! = 50 × 49 × … × 2 × 1 = 3.04140932 × 1064
200 towns - not enough time in the universe to solve the problem with traditional computers

Calculating Scale of Big-O

We only care about the most significant terms = fastest growing terms as the input grows larger; similar to taking limits towards infinity (dropping constants). Example:

Python

# O(n)
def print_once(lst):
    '''
    Prints all items once
    '''
    for val in lst:
        print(val, end=' ')
    
lst = [0, 1, 2, 3]    
print_once(lst)

Python

# O(3n)
def print_3(lst):
    '''
    Prints all items three times
    '''
    for val in lst:
        print(val, end=' ')
        
    for val in lst:
        print(val, end=' ')
        
    for val in lst:
        print(val, end=' ')
                
lst = [0, 1, 2, 3]                
print_3(lst)

As n goes to inifinity, the constant 3 can be dropped since it will not have a large effect => both f(x) are O(n).

More complex example:

Python

# O(1 + n/2 + 10) = O(n)
def comp(lst):
    '''
    This function prints the first item O(1)
    Then is prints the first 1/2 of the list O(n/2)
    Then prints a string 10 times O(10)
    '''
    print lst[0]
    
    midpoint = len(lst)/2
    
    for val in lst[:midpoint]:
        print val
        
    for x in range(10):
        print 'number'

Python

lst = [1,2,3,4,5,6,7,8,9,10]

comp(lst)

Combining each operation: $$O(1 + n/2 + 10)$$

As n grows larger, the 1 and 10 terms become insignificant and the 1/2 term multiplied against n will also not have much of an effect as n goes towards infinity => O(n)!

Worst Case vs Best Case

Often we want know worst case O(), but in an interview setting remember that worst case and best case scenarios have different Big-O times!

Python

def matcher(lst,match):
    '''
    Given a list lst, return a boolean indicating if match item is in the list
    '''
    for item in lst:
        if item == match:
            return True
    return False

Python

lst

Python

matcher(lst,1)

Python

matcher(lst,11)

First scenario - first element O(1); second case - no match => O(n). There is also average case time.

Space Complexity

How quickly do the allocated memory/space grow relative to the size of input at large n for for any new variables we're allocating.

Below 'hello world!' assigned once => O(1) space complexity and O(n) time complexity:

Python

def printer(n=10):
    '''
    Prints "hello world!" n times
    '''
    for x in range(n):
        print 'Hello World!'

Python

printer()

O(n) space complexity, size of new_list scales with n:

Python

def create_list(n):
    new_list = []
    
    for num in range(n):
        new_list.append('new')
    
    return new_list

Python

print(create_list(5))

Space complexity = additional space => don't include space for inputs. For example, this is still O(1) space c.:

  public static int getLargestItem(int[] items) {  
    int largest = Integer.MIN_VALUE;  
    for (int item : items) {  
        if (item > largest) {  
            largest = item;  
        }  
    }  
    return largest;  
}

Sometimes you need a tradeoff between saving time and space => decide which optimization to pursue
Big O ignores constants, but sometimes the constants matter - reducing a 5-hr program to 1 hr may not affect big O, but saves a lot of time.
Premature optimization may negatively impact readability or coding time (e.g. for a young startup it may be important to write code that's easy to ship quickly or easy to understand later, even though it's less time and space efficient. Although a great engineer (startup or otherwise) always sees the right balance between optimization and maintainability
Time and space optimizations should become your natural skill!

Singly Linked List

Ordered list of items as individual Nodes that have pointers to other Nodes

Python

class Node:
    
    def __init__(self, value):
        
        self.value = value
        self.next = None

Python

a = Node(1)
b = Node(2)
c = Node(3)
a.next = b
b.next = c

sl_list = [a,b,c]

Python

print(a)
print(a.value)
print(a.next)
print(a.next.value)

for element in sl_list:
    print(element.value, end=' ')

Doubly Linked List (DLL)

Python

class DLL_Node(object):
    
    def __init__(self,value):
        
        self.value = value
        self.next = None
        self.prev = None

Python

a = DLL_Node(1)
b = DLL_Node(2)
c = DLL_Node(3)

# Setting b after a
b.prev = a
a.next = b

# Setting c after b
b.next = c
c.prev = b

dl_list = [a,b,c]

Python

print(a)
print(a.value)
print(a.next)
print(a.prev)
print(a.next.value)         # or b.value
print(a.next.prev)          # or b.prev
print(a.next.prev.value)    # or b.prev.value

for element in dl_list:
    print(element.value, end=' ')

LL manipulations

Python

# USED IN CODE BELOW
# SLL node
class Node:

    def __init__(self, value):
        self.value = value
        self.next  = None
        
# print singly linked list
def print_sll(head):
    
    print(head.value, end=' ')
    while head.next:
        print(head.next.value, end=' ')
        head = head.next
    print()

Get Nth to the last element

Python

# take head node and an integer, and return the nth to last node
def nth_to_last_node(head, n):

    left_pointer  = head
    right_pointer = head

    # left pointer is head, set right pointer at n nodes away from head
    for i in range(n-1):
        
        # Edge case
        if not right_pointer.next:
            print('n is larger than the linked list')
            return
        
        right_pointer = right_pointer.next

    # Move the left / right pointers block down the linked list
    while right_pointer.next:
        left_pointer  = left_pointer.next
        right_pointer = right_pointer.next

    # Now return left pointer, its at the nth to last element!
    return left_pointer.value

Python

a = Node(1)
b = Node(2)
c = Node(3)
d = Node(4)
e = Node(5)

a.next = b
b.next = c
c.next = d
d.next = e

n = 4
print('{}th to the last element: {}'.format(n, nth_to_last_node(a, n)))

Output

4th to the last element: 2

Reverse a singly linked list

Python

# O(n) time complexity, O(1) space complexity (in-place). To reverse: each node's next pointer to point to previous node
# In one pass from head to tail point each node's next pointer to the previous element
# copy current.next to current_next_node before setting current.next to previous

# take head node as input, reverse list, return new head
def reverse_sll(head):
    
    # Set up current,previous, and next nodes
    current = head
    previous = None
    next_node = None

    # until we have gone through to the end of the list
    while current:
        
        # copy current.next to next_node before overwriting as the previous node
        next_node = current.next

        # Reverse the pointer ot the next_node
        current.next = previous

        # Go one forward in the list
        previous = current
        current = next_node

    return previous

Python

a = Node(1)
b = Node(2)
c = Node(3)
d = Node(4)
e = Node(5)

a.next = b
b.next = c
c.next = d
d.next = e

print('Original list:', end=' ')
print_sll(a)
a = reverse_sll(a)
print('Reversed list:', end=' ')
print_sll(a)

Python

print_sll(a)

Check if there is cycle

Python

# each time marker1 moves 1 node fwrd while marker2 moves 2 nodes fwrd; if list circular, marker2 will catch up w/1
def cycle_check(node):

    # Begin both markers at the first node
    marker1 = node
    marker2 = node

    # Go until end of list
    while marker2 and marker2.next:
        
        # marker2 is moving faster
        marker1 = marker1.next
        marker2 = marker2.next.next

        # Check if marker2 caught up w/marker1
        if marker2 == marker1:
            return True

    # Case where marker2 reaches end of list
    return False

Python

# CIRCULAR LIST
a = Node(1)
b = Node(2)
c = Node(3)

a.next = b
b.next = c
c.next = a # Cycle Here!
print(cycle_check(a))

# NON-CIRCULAR LIST
x = Node(1)
y = Node(2)
z = Node(3)

x.next = y
y.next = z
print(cycle_check(x))

Output

True
False

Break cycle

Python

# loop_node: where marker1 == marker2
def removeLoop(head, loop_node): 
          
        pointer1 = head                                                         # initialize ptr1 on the left
        while(1):
                        
            # check if cycle is from pointer2 (loop_node) to pointer1 
            pointer2 = loop_node 
            while (pointer2.next != loop_node and pointer2.next != pointer1): 
                pointer2 = pointer2.next
              
            # if  cycle found, break and change pointer2.next to None - this will break the cycle 
            if pointer2.next == pointer1:  
                break 
              
            # else move pointer1 forward by one and repeat the check for cycle
            pointer1 = pointer1.next
          
        pointer2.next = None

Python

# CIRCULAR LIST
a = Node(1)
b = Node(2)
c = Node(3)

a.next = b
b.next = c
c.next = a # Cycle Here!
print('Is there a cycle:', cycle_check(a))
print('Next value for last element:', c.next.value)

removeLoop(a, c)

print('Is there a cycle:', cycle_check(a))
print('Next value for last element:', c.next)

Output

Is there a cycle: True
Next value for last element: 1
Is there a cycle: False
Next value for last element: None

Insert element into sorted LL

1) If LL empty, insert as head
2) If the value of the node to be inserted < head, insert before head (and make it head)
3) Else, in a loop, find the appropriate node whose value is greater, insert there

Time c. O(n)
Space c. O(1)

Python

# Node class  
class Node: 
      
    def __init__(self, data): 
        self.data = data 
        self.next = None

class LinkedList: 
  
    # initialize head 
    def __init__(self): 
        self.head = None
  
    def sorted_insert(self, new_node): 
          
        # LL empty  
        if self.head is None: 
            new_node.next = self.head 
            self.head = new_node 
  
        # new node < head 
        elif self.head.data >= new_node.data: 
            new_node.next = self.head 
            self.head = new_node 
  
        else:   
            
            current = self.head                                                             # find last smaller node 
            while (current.next is not None and current.next.data < new_node.data): 
                current = current.next
              
            new_node.next = current.next                                                    # insert in-between
            current.next = new_node 
  

    # print LL 
    def print_list(self):
                
        temp = self.head 
        while(temp): 
            print(temp.data, end=' ') 
            temp = temp.next
  
  
LL = LinkedList()

LL.sorted_insert(Node(5)) 
LL.sorted_insert(Node(10)) 
LL.sorted_insert(Node(7)) 
LL.sorted_insert(Node(3)) 
LL.sorted_insert(Node(1)) 
LL.sorted_insert(Node(9))

print('Linked List:')
LL.print_list()

Compare two strings represented as linked lists

Returns 0 if both strings are same, 1 if first string is lexicographically greater, -1 if second

Python

# A linked list node structure 
class Node: 
  
    def __init__(self, key):
        self.c = key ;  
        self.next = None

def compare(list1, list2):
      
    # traverse both LLs, stop when end reached or current chars don't match
    while (list1 and list2 and list1.c == list2.c): 
        list1 = list1.next 
        list2 = list2.next 
  
    # if both LLs not empty, compare mismatching chars
    if (list1 and list2): 
        return 1 if list1.c > list2.c else -1
  
    # if end reached in one LL
    if (list1 and not list2): 
        return 1 
  
    if (list2 and not list1): 
        return -1
    
    return 0

  
list1 = Node('g') 
list1.next = Node('e') 
list1.next.next = Node('e') 
list1.next.next.next = Node('k') 
list1.next.next.next.next = Node('s') 
list1.next.next.next.next.next = Node('b') 
  
list2 = Node('g') 
list2.next = Node('e') 
list2.next.next = Node('e') 
list2.next.next.next = Node('k') 
list2.next.next.next.next = Node('s') 
list2.next.next.next.next.next = Node('a') 
  
print(compare(list1, list2))

Length of linked list

Python

def length_LL(LL, head):        
    
    if (not head):                                                       # base case - no nodes
        return 0
    
    else:                                                                # recursive case
        return 1 + length_LL(LL, head.next) 


LL = LinkedList()  
LL.prepend(3) 
LL.prepend(4) 
LL.prepend(7) 
LL.prepend(11)
LL.prepend(15)

print(length_LL(LL, LL.head))

Output

Queue

Ordered collection of items: add new items at "rear", remove old items at "front". The item that has been in the collection the longest is at the front - FIFO (as a line in a store).

Python

class Queue:
    def __init__(self):
        self.items = []

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

    # adds new item to rear
    def enqueue(self, item):
        self.items.insert(0,item)

    # removes front item
    def dequeue(self):
        return self.items.pop()

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

Python

q = Queue()
print(q.size())
print(q.isEmpty())
q.enqueue(1)
print(q.dequeue())

Dequeue

Double Ended Queue provides capabilities of stacks and queues in a single data structure: insert and delete at both ends + no LIFO or FIFO requirements

Python

class Deque:
    def __init__(self):
        self.items = []

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

    # add new item to front
    def addFront(self, item):
        self.items.append(item)

    # add new item to rear
    def addRear(self, item):
        self.items.insert(0,item)

    # remove front item
    def removeFront(self):
        return self.items.pop()

    # removes rear item
    def removeRear(self):
        return self.items.pop(0)

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

Python

d = Deque()
d.addFront('hello')
d.addRear('world')
print(d.size())
print(d.removeFront() + ' ' +  d.removeRear())
print(d.size())

Stack

Ordered collection of items added and removed from one end ('top') - LIFO. Newer items are near the top, while older items are near the base. Stacks are fundamental because they can be used to reverse the order of items. Examples: string reversal, the Back button in a browser, etc.

Python

class Stack:    
    
    def __init__(self):
        self.items = []

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

    # adds new item to top
    def push(self, item):
        self.items.append(item)

    # remove top item
    def pop(self):
        return self.items.pop()

    # return top item, but do not remove it
    def peek(self):
        return self.items[len(self.items)-1]

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

Python

s = Stack()
print s.isEmpty()
s.push(1)
s.push('two')
s.peek()
s.push(True)
s.size()
s.isEmpty()
s.pop()
s.pop()
s.size()
s.pop()
s.isEmpty()

20. Balanced parenthesis check (stack)

A very common interview question * scan string left to right, push every opening parenthesis to stack (last opening parenthesis to be closed first - FILO) * when encounter closing parenthesis, pop last opening p. from stack and see if a match * if yes, proceed, if no False; if stack runs out, and there are still closing p. - False * once all matched - check if stack is empty - True

Python

def balance_check(s):
    
    if len(s)%2 != 0:                                        # even number of brackets
        return False    
   
    opening = set('([{')                                     # opening brackets    
    
    matches = set([ ('(',')'), ('[',']'), ('{','}') ])       # matching Pairs
    
    stack = []                                               # list as a "Stack"
    
    for paren in s:                                          # check every parenthesis        
        
        if paren in opening:
            stack.append(paren)
        
        else:

            if len(stack) == 0:                              # Are there parentheses in Stack
                return False
            
            
            last_open = stack.pop()                          # check last open parenthesis

            if (last_open,paren) not in matches:
                return False
            
    return len(stack) == 0

Python

to_check = ['[]', '[](){([[[]]])}', '()(){]}']
for i in to_check:
    print(balance_check(i))

Queue with two stacks

"Classic" interview question - use list as Stack * Stack reverses order (LIFO) * Two chained stacks will return elements in the original order * Fill in-stack, dequeue from out-stack * If out-stack empty, pop all elements from in-stack and push them to out-stack

Python

class Queue2Stacks(object):
    
    def __init__(self):
                
        self.instack  = []
        self.outstack = []
     
    def enqueue(self,element):                
        self.instack.append(element)
    
    def dequeue(self):
        if not self.outstack:
            while self.instack:                
                self.outstack.append(self.instack.pop())
        return self.outstack.pop()

Python

q = Queue2Stacks()

for i in range(5):
    q.enqueue(i)
    
for i in range(5):
    print(q.dequeue(), end=' ')

Output

0 1 2 3 4

Stack using two queues

s = stack, q1 & q2 = queues

Method 1 (push costly, implemented below)
Newly entered element is always at the front of q1 => pop dequeues from q1. q2 is used to put every new element at front of q1.

Push: * Enqueue x to q2 * Dequeue all from q1 and enqueue to q2 * Swap names of q1 and q2

Pop: * Dequeue item from q1

Method 2 (pop costly) In push, new elem is enqueued to q1. In pop, if q2 empty => move all elems except last to q2 => the last elem is dequeued from q1.

Push: * Enqueue x to q1

Pop: * Dequeue all but one from q1 and enqueue to q2 * Dequeue last item of q1, store it * Swap names q1 and q2 * Return item stored in step 2

Python

from queue import Queue 
  
class Stack: 
      
    def __init__(self): 
          
        # two queues  
        self.q1 = Queue() 
        self.q2 = Queue()  
              
        # current size 
        self.curr_size = 0
  
    def push(self, x): 
        self.curr_size += 1
  
        # push x first in empty q2  
        self.q2.put(x)  
  
        # push all elems in q1 to q2.  
        while (not self.q1.empty()): 
            self.q2.put(self.q1.queue[0])  
            self.q1.get() 
  
        # swap names  
        self.q = self.q1  
        self.q1 = self.q2  
        self.q2 = self.q 
  
    def pop(self): 
  
        # if no elements are there in q1  
        if (self.q1.empty()):  
            return
        self.q1.get()  
        self.curr_size -= 1
  
    def top(self): 
        if (self.q1.empty()): 
            return -1
        return self.q1.queue[0] 
  
    def size(self): 
        return self.curr_size 
    
    
s = Stack() 
s.push(1)  
s.push(2)  
s.push(3)  

print("current size: ", s.size()) 
print(s.top())  
s.pop()  
print(s.top())  
s.pop()  
print(s.top())  

print("current size: ", s.size())

Two stacks in an array (space efficient)

Start two stacks from opposite ends of arr[]. stack1 starts from the leftmost element, the first element in stack1 is pushed at index 0. The stack2 starts from the rightmost corner, the first element in stack2 is pushed at index (n-1). Both stacks grow (or shrink) in opposite direction. To check for overflow - check for space between top elements of both stacks (see code below)

Time c. for push and pop O(1)
Space c. O(N)

Python

class twoStacks: 
      
    def __init__(self, n): 
        self.size = n 
        self.arr = [None] * n 
        self.top1 = -1
        self.top2 = self.size 
          
    # push element to stack1 
    def push1(self, x): 
          
        # There is at least one empty space for new element 
        if self.top1 < self.top2 - 1 : 
            self.top1 = self.top1 + 1
            self.arr[self.top1] = x 
  
        else: 
            print("Stack Overflow ") 
            exit(1) 
  
    #  push element to stack2 
    def push2(self, x): 
  
        # There is at least one empty space for new element 
        if self.top1 < self.top2 - 1: 
            self.top2 = self.top2 - 1
            self.arr[self.top2] = x 
  
        else : 
           print("Stack Overflow ") 
           exit(1) 
  
    # pop element from stack1 
    def pop1(self): 
        if self.top1 >= 0: 
            x = self.arr[self.top1] 
            self.top1 = self.top1 -1
            return x 
        else: 
            print("Stack Underflow ") 
            exit(1) 
  
    # pop element from stack2 
    def pop2(self): 
        if self.top2 < self.size: 
            x = self.arr[self.top2] 
            self.top2 = self.top2 + 1
            return x 
        else: 
            print("Stack Underflow ") 
            exit()

# Driver program to test twoStacks class 
ts = twoStacks(5) 
ts.push1(5) 
ts.push2(10) 
ts.push2(15) 
ts.push1(11) 
ts.push2(7) 

print('Popped element from stack1 is ' + str(ts.pop1())) 
ts.push2(40) 
print('Popped element from stack2 is ' + str(ts.pop2()))

Next Greater Element with Stack Implementation ((O(n))

Print the Next Greater Element (NGE) for every element of array (-1 if no NGE). NGE - the first greater element on the right side

Push first elem to stack
Pick remaining elems in this loop:

Mark current elem as next.
If stack not empty, compare next with top elem in stack
If next > top elem, pop top elem from stack => next is NGE for the popped elem
Else: keep popping from stack while the popped elem < next => next is NGE for all such popped elems
Finally, push the next into stack

After the loop, pop all the elems from stack and print -1.

Python

# simple solution, O(n^2)
def printNGE(arr): 
  
    for i in range(0, len(arr), 1): 
  
        next = -1
        for j in range(i+1, len(arr), 1): 
            if arr[i] < arr[j]: 
                next = arr[j] 
                break
              
        print(str(arr[i]) + " : " + str(next)) 
        
        
arr = [11,14,21,3] 
printNGE(arr)

Python

# using stack, O(n) 
def createStack(): 
    stack = [] 
    return stack 
  
def isEmpty(stack): 
    return len(stack) == 0
  
def push(stack, x): 
    stack.append(x) 

def pop(stack): 
    if isEmpty(stack): 
        print("Error : stack underflow") 
    else: 
        return stack.pop() 

    
def printNGE(arr):
        
    s = createStack()        
    push(s, arr[0])                                                                   # push first elem  
    
    for i in range(1, len(arr)):                                                      # iterate for remaining
                
        next = arr[i]  
        if not isEmpty(s):  
            
            element = pop(s)                                                          # if stack not empty, pop elem from stack 
  
            '''If popped elem < next, print the pair &
               keep popping while elems < next'''
        
            while element < next : 
                print(str(element)+ " :  " + str(next)) 
                if isEmpty(s): 
                    break
                element = pop(s)  
            
            if  element > next:                                                       # if elem > next, push it back  
                push(s, element)  
        
        push(s, next)                                                                 # push next to stack to find NGE for it    
  
    while not isEmpty(s):                                        # after the loop, the remaining elements in stack have no NGE
            element = pop(s) 
            next = -1
            print(str(element) + " : " + str(next)) 


arr = [11, 14, 21, 3]
printNGE(arr)

Output

Bitwise operators

Python

# BINARY REPRESENTATION
def convert_tobin(n):
    '''
       Convert any number, but 0. Remainder from division by 2 is either 0 or 1 - keep adding them from right to left
       as the first remainder is the least significant bit (LSB) on the right, and the last remainder will be the most
       significant bit on the right
    '''
    if n==0: return ''
    else:
        return binary(n//2) + str(n%2)
    
def binary(m):    
    '''Convert 0; if not 0, use convert_tobin()'''    
    if m==0: return '0'
    else:
        return convert_tobin(m)

print('Decimal  |  Binary')
for i in range(15):
    print('  {}           {}'.format(i, binary(i)))

Output

Decimal  |  Binary
  0           0
  1           01
  2           010
  3           011
  4           0100
  5           0101
  6           0110
  7           0111
  8           01000
  9           01001
  10           01010
  11           01011
  12           01100
  13           01101
  14           01110

RATIONALE

Convert decimal to binary (the leftmost MSB is at the bottom) and the result is '100100110':

Back to decimal: 2**n + 2**(n-1) + 2**(n-2) ... + 2**0 for set bits only (for "1")

For example from the first picture: 2**8 + 2**5 + 2**2 + 2**1 = 294

XOR

"Exclusive or" compares two binary numbers bitwise: both bits the same => 0, if not => 1. Example: 6^3=5 i.e. 110^011=101. For booleans: True=1, False=0 True^False=True. Outputs integer for integers and bollean for booleans. Decimals: 9^0=9, 9^9=0 (the same), 9^9^5=5 - useful for finding a missing value in one of the two arrays

Python

# FIND A MISSING NUMBER
arr1 = [1,2,3,4,5]
arr2 = [1,2,4,5]
res = 0
for i in arr1+arr2:
    res ^= i
print(res)

Python

# FIND A DIFFERENT NUMBER
arr = [5,5,5,4,5]
res = 0
for i in arr:
    res ^= i
print(res)

Python

'100100110'

Other bitwise operators

Python

a = 60            # 60 = 0011 1100 
b = 14            # 13 = 0000 1110 

c = a & b;        # 12 = 0000 1100                      # 0=False, 1=True => False & True = False
print("Line 1 - Value of c is ", c)

c = a | b;        # 62 = 0011 1110                      # False or True = True
print("Line 2 - Value of c is ", c)

c = a ^ b;        # 49 = 0011 0010
print("Line 3 - Value of c is ", c)

c = ~a;           # -61 = 1100 0011                     # not - reverse bit
print("Line 4 - Value of c is ", c)

# The left operand's value is moved left by the number of bits specified by the right operand (void filled with 0s)
c = a << 2;       # 240 = 1111 0000
print("Line 5 - Value of c is ", c, ' : ', bin(c))

# same as above, but to the right
c = a >> 2;       # 15 = 0000 1111
print("Line 6 - Value of c is ", c)

Definition: 1 = set bit, 0 = clear bit.To find if the Nth bit of an integer is set, use a shift operation to check the value of only that one specific bit

Python

# Count number of bits to be flipped to convert A into B 
  
# Function that count set bits 
def countSetBits( n ): 
    count = 0
    while n: 
        count += 1
        n &= (n-1) 
    return count 
      
# Function that return count of flipped number 
def flippedCount(a , b): 
  
    # Return count of set bits in a XOR b 
    return countSetBits(a^b) 
  
a = 10
b = 20
print(flippedCount(a, b))

Number Theory (Geeksforgeeks)

Primality check

School Method: iterate from 2 to n-1, for every number check if it divides n. Time c. O(n)
Optimizations: * Iterate only up until sqrt(n) - larger factor of n must be multiple of smaller factor * Check only 6k ± 1 and 2 & 3 (this covers all primes). All integers can be expressed as (6k + i) for some integer k and for i = -1, 0, 1, 2, 3, or 4; 2 divides (6k + 0), (6k + 2), (6k + 4); and 3 divides (6k + 3)

Python

def isPrime(n) : 
     
    if (n <= 1): # Corner cases
        return False
    if (n <= 3) : 
        return True
      
    if (n % 2 == 0 or n % 3 == 0) : 
        return False
  
    i = 5
    while(i * i <= n) : 
        if (n % i == 0 or n % (i + 2) == 0) : 
            return False
        i = i + 6
  
    return True
  

print('Prime or not?')  
print('11:', isPrime(11))          
print('15:', isPrime(15))
print('23:', isPrime(23))
print('25:', isPrime(25))
print('27:', isPrime(27))

Appendix (disregard)

Reverse a Linked List in groups of given size | Set 1

Given a linked list, write a function to reverse every k nodes (where k is an input to the function).

Example:
Input: 1->2->3->4->5->6->7->8->NULL, K = 3
Output: 3->2->1->6->5->4->8->7->NULL

Input: 1->2->3->4->5->6->7->8->NULL, K = 5
Output: 5->4->3->2->1->8->7->6->NULL

Version 1 - using reverse(LL) function for every k elems
Time c. O(n), space c. O(1)

Version 2 - using stack
Space c. O(k) * push the k elements of LL to stack * pop elems one by one, keep track of prev popped node; point next pointer of prev node to top elem of stack; * reptead until NULL (end of LL)

Python

# Node class 
class Node(object): 
     
    def __init__(self, data = None, next = None): 
        self.data = data 
        self.next = next
  
    def __repr__(self): 
        return repr(self.data) 

class LinkedList(object): 
  
    # initialize head 
    def __init__(self): 
        self.head = None
  
    # print nodes of LL
    def __repr__(self): 
        nodes = [] 
        curr = self.head 
        while curr: 
            nodes.append(repr(curr)) 
            curr = curr.next
        return '[' + ', '.join(nodes) + ']'
  
    # insert a new node at beginning 
    def prepend(self, data): 
        self.head = Node(data = data, 
                         next = self.head) 
  
    # reverse LL in groups of size k, return pointer to new head 
    def reverse(self, k = 1): 
        if self.head is None: 
            return
  
        curr = self.head 
        prev = None
        new_stack = [] 
        while curr is not None: 
            val = 0
                        
            while curr is not None and val < k: 
                new_stack.append(curr.data) 
                curr = curr.next
                val += 1
  
            # pop elems of stack one by one 
            while new_stack: 
                  
                # if final list has not been started yet. 
                if prev is None: 
                    prev = Node(new_stack.pop()) 
                    self.head = prev 
                else: 
                    prev.next = Node(new_stack.pop()) 
                    prev = prev.next
                      
        # next of last elem points to None
        prev.next = None
        return self.head 
    
    
LL = LinkedList()  
LL.prepend(9) 
LL.prepend(8) 
LL.prepend(7) 
LL.prepend(6) 
LL.prepend(5) 
LL.prepend(4) 
LL.prepend(3) 
LL.prepend(2) 
LL.prepend(1) 
  
print('Given LL:')
print(LL) 
LL.head = LL.reverse(3) 
  
print('\nReversed LL:')
print(LL)

Output

Given LL:
[1, 2, 3, 4, 5, 6, 7, 8, 9]

Reversed LL:
[3, 2, 1, 6, 5, 4, 9, 8, 7]

Big-O, Linked Lists, Stacks, Queues & Bitwise

DATA STRUCTURES

BIG O NOTATION

THEORY

Order of magnitude

Phases

Several variables

Recursion

Complexity classes

Lists

Dictionaries

Big-O Cheatsheet

Big O Examples

O(1) Constant

O(n) Linear

O(log n) Logarithmic time

O(n log n) Loglinear or linearithmic time

O(n^2) Quadratic

O(n**a) Polynomial Time Generalized

O(n!) Factorial or combinatorial complexity

The Traveling Salesman

Calculating Scale of Big-O

Worst Case vs Best Case

Space Complexity

Singly Linked List

Doubly Linked List (DLL)

LL manipulations

Get Nth to the last element

Reverse a singly linked list

Check if there is cycle

Break cycle

Insert element into sorted LL

Compare two strings represented as linked lists

Length of linked list

Queue

Dequeue

Stack

20. Balanced parenthesis check (stack)

Queue with two stacks

Stack using two queues

Two stacks in an array (space efficient)

Next Greater Element with Stack Implementation ((O(n))

Bitwise operators

RATIONALE

XOR

Other bitwise operators

Number Theory (Geeksforgeeks)

Primality check

Appendix (disregard)

Reverse a Linked List in groups of given size | Set 1