Binary Search | Python

Binary Search implementation in Python

def binary_search(arr,ele):
	"""
		binary_search works only on sorted array, also it follows divide and conquer fundamentals
	"""

	first = 0
	last = len(arr) - 1 # as indexing starts at 0
	found = False

	while first <= last and not found:

		mid = (first+last)/2 # to get mid point of array

		if arr[mid] == ele:
			found = True
		else:
			if ele < arr[mid]:
				last = mid - 1
			else:
				first = mid + 1

	return found

b = binary_search([1,2,3,4,5],2)
print b
Advertisements

Reverse Linked List | Python

class Node(object):
    
    def __init__(self,value):
        
        self.value = value
        self.nextnode = None
def reverse(head):
    
    # Set up current,previous, and next nodes
    current = head
    previous = None
    nextnode = None

    # until we have gone through to the end of the list
    while current:
        nextnode = current.nextnode

        # Reverse the pointer ot the next_node
        current.nextnode = previous

        # Go one forward in the list
        previous = current
        current = nextnode

    return previous

# Create a list of 4 nodes
a = Node(1)
b = Node(2)
c = Node(3)
d = Node(4)
e = Node(5)

# Set up order a,b,c,d with values 1,2,3,4
a.nextnode = b
b.nextnode = c
c.nextnode = d
d.nextnode = e

print a.nextnode.value
print b.nextnode.value
print c.nextnode.value
print d.nextnode.value
print e.nextnode

reverse(a)

print 'after reverse----'
print e.nextnode.value
print d.nextnode.value
print c.nextnode.value
print b.nextnode.value
print a.nextnode

Doubly Linked List | Python

Implementation of Doubly Linked List in Python

class DoublyLinkedList(object):

	def __init__(self,val):

		self.value = val
		self.next_node = None
		self.prev_node = None

a = DoublyLinkedList(1)
b = DoublyLinkedList(2)
c = DoublyLinkedList(3)

a.next_node = b
b.prev_node = a

b.next_node = c
c.prev_node = b

Singly Linked Lists | Python

Implementation of singly linked lists in Python.

class Node(object):

	def __init__(self,val):

		self.value = val
		self.nextNode = Node

a = Node(1)
b = Node(2)
c = Node(3)
a.nextNode = b
b.nextNode = c
print a.nextNode.value

Array Pair Sum | Python

Problem
Given an integer array, output all the unique pairs that sum up to a specific value k.
So the input:
pair_sum([1,3,2,2],4)

would return 2 pairs:
 (1,3)
 (2,2)

Solution

def get_unique_pair(list_of_elems,k):
	if len(list_of_elems) < 2:
		print "Please increase data"
	else:
		seen = set()
		output = set()

		for num in list_of_elems:

			target = k - num

			if target not in seen:
				seen.add(num)
			else:
				output.add(((min(num,target)),max(num,target)))

	print output

get_unique_pair([1,3,2,2],4)

FizzBuzz Problem | Python

FizzBuzz Problem in Python

# write program to print number from 1 to 100
# multiple of 3 print "fizz" instead of number
# multiple of 5 print "buzz" instead of number
# for number which are mutiple of both 3 and 5 print "fizzbuzz"

start = 1
end = 101
val_3 = 3
val_5 = 5
word1 = 'FizzBuzz'
word2 = 'Fizz'
word3 = 'Buzz'

for i in xrange(start,end):
    if i%val_3==0 and i%val_5==0:
	print word1
    elif i%val_5==0:
	print word3
    elif i%val_3==0:
	print word2
    else:
	print i

Anagram problem | Python

Solution for Anagram problem in Python.

#Anagram problem

# input1 = 'public relations'
# output1 = 'crap built on lies'

input = 'client eastwood'
output = 'old west action'


def check_for_anagram(input1,output1):

    """
	checks for Anagram
    """
    input1 = input1.lower()
    output1 = output1.lower()
    len_of_input1 = len(input1)
    len_of_output1 = len(output1)

    input_1_dict = {}
    output_1_dict = {}

    if len_of_input1 == len_of_output1:
	striped_input1 = ''.join(input1.split(' '))
	striped_output1 = ''.join(input1.split(' '))

	for i in range(len(striped_input1)+1):
	    if i in input_1_dict:
		input_1_dict[i] += 1
	    else:
		input_1_dict[i] = 1

	for i in range(len(striped_output1)+1):
            if i in output_1_dict:
		output_1_dict[i] += 1
	    else:
		output_1_dict[i] = 1

	if output_1_dict == input_1_dict:
	    print True
	else:
	    print False
    else:
	print False

check_for_anagram(input,output)