## Programming

### Math

Probabilities to have two dices with 9

Calculate 2^22 (2^11 * 2^11)

### Fizzbuzz

``````for num in xrange(1,101):
if num % 5 == 0 and num % 3 == 0:
msg = "FizzBuzz"
elif num % 3 == 0:
msg = "Fizz"
elif num % 5 == 0:
msg = "Buzz"
else:
msg = str(num)
print msg
``````

### Trees

#### Detect the mirror of a tree

``````class Node:
def __init__(self, key):
self.key = key
self.left = None
self.right = None

def isMirror(root1 , root2):
if root1 is None and root2 is None:
return True

""" For two trees to be mirror images, the following three
conditions must be true
1 - Their root node's key must be same
2 - left subtree of left tree and right subtree
of right tree have to be mirror images
3 - right subtree of left tree and left subtree
of right tree have to be mirror images
"""
if (root1 is not None and root2 is not None):
if  root1.key == root2.key:
return (isMirror(root1.left, root2.right)and
isMirror(root1.right, root2.left))

# If neither of above conditions is true then root1
# and root2 are not mirror images
return False

def isSymmetric(root):
return isMirror(root, root)

root = Node(1)
root.left = Node(2)
root.right = Node(2)
root.left.left = Node(3)
root.left.right = Node(4)
root.right.left = Node(4)
root.right.right = Node(3)
print "1" if isSymmetric(root) == True else "0"
``````

#### Max Height

``````class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None

def height(n):
if n == None:
return 0

return max(height(n.left), height(n.right)) + 1

node = Node(5)
node.left = Node(8)
node.right = Node(3)
node.left.left = Node(3)
node.left.left.left = Node(22)

print height(node)
``````

#### Serialize and unserialize a tree (not finished)

``````class Node:
def __init__(self, val):
self.left = None
self.right = None
self.val = val
self.str = []

def traverse(self):
list = []

node = [self]

while (len(node) > 0):
val = node.pop()

if val.left != None:
node.push(val.left)

if val.right != None:
node.push(val.right)

if val.left == None and val.right != None:
self.str.push("-1")

if val.left != None and val.right == None:
self.str.push("-1")

self.str.append(val.val)

def decode(self, str):
node = str
stack.append(node)
for i in range(len(str), 1):
if left(str, i) != -1:
appendLeft(stack.pop().left, left(str, i))
stack.append(str[i])
if right(str, i) != -1:
appendRight(stack.pop().right,, node.right, right(str, i)
stack.append(str[i])

def appendLeft(node, left):
node.left = left

def appendRight(node, right):
node.right = right
``````

### Traverse a tree (BFS/DFS)

``````BFS
class Node(object):
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right

def traverse(rootnode):
thislevel = [rootnode]
while thislevel:
nextlevel = list()
for n in thislevel:
print n.value,
if n.left: nextlevel.append(n.left)
if n.right: nextlevel.append(n.right)
print
thislevel = nextlevel

t = Node(1, Node(2, Node(4, Node(7))), Node(3, Node(5), Node(6)))

traverse(t)
``````
``````def get_breadth_first_nodes(root):
nodes = []
stack = [root]
while stack:
cur_node = stack
stack = stack[1:]
nodes.append(cur_node)
for child in cur_node.get_children():
stack.append(child)
return nodes

def get_depth_first_nodes(root):
nodes = []
stack = [root]
while stack:
cur_node = stack
stack = stack[1:]
nodes.append(cur_node)
for child in cur_node.get_rev_children():
stack.insert(0, child)
return nodes

########################################################################
class Node(object):
def __init__(self, id_):
self.id = id_
self.children = []

def __repr__(self):
return "Node: [%s]" % self.id

self.children.append(node)

def get_children(self):
return self.children

def get_rev_children(self):
children = self.children[:]
children.reverse()
return children

########################################################################
def println(text):
sys.stdout.write(text + "\n")

def make_test_tree():
a0 = Node("a0")
b0 = Node("b0")
b1 = Node("b1")
b2 = Node("b2")
c0 = Node("c0")
c1 = Node("c1")
d0 = Node("d0")

return a0

root = make_test_tree()
for node in node_list:
println(str(node))

def test_depth_first_nodes():
root = make_test_tree()
node_list = get_depth_first_nodes(root)
for node in node_list:
println(str(node))

########################################################################
if __name__ == "__main__":
println("")
test_depth_first_nodes()
``````

### Topological Sort

``````def dfs(graph,start):
path = []
stack = [start]
label = len(graph)
result = {}
while stack != []:
for element in stack:
if element not in result:
result[element] = label
label = label – 1
v = stack.pop()
if v not in path: path.append(v)
for w in reversed(graph[v]):
if w not in path and not w in stack:
stack.append(w)
result = {v:k for k, v in result.items()}
return path, result
``````

### Sets

#### Remove duplicates

``````seen = set()
uniq = []
for x in a:
if x not in seen:
uniq.append(x)
``````

#### Detect duplicates in a list

``````l = [1,2,3,4,4,5,5,6,1]
set([x for x in l if l.count(x) > 1])
``````

### Recursion

#### Reverse a string

``````    def reverseString(string):
if len(string)==0:
return string
else:
return string[-1:] + reverseString(string[:-1])
``````

#### Length of a string

``````    def strlen(s):
if s == '':
return 0
return 1 + strlen(s[1:])
``````

#### Count a string

``````def count(s):
if s == '':
return 0
else:
return 1 + count(s[1::])
``````

#### Permutations

``````def permut(array):
if len(array) == 1:
return [array]
res = []
for permutation in permut(array[1:]):
for i in range(len(array)):
res.append(permutation[:i] + array[0:1] + permutation[i:])
return res
``````

### Python

What is the deadlock

Python 2.x vs 2.3

#### Write code to parse generic web logs and format it in different ways

Recursive call of LinkedIn api using REST.

### Java

Mvn

Devops

Parsing a log

REST Interface

#### Lifecycle of an object

As you work with objects in Java, understanding how objects are born, live their lives, and die is important. This topic is called the life cycle of an object, and it goes something like this:

1. Before an object can be created from a class, the class must be loaded. To do that, the Java runtime locates the class on disk (in a .class file) and reads it into memory. Then Java looks for any static initializers that initialize static fields — fields that don’t belong to any particular instance of the class, but rather belong to the class itself and are shared by all objects created from the class.

A class is loaded the first time you create an object from the class or the first time you access a static field or method of the class. For example, when you run the main method of a class, the class is initialized because the main method is static.

1. An object is created from a class when you use the new keyword. To initialize the class, Java allocates memory for the object and sets up a reference to the object so the Java runtime can keep track of it. Then, Java calls the class constructor, which is like a method but is called only once, when the object is created. The constructor is responsible for doing any processing required to initialize the object, such as initializing variables, opening files or databases, and so on.

2. The object lives its life, providing access to its public methods and fields to whoever wants and needs them.

3. When it’s time for the object to die, the object is removed from memory and Java drops its internal reference to it. You don’t have to destroy objects yourself. A special part of the Java runtime called the garbage collector takes care of destroying all objects when they are no longer in use.

### Big O Notation

#### Between red black trees, binary tree, linked list, hash table, btree, what is doesn't have to be nlogn

Btree (doesn't have to be balanced), Hash Table and LinkedList.

#### Array of 10000 having 16bit elements, find bits set (unlimited RAM)

Brute force: 10000 * 16 * 4 = 640,000 ops. (shift, compare, increment and iteration for each 16 bits word)

Faster way:

We can build table 00-FF -> number of bits set. 256 * 8 * 4 = 8096 ops

I.e. we build a table where for each byte we calculate a number of bits set.

Then for each 16-bit int we split it to upper and lower

``````for (n in array) {
byte lo = n & 0xFF; // lower 8-bits
byte hi = n >> 8; // higher 8-bits
// simply add number of bits in the upper and lower parts
// of each 16-bits number
// using the pre-calculated table
k += table[lo] + table[hi];
}
``````

60000 ops in total in the iteration. I.e. 68096 ops in total. It's O(n) though, but with less constant (~9 times less).

In other words, we calculate number of bits for every 8-bits number, and then split each 16-bits number into two 8-bits in order to count bits set using the pre-built table.

### How do you implement a Priority Queue

While priority queues are often implemented with heaps, they are conceptually distinct from heaps. A priority queue is an abstract concept like "a list" or "a map"; just as a list can be implemented with a linked list or an array, a priority queue can be implemented with a heap or a variety of other methods such as an unordered array.

### When does the worst case of Quicksort occur?

The answer depends on strategy for choosing pivot. In early versions of Quick Sort where leftmost (or rightmost) element is chosen as pivot, the worst occurs in following cases.

1) Array is already sorted in same order.
2) Array is already sorted in reverse order.
3) All elements are same (special case of case 1 and 2)

Implement merge sort (merging two lists)

Is it possible inplace?

Why people implement quicksort even heapsort is better in some cases?

### Quicksort

``````from random import randrange
​
def partition(list, start, end, pivot):
list[pivot], list[end] = list[end], list[pivot]
store_index = start

for i in xrange(start, end):
if list[i] < list[end]:
list[i], list[store_index] = list[store_index], list[i]
store_index += 1

list[store_index], list[end] = list[end], list[store_index]

return store_index
​
def quick_sort(list, start, end):
if start >= end:
return list

pivot = randrange(start, end + 1)
new_pivot = partition(list, start, end, pivot)
quick_sort(list, start, new_pivot - 1)
quick_sort(list, new_pivot + 1, end)
​
def sort(list):
quick_sort(list, 0, len(list) - 1)
return list
​
print sort([])
print sort([1,2,3,4])
print sort([2,3,4,1])
print sort([2,3,4,1, 5, -2])

W
[]
2 3
Store index 2
1 1
Store index 1
[1, 2, 4, 3]
1 3
Store index 2
1 1
Store index 0
[2, 1, 4, 3]

>>>

Alejandro Sanchez ran 36 lines of Python 2 (finished in 557ms):

[]
0 3
Store index 0
1 3
Store index 1
3 3
Store index 3
[4, 4, 3, 4]
0 3
Store index 1
2 3
Store index 3
[1, 3, 3, 4]

>>>

Alejandro Sanchez ran 34 lines of Python 2 (finished in 564ms):

[]
[2, 2, 4, 4]
[1, 2, 4, 4]

>>>

Alejandro Sanchez ran 35 lines of Python 2 (finished in 594ms):

[]
[2, 2, 4, 4]
[2, 2, 4, 4]
[1, 1, 1, 5, 5, 7]

>>>

Alejandro Sanchez ran 34 lines of Python 2 (finished in 720ms):

[]
[1, 2, 3, 4]
[1, 2, 3, 4]

>>>

Alejandro Sanchez ran 35 lines of Python 2 (finished in 876ms):

[]
[1, 2, 3, 4]
[1, 2, 3, 4]
[-2, 1, 2, 3, 4, 5]

>>>
``````

## Calculate the throughput in (b/s) for a particular ip (e.g. 10.4.3.34)

0, 30, 3874, 10.4.3.34

0, 30, 324235, 10.4.3.32

0, 30, 324235, 10.4.3.38

10, 30, 324235, 10.4.3.34

10, 30, 324235, 10.4.3.34

10, 30, 324, 10.4.3.34

10, 30, 324235, 10.4.3.34

Log is 50K lines long

``````START_TIME,END_TIME,FILE_SIZE,IP_ADDRESS

0, 30, 3874, 10.4.3.34
0, 30, 324235, 10.4.3.32
0, 30, 324235, 10.4.3.38
10, 30, 324235, 10.4.3.34
10, 30, 324235, 10.4.3.34
10, 30, 324, 10.4.3.34
10, 30, 324235, 10.4.3.34

Log is 50K lines long

throughput = {}

with open ('times.log') as f:
for line in f:
data = line.split(",")
initial = data
end = data
size = data
ip = data

bpers = size / (end - initial)

if throughput.has_key(ip):
throughput[ip] += bpers
else
throughput[ip] = bpers

for k,v in throughput.items():
print k,v
``````