eBay Demo Link

http://www.ebay.com/itm/161579456719

Two Sum III - Data structure design @LeetCode

Design and implement a TwoSum class. It should support the following operations: add and find.

add - Add the number to an internal data structure.
find - Find if there exists any pair of numbers which sum is equal to the value.

For example,

add(1); add(3); add(5);
find(4) -> true
find(7) -> false

	import java.util.HashMap;
	import java.util.Map;
	// case: add(0) -> find(0) -> should be false
	public class TwoSumIII {
	Map<Integer, Integer> dict = new HashMap<Integer, Integer>();
	public void add(int number) {
	if (dict.containsKey(number)) {
	dict.put(number, dict.get(number) + 1);
	} else {
	dict.put(number, 1);
	}
	}
	public boolean find(int value) {
	for (Integer key : dict.keySet()) {
	if (value - key == key) {
	if (dict.get(key) >= 2) {
	return true;
	}
	} else if (dict.containsKey(value - key)) {
	return true;
	}
	}
	return false;
	}
	public static void main(String[] args) {
	TwoSumIII util = new TwoSumIII();
	util.add(1);
	util.add(3);
	util.add(5);
	System.out.println(util.find(4));
	System.out.println(util.find(7));
	}
	}

view raw TwoSumIII.java hosted with ❤ by GitHub

Two Sum II - Input array is sorted @LeetCode

Given an array of integers that is already sorted in ascending order, 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 TwoSumII {
	public int[] twoSum(int[] numbers, int target) {
	int[] result = {-1, -1};
	if (numbers == null || numbers.length == 0) {
	return result;
	}
	int start = 0;
	int end = numbers.length - 1;
	while (start < end) {
	int sum = numbers[start] + numbers[end];
	if (sum == target) {
	result[0] = start + 1;
	result[1] = end + 1;
	break;
	} else if (sum < target) {
	start++;
	} else {
	end--;
	}
	}
	return result;
	}
	}

view raw TwoSumII.java hosted with ❤ by GitHub

Factorial Trailing Zeroes @LeetCode

Given an integer n, return the number of trailing zeroes in n!.

Note: Your solution should be in logarithmic time complexity.

Credits:
Special thanks to @ts for adding this problem and creating all test cases.

	/*
	* Trailing zeros of n!
	*
	* take care Integer OverFlow
	* Reference:
	* http://www.purplemath.com/modules/factzero.htm
	* http://www.cnblogs.com/EdwardLiu/p/4207498.html
	*/
	public class TrailingZeroes {
	public static int trailingZeroes(int n) {
	if (n < 0) {
	n = -1* n;
	}
	int result = 0;
	for (int i = 5; n / i >= 1; n = n / 5) {
	result += n / i;
	}
	return result;
	}
	public static void main(String[] args) {
	System.out.println(trailingZeroes(1808548329));
	}
	}

view raw TrailingZeroes.java hosted with ❤ by GitHub

Read N Characters Given Read4 II - Call multiple times @LeetCode

The API: int read4(char *buf) reads 4 characters at a time from a file.

The return value is the actual number of characters read. For example, it returns 3 if there is only 3 characters left in the file.

By using the read4 API, implement the function int read(char *buf, int n) that reads n characters from the file.

Note:
The read function may be called multiple times.

	/*
	* The read function may be called multiple times.
	* The previous one we can't use it for multiple times since read4 actually read more and break continuity.
	* This one will sovle that problem. read the buffer used last time.(through offset)
	*/
	public class Read4KII {
	// reused variable.
	private char[] buffer = new char[4];
	private int bufsize = 0;
	private int offset = 0;
	public int read(char[] buf, int n) {
	int total = 0;
	boolean eof = true;
	while (eof && total < n) {
	if (bufsize == 0) {
	bufsize = read4(buffer);
	if (bufsize < 4) {
	eof = false;
	}
	}
	int bytes = Math.min(n - total, bufsize);
	System.arraycopy(buffer, offset, buf, total, bytes);
	offset = (offset + bytes) % 4;
	bufsize -= bytes;
	total += bytes;
	}
	return total;
	}
	// API funciton
	public int read4(char[] buf) {
	return 0;
	}

view raw Read4KII.java hosted with ❤ by GitHub

Read N Characters Given Read4 @LeetCode

The API: int read4(char *buf) reads 4 characters at a time from a file.

The return value is the actual number of characters read. For example, it returns 3 if there is only 3 characters left in the file.

By using the read4 API, implement the function int read(char *buf, int n) that reads n characters from the file.

Note:
The read function will only be called once for each test case.

	/* The read4 API is defined in the parent class Reader4.
	int read4(char[] buf); */
	// Implement readline using read 4k
	public class Read4KI {
	//public class Read4KI extends Reader4 {
	/**
	* @param buf Destination buffer
	* @param n Maximum number of characters to read
	* @return The number of characters read
	*/
	public int read(char[] buf, int n) {
	char[] buffer = new char[4];
	boolean eof = true;
	int total = 0;
	while (eof && total < n) {
	int temp = read4(buffer);
	if (temp < 4) {
	eof = false;
	}
	int bytes = Math.min(n - total, temp);
	System.arraycopy(buffer, 0, buf, total, bytes);
	total += bytes;
	}
	return total;
	}
	// API funciton
	public int read4(char[] buf) {
	return 0;
	}
	}

view raw Read4KI.java hosted with ❤ by GitHub

Min Stack @LeetCode

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

• push(x) -- Push element x onto stack.
• pop() -- Removes the element on top of the stack.
• top() -- Get the top element.
• getMin() -- Retrieve the minimum element in the stack.

	import java.util.HashMap;
	import java.util.Map;
	import java.util.Stack;
	public class MinStack {
	// retrieving the minimum element in constant time.
	Stack<Integer> stack = new Stack<Integer>();
	Stack<Integer> minStack = new Stack<Integer>();
	Map<Integer, Integer> cache = new HashMap<Integer, Integer>();
	public void push(int x) {
	if (x == getMin()) {
	cache.put(x, cache.get(x) + 1);
	}
	if (x < getMin()) {
	minStack.push(x);
	cache.put(x, 1);
	}
	stack.push(x);
	}
	public void pop() {
	int value = stack.pop();
	if (value == getMin()) {
	if (cache.get(value) == 1) {
	minStack.pop();
	}
	cache.put(value, cache.get(value) - 1);
	}
	}
	public int top() {
	return stack.peek();
	}
	public int getMin() {
	if (minStack.isEmpty()) {
	return Integer.MAX_VALUE;
	} else {
	return minStack.peek();
	}
	}

view raw MinStack.java hosted with ❤ by GitHub