Tag: python

Python: Unit Tests

One way to write unit tests in Python is by using Nose Tools. If you don’t have it installed, it can be done via command line by typing in pip install nose in the terminal.

from nose.tools import assert_equal

def solution(num1, num2):
    return num1+num2

class SolutionTest(object):
    
    def test(self, sol):
        assert_equal(sol(2,2),4)
        assert_equal(sol(4,4),8)
        
        print("All test cases passed")
        
# run tests
t1 = SolutionTest()
t1.test(solution)

In the code above, we import assert_equal from nose.tools. The function solution below it accepts two numbers and returns their sum.

Then we have a class SolutionTest that has a test function accepting self and sol as two arguments to it.

The assert_equal function then checks whether the output of its first argument is equal to the second. e.g it checks whether sol(2,2) equals to 4.

Our code above returns “All test cases passed” as the output.

However, if we modify the code to assert_equal(sol(2,2),4), it’ll return AssertionError: 5 != 4.

Using this basic idea, you can implement unit tests in Python. Thanks for reading! 🙂

Python: Find Nth Last Node In A Linked List

The goal is to find Nth last node in a given linked list. This can be done by using an imaginary stick.

A stick can be imagined in code by using left and right pointers.

# Problem: Getting Nth to last node in LinkedList
# Logic: Use a stick with two pointers

def find_nth_node(n, node):
    
    left_pointer = node
    right_pointer = node
    
    for i in range(n):
        
        if right_pointer:
            right_pointer = right_pointer.next
        
    # right_pointer is now n nodes ahead
    
    while right_pointer:
        left_pointer = left_pointer.next
        right_pointer = right_pointer.next
        
    return left_pointer

# Testing the result

a = Node(1) #0 -- default right_pointer value
b = Node(2) #1 -- first iteration
c = Node(3) #2 -- second iteration - right_pointer gets here after being n nodes ahead
d = Node(4) #3
e = Node(5) #4

a.next = b
b.next = c
c.next = d
d.next = e

find_nth_node(2, a).value # second last node's val is 4

The first for loop in the code brings our right_pointer in position (n steps ahead of left_pointer), thus creating our imaginary stick.

Once that’s in place, we are ready to find the Nth last node.

The second for loop keeps moving the left_pointer and the right_pointer to the next node as long as the right_pointer points to some node. It stops once it points to Null or None (which is at the end of the Linked List).

The above can be imagined as our stick moving across the given Linked List with left_pointer and right_pointer moving to the right one step (one node) at a time.

Once the second for loop stops, the right_pointer will point to None (the end of the Linked List). Since the length of the stick is N, we can safely say our left_pointer is now pointing at Nth last node.

Therefore printing the value of the node pointed by the left_pointer gives us the value of Nth last node.

In the example given above, the Nth last node (the second last node) is 4.

Python: String Compression

The idea of string compression is as follows: AAAB > A3B1. That is, if we’re given 3 A’s and 1 B, the output should be A3B1.

If we go by this logic, for input of AAABaaaaAA, we should get A5B1a4. This can be achieved by the code given below:

# string compression problem
# AAAB > A3B1

def compress_string(s):
    
    temp = {}
    for letter in s:
        if letter in temp:
            temp[letter] += 1
        else:
            temp[letter] = 1
            
    compressed_string = ''
    
    for letter in temp:
        compressed_string += letter + str(temp[letter])
        
    return compressed_string

compress_string('AAABaaaaAA') #Output: A5B1a4

The code starts with a temp dictionary. It then looks at each letter in the input string and counts it using temp.

Next it simply concatenates letter (the actual character) and str(temp[letter]) (the count of that character) in a variable called compressed_String and prints it.

Python: Sentence Reversal

In the previous post I wrote about reversing a word or an input string. In this one, let’s look at reversing a sentence. For example: “landed has Eagle The” should become “The Eagle has landed”.

To achieve this we’re going to build on top of the string reversal code from the previous post.

def reverse_word(word):
    
    letters = list(word)
    start = 0
    end = len(letters)-1
    
    while start < end:
        letters[start], letters[end] = letters[end], letters[start]
        start+=1
        end-=1
        
    return ''.join(letters)

def reverse_sentence(words):
    
    # reverse the whole string -- # O(n)
    words = reverse_word(words) 
    
    # convert string to a list
    temp = words.split(' ')
    
    # reverse each word in that list -- # O(n)
    for i in range(len(temp)):
        temp[i] = reverse_word(temp[i]) 
        
    # the above loop is O(n) 
    # because we only go through every letter once
        
    # convert list to a string and return it
    return ' '.join(temp)
    
reverse_sentence('landed has Eagle The') #Output: The Eagle has landed

In the code above, we accept an input string, use the string reversal function to reverse it. This gets us ehT elgaE sah dednal as the output and we store it in temp by splitting it at spaces.

The next step is to use string reversal code again but this time we use it for each word and that gets us our intended output, which is: The Eagle has landed.

Python: Stack And Queue

Stack and Queue are abstract data types in Computer Science. In this short post, I’ll try to cover them in as few words as possible.

Stack has a LIFO concept (last in first out). The last item that goes in is the first item that goes out. Example: A stack of books or plates.

While Queue has a FIFO concept (first in first out). The first item that goes in is the first item that goes out. Example: A queue of people at a counter.

# Stack implementation
class Stack(object):
def __init__(self):
self.items = []
def isEmpty(self):
return self.items == []
def push(self, item):
self.items.append(item) #imp
def pop(self):
return self.items.pop() #imp
def peek(self):
return self.items[-1]
def size(self):
return len(self.items)
# Queue implementation
class Queue(object):
def __init__(self):
self.items = []
def isEmpty(self):
return self.items == []
def enqueue(self, item):
self.items.append(item) #imp
def dequeue(self):
return self.items.pop(0) #imp
def size(self):
return len(self.items)
# implementing a queue with 2 stacks
class QueueTwoStacks(object):
def __init__(self):
self.in_stack = []
self.out_stack = []
def enqueue(self, item):
self.in_stack.append(item)
def dequeue(self):
if len(self.out_stack) == 0:
# Move items from in_stack to out_stack, reversing order
while len(self.in_stack) > 0:
newest_in_stack_item = self.in_stack.pop()
self.out_stack.append(newest_in_stack_item)
# If out_stack is still empty, raise an error
if len(self.out_stack) == 0:
raise IndexError("Can't dequeue from empty queue!")
return self.out_stack.pop()
view raw stack_queue.py hosted with ❤ by GitHub
Gist – Stack And Queue

I hope this helps to refresh your knowledge on Stack and Queues in under a minute (or a few minutes).