Serena211
diff --git a/‎bin/Class02_Recursion/DictImpl.class‎
1.39 KB b/‎bin/Class02_Recursion/DictImpl.class‎
1.39 KB
diff --git a/‎bin/Class02_Recursion/SearchInUnknownSizedSortedArray.class‎
199 Bytes b/‎bin/Class02_Recursion/SearchInUnknownSizedSortedArray.class‎
199 Bytes
diff --git a/‎bin/Class03_List/QueueByTwoStacks.class‎
1.5 KB b/‎bin/Class03_List/QueueByTwoStacks.class‎
1.5 KB
diff --git a/‎bin/Class03_List/ReverseLinkedList.class‎
420 Bytes b/‎bin/Class03_List/ReverseLinkedList.class‎
420 Bytes
diff --git a/‎bin/Class03_List/StackWithMin.class‎
1.35 KB b/‎bin/Class03_List/StackWithMin.class‎
1.35 KB
diff --git a/‎bin/Class03_List/TopKFrequentWords$1.class‎
-99 Bytes b/‎bin/Class03_List/TopKFrequentWords$1.class‎
-99 Bytes
diff --git a/‎bin/Class03_List/TopKFrequentWords.class‎
166 Bytes b/‎bin/Class03_List/TopKFrequentWords.class‎
166 Bytes
diff --git a/‎src/Class02_Recursion/SearchInUnknownSizedSortedArray.java‎
Lines changed: 47 additions & 7 deletions b/‎src/Class02_Recursion/SearchInUnknownSizedSortedArray.java‎
Lines changed: 47 additions & 7 deletions
diff --git a/‎src/Class03_List/QueueByTwoStacks.java‎
Lines changed: 59 additions & 0 deletions b/‎src/Class03_List/QueueByTwoStacks.java‎
Lines changed: 59 additions & 0 deletions
diff --git a/‎src/Class03_List/ReverseLinkedList.java‎
Lines changed: 10 additions & 0 deletions b/‎src/Class03_List/ReverseLinkedList.java‎
Lines changed: 10 additions & 0 deletions
@@ -1,4 +1,7 @@
 package Class02_Recursion;
+
+import java.util.Arrays;
+
 /*
  * Given a integer dictionary A of unknown size, where the numbers 
  * in the dictionary are sorted in ascending order, determine if a 
@@ -14,10 +17,6 @@
  * A = {1, 2, 5, 9, 12, ......}, T = 7, return -1
  * */
 
-
-interface Dictionary {
-	public Integer get(int index);
-}
 // Solution:
 // Step1: keep jumping out until array[2^k] >= target || array[2^k] == null
 // Step2: left = 2^(k - 1); right = 2^k; do binary search.
@@ -33,12 +32,12 @@ public int search(Dictionary dict, int target) {
 		while(dict.get(index) != null && dict.get(index) < target) {
 			index = index * 2;
 		}
-		return BST(dict, target, (int)Math.sqrt(index),index);
+		return BST(dict, target, index/2,index);
 		}
 	private int BST(Dictionary dict, int target, int l, int r) {
 
 		while (l <= r) {
-			int mid = l + (l + r) / 2;
+			int mid = l + (r - l) / 2;
 			if (dict.get(mid) == null) {
 				r = mid - 1;
 			} else if (dict.get(mid) == target) {
@@ -52,7 +51,48 @@ private int BST(Dictionary dict, int target, int l, int r) {
 		return -1;
 	}
 	public static void main(String[] args) {
-
+		SearchInUnknownSizedSortedArray sol = new SearchInUnknownSizedSortedArray();
+		Dictionary dict = new DictImpl(null);
+		System.out.println(sol.search(dict, 4));
 	}
 
 }
+interface Dictionary {
+	public Integer get(int index);
+}
+class DictImpl implements Dictionary {
+	private int[] array;
+	public DictImpl(int[] input) {
+		// TODO Auto-generated constructor stub
+		array = input;
+	}
+	@Override
+	public Integer get(int index) {
+		// TODO Auto-generated method stub
+		if(array == null || index >= array.length) {
+			return null;
+		}
+		return array[index];
+	}
+	@Override
+	public String toString() {
+		if(array == null) {
+			return String.valueOf(null);
+		}
+		if(array.length < 10) {
+			return Arrays.toString(array);
+		}
+		// truncate array
+		StringBuilder sb = new StringBuilder("[");
+		for (int i = 0; i < 5; i++) {
+			sb.append(array[i]).append(", ");
+		}
+		sb.append("..........");
+		for (int j = array.length - 5; j < array.length; j++) {
+			sb.append(array[j]).append(", ");
+		}
+		sb.replace(sb.length()-2, sb.length()-1, "]");
+		return sb.toString();
+	}
+	
+}
@@ -0,0 +1,59 @@
+package Class03_List;
+
+import java.util.LinkedList;
+
+/*
+ * Java: Implement a queue by using two stacks. The queue should provide size(), 
+ * isEmpty(), offer(), poll() and peek() operations. When the queue is empty, 
+ * poll() and peek() should return null.
+ * 
+ * Assumptions
+ * The elements in the queue are all Integers.
+ * size() should return the number of elements buffered in the queue.
+ * isEmpty() should return true if there is no element buffered in the queue, false otherwise.
+ * */
+
+public class QueueByTwoStacks {
+	private LinkedList<Integer> in;
+	private LinkedList<Integer> out;
+
+	public QueueByTwoStacks() {
+		in = new LinkedList<Integer>();
+		out = new LinkedList<Integer>();
+	}
+
+	public Integer poll() {
+		move();
+		return out.isEmpty() ? null : out.pollFirst();
+	}
+
+	public void offer(int element) {
+		in.offerFirst(element);
+	}
+
+	public Integer peek() {
+		move();
+		return out.isEmpty() ? null : out.peekFirst();
+	}
+
+	public int size() {
+		return in.size() + out.size();
+	}
+
+	public boolean isEmpty() {
+		return in.isEmpty() && out.isEmpty();
+	}
+	private void move() {
+		if(out.isEmpty()) {
+			while(!in.isEmpty()) {
+				out.offerFirst(in.pollFirst());
+			}
+		}
+	}
+
+	public static void main(String[] args) {
+		// TODO Auto-generated method stub
+
+	}
+
+}
@@ -0,0 +1,10 @@
+package Class03_List;
+
+public class ReverseLinkedList {
+
+	public static void main(String[] args) {
+		// TODO Auto-generated method stub
+
+	}
+
+}