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));
      }
    }
  }
}