# Binary search tree using and check if a given tree is binary serach tree Python

”’

Created on Aug 11, 2015

@author: ishaansutaria

”’

class Node():

”’

Initialize a node with the data

with both their childreen being null

”’

def __init__(self,data):

self.data = data

self.left = None

self.right = None

”’

Using recursion

1) If root is less/greater than data and null insert right/left.(return)

2) Else if right/left node is not null call the function again with right/left node as root

”’

def insertData(self,data):

if self.data < data:

if self.right == None:

self.right = Node(data)

else:

self.right.insertData(data)

elif self.data > data:

if self.left == None:

self.left = Node(data)

else:

self.left.insertData(data)

”’

You need to traverse the list(in-order)

Go to the leftmost node in the tree and print it

Check if the node has right node and get to the leftmost node of that node

and print the list.

1) Check if root has a left child

2) If yes call the function with the left child as the root node.

3) print the root value

4) Check if the root has right child

5) If yes then call the function with the right child as the root

”’

def printBinaryList(self):

if self.left != None:

self.left.printBinaryList()

print self.data

if self.right != None:

self.right.printBinaryList()

”’

Recursion:

1) Check if the root node matches the value is yes then return

2) Else check if data to be found is less/greater than the root node.

3) If yes/no call the function again with the left/right child as the root node.

”’

def serachBinaryTree(self,data):

if self.data == data:

print ‘found’

return data

if self.data > data:

if self.left != None:

return self.left.serachBinaryTree(data)

if self.data < data:

if self.right != None:

return self.right.serachBinaryTree(data)

”’

Helper function for deleting a node

Returns the number of childs a node has

”’

def countChildreen(self):

count = 0

if self.left:

count +=1

if self.right:

count +=1

return count

”’

”’

def delNode(self,data,parent=None):

if self.data == data:

if parent.data > data:

self.right = self.left

parent.left = self.right

print ‘found’

return data

if self.data > data:

if self.left != None:

return self.left.serachBinaryTree(data,self)

if self.data < data:

if self.right != None:

return self.right.serachBinaryTree(data,self)

”’

Traverse a node in-order and append the values you print in an array.

Check if the array and its sorted version are the same.

(Here you can also use compare with the prev node removing the need to have an

extra array)

”’

def checkBinaryTree(self):

temp = []

stack = []

while True:

while self != None:

temp.append(self)

self = self.left

if len(temp) == 0:

break

self = temp.pop()

stack.append(self.data)

while self.right != None and len(temp) != 0:

self = temp.pop()

#print  self.data

stack.append(self.data)

self = self.right

break

if sorted(stack) == stack:

print ‘Binary tree’

else:

print ‘Not a binary tree’

root = Node(5)

root.insertData(8)

root.insertData(9)

root.insertData(6)

root.insertData(5)

#root.printBinaryList()

root.checkBinaryTree()

print root.serachBinaryTree(8)

# Rest API Design guidelines and best practices

When designing an api you should think about

• naming
• Proper http verbs and response codes for different CRUD operations

General guidelines to keep in mind:

-> Always prefer to use lowercase characters in uri’s. A forward slash should be used to indicate a hierarchical relationship. Also a trailing forward slash should be not be included. Hyphens (-) can be used for better readability but underscores ( _ ) should not be used.

Note: File extensions like ‘json’ or ‘xml’ should not be used to indicate a format preference. You should look at the ‘Content-Type’ header to determine how to process the body’s content.

-> The uri path should convey the resource model with each segment path identifying an addressable resource.

-> The actual words in the path should either be a singular ,plural  noun or a verb.

Note: Do not use CRUD function names in the uri’s. You can use the query component of the uri for pagination.

HTTP

-> GET and POST must not be used to tunnel other request methods

->  POST must be used to execute controllers

Response Codes:

 200 (OK) Non-specific Success.Must not be used to communicate errors in response body. 201 (OK) Successful resource creation. 204 (No content) Used when response body is intentionally empty 301(“Moved Permanently”) Should be used to relocate resources 302 (“Found”) Should not be used 303 (“See Other”) Should be used to refer the client to a different URI 307 (“Temporary Redirect”) Should be used to tell clients to resubmit the request to another URI 400 (“Bad Request”) Used to indicate nonspecific failure 401 (“Unauthorized”) Used when there is a problem with the client’s credentials 403 (“Forbidden”) Used to forbid access regardless of authorization state 404 (“Not Found”) Used when a client’s URI cannot be mapped to a resource 405 (“Method Not Allowed”) Used when the HTTP method is not supported 406 (“Not Acceptable”) Used when the requested media type cannot be served 415 (“Unsupported Media Type”) Used when the media type of a request’s payload cannot be processed 500 (“Internal Server Error”) Used to indicate API malfunction

-> Content-Type, Content-Length should be used

Note: Cache-Control, Expires, and Date response headers should be used to encourage caching.Expiration caching headers should be used with 200 (“OK”) responses

-> Custom HTTP headers must not be used to change the behavior of HTTP methods

Error Representation

A consistent form should be used to represent errors and error responses.Consistent error types should be used for common error conditions.

# Bitwise AND between a range of integers

Problem Statement

You will be given two integers A and B. You are required to compute the bitwise AND amongst all natural numbers lying between A and B, both inclusive.

”’
Since & is only 1 when both are 1 and when calculating in a range if the range ends do not both have 1 the rest of the whole binary is 0

The only bits that will be 1 will be bits that are common to the upper bits of A and B. Everything else will have at least one instance of a 0 in that range. So just start from the high order bit downwards. Output the matching bits. As soon as you hit a disagreement between the binaries of A and B (which will be 0 in A and 1 in B) output zeros until you get to the length of B.

”’
def bitAndWholeArray(arr):
string1 = bin(arr[0])
string2 = bin(arr[1])
index_count = 0
res = ‘0b’
for index,i in enumerate(string1):
if index == 0 or index == 1:
continue
if i == string2[index]:
res = res + i
else:
index_count = index
break

for _ in range(index_count,len(string2)):
res = res + ‘0’

return int(res,2)
n = int(raw_input())
for _ in range(n):
arr = map(int,raw_input().split(‘ ‘))
print bitAndWholeArray(arr)

# Find the maximum sub array

def maxSubArray(arr):
final_max = cur_max = arr[0]
for i in arr[1:]:
cur_max = max(i,cur_max + i)
final_max = max(final_max,cur_max)

return final_max

# Find the majority element in an array

”’

1) take the maj element as x

2) Loop through the array and

– Increment counter if x

– Decrement counter if not x

– If counter 0 the maj element is the new element

”’

def checkMajorityElement(arr):

x = arr[0]

count = 1

for i,index in enumerate(arr):

if index == 1:

continue

if i == x:

count = count +  1

else:

count = count – 1

return x

# Convert to 24 hour time format

”’

Created on Jun 17, 2015

@author: ishaansutaria

”’

def convert24HourFormat(time_str):

time_str = time_str.upper()

time_24 =

if ‘PM’ in time_str and ’12’ in time_str:

time_24 = time_str

elif ‘PM’ in time_str:

temp_list = time_str.split(‘:’)

time_24 = time_24 + str(int(temp_list[0]) + 12)

time_24 = time_24 + ‘:’ + temp_list[1] + ‘:’ + temp_list[2]

elif ‘AM’ in time_str and ’12’ in time_str:

temp_list = time_str.split(‘:’)

time_24 = time_24 + ‘0’ + str(int(temp_list[0]) – 12)

time_24 = time_24 + ‘:’ + temp_list[1] + ‘:’ + temp_list[2]

else:

time_24 = time_str

print time_24[:-2]

convert24HourFormat(’12:45:54PM’)

# Print a staircase

Example Output:

#

##

###

####

#####

######

def staircase(n):

for j in range(n-1,-1,-1):

s =

for i in xrange(n):

if i >= j:

s = s + ‘#’

else:

s = s + ‘ ‘

print s

staircase(6)