Search This Blog

Thursday, March 27, 2014

Design an algorithm and write code to find the first common ancestor of two nodes in a binary tree. Avoid storing additional nodes in a data structure. NOTE: This is not necessarily a binary search tree.



If this were a binary search tree, we could do a modified find on the two nodes and see where the paths diverge. Unfortunately, this is not a binary search tree, so we much try other ap- proaches. 

Attempt #1:
If each node has a link to its parent, we could trace p and q’s paths up until they intersect. 

Attempt #2:
Alternatively, you could follow a chain in which p and q are on the same side. That is, if p and q are both on the left of the node, branch left to look for the common ancestor. When p and q are no longer on the same side, you must have found the first common ancestor. 

__author__ = 'nitin'

def common_ancestor(root,node_p,node_q):
    if covers(root.getLeftChild(),node_p) and covers(root.getLeftChild(),node_q):
        return common_ancestor(root.getLeftChild(),node_p,node_q)
    if covers(root.getRightChild(),node_p) and covers(root.getRightChild(),node_q):
        return common_ancestor(root.getRightChild(),node_p,node_q)
    return root

def covers(root,node_p):
    if root is None:
        return False
    if root ==node_p:
        return True
    return covers(root.getLeftChild(),node_p) or covers(root.getRightChild(),node_p)
 

Write an algorithm to find the ‘next’ node (e.g., in-order successor) of a given node in a binary search tree where each node has a link to its parent.

__author__ = 'nitin'

def find_inorder_succ(node):
    if node is not None:
        if node.getRootVal() is None and node.getRightChild() is not None:
            p=left_most_child(node.getRightChild())
        else:
            p=node
            while p.getRootVal() is not None:
                if p.getLeftChild()==node:
                    break
                node=node.getRootVal()
                p=node
        return p
    return None

def left_most_child(node):
    if node is None:
        return None
    while node.getLeftChild() is not None:
        node=node.getLeftChild()
    return node

Inspiring Lines...!!!

Today gentlemen, I am honored to coach you

More honored to be leading you onto the field of battle

But theres another honor to be bestowed upon you

And that is in the answer that comes with that question:

Who am I? I AM A CHAMPION!

Thats right, and you need to remember that all through this game

I will conquer what has not been conquered

Defeat will not be in my creed

I will believe what others have doubted

I will always endeavor to pull esteem, honor, and respect out of my team

I have trained my mind and my body will follow

Who am I? I AM A CHAMPION!

I will acknowledge the fact that my opponent does not expect me to win

But I will never surrender

Weakness will not be in my heart

I will look to my comrades and to those who are a part of me in this world and those who have trained

me

And I will draw strength from them

Who am I? I AM A CHAMPION!

I will gladly go out into the field of battle

And I will move in everything I can do

And I will reach my field of battle by any means at my disposal

And when I get there, I will arrive violently

I will rip the heart from my enemy, and leave it bleeding on the ground

Because he cannot stop me

Who am I? I AM A CHAMPION!

To my side I have comrades, comrades that have been with me through thick and thin

Who have sacrificed their blood, sweat and tears

Never will I let them fall, never will I let them down, and I will never leave an enemy behind

Because our opponent does not know my heart

Who am I? I AM A CHAMPION!

No one will deny me, no one will define me

And no one will tell me who and what I am and can be

Belief will change my world

It has moved continents, it has moved countries, it has put men on the moon

And it will carry me through this battle

Who am I? I AM A CHAMPION!

Defeat, retreat: those are not in my words

I dont understand those definitions

I dont understand when things go wrong

I dont understand mistakes

But I do understand this:

I understand victory,

And I understand never surrendering

No matter how bad things go my heart and my mind will carry my body through limits and weakness

Who am I? I AM A CHAMPION!

Today will be that day

Not tomorrow, not next week, but right now, right here

In your house and in your homes

Who am I? I AM A CHAMPION!

History will remember me

I will not let worrying affect my cause

I will define myself

I will write my own pages

And no one will tell me what I cannot be

I will never give up

Not until Ive given everything I got

Because who am I? I AM A CHAMPION!

Who am I? I AM A CHAMPION!

Who am I? I AM A CHAMPION!

Who am I? I AM A CHAMPION!

Who am I? I AM A CHAMPION!

Who am I? I AM A CHAMPION!

Who am I? I AM A CHAMPION!

Who am I? I AM A CHAMPION!

Who am I? I AM A CHAMPION!

========================

ENOUGH SAID!!!

LEAD FROM THE FRONT!

Awk Introduction Tutorial – 7 Awk Print Examples

Awk Introduction and Printing Operations

Awk is a programming language which allows easy manipulation of structured data and the generation of formatted reports. Awk stands for the names of its authors “Aho, Weinberger, and Kernighan”
The Awk is mostly used for pattern scanning and processing. It searches one or more files to see if they contain lines that matches with the specified patterns and then perform associated actions.
Some of the key features of Awk are:
  • Awk views a text file as records and fields.
  • Like common programming language, Awk has variables, conditionals and loops
  • Awk has arithmetic and string operators.
  • Awk can generate formatted reports
Awk reads from a file or from its standard input, and outputs to its standard output. Awk does not get along with non-text files.
Syntax:

awk '/search pattern1/ {Actions}
     /search pattern2/ {Actions}' file
In the above awk syntax:
  • search pattern is a regular expression.
  • Actions – statement(s) to be performed.
  • several patterns and actions are possible in Awk.
  • file – Input file.
  • Single quotes around program is to avoid shell not to interpret any of its special characters.

Awk Working Methodology

  1. Awk reads the input files one line at a time.
  2. For each line, it matches with given pattern in the given order, if matches performs the corresponding action.
  3. If no pattern matches, no action will be performed.
  4. In the above syntax, either search pattern or action are optional, But not both.
  5. If the search pattern is not given, then Awk performs the given actions for each line of the input.
  6. If the action is not given, print all that lines that matches with the given patterns which is the default action.
  7. Empty braces with out any action does nothing. It wont perform default printing operation.
  8. Each statement in Actions should be delimited by semicolon.
Let us create employee.txt file which has the following content, which will be used in the
examples mentioned below.
$cat employee.txt
100  Thomas  Manager    Sales       $5,000
200  Jason   Developer  Technology  $5,500
300  Sanjay  Sysadmin   Technology  $7,000
400  Nisha   Manager    Marketing   $9,500
500  Randy   DBA        Technology  $6,000

Awk Example 1. Default behavior of Awk

By default Awk prints every line from the file.
$ awk '{print;}' employee.txt
100  Thomas  Manager    Sales       $5,000
200  Jason   Developer  Technology  $5,500
300  Sanjay  Sysadmin   Technology  $7,000
400  Nisha   Manager    Marketing   $9,500
500  Randy   DBA        Technology  $6,000
In the above example pattern is not given. So the actions are applicable to all the lines.
Action print with out any argument prints the whole line by default. So it prints all the
lines of the file with out fail. Actions has to be enclosed with in the braces.

Awk Example 2. Print the lines which matches with the pattern.

$ awk '/Thomas/
> /Nisha/' employee.txt
100  Thomas  Manager    Sales       $5,000
400  Nisha   Manager    Marketing   $9,500
In the above example it prints all the line which matches with the ‘Thomas’ or ‘Nisha’. It has two patterns. Awk accepts any number of patterns, but each set (patterns and its corresponding actions) has to be separated by newline.

Awk Example 3. Print only specific field.

Awk has number of built in variables. For each record i.e line, it splits the record delimited by whitespace character by default and stores it in the $n variables. If the line has 4 words, it will be stored in $1, $2, $3 and $4. $0 represents whole line. NF is a built in variable which represents total number of fields in a record.
$ awk '{print $2,$5;}' employee.txt
Thomas $5,000
Jason $5,500
Sanjay $7,000
Nisha $9,500
Randy $6,000

$ awk '{print $2,$NF;}' employee.txt
Thomas $5,000
Jason $5,500
Sanjay $7,000
Nisha $9,500
Randy $6,000
In the above example $2 and $5 represents Name and Salary respectively. We can get the Salary using  $NF also, where $NF represents last field. In the print statement ‘,’ is a concatenator.

Awk Example 4. Initialization and Final Action

Awk has two important patterns which are specified by the keyword called BEGIN and END.
Syntax: 

BEGIN { Actions}
{ACTION} # Action for everyline in a file
END { Actions }

# is for comments in Awk
Actions specified in the BEGIN section will be executed before starts reading the lines from the input.
END actions will be performed after completing the reading and processing the lines from the input.
$ awk 'BEGIN {print "Name\tDesignation\tDepartment\tSalary";}
> {print $2,"\t",$3,"\t",$4,"\t",$NF;}
> END{print "Report Generated\n--------------";
> }' employee.txt
Name Designation Department Salary
Thomas   Manager   Sales           $5,000
Jason   Developer   Technology   $5,500
Sanjay   Sysadmin   Technology   $7,000
Nisha   Manager   Marketing   $9,500
Randy   DBA     Technology   $6,000
Report Generated
--------------
In the above example, it prints headline and last file for the reports.

Awk Example 5. Find the employees who has employee id greater than 200

$ awk '$1 >200' employee.txt
300  Sanjay  Sysadmin   Technology  $7,000
400  Nisha   Manager    Marketing   $9,500
500  Randy   DBA        Technology  $6,000
In the above example, first field ($1) is employee id. So if $1 is greater than 200, then just do the default print action to print the whole line.

Awk Example 6. Print the list of employees in Technology department

Now department name is available as a fourth field, so need to check if $4 matches with the string “Technology”, if yes print the line.
$ awk '$4 ~/Technology/' employee.txt
200  Jason   Developer  Technology  $5,500
300  Sanjay  Sysadmin   Technology  $7,000
500  Randy   DBA        Technology  $6,000
Operator ~ is for comparing with the regular expressions. If it matches the default action i.e print whole line will be  performed.

Awk Example 7. Print number of employees in Technology department

The below example, checks if the department is Technology, if it is yes, in the Action, just increment the count variable, which was initialized with zero in the BEGIN section.
$ awk 'BEGIN { count=0;}
$4 ~ /Technology/ { count++; }
END { print "Number of employees in Technology Dept =",count;}' employee.txt
Number of employees in Tehcnology Dept = 3
Then at the end of the process, just print the value of count which gives you the number of employees in Technology department.

8 Powerful Awk Built-in Variables – FS, OFS, RS, ORS, NR, NF, FILENAME, FNR

There are two types of built-in variables in Awk.
  1. Variable which defines values which can be changed such as field separator and record separator.
  2. Variable which can be used for processing and reports such as Number of records, number of fields.

1. Awk FS Example: Input field separator variable.

Awk reads and parses each line from input based on whitespace character by default and set the variables $1,$2 and etc. Awk FS variable is used to set the field separator for each record. Awk FS can be set to any single character or regular expression. You can use input field separator using one of the following two options:
  1. Using -F command line option.
  2. Awk FS can be set like normal variable.
Syntax:

$ awk -F 'FS' 'commands' inputfilename

(or)

$ awk 'BEGIN{FS="FS";}'
  • Awk FS is any single character or regular expression which you want to use as a input field separator.
  • Awk FS can be changed any number of times, it retains its values until it is explicitly changed. If you want to change the field separator, its better to change before you read the line. So that change affects the line what you read.
Here is an awk FS example to read the /etc/passwd file which has “:” as field delimiter.
$ cat etc_passwd.awk
BEGIN{
FS=":";
print "Name\tUserID\tGroupID\tHomeDirectory";
}
{
 print $1"\t"$3"\t"$4"\t"$6;
}
END {
 print NR,"Records Processed";
}
$awk -f etc_passwd.awk /etc/passwd
Name    UserID  GroupID        HomeDirectory
gnats 41 41 /var/lib/gnats
libuuid 100 101 /var/lib/libuuid
syslog 101 102 /home/syslog
hplip 103 7 /var/run/hplip
avahi 105 111 /var/run/avahi-daemon
saned 110 116 /home/saned
pulse 111 117 /var/run/pulse
gdm 112 119 /var/lib/gdm
8 Records Processed

2. Awk OFS Example: Output Field Separator Variable

Awk OFS is an output equivalent of awk FS variable. By default awk OFS is a single space character. Following is an awk OFS example.
$ awk -F':' '{print $3,$4;}' /etc/passwd
41 41
100 101
101 102
103 7
105 111
110 116
111 117
112 119
Concatenator in the print statement “,” concatenates two parameters with a space which is the value of awk OFS by default. So, Awk OFS value will be inserted between fields in the output as shown below.
$ awk -F':' 'BEGIN{OFS="=";} {print $3,$4;}' /etc/passwd
41=41
100=101
101=102
103=7
105=111
110=116
111=117
112=119

3. Awk RS Example: Record Separator variable

Awk RS defines a line. Awk reads line by line by default.
Let us take students marks are stored in a file, each records are separated by double new line, and each fields are separated by a new line character.
$cat student.txt
Jones
2143
78
84
77

Gondrol
2321
56
58
45

RinRao
2122
38
37
65

Edwin
2537
78
67
45

Dayan
2415
30
47
20
Now the below Awk script prints the Student name and Rollno from the above input file.
$cat student.awk
BEGIN {
 RS="\n\n";
 FS="\n";

}
{
 print $1,$2;
}

$ awk -f student.awk  student.txt
Jones 2143
Gondrol 2321
RinRao 2122
Edwin 2537
Dayan 2415
In the script student.awk, it reads each student detail as a single record,because awk RS has been assigned to double new line character and each line in a record is a field, since FS is newline character.

4. Awk ORS Example: Output Record Separator Variable

Awk ORS is an Output equivalent of RS. Each record in the output will be printed with this delimiter. Following is an awk ORS example:
$  awk 'BEGIN{ORS="=";} {print;}' student-marks
Jones 2143 78 84 77=Gondrol 2321 56 58 45=RinRao 2122 38 37 65=Edwin 2537 78 67 45=Dayan 2415 30 47 20=
In the above script,each records in the file student-marks file is delimited by the character “=”.

5. Awk NR Example: Number of Records Variable

Awk NR gives you the total number of records being processed or line number. In the following awk NR example, NR variable has line number, in the END section awk NR tells you the total number of records in a file.
$ awk '{print "Processing Record - ",NR;}END {print NR, "Students Records are processed";}' student-marks
Processing Record -  1
Processing Record -  2
Processing Record -  3
Processing Record -  4
Processing Record -  5
5 Students Records are processed

6. Awk NF Example: Number of Fields in a record

Awk NF gives you the total number of fields in a record. Awk NF will be very useful for validating whether all the fields are exist in a record.
Let us take in the student-marks file, Test3 score is missing for to students as shown below.
$cat student-marks
Jones 2143 78 84 77
Gondrol 2321 56 58 45
RinRao 2122 38 37
Edwin 2537 78 67 45
Dayan 2415 30 47
The following Awk script, prints Record(line) number, and number of fields in that record. So It will be very simple to find out that Test3 score is missing.
$ awk '{print NR,"->",NF}' student-marks
1 -> 5
2 -> 5
3 -> 4
4 -> 5
5 -> 4

7. Awk FILENAME Example: Name of the current input file

FILENAME variable gives the name of the file being read. Awk can accept number of input files to process.
$ awk '{print FILENAME}' student-marks
student-marks
student-marks
student-marks
student-marks
student-marks
In the above example, it prints the FILENAME i.e student-marks for each record of the input file.

8. Awk FNR Example: Number of Records relative to the current input file

When awk reads from the multiple input file, awk NR variable will give the total number of records relative to all the input file. Awk FNR will give you number of records for each input file.
$ awk '{print FILENAME, FNR;}' student-marks bookdetails
student-marks 1
student-marks 2
student-marks 3
student-marks 4
student-marks 5
bookdetails 1
bookdetails 2
bookdetails 3
bookdetails 4
bookdetails 5
In the above example, instead of awk FNR, if you use awk NR, for the file bookdetails the you will get from 6 to 10 for each record.

Wednesday, March 26, 2014

Given a binary search tree, design an algorithm which creates a linked list of all the nodes at each depth (i.e., if you have a tree with depth D, you’ll have D linked lists).

__author__ = 'nitin'

class BinaryTree:
    def __init__(self,rootObj):
        self.key = rootObj
        self.leftChild = None
        self.rightChild = None

    def insertLeft(self,newNode):
        if self.leftChild == None:
            self.leftChild = BinaryTree(newNode)
        else:
            t = BinaryTree(newNode)
            t.leftChild = self.leftChild
            self.leftChild = t

    def insertRight(self,newNode):
        if self.rightChild == None:
            self.rightChild = BinaryTree(newNode)
        else:
            t = BinaryTree(newNode)
            t.rightChild = self.rightChild
            self.rightChild = t

    def getRightChild(self):
        return self.rightChild

    def getLeftChild(self):
        return self.leftChild

    def setRootVal(self,obj):
        self.key = obj

    def getRootVal(self):
        return self.key

def max_depth(root):
    if root is None:
        return 0
    else:
        return 1 + max(max_depth(root.getLeftChild()),max_depth(root.getRightChild()))

def find_level_list(root):
    level=0
    depth=max_depth(root)
    print depth
    result=[[] for x in xrange(depth)]
    tmp_list=[]
    tmp_list.append(root)
    result[level]=tmp_list
    while True:
        tmp_list=[]
        i=0
        while i            n=result[level][i]
            if n is not None:
                if n.getLeftChild() is not None:
                    tmp_list.append(n.getLeftChild())
                if n.getRightChild() is not None:
                    tmp_list.append(n.getRightChild())
            i=i+1
        if len(tmp_list)>0:
            result[level+1]=tmp_list
        else:
            break
        level=level +1
    return result

r = BinaryTree('a')
r.insertLeft('b')
r.insertRight('c')
r.insertLeft('d')

print find_level_list(r)

Tuesday, March 25, 2014

Given a sorted (increasing order) array, write an algorithm to create a binary tree with minimal height.

__author__ = 'nitin'

class BinaryTree:
    def __init__(self,rootObj):
        self.key = rootObj
        self.leftChild = None
        self.rightChild = None

    def insertLeft(self,newNode):
        if self.leftChild == None:
            self.leftChild = BinaryTree(newNode)
        else:
            t = BinaryTree(newNode)
            t.leftChild = self.leftChild
            self.leftChild = t

    def insertRight(self,newNode):
        if self.rightChild == None:
            self.rightChild = BinaryTree(newNode)
        else:
            t = BinaryTree(newNode)
            t.rightChild = self.rightChild
            self.rightChild = t

    def getRightChild(self):
        return self.rightChild

    def getLeftChild(self):
        return self.leftChild

    def setRootVal(self,obj):
        self.key = obj

    def getRootVal(self):
        return self.key

def add_to_tree(alist,start,end):
    if end        return None
    mid=(start+end)/2
    n=BinaryTree(mid)
    n.insertLeft(add_to_tree(alist,start,mid-1))
    n.insertRight(add_to_tree(alist,mid+1,end))
    return n

def create_minimal_bst(alist):
    return add_to_tree(alist,0,len(alist)-1)

alist=[2,5,7,9,12,14,21,33,43,55,67,88]
print create_minimal_bst(alist)

Implement a function to check if a tree is balanced. For the purposes of this question, a balanced tree is defined to be a tree such that no two leaf nodes differ in distance from the root by more than one.

__author__ = 'nitin'

class BinaryTree:
    def __init__(self,rootObj):
        self.key = rootObj
        self.leftChild = None
        self.rightChild = None

    def insertLeft(self,newNode):
        if self.leftChild == None:
            self.leftChild = BinaryTree(newNode)
        else:
            t = BinaryTree(newNode)
            t.leftChild = self.leftChild
            self.leftChild = t

    def insertRight(self,newNode):
        if self.rightChild == None:
            self.rightChild = BinaryTree(newNode)
        else:
            t = BinaryTree(newNode)
            t.rightChild = self.rightChild
            self.rightChild = t

    def getRightChild(self):
        return self.rightChild

    def getLeftChild(self):
        return self.leftChild

    def setRootVal(self,obj):
        self.key = obj

    def getRootVal(self):
        return self.key

def max_depth(root):
    if root is None:
        return 0
    else:
        return 1 + max(max_depth(root.getLeftChild()),max_depth(root.getRightChild()))

def min_depth(root):
    if root is None:
        return 0
    else:
        return 1 + min(min_depth(root.getLeftChild()),min_depth(root.getRightChild()))

def is_balanced(root):
    result=max_depth(root) - min_depth(root)
    if result>1:
        return False
    else:
        return True

r = BinaryTree('a')
r.insertLeft('b')
r.insertRight('c')
r.insertLeft('d')
r.insertLeft('e')
r.insertLeft('f')
r.insertLeft('g')
r.insertLeft('h')

print is_balanced(r)

Binary Search Tree Implementation in Python

__author__ = 'nitin'

class TreeNode:
    def __init__(self,key,val,left=None,right=None,parent=None):
        self.key = key
        self.payload = val
        self.leftChild = left
        self.rightChild = right
        self.parent = parent

    def hasLeftChild(self):
        return self.leftChild

    def hasRightChild(self):
        return self.rightChild

    def isLeftChild(self):
        return self.parent and self.parent.leftChild == self

    def isRightChild(self):
        return self.parent and self.parent.rightChild == self

    def isRoot(self):
        return not self.parent

    def isLeaf(self):
        return not (self.rightChild or self.leftChild)

    def hasAnyChildren(self):
        return self.rightChild or self.leftChild

    def hasBothChildren(self):
        return self.rightChild and self.leftChild

    def replaceNodeData(self,key,value,lc,rc):
        self.key = key
        self.payload = value
        self.leftChild = lc
        self.rightChild = rc
        if self.hasLeftChild():
            self.leftChild.parent = self
        if self.hasRightChild():
            self.rightChild.parent = self


class BinarySearchTree:

    def __init__(self):
        self.root = None
        self.size = 0

    def length(self):
        return self.size

    def __len__(self):
        return self.size

    def put(self,key,val):
        if self.root:
            self._put(key,val,self.root)
        else:
            self.root = TreeNode(key,val)
        self.size = self.size + 1

    def _put(self,key,val,currentNode):
        if key < currentNode.key:
            if currentNode.hasLeftChild():
                   self._put(key,val,currentNode.leftChild)
            else:
                   currentNode.leftChild = TreeNode(key,val,parent=currentNode)
        else:
            if currentNode.hasRightChild():
                   self._put(key,val,currentNode.rightChild)
            else:
                   currentNode.rightChild = TreeNode(key,val,parent=currentNode)

    def __setitem__(self,k,v):
       self.put(k,v)

    def get(self,key):
       if self.root:
           res = self._get(key,self.root)
           if res:
                  return res.payload
           else:
                  return None
       else:
           return None

    def _get(self,key,currentNode):
       if not currentNode:
           return None
       elif currentNode.key == key:
           return currentNode
       elif key < currentNode.key:
           return self._get(key,currentNode.leftChild)
       else:
           return self._get(key,currentNode.rightChild)

    def __getitem__(self,key):
       return self.get(key)

    def __contains__(self,key):
       if self._get(key,self.root):
           return True
       else:
           return False

    def delete(self,key):
      if self.size > 1:
         nodeToRemove = self._get(key,self.root)
         if nodeToRemove:
             self.remove(nodeToRemove)
             self.size = self.size-1
         else:
             raise KeyError('Error, key not in tree')
      elif self.size == 1 and self.root.key == key:
         self.root = None
         self.size = self.size - 1
      else:
         raise KeyError('Error, key not in tree')

    def __delitem__(self,key):
       self.delete(key)

    def spliceOut(self):
       if self.isLeaf():
           if self.isLeftChild():
                  self.parent.leftChild = None
           else:
                  self.parent.rightChild = None
       elif self.hasAnyChildren():
           if self.hasLeftChild():
                  if self.isLeftChild():
                     self.parent.leftChild = self.leftChild
                  else:
                     self.parent.rightChild = self.leftChild
                  self.leftChild.parent = self.parent
           else:
                  if self.isLeftChild():
                     self.parent.leftChild = self.rightChild
                  else:
                     self.parent.rightChild = self.rightChild
                  self.rightChild.parent = self.parent

    def findSuccessor(self):
      succ = None
      if self.hasRightChild():
          succ = self.rightChild.findMin()
      else:
          if self.parent:
                 if self.isLeftChild():
                     succ = self.parent
                 else:
                     self.parent.rightChild = None
                     succ = self.parent.findSuccessor()
                     self.parent.rightChild = self
      return succ

    def findMin(self):
      current = self
      while current.hasLeftChild():
          current = current.leftChild
      return current

    def remove(self,currentNode):
         if currentNode.isLeaf(): #leaf
           if currentNode == currentNode.parent.leftChild:
               currentNode.parent.leftChild = None
           else:
               currentNode.parent.rightChild = None
         elif currentNode.hasBothChildren(): #interior
           succ = currentNode.findSuccessor()
           succ.spliceOut()
           currentNode.key = succ.key
           currentNode.payload = succ.payload

         else: # this node has one child
           if currentNode.hasLeftChild():
             if currentNode.isLeftChild():
                 currentNode.leftChild.parent = currentNode.parent
                 currentNode.parent.leftChild = currentNode.leftChild
             elif currentNode.isRightChild():
                 currentNode.leftChild.parent = currentNode.parent
                 currentNode.parent.rightChild = currentNode.leftChild
             else:
                 currentNode.replaceNodeData(currentNode.leftChild.key,
                                    currentNode.leftChild.payload,
                                    currentNode.leftChild.leftChild,
                                    currentNode.leftChild.rightChild)
           else:
             if currentNode.isLeftChild():
                 currentNode.rightChild.parent = currentNode.parent
                 currentNode.parent.leftChild = currentNode.rightChild
             elif currentNode.isRightChild():
                 currentNode.rightChild.parent = currentNode.parent
                 currentNode.parent.rightChild = currentNode.rightChild
             else:
                 currentNode.replaceNodeData(currentNode.rightChild.key,
                                    currentNode.rightChild.payload,
                                    currentNode.rightChild.leftChild,
                                    currentNode.rightChild.rightChild)




mytree = BinarySearchTree()
mytree[3]="red"
mytree[4]="blue"
mytree[6]="yellow"
mytree[2]="at"

print(mytree[6])
print(mytree[2])

Binary Heap Implementation in Python

__author__ = 'nitin'

class BinHeap:
    def __init__(self):
        self.heapList = [0]
        self.currentSize = 0

    def percUp(self,i):
        while i // 2 > 0:
            if self.heapList[i] < self.heapList[i // 2]:
                tmp = self.heapList[i // 2]
                self.heapList[i // 2] = self.heapList[i]
                self.heapList[i] = tmp
            i = i // 2

    def insert(self,k):
        self.heapList.append(k)
        self.currentSize = self.currentSize + 1
        self.percUp(self.currentSize)

    def percDown(self,i):
        while (i * 2) <= self.currentSize:
            mc = self.minChild(i)
            if self.heapList[i] > self.heapList[mc]:
                tmp = self.heapList[i]
                self.heapList[i] = self.heapList[mc]
                self.heapList[mc] = tmp
            i = mc

    def minChild(self,i):
        if i * 2 + 1 > self.currentSize:
            return i * 2
        else:
            if self.heapList[i*2] < self.heapList[i*2+1]:
                return i * 2
            else:
                return i * 2 + 1

    def delMin(self):
        retval = self.heapList[1]
        self.heapList[1] = self.heapList[self.currentSize]
        self.currentSize = self.currentSize - 1
        self.heapList.pop()
        self.percDown(1)
        return retval

    def buildHeap(self,alist):
        i = len(alist) // 2
        self.currentSize = len(alist)
        self.heapList = [0] + alist[:]
        while (i > 0):
            self.percDown(i)
            i = i - 1

bh = BinHeap()
bh.insert(5)
bh.insert(7)
bh.insert(4)
bh.insert(11)

print(bh.delMin())

print(bh.delMin())

print(bh.delMin())

print(bh.delMin())

Binary Tree with nodes and referrences in Python

__author__ = 'nitin'

class BinaryTree:
    def __init__(self,rootObj):
        self.key = rootObj
        self.leftChild = None
        self.rightChild = None

    def insertLeft(self,newNode):
        if self.leftChild == None:
            self.leftChild = BinaryTree(newNode)
        else:
            t = BinaryTree(newNode)
            t.leftChild = self.leftChild
            self.leftChild = t

    def insertRight(self,newNode):
        if self.rightChild == None:
            self.rightChild = BinaryTree(newNode)
        else:
            t = BinaryTree(newNode)
            t.rightChild = self.rightChild
            self.rightChild = t

    def getRightChild(self):
        return self.rightChild

    def getLeftChild(self):
        return self.leftChild

    def setRootVal(self,obj):
        self.key = obj

    def getRootVal(self):
        return self.key


r = BinaryTree('a')
print(r.getRootVal())
print(r.getLeftChild())
r.insertLeft('b')
print(r.getLeftChild())
print(r.getLeftChild().getRootVal())
r.insertRight('c')
print(r.getRightChild())
print(r.getRightChild().getRootVal())
r.getRightChild().setRootVal('hello')
print(r.getRightChild().getRootVal())

Binary Tree Implementation with list of list in Python

__author__ = 'nitin'

def BinaryTree(r):
    return [r, [], []]

def insertLeft(root,newBranch):
    t = root.pop(1)
    if len(t) > 1:
        root.insert(1,[newBranch,t,[]])
    else:
        root.insert(1,[newBranch, [], []])
    return root

def insertRight(root,newBranch):
    t = root.pop(2)
    if len(t) > 1:
        root.insert(2,[newBranch,[],t])
    else:
        root.insert(2,[newBranch,[],[]])
    return root

def getRootVal(root):
    return root[0]

def setRootVal(root,newVal):
    root[0] = newVal

def getLeftChild(root):
    return root[1]

def getRightChild(root):
    return root[2]

r = BinaryTree(3)
insertLeft(r,4)
insertLeft(r,5)
insertRight(r,9)
insertRight(r,7)
l = getLeftChild(r)
print(l)

setRootVal(l,9)
print(r)
insertLeft(l,11)
print(r)
print(getRightChild(getRightChild(r)))

Friday, March 21, 2014

Given a circular linked list, implement an algorithm which returns node at the begin- ning of the loop. DEFINITION Circular linked list: A (corrupt) linked list in which a node’s next pointer points to an earlier node, so as to make a loop in the linked list. EXAMPLE input: A -> B -> C -> D -> E -> C [the same C as earlier] output: C

__author__ = 'nitin'

class Node:
    def __init__(self,initdata):
        self.data=initdata
        self.next=None
    def getData(self):
        return self.data
    def setData(self,item):
        self.data=item
    def getNext(self):
        return self.next
    def setNext(self,item):
        self.next=item

def find_circular_node(n0):
    n1=n0
    n2=n0
    while n2.getNext() is not None:
        n1=n1.getNext()
        n2=n2.getNext().getNext()
        if n1==n2:
            break
    if n2.getNext() is None:
        return None
    n1=n0
    while n1!=n2:
        n1=n1.getNext()
        n2=n2.getNext()
    return n2.getData()

n0=Node('A')
n1=Node('B')
n2=Node('C')
n3=Node('D')
n4=Node('E')
n0.setNext(n1)
n1.setNext(n2)
n2.setNext(n3)
n3.setNext(n4)
n4.setNext(n2)

print find_circular_node(n0)

My Profile

My photo
can be reached at 09916017317