Forem: CodeWithML

Implement a Queue using a Linked List

CodeWithML — Tue, 20 Oct 2020 13:35:48 +0000

Problem Statement: Implement a queue using a linked list with methods like enqueue and dequeue.

What is a Queue?
A Queue is a linear data structure, where the elements are stored in a particular order. It follows the FIFO(First In First Out) order in which the operations are performed.

Test Cases:

Enqueue
- Enqueue on an empty queue
- Enqueue on a non-empty queue
Dequeue
- Dequeue on an empty queue. --> None
- Dequeue on a non-empty queue. --> value
getData
- getData on an empty queue. --> None
- getData on a non-empty queue. --> List of elements in queue

Algorithm:

Enqueue
- Create a new node with data
- If head and tail pointers are None,
  - set head and tail to new node
- Else,
  - set tail to new node.
Dequeue
- If the queue is empty,
  - return None
- If queue has only one element, i.e head and tail pointers are equal,
  - save head's value
  - set head and tail value to None
  - return value.
- Else,
  - save head's value.
  - set head to next of head.
  - return value.
getData
- initialise an empty list and a current pointer pointing to head.
- iterate through the queue till current pointer is not None.
- append value to the list at each iteration
- return the list.

Time and Space Complexity

Enqueue
- Time: O(1)
- Space: O(1)
Dequeue
- Time: O(1)
- Space: O(1)
getData
- Time: O(n)
- Space: O(n)
Length
- Time: O(n)
- Space: O(1)

Code

class Node(object):

    def __init__(self, data):
        self.data = data
        self.next = None


class Queue(object):

    def __init__(self):
        self.head = None
        self.tail = None

    def __len__(self):
        counter = 0
        curr_node = self.head
        while curr_node is not None:
            counter += 1
            curr_node = curr_node.next
        return counter

    def enqueue(self, data):
        node = Node(data)
        if self.head is None and self.tail is None:
            self.head = node
            self.tail = node
        else:
            self.tail.next = node
            self.tail = node

    def dequeue(self):
        if self.head is None and self.tail is None:
            return None
        data = self.head.data
        if self.head == self.tail:
            self.head = None
            self.tail = None
        else:
            self.head = self.head.next
        return data

    def getData(self):
        data = []
        curr_node = self.head
        while curr_node is not None:
            data.append(curr_node.data)
            curr_node = curr_node.next
        return data

Unit Test

import unittest
from queue import Queue


class TestQueue(unittest.TestCase):
    def testEnqueue(self):
        print('Test: Enqueue on an empty queue')
        qu = Queue()
        qu.enqueue(1)
        self.assertEqual(qu.getData(), [1])

        print('Test: Enqueue on a non-empty queue')
        qu = Queue()
        qu.enqueue(2)
        qu.enqueue(3)
        self.assertEqual(len(qu), 2)
        self.assertEqual(qu.getData(), [2, 3])
        print('Success: enqueue')

    def testDequeue(self):
        print('Test: Dequeue on an empty queue')
        qu = Queue()
        self.assertEqual(qu.dequeue(), None)

        print('Test: Dequeue on a non-empty queue')
        qu = Queue()
        qu.enqueue(1)
        qu.enqueue(3)
        qu.enqueue(5)
        self.assertEqual(len(qu), 3)
        self.assertEqual(qu.dequeue(), 1)
        self.assertEqual(qu.dequeue(), 3)
        self.assertEqual(qu.dequeue(), 5)

        print('Success: testDequeue')


def main():
    test = TestQueue()
    test.testEnqueue()
    test.testDequeue()


if __name__ == "__main__":
    main()

Github solution repo

Happy Coding !!! 🌟

Implement a Stack using a Linked List

CodeWithML — Mon, 19 Oct 2020 04:17:55 +0000

Problem Statement: Implement a stack using a linked list with it's functions like push, pop, peek, isEmpty.

What is a Stack?
A Stack is a linear data structure, where the elements are stored in a particular order. It follows the LIFO(Last In First Out) order in which the operations are performed.

Test Cases:

Push
- Push on an empty stack
- Push on a non-empty stack
Peek
- Peek on an empty stack --> None.
- Peek on a non-empty stack --> value.
Pop
- Pop from an empty stack --> None.
- Pop from a non-empty stack --> value
isEmpty
- isEmpty on an empty stack --> True
- isEmpty on a non-empty stack --> False

Algorithm:

Push
- Create a new node with data
- Set next of new node to top
- Set top to node
Peek
- if stack is empty,
  - return None
- else,
  - return value of top
Pop
- if stack is empty,
  - return None
- else,
  - save value of top in a temporary variable
  - set top to next of top
  - return temporary variable
isEmpty
- if top has value,
  - return false
- else,
  - return true

Time and Space Complexity:

Push
- Time: O(1)
- Space: O(1)
Pop
- Time: O(1)
- Space: O(1)
Peek
- Time: O(1)
- Space: O(1)
isEmpty
- Time: O(1)
- Space: O(1)
Length
- Time: O(n)
- Space: O(1)

Code

class Node(object):
    def __init__(self, data, next=None):
        self.data = data
        self.next = next


class Stack(object):
    def __init__(self, top=None):
        self.top = top

    def __len__(self):
        curr = self.top
        counter = 0
        while curr is not None:
            counter += 1
            curr = curr.next
        return counter

    def pop(self):
        if self.top is None:
            return None
        data = self.top.data
        self.top = self.top.next
        return data

    def push(self, data):
        self.top = Node(data, self.top)

    def peek(self):
        return self.top.data if self.top is not None else None

    def isEmpty(self):
        return self.peek() is None

Unit Tests

import unittest
from stack import Stack, Node


class TestStack(unittest.TestCase):
    def test_end_to_end(self):
        print('Test: Empty stack')
        stack = Stack()
        self.assertAlmostEqual(len(stack), 0)
        self.assertEqual(stack.peek(), None)
        self.assertEqual(stack.pop(), None)

        print('Test: One element')
        top = Node(5)
        stack = Stack(top)
        self.assertEqual(len(stack), 1)
        self.assertEqual(stack.pop(), 5)
        self.assertEqual(stack.peek(), None)

        print('Test: More than one element')
        stack = Stack()
        stack.push(1)
        stack.push(2)
        stack.push(3)
        self.assertEqual(len(stack), 3)
        self.assertEqual(stack.pop(), 3)
        self.assertEqual(len(stack), 2)
        self.assertEqual(stack.peek(), 2)
        self.assertEqual(stack.pop(), 2)
        self.assertEqual(len(stack), 1)
        self.assertEqual(stack.peek(), 1)
        self.assertEqual(stack.isEmpty(), False)
        self.assertEqual(stack.pop(), 1)
        self.assertEqual(len(stack), 0)
        self.assertEqual(stack.peek(), None)
        self.assertEqual(stack.isEmpty(), True)
        print('Success: test_end_to_end')


def main():
    test = TestStack()
    test.test_end_to_end()


if __name__ == '__main__':
    main()

Github solution repo

Happy coding !! 🌟

Implement a Linked List

CodeWithML — Sun, 18 Oct 2020 07:13:30 +0000

Problem statement: Implement a Linked List with it's functions like inserting an element at start of the linked list and inserting at the end of linked list, searching an element in the list and removing an element from the list.

What is a Linked List?
It's a linear data structure, but the elements are not stored in next to each other or in a sequence, but rather they're linked using pointers.

Test Cases:

Insert at start
- Insert a None.
- Insert at start in an empty linked list.
- Insert at start in a non-empty linked list.
Insert at end.
- Insert a None.
- Insert at end in an empty linked list.
- Insert at end in a non-empty linked list.
Search
- Search for element present in linked list.
- Search for element in an empty linked list.
- Search for element not present in linked list.
- Search for None.
Remove
- Remove element from an empty linked list.
- Remove element from a non-empty linked list.
- Remove element not present in linked list.
- Remove a None.
Length
- Print length of the linked list.

Algorithm:

Insert to start
- If data is None
  - return
- Create a new node with data
- Set the next of new node to head
- Set the head to the new node
Insert to end
- If data is None
  - return
- Create a new node with data
- If linked list is empty,
  - set the head to the node
- Else,
  - iterate through the end of list
  - Set the next of last node to new node.
Search
- Initialise a current pointer to head
- Iterate through the linked list
  - If value is matched, return the value
  - Else, move onto the next node
Remove
- Initialise a current pointer, pointing to node next to head
- Initialise a previous pointer, pointing to head
- Iterate through the linked list,
  - If value is found,
    - Set the previous node, next pointer to current node next
  - Else, move onto the next node
Length
- Initialise a counter
- Iterate through the entire linked list
- For each node in the list,
  - increase the counter
- Return the counter

Time Complexity:

Insert to start
- Time complexity: O(1)
- Space complexity: O(1)
Insert to end
- Time complexity: O(n)
- Space complexity: O(1)
Search
- Time complexity: O(n)
- Space complexity: O(1)
Remove
- Time complexity: O(n)
- Space complexity: O(1)
Length
- Time complexity: O(n)
- Space complexity: O(1)

Code

class Node(object):
    def __init__(self, data, next=None):
        self.data = data
        self.next = next


class LinkedList(object):
    def __init__(self, head=None):
        self.head = head

    def __len__(self):
        current = self.head
        counter = 0
        while current is not None:
            counter += 1
            current = current.next
        return counter

    def insertStart(self, data):
        if data is None:
            return None
        node = Node(data, self.head)
        self.head = node
        return node

    def insertEnd(self, data):
        if data is None:
            return None
        node = Node(data)
        if self.head is None:
            self.head = node
            return node
        curr_node = self.head
        while curr_node.next is not None:
            curr_node = curr_node.next
        curr_node.next = node
        return node

    def search(self, data):
        if data is None:
            return None
        curr_node = self.head
        while curr_node is not None:
            if curr_node.data == data:
                return curr_node.data
            curr_node = curr_node.next
        return None

    def remove(self, data):
        if data is None:
            return None
        if self.head is None:
            return
        if self.head.data == data:
            self.head = self.head.next
            return
        prev_node = self.head
        curr_node = self.head.next
        while curr_node is not None:
            if curr_node.data == data:
                prev_node.next = curr_node.next
                return
            prev_node = curr_node
            curr_node = curr_node.next

    def remove2(self, data):
        if data is None:
            return None
        if self.head is None:
            return None
        curr_node = self.head
        if curr_node.data == data:
            curr_node = curr_node.next
            return
        while curr_node.next is not None:
            if curr_node.next.data == data:
                curr_node.next = curr_node.next.next
                return
            curr_node = curr_node.next

    def printList(self):
        curr_node = self.head
        while curr_node is not None:
            print(curr_node.data)
            curr_node = curr_node.next

    def getData(self):
        data = []
        curr_node = self.head
        while curr_node is not None:
            data.append(curr_node.data)
            curr_node = curr_node.next
        return data

Unit Test

import unittest
from linkedList import LinkedList, Node


class TestLinkedList(unittest.TestCase):

    def testInsertStart(self):
        print('Test: insertStart on an empty linked list')
        linkedList = LinkedList(None)
        linkedList.insertStart(1)
        self.assertEqual(linkedList.getData(), [1])

        print('Test: insertStart on a None')
        linkedList.insertStart(None)
        self.assertEqual(linkedList.getData(), [1])

        print('Test: insertStart on a non-empty linked list')
        linkedList.insertStart(11)
        linkedList.insertStart('letters')
        self.assertEqual(linkedList.getData(), ['letters', 11, 1])

        print('Success: testInsertStart')

    def testInsertEnd(self):
        print('Test: insertLast on an empty linked list')
        linkedList = LinkedList(None)
        linkedList.insertEnd(2)
        self.assertEqual(linkedList.getData(), [2])

        print('Test: insertEnd a None')
        linkedList.insertEnd(None)
        self.assertEqual(linkedList.getData(), [2])

        print('Test: insertEnd on a non-empty linked list')
        linkedList.insertEnd('4')
        linkedList.insertEnd(6)
        self.assertEqual(linkedList.getData(), [2, '4', 6])

        print('Success: insertEnd')

    def testSearch(self):
        print('Test: Search on an empty linked list')
        linkedList = LinkedList(None)
        element = linkedList.search(1)
        self.assertEqual(element, None)

        print('Test: Search on a None')
        linkedList1 = LinkedList(10)
        element = linkedList1.search(None)
        self.assertEqual(element, None)

        print('Test: Search on a non-empty linked list')
        head = Node(10)
        linkedList2 = LinkedList(head)
        linkedList2.insertStart(9)
        linkedList2.insertStart(8)
        linkedList2.insertStart(7)
        linkedList2.insertEnd(11)
        element = linkedList2.search(11)
        element2 = linkedList2.search('aaa')
        self.assertEqual(element, 11)
        self.assertEqual(element2, None)
        print('Success: testSearch')

    def testRemove(self):
        print('Test: remove element from an empty linked list')
        linkedList = LinkedList(None)
        linkedList.remove(2)
        self.assertEqual(linkedList.getData(), [])

        print('Test: remove a None')
        head = Node(1)
        linkedList = LinkedList(head)
        linkedList.remove(None)
        self.assertEqual(linkedList.getData(), [1])

        print('Test: remove element from a non-empty linked list')
        head = Node(1)
        linkedList = LinkedList(head)
        linkedList.insertEnd(2)
        linkedList.insertEnd(3)
        linkedList.insertStart(0)
        linkedList.remove(0)
        linkedList.remove2(2)
        self.assertEqual(linkedList.getData(), [1, 3])
        linkedList.remove('abc')
        self.assertEqual(linkedList.getData(), [1, 3])

        print('Success: testRemove')

    def testLen(self):
        print('Test length of thean empty linked list')
        linkedList = LinkedList(None)
        self.assertEqual(len(linkedList), 0)

        print('Test length of non empty linked list')
        head = Node(0)
        linkedList = LinkedList(head)
        linkedList.insertStart(1)
        linkedList.insertStart(2)
        linkedList.insertEnd(3)
        self.assertEqual(len(linkedList), 4)

        print('Success: testLen')


def main():
    test = TestLinkedList()
    test.testInsertStart()
    test.testInsertEnd()
    test.testSearch()
    test.testRemove()
    test.testLen()


if __name__ == "__main__":
    main()

Github solution repo

Happy coding ⭐

Implement a Deque using a List

CodeWithML — Thu, 08 Oct 2020 05:55:44 +0000

Problem Statement: Implement a Deque with all it's functions using a List.

A Deque is a double ended queue, where elements can be added from both the ends of the queue.

Functions to be implemented

addRear
addFront
getRear
getFront
deleteRear
deleteFront
isEmpty
Size

Test Cases

addRear
- Add element at the rear of deque on an empty deque.
- Add element at the rear of deque on a non-empty deque.
addFront
- Add element at the front of deque on an empty deque.
- Add element at the front of deque on a non-empty deque.
getRear
- Get element from the rear of deque on an empty deque --> None.
- Get element from the rear of deque on a non-empty deque --> value.
getFront
- Get element from the front of deque on an empty deque --> None.
- Get element from the front of deque on a non-empty deque --> value.
deleteRear
- Delete element from the rear of deque on an empty deque --> None.
- Delete element from the rear of deque on a non-empty deque --> value.
deleteFront
- Delete element from the front of deque on an empty deque --> None.
- Delete element from the front of deque on a non-empty deque --> value.
isEmpty
- isEmpty on an non-empty deque --> True.
- isEmpty on a empty deque --> False.
Size
- size on an non-empty deque --> None.
- size on a empty deque --> value.

Algorithm

addRear
- Insert the element at the first index of list.
addFront
- Insert the element at the last index of list.
getRear
- If deque is empty,
  - return None.
- Else,
  - Get the element present at the first index of list.
getFront
- If deque is empty,
  - return None.
- Else,
  - Get the element present at the last index of list.
deleteRear
- If deque is empty,
  - return None.
- Else,
  - remove the element at the first index of list.
deleteFront
- If deque is empty,
  - return None.
- Else,
  - remove the element at the last index of list.
isEmpty
- If list is empty,
  - return True.
- Else,
  - return False.
Size
- Return the length of the list.

Time and Space complexity

addFront
- Time complexity: Best case - O(1), Worst case - O(n)
- Space complexity: O(1)
addRear
- Time complexity: Best case - O(1), Worst case - O(n)
- Space complexity: O(1)
getFront
- Time complexity: O(1)
- Space complexity: O(1)
getRear
- Time complexity: O(1)
- Space complexity: O(1)
deleteFront
- Time complexity: O(1)
- Space complexity: O(1)
deleteRear
- Time complexity: O(1)
- Space complexity: O(1)
isEmpty
- Time complexity: O(1)
- Space complexity: O(1)
Size
- Time complexity: O(1)
- Space complexity: O(1)

Code

class Deque(object):
    def __init__(self):
        self.deque = []

    def isEmpty(self):
        return self.deque == []

    def addRear(self, data):
        self.deque.insert(0, data)

    def addFront(self, data):
        self.deque.append(data)

    def getRear(self):
        if self.isEmpty():
            return None
        return self.deque[0]

    def getFront(self):
        if self.isEmpty():
            return None
        return self.deque[-1]

    def removeRear(self):
        if self.isEmpty():
            return None
        return self.deque.pop(0)

    def removeFront(self):
        if self.isEmpty():
            return None
        return self.deque.pop()

    def size(self):
        return len(self.deque)

Unit Test

import unittest
from deque import Deque


class TestDeque(unittest.TestCase):
    def testDeque(self):
        print('Test: Empty Deque')
        deque = Deque()
        self.assertEqual(deque.size(), 0)
        self.assertEqual(deque.getFront(), None)
        self.assertEqual(deque.getRear(), None)
        self.assertEqual(deque.removeFront(), None)
        self.assertEqual(deque.removeRear(), None)
        self.assertEqual(deque.isEmpty(), True)

        print('Test: One element')
        deque = Deque()
        deque.addFront(5)
        self.assertEqual(deque.size(), 1)
        self.assertEqual(deque.getFront(), 5)
        self.assertEqual(deque.removeFront(), 5)
        self.assertEqual(deque.isEmpty(), True)
        deque.addRear(5)
        self.assertEqual(deque.isEmpty(), False)
        self.assertEqual(deque.size(), 1)
        self.assertEqual(deque.getRear(), 5)
        self.assertEqual(deque.removeRear(), 5)
        self.assertEqual(deque.isEmpty(), True)

        print('Test: Multiple elements')
        deque = Deque()
        deque.addFront(1)
        deque.addRear(3)
        deque.addFront(2)
        deque.addRear(4)
        self.assertEqual(deque.size(), 4)
        self.assertEqual(deque.getFront(), 2)
        self.assertEqual(deque.removeFront(), 2)
        self.assertEqual(deque.size(), 3)
        self.assertEqual(deque.removeRear(), 4)
        self.assertEqual(deque.getRear(), 3)
        self.assertEqual(deque.size(), 2)
        self.assertEqual(deque.isEmpty(), False)
        self.assertEqual(deque.removeFront(), 1)
        self.assertEqual(deque.removeRear(), 3)
        self.assertEqual(deque.isEmpty(), True)
        print('Success: testDeque')


def main():
    test = TestDeque()
    test.testDeque()


if __name__ == "__main__":
    main()

Github repo

Happy Coding !!!

Setup Adminer with docker for Database Management

CodeWithML — Wed, 07 Oct 2020 06:38:33 +0000

If docker and docker-compose is not installed on your machine, you can do it by checking these pages.
Docker engine
Docker compose.

What is Adminer?

Adminer is a web based database management tool written in a single PHP file which can be deployed to any server. It supports MySQL, PostgreSQL, MongoDB, MS SQl, Elasticsearch, MariaDB, SQLite, Oracle, Firebird and Simple DB. It also comes with better security and performance, compared to phpMyAdmin.

For testing it locally, you probably have to use a local server like WAMP or XAMPP and configure it for adminer., by adding the adminer.php file.

This process can be simplified by using docker and docker-compose and a single yaml file.

Using docker-compose, you use a YAML file to configure your application’s services. Then, with a single command, you create and start all the services from your configuration.

A sample docker-compose file for MySQL.

version: '3.7'
services:
    mysql_db:
        image: mysql:latest
        ports: 
          -  3307:3307
        volumes:
            - mysql_db_data:/var/lib/mysql
volumes:
    mysql_db_data:

To start the container run the command

docker-compose up -d

-d flag will run the container in detached mode.

version - Specifies docker engine version
services - Used for specifying the containers which will be started at run time.
- image - The container image, here we'll use mysql.
- ports - The port mapped from the Host machine to the container
- volume - Mount the local volume to docker container.
volumes - This will persist the mounted volume, even if the container is stopped.

Here we're using pre-built images so we don't need to build these images, if we were to use our own custom DockerFile for this, we first need to build the image by running

docker-compose build

and then,

docker-compose up -d

Now adding adminer to docker-compose file

version: '3.7'
services:
    adminer_container:
        image: adminer:latest
        environment: 
            ADMINER_DEFAULT_SERVER: mysql_db
            ADMINER_DESIGN: galkaev
        ports: 
          - 8080:8080

image: Here we're using the official docker image provided by adminer followed by the latest tag, which shows, it is the latest version of the image.
Environment variable: As we're using an external mysql-db we have to specify it in the environment variable.
- ADMINER_DEFAULT_SERVER - external db.
- ADMINER_DESIGN - theme of adminer ui.

Final docker-compose yaml file

version: '3.7'
services: 
    mysql_db_container:
        image: mysql:latest
        command: --default-authentication-plugin=mysql_native_password
        env_file:
          - ./config/mysql.env
        ports: 
          - 3307:3307
        volumes: 
            - mysql_db_data_container:/var/lib/mysql

    adminer_container:
        image: adminer:latest
        environment: 
            ADMINER_DEFAULT_SERVER: mysql_db_container
            ADMINER_DESIGN: galkaev
        ports: 
          - 8080:8080


volumes: 
    mysql_db_data_container:

A few additions to the mysql container.

command : Provides authentication for root and other users.

env_file: This file stores environment variables like password in a seperate .env file.

Run the command,

docker-compose up -d

and visit localhost:8080 and you'll see the adminer ui.

Github repo

Happy coding 😃

Implement a Queue using a List.

CodeWithML — Tue, 06 Oct 2020 11:50:48 +0000

Problem Statement: Implement a Queue with methods like Enqueue, Dequeue, Size, isEmpty using Lists in Python.

This approach will be slow because of the following reason

It is possible to use a list as a queue, where the first element added is the first element retrieved (“first-in, first-out”); however, lists are not efficient for this purpose. While appends and pops from the end of list are fast, doing inserts or pops from the beginning of a list is slow (because all of the other elements have to be shifted by one).
Source

Test Cases

Enqueue
- Enqueue on an empty Queue.
- Enqueue on non-empty Queue.
Dequeue
- Dequeue on an empty Queue --> None.
- Dequeue on a Queue with only one element --> value.
- Dequeue on a Queue with multiple elements --> value.
Size
- Size on an empty Queue --> None.
- Size on non empty Queue --> value.
isEmpty
- isEmpty on an empty Queue --> True.
- isEmpty on non empty Queue --> False.

Algorithm

Enqueue
- Insert the element at first index of the list.
- If an element is already present at the index, it will be shifted one bit.
Dequeue
- If queue is empty,
  - return None
- Else,
  - Delete the last element from the list
  - Return the element
Size
- Return the length of the list.
isEmpty
- If list is empty,
  - return True.
- Else,
  - return False

Time and Space Complexity

Enqueue.
- Time complexity: Best case - O(1), Worst case - O(n)
- Space complexity: O(1)
Dequeue.
- Time complexity: O(1)
- Space complexity: O(1)
Size
- Time complexity: O(1)
- Space complexity: O(1)
isEmpty
- Time complexity: O(1)
- Space complexity: O(1) ***

Code

class Queue(object):
    def __init__(self):
        self.items = []

    def isEmpty(self):
        return self.items == []

    def enqueue(self, data):
        self.items.insert(0, data)

    def dequeue(self):
        if self.isEmpty():
            return None
        print(self.items)
        return self.items.pop()

    def size(self):
        return len(self.items)

Unit Test

import unittest
from queueList import Queue


class TestQueueList(unittest.TestCase):
    def testQueue(self):
        print('Test: Empty Queue')
        queue = Queue()
        self.assertEqual(queue.dequeue(), None)
        self.assertEqual(queue.size(), 0)
        self.assertEqual(queue.isEmpty(), True)

        print('Test: One element')
        queue = Queue()
        queue.enqueue(5)
        self.assertEqual(queue.size(), 1)
        self.assertEqual(queue.dequeue(), 5)
        self.assertEqual(queue.isEmpty(), True)

        print('Test: Multiple elements')
        queue = Queue()
        queue.enqueue(1)
        queue.enqueue(2)
        queue.enqueue(3)
        self.assertEqual(queue.size(), 3)
        self.assertEqual(queue.dequeue(), 1)
        self.assertEqual(queue.dequeue(), 2)
        self.assertEqual(queue.isEmpty(), False)
        self.assertEqual(queue.dequeue(), 3)
        self.assertEqual(queue.isEmpty(), True)
        print('Success: testQueue')


def main():
    test = TestQueueList()
    test.testQueue()


if __name__ == '__main__':
    main()

Github repo

Happy coding !!!

Implement Stack using a List.

CodeWithML — Sun, 04 Oct 2020 07:41:23 +0000

Problem Statement: Implement stack with push, pop, peek, isEmpty, size methods using a List.

Test Cases

Push
- Push on empty stack.
- Push on non-empty stack
Pop
- Pop on empty stack --> None.
- Pop on non-empty stack. --> value
Peek
- Peek on empty stack --> None.
- Peek on non empty stack. --> value
isEmpty
- isEmpty on empty stack --> True
- isEmpty on non-empty stack --> False.
Size
- size on empty stack --> None.
- size on non empty stack. --> value

Algorithm

Push
- Append new value to end of the list.
Pop
- If stack is empty,
  - return None
- Else,
  - Pop element from the end of list.
  - return the element.
Peek
- If stack is empty,
  - return None
- Else,
  - return the last element of the list.
isEmpty
- If stack is empty,
  - return True
- Else,
  - return False
Size
- Return the length of the list.

Time and Space complexity

Push
- Time complexity: O(1)
- Space complexity: O(1)
Pop
- Time complexity: O(1)
- Space complexity: O(1)
Peek
- Time complexity: O(1)
- Space complexity: O(1)
isEmpty
- Time complexity: O(1)
- Space complexity: O(1)
Size
- Time complexity: O(1)
- Space complexity: O(1)

Code

class Stack(object):
    def __init__(self):
        self.items = []

    def isEmpty(self):
        return self.items == []

    def push(self, data):
        self.items.append(data)

    def pop(self):
        if self.isEmpty():
            return None
        return self.items.pop()

    def peek(self):
        if self.isEmpty():
            return None
        return self.items[-1]

    def size(self):
        return len(self.items)

Unit Test

import unittest
from stackLists import Stack


class TestStackLists(unittest.TestCase):
    def test_end_to_end(self):
        print('Test: Empty stack')
        stack = Stack()
        self.assertEqual(stack.peek(), None)
        self.assertEqual(stack.pop(), None)

        print('Test: One element')
        stack = Stack()
        stack.push(5)
        self.assertEqual(stack.size(), 1)
        self.assertEqual(stack.pop(), 5)
        self.assertEqual(stack.peek(), None)

        print('Test: More than one element')
        stack = Stack()
        stack.push(1)
        stack.push(2)
        stack.push(3)
        self.assertEqual(stack.size(), 3)
        self.assertEqual(stack.pop(), 3)
        self.assertEqual(stack.peek(), 2)
        self.assertEqual(stack.pop(), 2)
        self.assertEqual(stack.peek(), 1)
        self.assertEqual(stack.isEmpty(), False)
        self.assertEqual(stack.pop(), 1)
        self.assertEqual(stack.peek(), None)
        self.assertEqual(stack.isEmpty(), True)
        print('Success: test_end_to_end')


def main():
    test = TestStackLists()
    test.test_end_to_end()


if __name__ == '__main__':
    main()

Github repo

Happy Coding !! 😃

Implement a Hashmap with its various methods

CodeWithML — Sat, 03 Oct 2020 14:42:50 +0000

Problem Statement: Implement Hash Map with get, set and remove methods.

Difficulty level: Easy

Test Cases

Get
- Get - key exists --> value
- Get - key doesn't exist --> Keyerror
Set
- Set - key exists --> Overwrite value
- Set - key doesn't exist --> new key, value
Remove
- Remove - key exists --> delete key, value
- Remove - key doesn't exist --> Keyerror

Algorithm

Hash Function
- Return key modulo(%) table size
Get Function
- Get hashIndex for lookup
- If key exists, return the value
- Else, keyerror
Set Function
- Get hashIndex for lookup
- If key exists, overwrite the value
- Else, add value
Remove Function
- Get hashIndex for lookup
- If key exists, delete the entry from the table
- Else, keyerror

Time and Space Complexity

Hash Function
- Time complexity: O(1)
- Space complexity: O(1)
Get Function
- Time complexity: O(1) average and best case, O(n) worst case
- Space complexity: O(1)
Set Function
- Time complexity: O(1) average and best case, O(n) worst case
- Space complexity: O(1)
Remove Function
- Time complexity: O(1) average and best case, O(n) worst case
- Space complexity: O(1)

Code

class Item(object):
    def __init__(self, key, value):
        self.key = key
        self.value = value


class HashTable(object):
    def __init__(self, size):
        self.size = size
        self.table = [[] for _ in range(self.size)]

    def hashFunction(self, key):
        return key % self.size

    def set(self, key, value):
        hashIndex = self.hashFunction(key)
        for item in self.table[hashIndex]:
            if item.key == key:
                item.value = value
                return
        self.table[hashIndex].append(Item(key, value))

    def get(self, key):
        hashIndex = self.hashFunction(key)
        for item in self.table[hashIndex]:
            if item.key == key:
                return item.value
        raise KeyError('Key not found')

    def remove(self, key):
        hashIndex = self.hashFunction(key)
        for index, item in enumerate(self.table[hashIndex]):
            if item.key == key:
                del self.table[hashIndex][index]
                return
        raise KeyError('Key not found')

Unit Test

import unittest
from hashmap import HashTable


class TestHashMap(unittest.TestCase):

    def test_end_to_end(self):
        hash_table = HashTable(10)

        print("Test: get on an empty hash table index")
        self.assertRaises(KeyError, hash_table.get, 0)

        print("Test: set on an empty hash table index")
        hash_table.set(0, 'first')
        self.assertEqual(hash_table.get(0), 'first')
        hash_table.set(1, 'second')
        self.assertEqual(hash_table.get(1), 'second')

        print("Test: set on a non empty hash table index")
        hash_table.set(10, 'third')
        self.assertEqual(hash_table.get(0), 'first')
        self.assertEqual(hash_table.get(10), 'third')

        print("Test: set on a key that already exists")
        hash_table.set(10, 'fourth')
        self.assertEqual(hash_table.get(0), 'first')
        self.assertEqual(hash_table.get(10), 'fourth')

        print("Test: remove on a key that already exists")
        hash_table.remove(10)
        self.assertEqual(hash_table.get(0), 'first')
        self.assertRaises(KeyError, hash_table.get, 10)

        print("Test: remove on a key that doesn't exist")
        self.assertRaises(KeyError, hash_table.remove, -1)

        print('Success: test_end_to_end')


def main():
    test = TestHashMap()
    test.test_end_to_end()


if __name__ == "__main__":
    main()

Github repo

Happy Coding !! 🌟

Find missing element from given two arrays.

CodeWithML — Fri, 02 Oct 2020 09:35:20 +0000

Problem Statement: Write a function to find the missing element from given two arrays.

Difficulty level: Easy

Test Cases:

[1, 2, 3, 4, 5, 6, 7],[3, 7, 2, 1, 4, 6] --> 5
[5, 7, 7, 5, 7], [7, 7 ,5, 5] --> 7
[9, 8, 7, 6, 5, 4, 3, 2, 1],[9, 8, 7, 5, 4, 3, 2, 1] --> 6
[1, 2, 4, 7, 9], [7, 9, 4, 2] --> 1

There are number of ways this problem can be solved, below are 4 possible solutions

Algorithm

Dictionary Method
- Initialise a dictionary.
- Iterate through the first array,
- If element at current iteration exists in dictionary,
  - Increment it's value by 1.
- Else,
  - Add the element as key and value as 1 in dictionary
- Iterate through the second array,
- If element at current iteration exists in dictionary,
  - Decrement it's value by 1.
- Else,
  - Add the element as key and value as 1 in dictionary.
- for every element in dictionary
  - if value of the element is not 0
    - return the element
Exclusive OR (XOR) Method
- Initialise variable result to 0
- Combine both the arrays.
- Iterate through the combined array
- Do XOR operation of every element with result
- Return the result, which will be the missing element
Sort Method
- Sort both the given arrays.
- Iterate over both the arrays simultaneously.
- At a given iteration if value of both the iterators are different,
  - return the element from first array, as it is the missing element.
Sum Method
- Calculate the sum of all the elements in both the arrays.
- Subtract the sum of second array from the first array.
- The result will be the missing element.

Time and Space complexity

Dictionary Method
- Time Complexity: O(n)
- Space Complexity: O(n)
XOR Method
- Time Complexity: O(n)
- Space Complexity: O(n)
Sort Method
- Time Complexity: O(nlogn)
- Space Complexity: O(n)
Sum Method
- Time Complexity: O(n)
- Space Complexity: O(1)

Code

class MissingElement(object):
    def missingElement(self, arr1, arr2):
        count = {}
        for element in arr1:
            if element in count:
                count[element] += 1
            else:
                count[element] = 1
        for element in arr2:
            if element in count:
                count[element] -= 1
            else:
                count[element] = 1
        for k in count:
            if count[k] != 0:
                return k

    def missingElement2(self, arr1, arr2):
        result = 0
        for element in arr1 + arr2:
            result ^= element
        return result

    def missingElement3(self, arr1, arr2):
        arr1.sort()
        arr2.sort()
        for ele1, ele2 in zip(arr1, arr2):
            if ele1 != ele2:
                return ele1
        return arr1[-1]

    def missingElement4(self, arr1, arr2):
        return abs(sum(arr1) - sum(arr2))

Unit Test

import unittest
from missingElement import MissingElement


class TestMisssingElement(unittest.TestCase):
    def test_ele(self, sol):
        self.assertEqual(sol([5, 5, 7, 7], [5, 7, 7]), 5)
        self.assertEqual(sol([1, 2, 3, 4, 5, 6, 7],
                             [3, 7, 2, 1, 4, 6]), 5)
        self.assertEqual(sol([9, 8, 7, 6, 5, 4, 3, 2, 1],
                             [9, 8, 7, 5, 4, 3, 2, 1]), 6)
        print("All test cases passed")


def main():
    test = TestMisssingElement()
    element = MissingElement()
    test.test_ele(element.missingElement)
    test.test_ele(element.missingElement2)
    test.test_ele(element.missingElement3)
    test.test_ele(element.missingElement4)


if __name__ == "__main__":
    main()

Github repo

Original article

Happy Coding ! 🌟

Valid Elements in a sorted array

CodeWithML — Wed, 30 Sep 2020 10:01:03 +0000

Problem: Statement Write a function to count number of distinct elements given in a sorted array.

Difficulty level: Easy

Test Cases

[2, 2, 3, 3, 4, 5] --> 4
[4, 5, 7, 10, 15] --> 5
[1, 1, 1, 2, 5, 5, 5] --> 3
[1, 2, 3, 4, 4, 5, 5, 5] --> 5
None --> 0

Algorithm

Python Set Solution
- Add elements of array to set and return it's length.
Dictionary Solution
- Iterate through the given array
- If element was previously not seen in dictionary than,
- Add the element to dictionary with value of 1.
- Return the length of dictionary.
Best Solution
- Initialise index at 1
- Iterate from 1 to length of given array.
- If, the element at current iteration i is not equal to element at position of index - 1, than
- Overwrite the element at index with the element at current iteration i
- increment value of index by 1
- Return index

Time and Space complexity

Time complexity of all solutions: O(n)
Space complexity
- Set: O(n)
- Dictionary: O(n)
- Best solution: O(1)

Code

class ValidElements(object):
    def validElements(self, arr):
        if not arr:
            return 0
        return len(set(arr))

    def validElements2(self, arr):
        if not arr:
            return 0
        seen = {}
        for entry in arr:
            if entry not in seen:
                seen[entry] = 1
        return len(seen)

    def validElements3(self, arr):
        if not arr:
            return 0
        index = 1
        for i in range(1, len(arr)):
            if arr[index - 1] != arr[i]:
                arr[index] = arr[i]
                index += 1
        print(arr)
        return index

Unit Test

import unittest
from validElements import ValidElements


class TestValidElements(unittest.TestCase):
    def testValidElements(self, func):
        self.assertEqual(func([2, 2, 3, 3, 4, 5]), 4)
        self.assertEqual(func([1, 2, 3, 4, 4, 5, 5, 5]), 5)
        self.assertEqual(func([1, 1, 1, 2, 5, 5, 5]), 3)
        print("All test cases passed")


def main():
    test = TestValidElements()
    elements = ValidElements()
    test.testValidElements(elements.validElements)
    test.testValidElements(elements.validElements2)
    test.testValidElements(elements.validElements3)


if __name__ == "__main__":
    main()

Original article
Github solution

Happy Coding ! 😃

String Reversal

CodeWithML — Tue, 29 Sep 2020 08:32:13 +0000

Problem Statement: Write a function to reverse the words in a given string. Also give the solution without using the python in-built functions.

Difficulty level: Easy

Constraints

Can we assume the given strings are ASCII?

Yes
1. Is this case sensitive?
Yes
1. Can we assume this fits memory?
Yes
1. Can we use additional data structures?
Yes

Test Cases

None --> None
how are you john ? --> ? john you are how
1 --> 1
it's great to be --> be to great it's

Algorithm

Solution 1
- Python strings are immutable so we'll split the string based on space and convert it to a list.
- Iterate to len(list)/2 time, starting from i = 0
- swap element at index (i) with element at index (len(list) - 1 -i)
- increment i
Solution 2 : Without using split function
- Initialise an empty words list.
- Iterate through the string indexes till the length of string.
- if the character in string is not a space, then that is the starting index of a word
- set word_start to index of character
  - iterate again till the length of string until a space is encountered
  - increment i
  - when this iteration stops, add from word_start till i to the words list
- iterate till the end of string and increment i
- return the words list.
Solution 3 : One line python solution (using in-built functions.)
- Use split function to split the string by spaces and the slice operation to reverse the list, lastly return reversed string by using join function.

Time and Space Complexity

Solution 1
- Time complexity: O(n)
- Space complexity: O(n)
Solution 2
- Time complexity: O(n)
- Space complexity: O(n)

Code

class SentenceReversal(object):
    def sentenceReversal(self, string):
        if string is None:
            return None
        words = string.split()
        size = len(words)
        for word in range(size//2):
            words[word], words[size - 1 - word] = \
                words[size - 1 - word], words[word]
        return " ".join(words)

    def sentenceReversal2(self, string):
        if string is None:
            return None
        words = []
        size = len(string)
        spaces = [' ']
        i = 0

        while i < size:
            if string[i] not in spaces:
                word_start = i
                while i < size and string[i] not in spaces:
                    i += 1
                words.append(string[word_start:i])
            i += 1
        return " ".join(words[::-1])

    def sentenceReversal3(self, string):
        if string is None:
            return None
        return " ".join(string.split()[::-1])

Unit Test

import unittest
from sentenceReversal import SentenceReversal


class TestSentenceReversal(unittest.TestCase):
    def testSentenceReversal(self, func):
        self.assertEqual(func(None), None)
        self.assertEqual(func('   space before plague'), 'plague before space')
        self.assertEqual(func('space after    '), 'after space')
        self.assertEqual(func(' Hello John  how are you   ?'),
                         '? you are how John Hello')
        self.assertEqual(func('1'), '1')
        print("ALL TEST CASES PASSED")


def main():
    test = TestSentenceReversal()
    sent = SentenceReversal()
    test.testSentenceReversal(sent.sentenceReversal)
    test.testSentenceReversal(sent.sentenceReversal2)


if __name__ == "__main__":
    main()

Original article

Github solution

Happy Coding !

String Compression

CodeWithML — Tue, 29 Sep 2020 08:29:52 +0000

Problem statement : Write a function to Compress a given string. Only return the compressed string if it saves space.

Difficulty level: Easy

Test Cases

'AAABAACCDDDD' ---> 'A3BA2C2D4'
'BAAACCDDDD' ---> 'BA3C2D4'
'AABBCC' --> 'AABBCC'
'BBBAACCCCDD' --> 'B3A2C4D2'

Algorithm

Setup a pointer at first character of string, initialise an empty string and a counter.
Iterate through the string and check if character is equal to the first character of the string.
- if both are equal increment counter.
Else,
- add the first character and it's count to result string.
  - if count is greater than 1 then only add count to the result string.
  - Else, add an empty string to the result string.
- now, the first character will be the current character.
- reset the counter value to 1.
Add the last character and it's count to result string.
Return the resultant compressed string if it's length is less than the given string, else return the given string.

Time and Space Complexity

Time complexity: O(n)
Space complexity: O(n)

Code

class CompressString(object):
    def compress(self, input):
        if input is None or not input:
            return input
        result = ''
        count = 0
        prev_char = input[0]
        for char in input:
            if char == prev_char:
                count += 1
            else:
                result += prev_char + (str(count) if count > 1 else '')
                prev_char = char
                count = 1
        result += prev_char + (str(count) if count > 1 else '')
        return result if len(result) < len(input) else input

More precise compression

class CompressString(object):
    def compress(self, input):
        if input is None or not input:
            return input
        result = ''
        count = 0
        prev_char = input[0]
        for char in input:
            if char == prev_char:
                count += 1
            else:
               if count > 2:
                    result += prev_char + (str(count))
                    prev_char = char
                    count = 1
               elif count == 1:
                    result += prev_char
                    count = 1
                    prev_char = char
               else:
                    result += prev_char
                    result += prev_char
                    count = 1
                    prev_char = char
        result += prev_char + (str(count) if count > 2 else prev_char)
        return result if len(result) < len(input) else input

Test

import unittest
from compressString import CompressString


class TestCompress(unittest.TestCase):

    def testCompress(self, func):
        self.assertEqual(func(None), None)
        self.assertEqual(func(''), '')
        self.assertEqual(func('AABBCC'), 'AABBCC')
        self.assertEqual(func('AAABCCDDDDE'), 'A3BC2D4E')
        self.assertEqual(func('BAAACCDDDD'), 'BA3C2D4')
        self.assertEqual(func('AAABAACCDDDD'), 'A3BA2C2D4')
        print('Success: testCompress')


def main():
    test = TestCompress()
    compress_string = CompressString()
    test.testCompress(compress_string.compress)


if __name__ == '__main__':
    main()

Original article

Github solution