Implemeting Data Structures and Algorithms in Python: Problems and solutions Contd..

Contd.. from last post

Array Pair SumArray Pair Sum

Given an integer array, output all the unique pairs that sum up to a specific value k. So the input:

sum_arr_uniq_pairs([1,2,2,3,4,1,1,3,2,1,3,1,2,2,4,0],5) 

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

Find a missing element in an array/list

Consider an array of non-negative integers. A second array is formed by shuffling the elements of the first array and deleting a random element. Given these two arrays, find which element is missing in the second array. Here is an example input, the first array is shuffled and the number 5 is removed to construct the second array.
Input:

 find_missing_ele([1,2,3,4,5,6,7],[3,7,2,1,4,6]) 

Output:5 is the missing numberStack class implementation

Implement basic stack operations (LIFO)

push() – Push an element in a stack pop()- POP an element from top of the stackpeek() – Just peek into top element of the stack (don’t perform any operation)Queue class implementation

Implement basic Queue operations (FIFO)

enqueue – adding a element to the queue dequeue – removing an element from the queueDeque (DECK) class implementation

Implement basic operation in deque (Add and remove elements both at front and rear)

addFront()

Add an element at the front

addRear()

Add an element at the rear

removeFront()

Remove from front

removeRear()

Remove from rear

Balance parentheses using stack/list

Given a string of opening and closing parentheses, check whether it’s balanced. We have 3 types of parentheses: round brackets: () square brackets: [] 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. Algo will take a string as the input string and will return boolean (TRUE/FALSE) Examples:

print (check_parentheses_match('([])'))
print (check_parentheses_match('[](){([[[]]])'))

Queue with 2 stack implementation

This is a classic problem. We need to use the basic characteristics of the stack (popping out elements in reverse order) will make a queue. Example:

# Create a object of the class
qObj = QueueWith2Stack()
# Add an element 
qObj.enqueue(1)
# Add another element
qObj.enqueue(2)
# Add more element
qObj.enqueue(4)
# Add more element
qObj.enqueue(8)
# Remove item
print (qObj.dequeue())
# Remove item 
print (qObj.dequeue())
# Remove item
print (qObj.dequeue())
# Remove item 
print (qObj.dequeue())

Singly Linked List class implementation

Implement basic skeleton for a Singly Linked List Example:

# Added node
a = LinkedListNode(1)
b = LinkedListNode(2)
c = LinkedListNode(3)        
# Set the pointers
a.nextnode = bb.nextnode = c
print (a.value)
print (b.value)
print (c.value)
# Print using class 
print (a.nextnode.value)

Doubly Linked List class implementation

Implement basic skeleton for a Doubly Linked List Example:

# Added node
a = DoublyLinkedListNode(1)
b = DoublyLinkedListNode(2)
c = DoublyLinkedListNode(3)        
# Set the pointers
# setting b after a (a before b)
b.prev_node = a
a.next_node = b
# Setting c after a
b.next_node = c
c.prev_node = b
print (a.value)
print (b.value)
print (c.value)
# Print using class 
print (a.next_node.value)
print (b.next_node.value)
print (b.prev_node.value)
print (c.prev_node.value)

Reverse a linked list implementation

The aim is to write a function to reverse a Linked List in place. The function will take in the head of the list as input and return the new head of the list. Example:

# Create a Linked List 
a = LinkedListNode(1)
b = LinkedListNode(2)
c = LinkedListNode(3)
d = LinkedListNode(4)
a.nextnode = b
b.nextnode = c
c.nextnode = d
print (a.nextnode.value)
print (b.nextnode.value)
print (c.nextnode.value)
# Call the reverse()
LinkedListNode().reverse(a)
print (d.nextnode.value)
print (c.nextnode.value)
print (b.nextnode.value)

Linked list Nth to the last node

The aim is a function that takes a head node and an integer value n and then returns the nth to last node in the linked list. Example:

# Create a Linked List 
a = LinkedListNode(1)
b = LinkedListNode(2)
c = LinkedListNode(3)
d = LinkedListNode(4)
e = LinkedListNode(5)

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)

# This would return the node d with a value of 4, because its the 2nd to last node.
target_node = LinkedListNode().nth_to_last_node(2, a) 
print (target_node.value)
# Ans: d=4