Merge Sort

Merge sort is a divide and conquer based algorithm. Its merge behavior names the algorithm. Algorithm details can be found elsewhere but I’ll give my basic merge-sort implementation here. It starts with dividing the array into two equal sized arrays. Division done until each array only holds an element. But merging procedure is the interesting part of the merge array. It merges 2 arrays into one sorted array. Continue reading

Finding The Half Of Linked List in Single Traversal

This is like a puzzle question: you iterate the list but at the end of the iteration (i.e. when you reach the end of linked list) you should display the half. The question seams hard because you do not know how many node exist in the list. So, how you find the half when you reach at the tail. One solution may be to store all elements into an array, but this is quite inefficient and possibly infeasible way to solve this question.

My proposed solution is:

  • Traverse the list with double next, this is iterating the list with node->next->next
  • Hold another pointer for half of the list. While iterating double next half of the list pointer iterates with one next.

I added the code for a simple list (supports addition to head, and tail – I did not test the tail :). Continue reading

Singleton Design Pattern

Singleton design pattern is well known design pattern which uses a single object to access its methods at all time. Assume that you have a configuration file to read settings from. You are expecting to access various settings from different source files. With singleton you’ll hold a single object in memory and use this object to access its methods.

Sample python code demonstrating singleton is given below:

class Mysingleton():
	#class variable holds singleton object's reference
    s = None
	
	#constructor
    def __init__(self):
        print "this will print only once!!!"
        self._name = None
		#set _name with setter
        self.name = "yuppii"

	#getter
    @property
    def name(self):
        return self._name

	#setter
    @name.setter
    def name(self,n):
        self._name = n

	#static method to get instance
    @staticmethod
    def getInstance():
		#if no object is created before, create new one
        if Mysingleton.s == None:
            Mysingleton.s = Mysingleton()

        return Mysingleton.s


print Mysingleton.getInstance().name
print Mysingleton.getInstance().name
print Mysingleton.getInstance().name
print Mysingleton.getInstance().name
print Mysingleton.getInstance().name
print Mysingleton.getInstance().name

You  should see an output like:

this will print only once!!!
yuppii
yuppii
yuppii
yuppii
yuppii
yuppii