public class Fib {
/*
* recursion O(2^N)
*/
public static int fib(int n){
if(n < 0){
throw new IllegalArgumentException();
}
if(n == 0) return 0;
if(n == 1) return 1;
return fib(n - 1) + fib(n - 2);
}
/*
* DP O(n) time and space complexity
*/
public static int fib2(int n){
if(n < 0){
throw new IllegalArgumentException();
}
if(n == 0) return 0;
if(n == 1) return 1;
int[] states = new int[n + 1];
states[0] = 0;
states[1] = 1;
for(int i = 2; i <=n; i++){
states[i] = states[i - 1] + states[i - 2];
}
return states[n];
}
/*
* Optimized DP O(n) time and O(1) space complexity
*/
public static int fib3(int n){
if(n < 0){
throw new IllegalArgumentException();
}
if(n == 0) return 0;
if(n == 1) return 1;
int num1 = 0, num2 = 1, res = 0;
for(int i = 2; i <= n; i++){
res = num1 + num2;
num1 = num2;
num2 = res;
}
return res;
}
/*
* [1 1] [Fn+1 Fn]
* [1 0] [Fn Fn -1]
* O(logn)
*/
public static int fib4(int n){
if(n < 0){
throw new IllegalArgumentException();
}
if(n == 0) return 0;
if(n == 1) return 1;
int[][] matrix = {{1, 1}, {1, 0}};
pow(matrix, n - 1);
return matrix[0][0];
}
private static void pow(int[][] matrix, int n){
if(n == 0 || n == 1){
return;
}
pow(matrix, n / 2);
multiply(matrix, matrix);
if(n % 2 != 0){
int[][] temp = {{1, 1}, {1, 0}};
multiply(matrix, temp);
}
}
private static void multiply(int[][] matrix, int[][] base){
int x = matrix[0][0] * base[0][0] + matrix[0][1] * base[1][0];
int y = matrix[0][0] * base[0][1] + matrix[0][1] * base[1][1];
int z = matrix[1][0] * base[0][0] + matrix[1][1] * base[1][0];
int k = matrix[1][0] * base[0][1] + matrix[1][1] * base[1][1];
matrix[0][0] = x;
matrix[0][1] = y;
matrix[1][0] = z;
matrix[1][1] = k;
}
public static void main(String[] args){
for(int i = 0; i <= 20; i++){
System.out.println(fib(i) + " " + fib2(i) + " " + fib3(i) + " " + fib4(i));
}
}
}
Palantir
Reservior Sample
import java.util.*;
public class ReserviorSample {
/*
* warm up
* knuth shuffle
*/
public static void shuffle(int[] num){
if(num == null || num.length == 0){
return;
}
Random rnd = new Random();
int N = num.length;
for(int i = 0; i < N; i++){
int idx = i + rnd.nextInt(N - i);
swap(num, i, idx);
}
}
/*
* Say you have a stream of items of large and unknown length that we can only iterate over once.
* Create an algorithm that randomly chooses an item from this stream such that each item is
* equally likely to be selected
*/
public static int sample(Iterator<Integer> it){
if(it == null || !it.hasNext()){
throw new IllegalArgumentException(" ");
}
Random rnd = new Random();
int n = 0, sample = 1;
while(it.hasNext()){
n++;
int num = it.next();
if(n == 1){
sample = num;
}else{
int idx = rnd.nextInt(n);
if(idx == 0){
sample = num;
}
}
}
return sample;
}
/*
* Reservoir sampling is a family of randomized algorithms for randomly choosing k
* samples from a list of n items, where n is either a very large or unknown number
*/
public static int[] reservoirSample(Iterator<Integer> it, int k){
if(it == null || !it.hasNext() || k <= 0){
return null;
}
Random rnd = new Random();
int[] res = new int[k];
int i = 0;
while(it.hasNext()){
int num = it.next();
if(i < k){
res[i] = num;
}else{
int idx = rnd.nextInt(i + 1);
if(idx < k){
res[idx] = num;
}
}
i++;
}
if(i < k) throw new RuntimeException();
return res;
}
private static void swap(int[] nums, int i, int j){
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
public static void main(String[] args){
int[] nums = {1, 2, 3, 4, 5};
shuffle(nums);
for(int i : nums){
//System.out.println(i);
}
ArrayList<Integer> res = new ArrayList<Integer>();
for(int i = 1; i <= 10; i++){
res.add(i);
}
int[] dist = new int[11];
for(int i = 0; i < 1000; i++){
int num = sample(res.iterator());
dist[num]++;
}
for(int i = 1; i < dist.length; i++){
System.out.println("num " + i + " produce " + dist[i] + " times");
}
int[] sams = reservoirSample(res.iterator(), 5);
for(int i : sams) System.out.print(i + " ");
}
}
Find Missing number
1, 1 – N missing 一个数
如果sorted， 用二分法，找到第一个a[i] != i + 1的地方
如果不sorted， 用通项公式求等差序列和 – sum of array
或者XOR (a1^a2^a3) ^ (a1^a2) = a^3
2, 如果missing两个数
解二元一次方程 x + y = num1
x^2 + y^2 = num2
3, 如果missing K个数
array sorted, 直接linear scan
not sorted http://stackoverflow.com/questions/3492302/easy-interview-question-got-harder-given-numbers-1-100-find-the-missing-numbe
/*
* 给一个sorted array, 这个array的size是N-K
原本这个array应该是有从1-N，N个数 但是miss了K个
请找出这miss的K个数
*/
public class FindMissingNumber {
public static int[] findMissing(int[] nums, int N){
if(nums == null || nums.length < 0 || N < 0){
return null;
}
int[] res = new int[N - nums.length];
int idx = 0;
//front
if(nums[0] != 1){
int counter = 1;
while(counter < nums[0]){
res[idx++] = counter++;
}
}
//middle
for(int i = 0; i < nums.length - 1; i++){
if(nums[i] != nums[i + 1] - 1){
int counter = nums[i] + 1;
while(counter < nums[i + 1]){
res[idx++] = counter++;
}
}
}
//end
if(nums[nums.length - 1] < N){
int counter = nums[nums.length - 1];
while(counter < N){
res[idx++] = counter++;
}
}
return res;
}
public static void main(String[] args){
int[] nums = {3, 4, 6, 7, 9, 10};
int[] res = findMissing(nums, 10);
for(int i : res) System.out.print(i + " ");
}
}
Robot Variant
/*
* 机器人走格子，要求生成所有路线，而不只是单纯的总方法数。改下返回的结果和递归时的传参
*/
import java.util.*;
public class Robot {
private class Pos{
int x;
int y;
public Pos(int x, int y){
this.x = x;
this.y = y;
}
public String toString(){
return "( " + x + " " + y + " )";
}
}
public List<List<Pos>> path(int[][] matrix){
List<List<Pos>> res = new ArrayList<List<Pos>>();
if(matrix == null || matrix.length == 0){
return res;
}
ArrayList<Pos> path = new ArrayList<Pos>();
dfs(res, path, matrix, 0, 0);
return res;
}
private void dfs(List<List<Pos>> res, ArrayList<Pos> path, int[][] matrix, int x, int y){
int m = matrix.length, n = matrix[0].length;
if(x == m - 1 && y == n - 1){
path.add(new Pos(x, y));
res.add(new ArrayList<Pos>(path));
path.remove(path.size() - 1);
return;
}
if(x < 0 || x > m || y < 0 || y > n) return;
path.add(new Pos(x, y));
dfs(res, path, matrix, x + 1, y);
dfs(res, path, matrix, x, y + 1);
path.remove(path.size() - 1);
}
public static void main(String[] args){
int[][] nums = {{1, 1, 1}};
System.out.println(new Robot().path(nums));
}
}
Longest Arithmetic Progression
//reference http://www.geeksforgeeks.org/length-of-the-longest-arithmatic-progression-in-a-sorted-array/
import java.util.*;
public class LongestArithmeticProgression {
/*
* warm up
* This function returns true if there exist three elements in AP
* Assumption: array is sorted
* 等差序列性质 a[n - 1] + a[n + 1] = 2a[n]
* 我们变量一边数组a[i]设为中间值，a[i - 1] 为第一个， a[i + 1]为第三个
* 就变成2sum了，如果和小，增加右边的pointer，和大，减少左边的pointer
*/
public static boolean ap3(int[] nums){
for(int i = 1; i < nums.length - 1; i++){
int left = i - 1, right = i + 1;
while(left >= 0 && right < nums.length){
int sum = nums[left] + nums[right];
if(sum == 2 * nums[i]) return true;
else if(sum < 2 * nums[i]) right++;
else left++;
}
}
return false;
}
public static int llap(int[] nums){
if(nums == null){
return 0;
}
if(nums.length <= 2){
return nums.length;
}
int n = nums.length, max = 2;
//状态为以a[i]. a[j]为前两个元素的等差序列的长度，j > i
int[][] states = new int[n][n];
//初始化
for(int i = 0; i < n; i++){
states[i][n - 1] = 2;
}
for(int j = n - 2; j >= 1; j--){
int i = j - 1, k = j + 1;
while(i >= 0 && k < n){
int sum = nums[i] + nums[k];
if(sum < 2 * nums[j]) k++;
else if(sum > 2 * nums[j]){
states[i][j] = 2;
i--;
}else{
//System.out.println(nums[i] + " " + nums[j] + " " + nums[k]);
states[i][j] = states[j][k] + 1;
max = Math.max(max, states[i][j]);
i--;
k++;
}
}
while(i >= 0){
states[i][j] = 2;
i--;
}
}
return max;
}
/*
* brute-force O(N^3)
*/
public static int llapBF(int[] nums){
if(nums == null) return 0;
if(nums.length <= 2) return nums.length;
int max = 2;
Arrays.sort(nums);
/*
* a[i], a[j]为等差序列的前两项 N^2 pair
* 每一次去找下一个 N
* TOTAL O(n^3)
*/
int n = nums.length;
for(int i = 0; i < n; i++){
for(int j = i + 1; j < n; j++){
int counter = 2;
int diff = nums[j] - nums[i];
int target = nums[j] + diff;
for(int k = j + 1; k < n; k++){
if(target == nums[k]){
counter++;
target = nums[k] + diff;
}
}
max = Math.max(max, counter);
}
}
return max;
}
public static void main(String[] args){
int[] nums = {1, 7, 10, 13, 14, 19};
System.out.println(llapBF(nums));
int[] nums1 = {2, 4, 6, 8, 10};
System.out.println(llapBF(nums1));
int[] nums2 = {1, 7, 10, 15, 27, 29};
System.out.println(llapBF(nums2));
}
}
Shortest unique prefix to represent word in an array
看到prefix肯定想到的是trie咯，在trie node里面多加一个field count，表示
这个字符出现多少次
1，insert word into the trie
2, search the word, 找到第一个count为1的node，返回
因为说明这个node下面没有分支了，他就应该是唯一的
/*
* 求一个string list的每个string对应的unique prefix，返回也是一个list
*/
public class TriePrefix {
public static final int R = 256;
private Node root;
private class Node{
private int count;
private boolean isEnd;
private Node next[] = new Node[R];
public Node(){
count = 0;
isEnd = false;
}
public Node(int count, boolean isEnd){
this.count = count;
this.isEnd = isEnd;
}
}
public void insert(String str){
if(root == null) root = new Node();
Node curr = root;
for(int i = 0; i < str.length(); i++){
char c = str.charAt(i);
if(curr.next[c] == null){
curr.next[c] = new Node(1, false);
}else{
curr.next[c].count++;
}
curr = curr.next[c];
}
curr.isEnd = true;
}
public String shortestPrefix(String str){
Node curr = root;
int len = 0;
for(int i = 0; i < str.length(); i++){
char c = str.charAt(i);
curr = curr.next[c];
len++;
if(curr.count == 1) break;
}
return str.substring(0, len);
}
public static void main(String[] args){
TriePrefix trie = new TriePrefix();
String[] words = {"by", "sea", "sells", "she", "shells", "shore", "the"};
String[] words1 = {"zebra", "dog", "duck", "dove"};
for(String word : words1){
trie.insert(word);
}
String[] res = new String[words1.length];
for(int i = 0; i < words1.length; i++){
res[i] = trie.shortestPrefix(words1[i]);
System.out.println(res[i]);
}
}
}
Port
需要实现一个routetable，ip的前缀 -> port number，有插入和查找两个操作。其中ip和ip前缀都是二进制，由vector表示。查找返回routetable中和ip最长匹配的前缀所对应的portnumber，如果没有前缀匹配，返回-1。
给定API. 1point 3acres 璁哄潧
void insert (vector prefix, int port);
void find (vector ip);
其实就是R = 2 的TRIE, 因为只有0，1两种
public class Port {
private class Node{
int port;
Node left;
Node right;
public Node(int port){
this.port = port;
}
}
private Node root = new Node(-1);
public void insert(int[] prefix, int port){
Node node = root;
for(int i = 0; i < prefix.length; i++){
if(prefix[i] == 0){
if(node.left == null){
node.left = new Node(-1);
}
node = node.left;
}else{
if(node.right == null){
node.right = new Node(-1);
}
node = node.right;
}
}
node.port = port;
}
public int find(int[] ip){
if(ip == null) return -1;
Node node = root;
for(int i = 0; i < ip.length; i++){
if(ip[i] == 0){
if(node.left == null) return -1;
else node = node.left;
}else{
if(node.right == null) return -1;
else node = node.right;
}
}
return node.port;
}
public static void main(String[] args){
Port p = new Port();
int[] ip1 = {1, 0, 1, 0, 1, 0};
p.insert(ip1, 10);
System.out.println(p.find(ip1));
int[] ip2 = {1, 0, 1, 0, 1};
System.out.println(p.find(ip2));
}
}
sum of 3 smallest number
一个数组中最小的三个的和, 用三个变量记录最小的三个就好了，处理数组长度小于3的情况
import java.util.*;
public class Solution {
/**
* @param lists: a list of ListNode
* @return: The head of one sorted list.
*/
public static int smallest3(int[] nums){
if(nums == null || nums.length < 3){
throw new IllegalArgumentException();
}
int min = Integer.MAX_VALUE, second = min, third = min;
for(int num : nums){
if(num < min){
third = second;
second = min;
min = num;
}else if(num < second){
third = second;
second = num;
}else if(num < third){
third = num;
}
}
return min + second + third;
}
public static void main(String[] args){
int[] nums = {-1, -2, -3, -4, -5, -6};
System.out.println(smallest3(nums));
}
}
Most Frequent Char
给一个字符串，找打至少出现N次的char,按大小顺序输出
/**
* Definition for ListNode.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int val) {
* this.val = val;
* this.next = null;
* }
* }
*/
import java.util.*;
public class Solution {
/**
* @param lists: a list of ListNode
* @return: The head of one sorted list.
*/
public static String mostFreq(String str, int N){
if(str == null || str.length() == 0){
return str;
}
TreeMap treemap = new TreeMap();
for(int i = 0; i < str.length(); i++){
char c = str.charAt(i);
if(c 'z') continue;
if(!treemap.containsKey(c)){
treemap.put(c, 1);
}else{
treemap.put(c, treemap.get(c) + 1);
}
}
StringBuilder sb = new StringBuilder();
for(char c : treemap.keySet()){
if(treemap.get(c) >= N){
sb.append(c);
}
}
return sb.toString();
}
public static void main(String[] args){
String s = "today is that saturday";
System.out.println(mostFreq(s, 3));
}
}
Duplicates 123
import java.util.*;
public class Solution{
/*
* Write a function that is given an array of integers. It should return true if
* any value appears at least twice in the array, and it should return false if
* every element is distinct
*/
public static boolean containsDuplicate(int[] arr) {
if(arr == null || arr.length == 0){
return true;
}
HashSet<Integer> hashset = new HashSet<Integer>();
for(int num : arr){
if(hashset.contains(num)){
return true;
}
hashset.add(num);
}
return false;
}
/**
* Write a function that is given an array of integers and an integer k. It
* should return true if and only if there are two distinct indices i and j into
* the array such that arr[i] = arr[j] and the difference between i and j is at
* most k.
*/
public static boolean containsNearbyDuplicate(int[] arr, int k) {
if(arr == null || arr.length == 0 || k < 1){
return false;
}
Queue<Integer> queue = new LinkedList<Integer>();
HashSet<Integer> hashset = new HashSet<Integer>();
for(int i = 0; i < arr.length; i++){
int num = arr[i];
if(hashset.contains(num)){
return true;
}
hashset.add(num);
queue.offer(num);
if(hashset.size() > k){
hashset.remove(queue.poll());
}
}
return false;
}
/**
* Write a function that is given an array of integers. It should return true if
* and only if there are two distinct indices i and j into the array such that
* the difference between arr[i] and arr[j] is at most l and the difference
* between i and j is at most k.
*/
public static boolean containsNearbyAlmostDuplicate(int[] arr, int k, int l) {
if(arr == null || arr.length == 0 || k < 1){
return false;
}
Queue<Integer> queue = new LinkedList<Integer>();
TreeSet<Integer> bst = new TreeSet<Integer>();
for(int i = 0; i < arr.length; i++){
int num = arr[i];
if(bst.floor(num) != null){
int pred = bst.floor(num);
if(Math.abs(pred - num) <= l){
return true;
}
}
if(bst.ceiling(num) != null){
int succ = bst.ceiling(num);
if(Math.abs(succ - num) <= l){
return true;
}
}
queue.add(num);
bst.add(num);
if(bst.size() > k){
bst.remove(queue.poll());
}
}
return false;
}
public static void main(String[] args){
int[] num = {1, 10, 20, 30, -7, 100};
System.out.println(containsNearbyAlmostDuplicate(num, 4, 8)); //k, l
}
}
shawnlincoding 