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)

            

Advertisements

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
  • Think about versioning.

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

-> HEAD should be used to retrieve response headers

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

HTTP Headers:

-> 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 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)