Initial commit

21 files changed, 608 insertions, 0 deletions

diff --git a/Anagram.java b/Anagram.java
new file mode 100644
index 0000000..d7f8280
--- /dev/null
+++ b/Anagram.java
@@ -0,0 +1,27 @@
+import java.lang.*;
+import java.util.*;
+
+class Anagram {
+	public static boolean isAnagram(String s, String t) {
+		char[] arrS = s.toCharArray();
+		char[] arrT = t.toCharArray();
+		int[] occur = new int[26];
+		for (char c : arrS) {
+			occur[c - 'a']++;
+		}
+		for (char c : arrT) {
+			occur[c - 'a']--;
+		}
+		for (int i : occur) {
+			if (i != 0)
+				return false;
+		}
+		return true;
+	}
+
+	public static void main(String[] args) {
+		String s = "anagram";
+		String t = "nagaram";
+		System.out.println(isAnagram(s, t));
+	}
+}
diff --git a/CloneGraph.java b/CloneGraph.java
new file mode 100644
index 0000000..ada085c
--- /dev/null
+++ b/CloneGraph.java
@@ -0,0 +1,39 @@
+import java.lang.*;
+import java.util.*;
+import node.*;
+
+class CloneGraph {
+	public static GraphNode cloneGraph(GraphNode node) {
+		Stack<GraphNode> stack = new Stack<GraphNode>();
+		ArrayList<GraphNode> visited = new ArrayList<GraphNode>();
+		stack.push(node);
+		GraphNode clone = new GraphNode(node.val, node.neighbors);
+		while (!stack.empty()) {
+			node = stack.pop();
+			if (visited.contains(node))
+				continue;
+			GraphNode curr = new GraphNode(node.val, node.neighbors);
+			visited.add(node);
+			System.out.println("Node: " + node.val);
+			System.out.print("Neighbors: ");
+			for (GraphNode neighbor : node.neighbors) {
+				stack.push(neighbor);
+				System.out.print(neighbor.val + " ");
+			}
+			System.out.println();
+		}
+		return clone;
+	}
+
+	public static void main(String[] args) {
+		GraphNode head = new GraphNode(1);
+		GraphNode first = new GraphNode(2);
+		GraphNode second = new GraphNode(3);
+		GraphNode third = new GraphNode(4, new ArrayList<>(Arrays.asList(first, second)));
+		second.neighbors = new ArrayList<>(Arrays.asList(head, third));
+		first.neighbors = new ArrayList<>(Arrays.asList(head, second));
+		head.neighbors = new ArrayList<>(Arrays.asList(first, second));
+
+		GraphNode curr = cloneGraph(head);
+	}
+}
diff --git a/CourseSchedule.java b/CourseSchedule.java
new file mode 100644
index 0000000..5b5ed02
--- /dev/null
+++ b/CourseSchedule.java
@@ -0,0 +1,60 @@
+import java.lang.*;
+import java.util.*;
+import node.*;
+
+class CourseSchedule {
+	public static boolean canFinish(int[][] prerequisites) {
+		GraphNode node = createGraph(prerequisites);
+		return !detectCycle(node);
+	}
+
+	public static GraphNode createGraph(int[][] prerequisites) {
+		HashMap<Integer, GraphNode> map = new HashMap<Integer, GraphNode>();
+		for (int[] prerequisite : prerequisites) {
+			if (map.containsKey(prerequisite[0])) {
+				if (map.containsKey(prerequisite[1])) {
+					map.get(prerequisite[0]).neighbors.add(map.get(prerequisite[1]));
+				} else {
+					GraphNode node = new GraphNode(prerequisite[1]);
+					map.put(node.val, node);
+					map.get(prerequisite[0]).neighbors.add(node);
+				}
+				continue;
+			}
+			GraphNode pre = new GraphNode(prerequisite[1]);
+			GraphNode node = new GraphNode(prerequisite[0],
+					new ArrayList<GraphNode>(Arrays.asList(pre)));
+			map.put(pre.val, pre);
+			map.put(node.val, node);
+		}
+		// TODO: return first GraphNode in map
+		return map.get(1);
+	}
+
+	public static boolean detectCycle(GraphNode node) {
+		Stack<GraphNode> stack = new Stack<GraphNode>();
+		ArrayList<GraphNode> visited = new ArrayList<GraphNode>();
+		stack.push(node);
+		while (!stack.empty()) {
+			node = stack.pop();
+			if (visited.contains(node)) {
+				System.out.println("Cycle " + node.val);
+				return true;
+			}
+			visited.add(node);
+			System.out.println("Node: " + node.val);
+			System.out.print("Neighbors: ");
+			for (GraphNode neighbor : node.neighbors) {
+				stack.push(neighbor);
+				System.out.print(neighbor.val + " ");
+			}
+			System.out.println();
+		}
+		return false;
+	}
+
+	public static void main(String[] args) {
+		int[][] prerequisites = {{1, 4}, {1, 2}, {2, 3}, {3, 6}, {6, 2}, {4, 5}};
+		System.out.println(canFinish(prerequisites));
+	}
+}
diff --git a/ListCycle.java b/ListCycle.java
new file mode 100644
index 0000000..a48f38a
--- /dev/null
+++ b/ListCycle.java
@@ -0,0 +1,32 @@
+import java.lang.*;
+import java.util.*;
+import node.*;
+
+class ListCycle {
+	public static boolean hasCycle(ListNode head) {
+		if (head == null)
+			return false;
+		else if (head.next == null)
+			return false;
+
+		ListNode slow = head;
+		ListNode fast = head.next;
+		while (slow != null && fast.next != null) {
+			if (slow == fast)
+				return true;
+			slow = slow.next;
+			fast = fast.next.next;
+		}
+		return false;
+	}
+
+	public static void main(String[] args) {
+		ListNode first = new ListNode(2, null);
+		ListNode third = new ListNode(4, first);
+		ListNode second = new ListNode(0, third);
+		first.next = second;
+		ListNode head = new ListNode(3, first);
+
+		System.out.println(hasCycle(head));
+	}
+}
diff --git a/LongestPalindrome.java b/LongestPalindrome.java
new file mode 100644
index 0000000..447bb27
--- /dev/null
+++ b/LongestPalindrome.java
@@ -0,0 +1,55 @@
+import java.lang.*;
+import java.util.*;
+
+class LongestPalindrome {
+	public static String longestPalindrome(String s) {
+		// TODO: check if s length is 0 or 1
+		// TODO: find simpler solution
+
+		s = s.toLowerCase();
+		char[] arr = s.toCharArray();
+		String ans = null;
+
+		int i = 0;
+		int j = 0;
+		int max = 0;
+		// Odd case: "aba"
+		for (int a = 1; a < arr.length - 1; a++) {
+			i = a - 1;
+			j = a + 1;
+			while (i >= 0 && j < arr.length) {
+				if (arr[i] == arr[j]) {
+					if (j - i > max) {
+						max = j - i;
+						ans = s.substring(i, j + 1);
+					}
+					i--;
+					j++;
+				} else {
+					break;
+				}
+			}
+		}
+		// Even case: "abba"
+		for (i = 0, j = i + 1; i < arr.length - 1; i++) {
+			while (i >= 0 && j < arr.length) {
+				if (arr[i] == arr[j]) {
+					if (j - i > max) {
+						max = j - i;
+						ans = s.substring(i, j + 1);
+					}
+					i--;
+					j++;
+				} else {
+					break;
+				}
+			}
+		}
+		return ans;
+	}
+
+	public static void main(String[] args) {
+		String s = "kl;fadsjf;dalscbbciuporeqwrpo";
+		System.out.println(longestPalindrome(s));
+	}
+}
diff --git a/LongestSubstringWithoutRepeat.java b/LongestSubstringWithoutRepeat.java
new file mode 100644
index 0000000..d01ecf3
--- /dev/null
+++ b/LongestSubstringWithoutRepeat.java
@@ -0,0 +1,27 @@
+import java.lang.*;
+import java.util.*;
+
+class LongestSubstringWithoutRepeat {
+	public static int lengthOfLongestSubstring(String s) {
+		char[] arr = s.toCharArray();
+		int max = 0;
+		ArrayList<Character> occur = new ArrayList<Character>();
+		for (char c : arr) {
+			if (!occur.contains(c)) {
+				occur.add(c);
+			} else {
+				occur.clear();
+				occur.add(c);
+			}
+			if (max < occur.size()) {
+				max = occur.size();
+			}
+		}
+		return max;
+	}
+
+	public static void main(String[] args) {
+		String s = "pwwkew";
+		System.out.println(lengthOfLongestSubstring(s));
+	}
+}
diff --git a/MaxSubArray.java b/MaxSubArray.java
new file mode 100644
index 0000000..89698c2
--- /dev/null
+++ b/MaxSubArray.java
@@ -0,0 +1,19 @@
+import java.lang.*;
+import java.util.*;
+
+class MaxSubArray {
+	public static int maxSubArray(int[] nums) {
+		int currSum = 0;
+		int maxSum = 0;
+		for (int i : nums) {
+			currSum = Math.max(currSum + i, 0);
+			maxSum = Math.max(maxSum, currSum);
+		}
+		return maxSum;
+	}
+
+	public static void main(String[] args) {
+		int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
+		System.out.println(maxSubArray(nums));
+	}
+}
diff --git a/MergeLists.java b/MergeLists.java
new file mode 100644
index 0000000..e939511
--- /dev/null
+++ b/MergeLists.java
@@ -0,0 +1,62 @@
+import java.lang.*;
+import java.util.*;
+import node.*;
+
+class MergeLists {
+	public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
+		if (list1 == null && list2 == null)
+			return new ListNode();
+		else if (list1 == null)
+			return list2;
+		else if (list2 == null)
+			return list1;
+
+		ListNode curr1 = list1;
+		ListNode curr2 = list2;
+
+		ListNode head;
+		if (curr1.val < curr2.val) {
+			head = curr1;
+			curr1 = curr1.next;
+		} else {
+			head  = curr2;
+			curr2 = curr2.next;
+		}
+
+		ListNode node = head;
+		while (curr1 != null && curr2 != null) {
+			if (curr1.val < curr2.val) {
+				node.next = curr1;
+				curr1 = curr1.next;
+			} else {
+				node.next = curr2;
+				curr2 = curr2.next;
+			}
+			node = node.next;
+		}
+
+		if (curr1 == null) {
+			node.next = curr2;
+		} else {
+			node.next = curr1;
+		}
+
+		return head;
+	}
+
+	public static void main(String[] args) {
+		ListNode second1 = new ListNode(4, null);
+		ListNode first1 = new ListNode(2, second1);
+		ListNode list1 = new ListNode(1, first1);
+
+		ListNode second2 = new ListNode(4, null);
+		ListNode first2 = new ListNode(3, second2);
+		ListNode list2 = new ListNode(1, first2);
+
+		ListNode curr = mergeTwoLists(list1, list2);
+		while (curr != null) {
+			System.out.println(curr.val);
+			curr = curr.next;
+		}
+	}
+}
diff --git a/MinRotatedArray.java b/MinRotatedArray.java
new file mode 100644
index 0000000..b93b2b4
--- /dev/null
+++ b/MinRotatedArray.java
@@ -0,0 +1,27 @@
+import java.lang.*;
+import java.util.*;
+
+class MinRotatedArray {
+	public static int findMin(int[] nums) {
+		int s = 0;
+		int e = nums.length - 1;
+		int min = Integer.MAX_VALUE;
+		while (s < e) {
+			int mid = (s + e) / 2;
+			if (nums[mid - 1] > nums[mid]) {
+				return nums[mid];
+			}
+			if (nums[s] < nums[mid] && nums[e] < nums[mid])
+				s = mid + 1;
+			else {
+				e = mid - 1;
+			}
+		}
+		return min;
+	}
+
+	public static void main(String[] args) {
+		int[] nums = {3, 4, 5, 1, 2};
+		System.out.println(findMin(nums));
+	}
+}
diff --git a/Palindrome.java b/Palindrome.java
new file mode 100644
index 0000000..2c1ca47
--- /dev/null
+++ b/Palindrome.java
@@ -0,0 +1,30 @@
+import java.lang.*;
+import java.util.*;
+
+class Palindrome {
+	public static boolean isPalindrome(String s) {
+		s = s.toLowerCase();
+		char[] nonAlpha = s.toCharArray();
+		ArrayList<Character> alpha = new ArrayList<Character>();
+		for (char c : nonAlpha) {
+		   if (Character.isLetter(c))
+			   alpha.add(c);
+		}
+
+		int i = 0;
+		int j = alpha.size() - 1;
+		while (i < j) {
+			if (alpha.get(i) != alpha.get(j))
+				return false;
+			i++;
+			j--;
+		}
+
+		return true;
+	}
+
+	public static void main(String[] args) {
+		String s = "A man, a plan, a canal: Panama";
+		System.out.println(isPalindrome(s));
+	}
+}
diff --git a/Parentheses.java b/Parentheses.java
new file mode 100644
index 0000000..b1a1b82
--- /dev/null
+++ b/Parentheses.java
@@ -0,0 +1,26 @@
+import java.lang.*;
+import java.util.*;
+
+class Parentheses {
+	public static boolean isValid(String s) {
+		HashMap<Character, Character> map = new HashMap<Character, Character>();
+		map.put(')','(');
+		map.put(']','[');
+		map.put('}','{');
+		Stack<Character> stack = new Stack<Character>();
+		char[] arr = s.toCharArray();
+		stack.push(arr[0]);
+		for (int i = 1; i < arr.length; i++) {
+			if (arr[i] == '(' || arr[i] == '[' || arr[i] == '{')
+				stack.push(arr[i]);
+			else if (map.get(arr[i]) == stack.peek())
+				stack.pop();
+		}
+		return stack.isEmpty();
+	}
+
+	public static void main(String[] args) {
+		String s = ")(";
+		System.out.println(isValid(s));
+	}
+}
diff --git a/ProductExceptSelf.java b/ProductExceptSelf.java
new file mode 100644
index 0000000..3b56f11
--- /dev/null
+++ b/ProductExceptSelf.java
@@ -0,0 +1,31 @@
+import java.lang.*;
+import java.util.*;
+
+class ProductExceptSelf {
+	public static int[] product(int[] nums) {
+		int[] left = new int[nums.length];
+		int[] right = new int[nums.length];
+		left[0] = 1;
+		right[nums.length - 1] = 1;
+
+		int s = 1;
+		int e = nums.length - 2;
+		while (s <= nums.length && e >= 0) {
+			left[s] = left[s - 1] * nums[s - 1];
+			right[e] = right[e + 1] * nums[e + 1];
+			s++;
+			e--;
+		}
+
+		int[] res = new int[nums.length];
+		for (int i = 0; i < nums.length; i++)
+			res[i] = left[i] * right[i];
+
+		return res;
+	}
+
+	public static void main(String[] args) {
+		int[] nums = {-1, 1, 0, -3, 3};
+		System.out.println(Arrays.toString(product(nums)));
+	}
+}
diff --git a/RemoveNthNode.java b/RemoveNthNode.java
new file mode 100644
index 0000000..bdcde30
--- /dev/null
+++ b/RemoveNthNode.java
@@ -0,0 +1,37 @@
+import java.lang.*;
+import java.util.*;
+import node.*;
+
+class RemoveNthNode {
+	public static ListNode removeNthFromEnd(ListNode head, int n) {
+		if (head.next == null && n == 1)
+			return head.next;
+
+		ListNode prev = head;
+		ListNode end = head;
+		while (n > 0 && end.next != null) {
+			end = end.next;
+			n--;
+		}
+		while (end.next != null) {
+			prev = prev.next;
+			end = end.next;
+		}
+		prev.next = prev.next.next;
+		return head;
+	}
+
+	public static void main(String[] args) {
+		ListNode fourth = new ListNode(5, null);
+		ListNode third = new ListNode(4, fourth);
+		ListNode second = new ListNode(3, third);
+		ListNode first = new ListNode(2, second);
+		ListNode head = new ListNode(1, first);
+
+		ListNode curr = removeNthFromEnd(head, 1);
+		while (curr != null) {
+			System.out.println(curr.val);
+			curr = curr.next;
+		}
+	}
+}
diff --git a/ReverseList.java b/ReverseList.java
new file mode 100644
index 0000000..96e09a2
--- /dev/null
+++ b/ReverseList.java
@@ -0,0 +1,31 @@
+import java.lang.*;
+import java.util.*;
+import node.*;
+
+class ReverseList {
+	public static ListNode reverseList(ListNode head) {
+		ListNode prev = null;
+		ListNode node = head;
+		while (node != null) {
+			ListNode tmp = node.next;
+			node.next = prev;
+			prev = node;
+			node = tmp;
+		}
+		return prev;
+	}
+
+	public static void main(String[] args) {
+		ListNode fourth = new ListNode(5, null);
+		ListNode third = new ListNode(4, fourth);
+		ListNode second = new ListNode(3, third);
+		ListNode first = new ListNode(2, second);
+		ListNode head = new ListNode(1, first);
+
+		ListNode curr = reverseList(head);
+		while (curr != null) {
+			System.out.println(curr.val);
+			curr = curr.next;
+		}
+	}
+}
diff --git a/Stock.java b/Stock.java
new file mode 100644
index 0000000..7a7915b
--- /dev/null
+++ b/Stock.java
@@ -0,0 +1,25 @@
+import java.lang.*;
+import java.util.*;
+
+class Stock {
+	public static int maxProfit(int[] prices) {
+		int s = 0;
+		int e = prices.length - 1;
+		int low = Integer.MAX_VALUE;
+		int high = 0;
+		while (s < e) {
+			if (prices[s] < low)
+				low = prices[s];
+			if (prices[e] > high)
+				high = prices[e];
+			s++;
+			e--;
+		}
+		return high - low > 0 ? high - low : 0;
+	}
+
+	public static void main(String[] args) {
+		int[] prices = {7, 1, 5, 3, 6, 4};
+		System.out.println(maxProfit(prices));
+	}
+}
diff --git a/SumTwoIntegers.java b/SumTwoIntegers.java
new file mode 100644
index 0000000..acb2590
--- /dev/null
+++ b/SumTwoIntegers.java
@@ -0,0 +1,30 @@
+import java.lang.*;
+import java.util.*;
+
+class SumTwoIntegers {
+	public static int getSum(int a, int b) {
+		int bitmask = 0b1;
+		int carry = 0b0;
+		int sum = 0;
+
+		while (bitmask != 0) {
+			int i = a & bitmask;
+			int j = b & bitmask;
+
+			sum |= (i ^ j) ^ carry;
+			carry = (i & j) | ((i | j) & carry);
+
+			bitmask <<= 1;
+			carry <<= 1;
+		}
+		return sum;
+	}
+
+	public static void main(String[] args) {
+		int a = 12;
+		int b = 32;
+		int ans = getSum(a, b);
+		System.out.println(ans);
+		System.out.println(Integer.toBinaryString(ans));
+	}
+}
diff --git a/TwoSum.java b/TwoSum.java
new file mode 100644
index 0000000..b285c60
--- /dev/null
+++ b/TwoSum.java
@@ -0,0 +1,20 @@
+import java.lang.*;
+import java.util.*;
+
+class TwoSum {
+	public static int[] twoSum(int[] nums, int target) {
+		HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
+		for (int i = 0; i < nums.length; i++) {
+			if (map.containsKey(target - nums[i]))
+				return new int[] {map.get(target - nums[i]), i};
+			map.put(nums[i], i);
+		}
+		return new int[] {-1, -1};
+	}
+
+	public static void main(String[] args) {
+		int[] nums = {2, 7, 11, 15};
+		int target = 9;
+		System.out.println(Arrays.toString(twoSum(nums, target)));
+	}
+}
diff --git a/node/GraphNode.class b/node/GraphNode.class
new file mode 100644
index 0000000..ae63fe4
--- /dev/null
+++ b/node/GraphNode.class
diff --git a/node/GraphNode.java b/node/GraphNode.java
new file mode 100644
index 0000000..db15ebb
--- /dev/null
+++ b/node/GraphNode.java
@@ -0,0 +1,21 @@
+package node;
+
+import java.lang.*;
+import java.util.*;
+
+public class GraphNode {
+	public int val;
+	public ArrayList<GraphNode> neighbors;
+	public GraphNode() {
+		val = 0;
+		neighbors = new ArrayList<GraphNode>();
+	}
+	public GraphNode(int val) {
+		this.val = val;
+		neighbors = new ArrayList<GraphNode>();
+	}
+	public GraphNode(int val, ArrayList<GraphNode> neighbors) {
+		this.val = val;
+		this.neighbors = neighbors;
+	}
+}
diff --git a/node/ListNode.class b/node/ListNode.class
new file mode 100644
index 0000000..a0f839b
--- /dev/null
+++ b/node/ListNode.class
diff --git a/node/ListNode.java b/node/ListNode.java
new file mode 100644
index 0000000..6b345ec
--- /dev/null
+++ b/node/ListNode.java
@@ -0,0 +1,9 @@
+package node;
+
+public class ListNode {
+	public int val;
+	public ListNode next;
+	public ListNode() {}
+	public ListNode(int val) { this.val = val;}
+	public ListNode(int val, ListNode next) { this.val = val; this.next = next; }
+}