Code Exercises Round II: #5 in 8 days

Problem: You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

Solution:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode rval = null;
        ListNode current = null;
        
        int carry = 0;

        while(l1 != null || l2 != null) {
            int subtotal = 0;
            
            if(l1 != null && l2 != null) {
                subtotal = l1.val + l2.val + carry;
                l1 = l1.next;
                l2 = l2.next;
            }
            // only l2 has content
            else if (l1 == null) {
                subtotal = l2.val + carry;
                l2 = l2.next;
            }
            // only l1 has content
            else {
                subtotal = l1.val + carry;
                l1 = l1.next;
            }
            
            if(subtotal > 9) {
                carry = 1;
            }                   
            else {
                carry = 0;
            }
            
            ListNode subtotalNode = new ListNode(subtotal % 10);
            
            // initialize
            if(rval == null) {
                current = subtotalNode;
                rval = current;
            }
            else {
                current.next = subtotalNode;
                current = current.next;
            }
        }
        
        if(carry > 0) {
            current.next = new ListNode(1);
        }
        return rval;
    }
}

Code Exercises Round II: #4 in 8 days

problem: Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.

solution:

    public int lengthOfLongestSubstring(String s) {
        int maxCount = 0;
        
        for(int i = 0; i < s.length(); i++) {
            Set<Character> previous = new HashSet<Character>();
            int count = 0;
            for(int j = i; j < s.length(); j++) {
                if(previous.add(s.charAt(j))) {
                    count++;
                }
                else {
                    break;
                }
            }
            maxCount = Math.max(maxCount, count);
        }
        
        return maxCount;
    }

Coding Exercises Round II: #3 in 8 days

Problem: There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays.

public static double findMedian(int[] a, int[] b) {
    int[] merged = new int[a.length + b.length];

    int i = 0;
    int j = 0;
    int k = 0;

    while(k < merged.length) {
      if(i < a.length && j < b.length) {
        if(a[i] <= b[j]) {
          merged[k] = a[i];
          i++;
        }
        else {
          merged[k] = b[j];
          j++;
        }
        k++;
      }
      else if (j == b.length) {
        for(int l = i; l < a.length; l++) {
          merged[k] = a[l];
          k++;
          i++;
        }
      }
      else {
        for(int l = j; l < b.length; l++) {
          merged[k] = b[l];
          k++;
          j++;
        }
      }

    }
    if(merged.length % 2 != 0) {
      return (double) merged[merged.length/2];
    }
    else {
      return ((double) (merged[merged.length/2] + merged[merged.length/2 - 1]))/2;
    }
  }

Coding Exercises Round II: #2 in 1 day

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2.

Please note that your returned answers (both index1 and index2) are not zero-based. You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

public class Solution {
  public int[] twoSum(int[] numbers, int target) {
    int[] rval = new int[2];
    boolean finished = false;

    for(int i = 0; i < numbers.length; i++) {
      if(finished) {
        break;
      }
      else {
        if(numbers[i] <= target) {
          for(int j = i + 1; j < numbers.length; j++) {
            if(numbers[i] + numbers[j] == target) {
              rval[0] = i + 1;
              rval[1] = j + 1;

              finished = true;
              break;
            }
          }
        }
      }
    }
    return rval;
  }
}

Coding Exercises Round II: #1 in 1 day

Question: Return all given permutations of a string.

import java.util.ArrayList;
import java.util.List;

public class PermuteString {

  private List permutations;

  public PermuteString() {
    permutations = new ArrayList();
  }

  /**
   * Permute a string.
   *
   * @param s
   */
  void permute(String s) {
    permuteString(s, "");
  }

  void permuteString(String remainingLetters, String partialPermutation) {
    if(remainingLetters.length() == 0) {
      permutations.add(partialPermutation);
    }
    else {
      String letter = String.valueOf(remainingLetters.charAt(0));
      remainingLetters = remainingLetters.substring(1);

      if(partialPermutation.length() == 0) {
        permuteString(remainingLetters, letter);
      }
      else {
        for(int j = 0; j <= partialPermutation.length(); j++) {
          String extendedPartialPermutation = partialPermutation.substring(0,j) + 
              letter + partialPermutation.substring(j);

          permuteString(remainingLetters, extendedPartialPermutation);
        }
      }
    }
  }

  public List getPermutations() {
    return permutations;
  }
}

Coding Exercises Day 27d (Problem #24)

Problem:

Implement Depth First Search for a Binary Tree

public <T> static boolean depthFirstSearch(Node<T extends Comparable<T>>  node, T value) {
  if (null == node) return false;

  if (value.compareTo(node.getValue()) == 0) {
    return true;
  }
  return depthFirstSearch(node.getLeft(), value) || 
         depthFirstSearch(node.getRight(), value);
}

Coding Exercises Day 27c (Problem #23)

Problem:

For a Binary Search Tree, insert a node.

class BinarySearchTree<T extends Comparable<T>> {

  Node<T> root;

  public BinarySearchTree(Node<T> root) {
    this.root = root;
  }
  
  public void insert(T value) {
    insert(root, value);
  }

  private void insert(Node<T> node, T value) {
    if (value.compareTo(node.getValue()) < 0) {
      if (node.getLeft() != null) {
        insert(node.getLeft(), value);
      }
      else {
        node.setLeft(new Node<T>(value));
      }
    }
    else if (value.compareTo(node.getValue()) > 0) {
      if (node.getRight() != null) {
        insert(node.getRight(), value);
      }
      else {
        node.setRight(new Node<T>(value));
      }
    }
  }
}

Coding Exercises Day 27b (Problem #22)

Problem:
Traverse a Binary Tree in InOrder, PreOrder, and PostOrder

class Tree <T> {
  Node<T> root;

  public <T> Tree(Node<T> root) {
    this.root = root;
  }

  public void inOrder() {
    inOrder(root);
  }
 
  private void inOrder(Node node) {
    if (node != null) {
      inOrder(node.getLeft());
      System.out.print(node.getValue());
      inOrder(node.getRight());
    }
  }

  public void preOrder() {
    preOrder(root);
  }
  
  private void preOrder(Node node) {
    if (node != null) {
      System.out.print(node.getValue());
      preOrder(node.getLeft());
      preOrder(node.getRight());
    }
  }

  public void postOrder() {
    postOrder(root);
  }

  private void postOrder(Node node) {
    if (node != null) {
      postOrder(node.getLeft());
      postOrder(node.getRight());
      System.out.print(node.getValue());
  } 
}

Coding Exercises Day 27 (Problem #21)

Problem:

Describe how you could use a single array to implement three stacks.

class ThreeStacks {
  private static final String STACK_ID_ERROR_MSG = "Stack Id must be 0, 1, or 2";
  
  int[] stackSize = new int[3];

  T[] dataArray;

  public ThreeStacks(int initialSize) {
    dataArray = new T[initialSize];
  }

  public push(int stackId, T element) throws IllegalArgumentException {
    if (stackId < 0 || stackId > 2) throw IllegalArgumentException(STACK_ID_ERROR_MSG);

    // if data array is too small, triple it and copy over contents
    if (dataArray.length < (stackSize[stackId] + 1) * 3) {
      increaseDataArray();
    }    

    for (int i = stackSize[stackId]; i > 0; i--) {
      int index = i * 3 + stackId;
      dataArray[index] = dataArray[index - 3];      
    }

    stackSize[stackId]++;
    dataArray[stackId] = element;
  }

  public pop(int stackId) {
    if (stackId < 0 || stackId > 2) throw IllegalArgumentException(STACK_ID_ERROR_MSG);

    if (stackSize[stackId] == 0) return null;

    T rval = dataArray[stackId];

    int index = stackId;

    for (int i = 0; i < stackSize[stackId]; i++) {
      dataArray[index] = dataArray[index + 3];      
    }    

    stackSize[stackId]--;

    return rval;
  }

  private increaseDataArray() {
    T[] biggerDataArray = new T[dataArray.length * 3];

    for (int i = 0; i < dataArray.length; i++) {
      biggerDataArray[i] = dataArray[i];
    }
  }
}

Coding Exercises Day 25b (Problem #20)

Problem:

Imagine a (literal) stack of plates.If the stack gets too high, it might topple.Therefore, in real life, we would likely start a new stack when the previous stack exceeds some threshold.Implement a data structure SetOfStacks that mimics this.SetOfStacks should be composed of several stacks, and should create a new stack once the previous one exceeds capacity.SetOfStacks.push() and SetOfStacks.pop() should behave identically to a single stack (that is, pop() should return the same values as it would if there were just a single stack).

Follow up:

Implement a function popAt(int index) which performs a pop operation on a specific sub-stack.

class SetOfStacks {
  int threshold;
  int size;

  List<Stack<Node>> stackList = new ArrayList<Stack<Node>>();

  public SetOfStacks(int threshold) {
    this.threshold = threshold;
  }

  public void push(Node node) {
    size++;
    if ((threshold * stackList.size()) < size) {
      stackList.add(0, new Stack<Node>);
    }
    stackList.get(0).push(node);
  }

  public Node pop() {
    if (0 == size) return null;

    size--;

    Stack topStack = stackList.get(0);

    Node rval = topStack.pop();

    if (topStack.empty()) {
      stackList.remove(0);
    }

    return rval; 
  }  

  public Node popAt(int index) {
    Stack<Node> stack = stackList.get(index);
    Node rval = stack.pop();

    Stack temp = new Stack();

    // Rebalance stacks
    for (int i = index - 1; i <= 0; i--) {
      Stack<Node> previousStack = stackList.get(i);
      
      while(!previousStack.empty()) {
        temp.push(previousStack.pop());
      }

      // Fill the empty slot with an element from the previous stack.
      stackList.get(i + 1).push(temp.pop());
      
      while (!temp.empty()) {
        previousStack.push(temp.pop());
      }
    }

    if (stack.empty()) {
      stackList.remove(index);
    }

    return rval;
  }
}

Coding Exercises Day 25 (Problem #19)

Problem:
How would you design a stack which, in addition to push and pop, also has a function min which returns the minimum element?  Push, pop, and min all operate in O(1) time.

class Stack {
  List<Node> minList = new LinkedList<Node>();

  Node top = null;

  public void push(Node node) {
    if (null == top) {
      top = node;
      node.setNext(null);

      minList.add(0, node);
    }    
    else {
      node.setNext(top);
      top = node;

      // This is the new minimum
      if (node.getValue() < minList.get(0).getValue()) {
        minList.add(0, node);
      }
      else {
        // previous minimum node is still the minimum
        minList.add(0, minList.get(0));
      }
    }
  } 

  public Node pop() {
    rval = top;

    top = top.getNext();

    minList.remove(0);

    return rval;
  }

  public Node min() {
    return minList.get(0);
  }
}

Coding Exercises Day 24b (Problem #18)

Problem:
Write a program to sort a stack in ascending order.  You should not make any assumptions about how the stack is implemented. The following are the only functions that should be used to write this program: push | pop | peek | isEmpty

public void sortStack(Stack<Node> stack) {
  List<Node> tempList = new ArrayList<Node>();

  while(!stack.isEmpty()) {
    tempList.add(stack.pop());  
  }
  
  Comparator comparator = new Comparator( {
    public int compare(Node nodeOne, Node nodeTwo) {
      if (nodeOne.getValue() == nodeTwo.getValue()) return 0;
      
      // Sort in Descending Order
      if (nodeOne.getValue() > nodeTwo.getValue())  {
        return -1;
      }
      else {
        return 1;
      }
    } 
  });

  Collections.sort(tempList, comparator);

  for (Node node : tempList) {
    stack.push(node);
  }
}

Coding Exercises Day 24 (Problem #17)

Problem:

Implement a MyQueue class which implements a queue using two stacks.

class MyQueue {
  Stack<Node> stackLIFO = new Stack<Node>(); 
  Stack<Node> stackFIFO = new Stack<Node>();
  
  public void enqueue(Node node) {
    stackLIFO.push(node);
  }

  public Node dequeue() {
    if (stackFIFO.isEmpty() && stackLIFO.isEmpty()) return null;

    if (!stackFIFO.isEmpty()) {
      return stackFIFO.pop();
    }
    else {
      while(!stackLIFO.isEmpty()) {
        Node temp = stackLIFO.pop();
        stackFIFO.push(temp);
      }
      return stackFIFO.pop();
    }
  }
}

Coding Exercises Day 12 (Problem #16)

Problem:
You have two numbers represented by a linked list, where each node contains a single digit.  The digits are stored in reverse order, such that the 1's digit is at the head of the list.  Write a function that adds the two numbers and returns the sum as a linked list.

Example:
Input: (7 -> 1 -> 6) + (5 -> 9 -> 2).  Translates to 617 + 295.
Output: 2 -> 1 -> 9.  Translates to 912.

Follow Up:
Suppose the digits are stored in forward order.  Repeat the above problem.

Example:
Input: (6 -> 1 -> 7) + (2 -> 9 -> 5).  Translates to 617 + 295.
Output: 9 -> 1 -> 2.  Translates to 912.

List sum(List<Integer> numOneList, List<Integer> numTwoList, boolean isReversed) {
  StringBuilder numOneString = new StringBuilder();
  StringBuilder numTwoString = new StringBuilder();
   
  for (Integer digit : numOneList) {
    numOneString.append(digit);
  }

  for (Integer digit : numTwoList) {
    numOneString.append(digit);
  }

  if (isReversed) {
    numOneString.reverse();
    numTwoString.reverse();
  }

  int sum = Integer.parseInt(numOneString.toString()) 
         + Integer.parseInt(numTwoString.toString());

  List<Integer> rval = new LinkedList<Integer>();
  
  String sumString = String.valueOf(sum);

  for (int i = 0; i < sumString.length(); i++) {
    int j = i;
    if (isReversed) {
      j = sumString.length() - 1 - i;  
    }
    rval.add(sumString.charAt(j));
  }
  return rval;
}

Coding Exercises Day 11 (Problem #15)

Problem:
Given a circular linked list, implement and algorithm which returns the node at the beginning of the loop.

Definition:
Circular linked list: A corrupt linked list in which a nodes next pointer points to an earlier node, so as to make a loop in the linked list.

Example:
Input: A -> B -> C -> D -> E -> C (same C as earlier)
Ouput: C

Node * findLoopHead(Node *head) {
  if (NULL == head) {
    return NULL;
  }
  int listSize = 1;

  Node *node = head->next;

  while (node != NULL) {
    // Start at head and look at previous nodes
    int i;
    Node *previous = head;
    
    for (i = 0; i < listSize; i++) {
      if (node == previous) {
        return node;
      }
      previous = head->next;
    }
 
    listSize++;
    node = node->next;
  }
  // Not a circular linked list
  return NULL;
}

Coding Exercises Day 10 (Problem #14)

Problem:
Implement a function to check if a linked list is a palindrome

 boolean isPalindrome(List<T> list) {
  Stack<T> stack = new Stack<T>();

  int size = list.size();

  if (size < 2) return true;
  
  boolean sizeIsOdd = (size % 2 != 0) ? true : false;

  for (int i = 0; i < size; i++) {
    T element = list.get(i);
    
    if (i < size / 2) stack.push(element);
    
    // Ignore the middle element if the list size is odd.
    if ((!sizeIsOdd && i == size / 2) || i > size / 2) {
      if (stack.peek() == element) { 
        stack.pop();
      }
      else {
        return false;
      }
    }
  }
  return true;
}

Coding Exercises Day 9b (Problem #13)

Problem:
Write code to partition a linked list around a value x such that all nodes less than x come before all nodes greater than or equal to x.

 void partitionList(List<T> list, int pivot) {
  int elementsSeen = 0;
  int size = list.size();
  
  Iterator<T> iter = list.iterator();  

  while (elementsSeen < size && iter.hasNext()) {
    T element = iter.next();
    iter.remove();
    
    if (element < pivot) {
      list.add(0);  
    }
    else {
      list.add(size - 1);
    }
    elementsSeen++;
  }  
}

Coding Exercises Day 9 (Problem #12)

Problem

Given an image represented by an NxN matrix, where each pixel in the image is 4 bytes, write a method to rotate the image by 90 degrees.  Can you do this in place?

void rotate90Degrees(byte[][] image) {
  // Run through rows 0 -> n/2 - 1 and rotate all bytes in that row
  for (int i = 0; i < n/2; i++) {
    for (int j = i; j < n - i; j++) {
      rotateByte90Degrees(image, i, j);
    }
  }  
}

// Rotate all four bytes corresponding to x,y.
void rotateByte90Degrees(byte[][] image, int x, int y) {
  int lastIndex = image.length - 1;
  
  byte nextByte = image[y][lastIndex - x];
  
  // Rotation 1
  image[y][lastIndex - x] = image[x][y];
  
  // Store the byte that was overwritten in x,y.
  // We are treating image[x][y] as an additional temp var.
  image[x][y] = nextByte;
  
  // Store the next byte that will be overwritten
  nextByte = image[lastIndex - x][lastIndex - y];
  
  // Rotation 2
  image[lastIndex - x][lastIndex - y] = image[x][y];

  image[x][y] = nextByte;
  nextByte = image[lastIndex - y][x];

  // Rotation 3
  image[lastIndex - y][x] = image[x][y];
  
  // Rotation 4
  image[x][y] = nextByte;
}

Coding Exercises Day 8c (Problem #11)

Problem:
Implement an algorithm in C to delete a node in the middle of a singly linked list.

void delete(Node *head, Node *nodeToDelete) {
  if (head == nodeToDelete) {
    head = head->next;
  }
  Node *current = head;
  Node *next = head->next;

  while (next != NULL) {
    if (next == nodeToDelete) {
      current->next = next->next;
      break;
    }
    current = next;
    next = next->next;
  }  
}

Followup:
Assume you only have access to that node and not the head of the list

void delete(Node *node) {
  if (node != NULL) {
    node->next = node->next->next;
    node->value = node->next->value;
  }
}

Coding Exercises Day 8b (Problem #10)

Problem:
Implement an algorithm to find the kth to last element of a singly linked list.

 T findKthToLast(List<T> list, k) {
  if (k = 0) return null;

  int size = 0;
  
  Map<Integer, T> elementMap = new HashMap<Integer, T>();

  for (T element : list) {
    size++;
    elementMap.put(size, element);
  }
  return elementMap.get(size - k + 1);
}