Balanced Parentheses Check | Python

Problem : 

Given a string of opening and closing parentheses, 
check whether it’s balanced. 

We have 3 types of parentheses: round brackets: (), square brackets:
[], and curly brackets: {}. 

Assume that the string doesn’t contain 
any other character than these, no spaces words or numbers. 

As a reminder, balanced parentheses require every opening
parenthesis to be closed in the reverse order opened.
For example ‘([])’ is balanced but ‘([)]’ is not.

You can assume the input string has no spaces.

Solution :

def check_balanced_string(s1):
	
	if len(s1)%2 != 0:
		return False

	opening = set('([{')

	matches = set([ ('{','}'), ('[',']'), ('(',')') ])

	stack = []
	for perm in s1:

		if perm in opening:
			stack.append(perm)
		else:

			if len(stack) == 0 :
				return False
			last_val = stack.pop()

			if (last_val,perm) not in matches:
				return False

	return len(stack) == 0

# '([])'
b = check_balanced_string('[()]')
print b
Advertisements

Find the largest continuous sum | Python

Problem :

Given an array of integers(positive and neg),
Find the largest continuous sum .

Solution : 

def large_cont_sum(arr):
	if len(arr) < 1 :
		return 0
	max_sum = current_sum = arr[0]

	for num in arr[1:]:

		current_sum = max(num,current_sum+num)
		max_sum = max(current_sum,max_sum)

	print max_sum

large_cont_sum([1,2,-1,3,4,10,10,-10,-1]) #29

Linked List Nth to Last Node | Python

Problem :

Function that takes a head node and an integer value n and 
then returns the nth to last node in the linked list.

Solution : 

class Node:

    def __init__(self, value):
        self.value = value
        self.nextnode  = None

    def nth_to_last_node(n, head):

	node = head

	nodes = []
	while node != None:
		nodes.append(node)
		node = node.nextnode

	return nodes[-n]

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

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