LeetCode Problem Solution : TwoSum III

Java solution for LeetCode Two Sum design problem:

package com.kpatil.leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * Design and implement TwoSum class, to support following methods: add and find
 * 
 * add(input) - add the number input two the internal data structure find(value)
 * - find if there exists any pair of numbers which sum is equal to the value
 *
 * e.g. add(1), add(3), add(5); find(4) -> true, find(7) -> false
 * 
 */

// Store each input into a hash table with the input as a key
// and it's count (no of times it is added) as value.
// To find if a pair sum exists, just iterate through the hash table in O(n) runtime.
// Make sure to handle duplicates

public class TwoSum {
 // O(n) space
 private Map lookupTable = new HashMap<>();

 // O(1) runtime
 public void add(int input) {
  int count = lookupTable.containsKey(input) ? lookupTable.get(input) : 0;
  lookupTable.put(input, count + 1);
 }

 // O(n) runtime
 public boolean find(int val) {

  for (Map.Entry entry : lookupTable.entrySet()) {
   int num = entry.getKey();
   int diff = val - num;
   if (diff == num) {
    // for duplicates, make sure there are at least two individual numbers
    if (entry.getValue() >= 2)
     return true;
   } else if (lookupTable.containsKey(diff)) {
    return true;
   }
  }

  return false;
 }

 public void print() {
  System.out.println("---------------------------------------------");
  for (Map.Entry entry : lookupTable.entrySet()) {
   System.out.println(entry.getKey() + " : " + entry.getValue());
  }
  System.out.println("---------------------------------------------");
 }

}

JUnit Test:

package com.kpatil.leetcode.test;

import static org.junit.Assert.*;

import org.junit.Test;

import com.kpatil.leetcode.TwoSum;

public class TwoSumTest {

 @Test
 public void testTwoSum() {
  TwoSum twoSum3 = new TwoSum();
  
  twoSum3.add(1);
  twoSum3.print();
  
  twoSum3.add(3);
  twoSum3.print();
  
  twoSum3.add(5);
  twoSum3.print();
  
  twoSum3.add(5);
  twoSum3.print();
  
  twoSum3.add(1);
  twoSum3.print();
  
  twoSum3.add(10);
  twoSum3.print();
  
  boolean found = twoSum3.find(4);
  assertEquals(found,true);
  
  boolean notFound = twoSum3.find(7);
  assertEquals(notFound,false);
  
  boolean found2 = twoSum3.find(10);
  assertEquals(found2,true);
  
  boolean found3 = twoSum3.find(11);
  assertEquals(found3,true);
  
  boolean nfound2 = twoSum3.find(12);
  assertEquals(nfound2,false);
 }
 

}

Top Down Merge Sort

Top down Merge Sort code in Java:

package com.kpatil.sort;

public class MergeSort {

 public static void sort(int[] list) {
  int[] aux = new int[list.length];
  sort(list, aux, 0, list.length - 1);
 }

 public static void sort(int[] list, int[] aux, int left, int right) {
  if (right <= left) {
   return;
  }

  int mid = left + (right - left) / 2;
  sort(list, aux, left, mid); // sort first half recursively
  sort(list, aux, mid + 1, right); // sort second half recursively
  merge(list, aux, left, mid, right); // merge two sorted halves
 }

 public static void merge(int[] list, int[] aux, int left, int mid, int right) {
  for (int k = left; k <= right; k++) {
   aux[k] = list[k];
  }
  int i = left;
  int j = mid + 1;
  for (int k = left; k <= right; k++) {
   if (i > mid) {
    list[k] = aux[j];
    j++;
   } else if (j > right) {
    list[k] = aux[i];
    i++;
   } else if (aux[j] < aux[i]) {
    list[k] = aux[j];
    j++;
   } else {
    list[k] = aux[i];
    i++;
   }
  }
 }

}

JUnit test cases:

package com.kpatil.test;

import static org.junit.Assert.assertEquals;

import java.util.Arrays;

import org.junit.Test;

import com.kpatil.sort.MergeSort;

public class MergeSortTest {
 @Test
 public void test1() {
  int[] array = { 5, 2, 89, 0, 10, 3, 20, 1 };
  int[] sorted = { 0, 1, 2, 3, 5, 10, 20, 89 };
  MergeSort.sort(array);
  assertEquals(true, Arrays.equals(array, sorted));
 }

 @Test
 public void test2() {
  int SIZE = 1000;
  int[] list = new int[SIZE];
  int[] expectedList = new int[SIZE];
  for (int i = 0; i < SIZE; i++) {
   int rand = (int) (Math.random() * SIZE);
   list[i] = rand;
   expectedList[i] = rand;
  }
  MergeSort.sort(list);
  System.out.println("------------------");
  Arrays.sort(expectedList);
  assertEquals(true, Arrays.equals(list, expectedList));

  for (int i = 0; i < SIZE; i++) {
   System.out.print(list[i] + " ");
  }
  System.out.println();
 }
}

Bubble Sort in Java

Bubble sort code in Java:

package com.kpatil.sort;

public class BubbleSort {
 public static void sort(int[] list) {
  int n = list.length;
  boolean swapped = true;
  while (swapped) {
   swapped = false;
   for (int i = 1; i < n; i++) {
    if (list[i - 1] > list[i]) {
     int temp = list[i - 1];
     list[i - 1] = list[i];
     list[i] = temp;
     swapped = true;
    }
   }
   n = n - 1;
  }
 }
}

JUnit Test Cases:

package com.kpatil.test;

import static org.junit.Assert.*;
import java.util.Arrays;
import org.junit.Test;
import com.kpatil.sort.BubbleSort;

public class BubbleSortTest {

 @Test
 public void test1() {
  int[] array = { 5, 2, 89, 0, 10, 3, 20, 1 };
  int[] sorted = { 0, 1, 2, 3, 5, 10, 20, 89 };
  BubbleSort.sort(array);
  assertEquals(true, Arrays.equals(array, sorted));
 }

 @Test
 public void test2() {
  int SIZE = 1000;
  int[] list = new int[SIZE];
  int[] expectedList = new int[SIZE];
  for (int i = 0; i < SIZE; i++) {
   int rand = (int) (Math.random() * SIZE);
   list[i] = rand;
   expectedList[i] = rand;
  }
  BubbleSort.sort(list);
  Arrays.sort(expectedList);
  assertEquals(true, Arrays.equals(list, expectedList));
  
  for (int i = 0; i < SIZE; i++) {
   System.out.print(list[i] + " ");
  }
  System.out.println();
 }

}