A list of coding exercises and solutions.

CanMakePalindrome.md

Problem:

Given a non-empty string s, you may delete at most one character. Judge whether you can make it a palindrome.

Example 1:

Input: "aba" Output: True

Example 2:

Input: "abca" Output: True

CanMakePalindrome.py

class CanMakePalindrome:
    """
    Attributes:
        checkString( [*string] ) [method]
        testInput( [*array of strings] ) [method]
    """
    

    def checkString(self, s):
        """Checks if a palindrome can be made from s by deleting characters.
        
        First, this method checks if the input string s is already a
        palindrome. If it isn't, the string is traversed character-by-
        character from the outside to the middle, deleting characters that
        aren't equal in their respective positions on either side of the 
        string. If the number of deletions is greater than 1, then the
        criteria for the problem aren't met, and the method prints False.
        Otherwise, it prints True.
        
        Parameters:
            s: The string being checked.
        """
        print('Input String: ', s)
        if s == s[::-1]:
            print('This string is already a palindrome!')
            return
    
        numDeletions = 0
        for i in range(int(len(s) / 2)):
            if s[i] != s[len(s)-i-1]:
                numDeletions += 1
        
        print('Can it be made a palindrome...? ', end=' ')
        if numDeletions <= 1:
            print('Yes!')
        else:
            print('No!')
            
    def testInput(self, stringArray):
        """Tests an array of strings for palindromes. 
        
        Parameters:
            string_array: The list of strings that will be tested.
        """
        for i in range(len(stringArray)):
            self.checkString(stringArray[i])
            print('\n')
        
        
testStrings = [
    'abcba', 'abba', '12345654321', 'abb', 'abbb', '123a321', 
    'bg0ss0gb', 'alva', 'alvaro', 'racecar', 'MmNm', 'AaaaA'
]

CanMakePalindrome().testInput(testStrings)

canPlant.md

Problem:

Suppose you have a long flowerbed in which some of the plots are planted and some are not. However, flowers cannot be planted in adjacent plots - they would compete for water and both would die.

Given a flowerbed (represented as an array containing 0 and 1, where 0 means empty and 1 means not empty), and a number n, return if n new flowers can be planted in it without violating the no-adjacent-flowers rule.

Example 1:

Input: flowerbed = [1,0,0,0,1], n = 1 Output: True

Example 2:

Input: flowerbed = [1,0,0,0,1], n = 2 Output: False

canPlant.py

def canPlant(bed, n):
    """Checks if we can plant n flowers in an existing bed.
    
    In order to determine if n flowers can be planted, I figured the simplest
    approach would be to first pad the ends with virtual empty plots so that
    the plots at either end can be compared with 2 adjacent plots. By symmetry,
    it shouldn't matter how the list is traversed, so I start on the left,
    planting flowers where possible. 
    
    Parameters:
        bed: A flowerbed where 0 represents an open plot, and 1 represents a
             planted flower.
        n: The number of flowers we'd like to plant in the flowerbed.
    
    Returns: 
        True: If n flowers can be planted in the given flowerbed, or
        False: If n flowers would not fit in the given flowerbed.
    """

    # Pads both sides of the flowerbed for the purposes of
    # comparing adjacent plots.

    new_bed = [0] + bed + [0]

    num_planted = 0
    for i in range(1, len(new_bed) - 1):
        if new_bed[i] != 1:  # checks the left-most, then adjacent plots
            if new_bed[i - 1] != 1 and new_bed[i + 1] != 1:
                new_bed[i] = 1  # plants the flower
                num_planted += 1

    print ('Input Flowerbed:', bed, '\nCan {n} flower(s) be planted? ->'
           , num_planted >= n, '\n')


canPlant([1, 0, 0, 0, 1], 1)
canPlant([1, 0, 0, 0, 1], 2)
canPlant([1, 0, 1, 0, 1], 1)
canPlant([0, 0, 0, 0, 1, 0, 0, 1], 2)
canPlant([0, 0, 0, 0, 1, 0, 0, 1], 3)

collisions.md

Problem:

Consider a one-dimensional array of asteroids.

For each asteroid, the absolute value represents its size, and the sign represents its direction (positive meaning right, negative meaning left). Each asteroid moves at the same speed. If two asteroids meet, the smaller one will explode. If both are the same size, both will explode. Two asteroids moving in the same direction will never meet.

Find out the state of the asteroids after all collisions.

collisions.py

def collisions(self, asteroids):
    system = [-1]
    for new in asteroids:
        while new < 0 < system[-1]:
            if -new < system[-1] or -new == system.pop():
                break
        else:
            system.append(new)
    return system[1:]

collisions([3, -2, 5, -8, 10])  
collisions([-1, 2, -5, 8, -10])     
collisions([1, 2, 5, 8, -10])
collisions([9, -9, 2, -10, 9])
collisions([-9, 9, 10, -10])

DoublyLinkedList.js

class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
    this.previous = null;
  }

  setNextNode(node) {
    node instanceof Node || node === null ? this.next = node : throw new Error('Argument must be a Node.');
  }

  setPreviousNode(node) {
    if (node instanceof Node || node === null) {
      this.previous = node;
    } else {
      throw new Error('Next node must be a member of the Node class')
    }
  }

  getNextNode() {
    return this.next;
  }

  getPreviousNode() {
    return this.previous;
  }
}


class DoublyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
  }

  addToHead(data) {
    const newHead = new Node(data);
    const currentHead = this.head;
    if (currentHead) {
      currentHead.setPreviousNode(newHead);
      newHead.setNextNode(currentHead);
    }
    this.head = newHead;
    if (!this.tail) {
      this.tail = newHead;
    }
  }

  addToTail(data) {
    const newTail = new Node(data);
    const currentTail = this.tail;
    if (currentTail) {
      currentTail.setNextNode(newTail);
      newTail.setPreviousNode(currentTail);
    }
    this.tail = newTail;
    if (!this.head) {
      this.head = newTail;
    }
  }
  
  printList() {
    let currentNode = this.head;
    let output = '<head> ';
    while (currentNode !== null) {
      output += currentNode.data + ' ';
      currentNode = currentNode.getNextNode();
    }
    output += '|tail>';
    console.log(output);
  }
  
  removeByData(data) {
    let nodeToRemove;
    let currentNode = this.head;
    while (currentNode !== null) {
      if (currentNode.data === data) {
        nodeToRemove = currentNode;
        break;
      }
      currentNode = currentNode.getNextNode();
    }
    if (!nodeToRemove) {
      return null;
    }
    if (nodeToRemove === this.head) {
      this.removeHead();
    } else if (nodeToRemove === this.tail) {
      this.removeTail();
    } else {
      const nextNode = nodeToRemove.getNextNode();
      const previousNode = nodeToRemove.getPreviousNode();
      nextNode.setPreviousNode(previousNode);
      previousNode.setNextNode(nextNode);
    }
    return nodeToRemove;
  }

  removeHead() {
    const removedHead = this.head;
    if (!removedHead) {
      return;
    }
    this.head = removedHead.getNextNode();
    if (this.head) {
      this.head.setPreviousNode(null);
    }
    if (removedHead === this.tail) {
      this.removeTail();
    }
    return removedHead.data;
  }

  removeTail() {
    const removedTail = this.tail;
    if (!removedTail) {
      return;
    }
    this.tail = removedTail.getPreviousNode();
    if (this.tail) {
      this.tail.setNextNode(null);
    }
    if (removedTail === this.head) {
      this.removeHead();
    }
    return removedTail.data;
  }
}

/*

const LinkedList = require('./LinkedList.js')

const testList = new LinkedList();
for (let i = 0; i <= 10; i++) {
  testList.addToTail(i);
}

testList.printList();
swapNodes(testList, 2, 5);
testList.printList();

function swapNodes(list, data1, data2) {
  console.log(`Swapping ${data1} and ${data2}:`);
  
  let node1Prev = null;
  let node2Prev = null;
  let node1 = list.head;
  let node2 = list.head;

  if (data1 === data2) {
    console.log('Elements are the same - no swap to be made');
    return;
  }
  
  while (node1 !== null) {
    if (node1.data === data1) { 
      break;
    }
    node1Prev = node1;
    node1 = node1.getNextNode();
  }
  
  while (node2 !== null) {
    if (node2.data === data2) {
      break;
    }
    node2Prev = node2;
    node2 = node2.getNextNode();
  }
  
  if (node1 === null || node2 === null) {
    console.log('Swap not possible - one or more element is not in the list');
    return;
  }

  if (node1Prev === null) {
    list.head = node2;
  } else {
    node1Prev.setNextNode(node2);
  }

  if (node2Prev === null) { 
    list.head = node1;
  } else {
node2Prev.setNextNode(node1);
  }
  
  let temp = node1.getNextNode();
  node1.setNextNode(node2.getNextNode());
  node2.setNextNode(temp); 
}*/

FizzBuzz.md

Problem:

Write a program that outputs the string representation of numbers from 1 to n.

But for multiples of three it should output 'Fizz' instead of the number and for the multiples of five output 'Buzz'. For numbers which are multiples of both three and five output 'FizzBuzz'.

Example:

Input: n = 15, Output:

[
    '1',
    '2',
    'Fizz',
    '4',
    'Buzz',
    'Fizz',
    '7',
    '8',
    'Fizz',
    'Buzz',
    '11',
    'Fizz',
    '13',
    '14',
    'FizzBuzz'
]

FizzBuzz.py

class FizzBuzz:

    def check(self, i):
        s = ''
        if i % 3 is 0:
            s += 'Fizz'
        if i % 5 is 0:
            s += 'Buzz'

        if s:
            return s
        else:
            return str(i)

    def fb(self, n):
        return map(self.check, range(1, n + 1))

HashMap.js

class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }

  setNextNode(node) {
    if (!(node instanceof Node)) {
      throw new Error('Next node must be a member of the Node class');
    }
    this.next = node;
  }

  setNext(data) {
    this.next = data;
  }

  getNextNode() {
    return this.next;
  }
}


class LinkedList {
  constructor() {
    this.head = null;
  }

  addToHead(data) {
    const newHead = new Node(data);
    const currentHead = this.head;
    this.head = newHead;
    if (currentHead) {
      this.head.setNextNode(currentHead);
    }
  }

  addToTail(data) {
    let tail = this.head;
    if (!tail) {
      this.head = new Node(data);
    } else {
      while (tail.getNextNode() !== null) {
        tail = tail.getNextNode();
      }
      tail.setNextNode(new Node(data));
    }
  }

  removeHead() {
    const removedHead = this.head;
    if (!removedHead) {
      return;
    }
    if (removedHead.next) {
      this.head = removedHead.next;
    }
    return removedHead.data;
  }

  printList() {
    let currentNode = this.head;
    let output = '<head> ';
    while (currentNode !== null) {
      output += currentNode.data + ' ';
      currentNode = currentNode.next;
    }
    output += `<tail>`;
    console.log(output);
  }

  findNodeIteratively(data) {
    let currentNode = this.head;
    while (currentNode !== null) {
      if (currentNode.data === data) {
        return currentNode;
      }
      currentNode = currentNode.next;
    }
    return null;
  }

  findNodeRecursively(data, currentNode = this.head) {
    if (currentNode === null) {
      return null;
    } else if (currentNode.data === data) {
      return currentNode;
    } else {
      return this.findNodeRecursively(data, currentNode.next);
    }
  }
}


class HashMap {
  constructor(size = 0) {
    this.hashmap = new Array(size)
      .fill(null)
      .map(() => new LinkedList());
  }

  hash(key) {
    let hashCode = 0;
    for (let i = 0; i < key.length; i++) {
      hashCode += hashCode + key.charCodeAt(i);
    }
    return hashCode % this.hashmap.length;
  }

  assign(key, value) {
    const arrayIndex = this.hash(key);
    const linkedList = this.hashmap[arrayIndex];
    if (linkedList.head === null) {
      linkedList.addToHead({ key, value });
      return;
    }
    let current = linkedList.head;
    while (current) {
      if (current.data.key === key) {
        current.data = { key, value };
      }
      if (!current.next) {
        current.next = new Node({ key, value });
        break;
      }
      current = current.getNextNode();
    }
  }

  retrieve(key) {
    const arrayIndex = this.hash(key);
    let current = this.hashmap[arrayIndex].head;
    while (current) {
      if (current.data.key === key) {
        return current.data.value;
      }
      current = current.getNextNode();
    }
    return null;
  }
}

module.exports = HashMap;

isPalindrome.md

Problem:

Given a string s, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

Note: For the purpose of this problem, we define an empty string as valid palindrome.

Example 1:

Input: "A man, a plan, a canal: Panama" Output: True

Example 2:

Input: "race a car" Output: False

Constraints: s consists only of printable ASCII characters.

isPalindrome.py

import re


def isPalindrome(self, s):
    s = re.sub('[\W_]+', '', s).lower()
    return s == s[::-1]

LinkedList.js

class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }

  setNextNode(node) {
    node instanceof Node || node === null ? this.next = node : throw new Error('Argument must be a Node.');
  }

  getNextNode() {
    return this.next;
  }
}


class LinkedList {
  constructor() {
    this.head = null;
  }

  addToHead(data) {
    const newHead = new Node(data);
    const currentHead = this.head;
    this.head = newHead;
    if (currentHead) {
      this.head.setNextNode(currentHead);
    }
  }

  addToTail(data) {
    let tail = this.head;
    if (!tail) {
      this.head = new Node(data);
    } else {
      while (tail.getNextNode() !== null) {
        tail = tail.getNextNode();
      }
      tail.setNextNode(new Node(data));
    }
  }
  
  printList() {
    let currentNode = this.head;
    let output = '|head> ';
    while (currentNode !== null) {
      output += `${currentNode.data} -> `;
      currentNode = currentNode.getNextNode();
    }
    output += '|tail>';
    console.log(output);
  }

  removeHead() {
    const removedHead = this.head;
    if (!removedHead) { return; }
    this.head = removedHead.getNextNode();
    return removedHead.data;
  }
}


const busRoute = new LinkedList();
// TODO: rotate, split and reconnect, etc.

LinkedList.md

Problem:

Given a linked list, rotate the list to the right by k places, where k is non-negative.

Example 1:

Input: 1->2->3->4->5->NULL, k = 2 Output: 4->5->1->2->3->NULL

Explanation:

rotate 1 steps to the right: 5->1->2->3->4->NULL rotate 2 steps to the right: 4->5->1->2->3->NULL

Example 2:

Input: 0->1->2->NULL, k = 4 Output: 2->0->1->NULL

Explanation:

rotate 1 steps to the right: 2->0->1->NULL rotate 2 steps to the right: 1->2->0->NULL rotate 3 steps to the right: 0->1->2->NULL rotate 4 steps to the right: 2->0->1->NULL

LinkedList.py

class LinkedList:
    """
    Attributes:
        Node [sub-class]: A container with data and 2 pointers.
        print_list() [method]: Loops through and prints the LinkedList's Nodes.
        push(data) [method]: Prepends a new Node to the LinkedList.
        pop() [method]: Removes the last node from the LinkedList.
        rotate_list(k) [method]: Uses pop() and push() to rotate LinkedList.
    """

    
    class Node:
        """
        Attributes:
            data: The value held by a Node.
            next_: The pointer from the current Node to the next.
            previous: The pointer from the current Node to the previous.
        """
        
        
        def __init__(self, data=None, next_=None, previous=None): 
            """Initialize the Node object with data and pointers.
                
            Parameters:
                data: The value held inside the node (default NULL).
                next_: The pointer to the next node (default NULL).
                previous: The pointer to the previous node (default NULL).
            """
            self.data = data 
            self.next_ = next_
            self.previous = previous

    def __init__(self): 
        """Initialize the list head pointer, list tail pointer, & length of
           the linked list.
        """
        self.head = None
        self.tail = None
        self.length = 0
    
    def print_list(self):
        """Print the contents and pointers of the LinkedList."""
        temp = self.head 
        while(temp): 
            print(temp.data, '->', end=' ') 
            temp = temp.next_
        print('NULL\n')
    
    def push(self, new_data): 
        """Create and insert a new Node at the head of the LinkedList.
        
        Parameters:
            new_data: The value held by the new Node.
        """
        new_node = self.Node(data=new_data, next_=self.head) 
  
        if self.head:
            self.head.previous = new_node
        else:
            self.tail = new_node
        self.head = new_node
        self.length += 1
        
    def pop(self):
        """Removes the tail Node from the end of the LinkedList.
        
        Returns: The data from the new Node.
        """
        new_node = self.tail
        
        if self.length == 0:
            raise LookupError('The list cannot be empty...') 
            
        if self.tail.previous:
            self.tail = self.tail.previous
            self.tail.next_ = None
        else:
            self.head = None
            self.tail = None
        self.length -= 1
            
        return new_node.data
       
    def rotate_list(self, k):
        """Rotates the LinkedList k places to the right.
        
        After giving this some thought, I can't see why rotating a linked list
        by k >= the list length would ever be useful or necessary. Unless some
        attribute(s) of the linked list are dependent on the number of 
        (probably redundant) rotations (k // length), k % length is de facto
        the same as k rotations, simplifying the logic.
        """
        if k < 0:
            print('\nk must be a non-negative integer!')
        elif k % self.length == 0:
            print('\nBeep boop...linked list rotated!')

        for i in range(k % self.length):
            temp_data = self.pop()
            self.push(temp_data)

############################################################################            
            
def test(first, last, k):
    """Function that defines the length and rotations of LinkedList.
    
    For the purposes of this problem, I just assume that each Node's data is
    an integer, and this method reflects that. For example, see the first
    test case. test(1, 5, 2) means that the first Node's value is 1 and the 
    last Node's value is 5, creating the LinkedList 1->2->3->4->5->NULL.
    
    Parameters:
        first: The data contained at the head Node.
        last: The data contained at the tail Node.
    """
    llist = LinkedList()
    for i in range(last, first-1, -1):
        llist.push(i)
    
    print('Given linked list:', end=' ')
    llist.print_list()
    print('k =', k)
    llist.rotate_list(k) 
    print('\nRotated Linked list:', end=' ')
    llist.print_list()
    print('\n')

test(1, 5, 2)
test(0, 2, 4)
test(1, 5, -2)
test(0, 2, 0)
test(0, 2, 9)

PlusOne.md

Problem:

Given a non-empty array of digits representing a non-negative integer, increment one to the integer.

The digits are stored such that the most significant digit is at the head of the list, and each element in the array contains a single digit.

You may assume the integer does not contain any leading zero, except the number 0 itself.

Example 1:

Input: [1,2,3] Output: [1,2,4] Explanation: The array represents the integer 123.

Example 2:

Input: [4,3,2,1] Output: [4,3,2,2] Explanation: The array represents the integer 4321.

PlusOne.py

def plusOne(digits):
    if digits[len(digits)-1] < 9:
        digits[len(digits)-1] += 1
    else:
        i = len(digits) - 1
        while digits[i] == 9:
            digits[i] = 0
            if i == 0:
                return [1] + digits
           i -= 1
        digits[i] += 1
    return digits

Queue.js

import DoublyLinkedList from './DoublyLinkedList';

class Queue {
  constructor(maxSize = Infinity) {
    this.queue = new LinkedList();
    this.maxSize = maxSize;
    this.size = 0;
  }

  isEmpty() {
    return this.size === 0;
  }

  hasRoom() {
    return this.size < this.maxSize;
  }

  enqueue(data) {
    if (this.hasRoom()) {
      this.queue.addToTail(data);
      ++this.size;
    } else {
      throw new Error("The queue is full!");
    }
  }

  dequeue() {
    if (!this.isEmpty()) {
      const data = this.queue.removeHead();
      --this.size;
      return data;
    } else {
      throw new Error("The queue is empty!");
    }
  }
}

RecursionVsIteration.js

const recursive = n => {
  if (n === 0) {
    return 1;
  } else if (n > 0) {
    return n * recursive(n - 1);
  }
}

const iterative = n => {
  let res = 1;
  while (n > 0) {
    res *= n;
    n -= 1;
  }
  return res;
}

Stack.js

class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }

  setNextNode(node) {
    if (!(node instanceof Node)) {
      throw new Error('Next node must be a member of the Node class');
    }
    this.next = node;
  }

  setNext(data) {
    this.next = data;
  }

  getNextNode() {
    return this.next;
  }
}


class LinkedList {
  constructor() {
    this.head = null;
  }

  addToHead(data) {
    const newHead = new Node(data);
    const currentHead = this.head;
    this.head = newHead;
    if (currentHead) {
      this.head.setNextNode(currentHead);
    }
  }

  addToTail(data) {
    let tail = this.head;
    if (!tail) {
      this.head = new Node(data);
    } else {
      while (tail.getNextNode() !== null) {
        tail = tail.getNextNode();
      }
      tail.setNextNode(new Node(data));
    }
  }

  removeHead() {
    const removedHead = this.head;
    if (!removedHead) {
      return;
    }
    if (removedHead.next) {
      this.head = removedHead.next;
    }
    return removedHead.data;
  }

  printList() {
    let currentNode = this.head;
    let output = '<head> ';
    while (currentNode !== null) {
      output += currentNode.data + ' ';
      currentNode = currentNode.next;
    }
    output += `<tail>`;
    console.log(output);
  }

  findNodeIteratively(data) {
    let currentNode = this.head;
    while (currentNode !== null) {
      if (currentNode.data === data) {
        return currentNode;
      }
      currentNode = currentNode.next;
    }
    return null;
  }

  findNodeRecursively(data, currentNode = this.head) {
    if (currentNode === null) {
      return null;
    } else if (currentNode.data === data) {
      return currentNode;
    } else {
      return this.findNodeRecursively(data, currentNode.next);
    }
  }

}


class Stack {
  constructor(maxSize = Infinity) {
    this.stack = new LinkedList();
    this.maxSize = maxSize;
    this.size = 0;
  }

  isEmpty() {
    return this.size === 0;
  }

  hasRoom() {
    return this.size < this.maxSize;
  }

  push(value) {
    if (this.hasRoom()) {
      this.stack.addToHead(value);
      this.size++;
    } else {
      throw new Error('Stack is full');
    }
  }

  peek() {
    if (this.isEmpty()) {
      return null;
    } else {
      return this.stack.head.data;
    }
  }

  pop() {
    if (!this.isEmpty()) {
      const value = this.stack.removeHead();
      this.size--;
      return value;
    } else {
      throw new Error('Stack is empty');
    }
  }

}