Skip to content

Commit bd0856e

Browse files
author
mingchuw
committed
algorithm code
1 parent 08692fa commit bd0856e

67 files changed

Lines changed: 1928 additions & 15 deletions

File tree

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

‎src/main/java/baseKnowledge/HeapImplemention.java‎

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
package baseKnowledge;
2+
3+
import java.util.Collections;
4+
import java.util.PriorityQueue;
5+
6+
/**
7+
* java 中堆的实现可以用 PriorityQueue，
8+
* 但是默认PriorityQueue 是最小堆，即每次poll 得到当前堆最小值
9+
* 如果要讲PriorityQueue 改造成最大堆，可以传入特定的Comparator
10+
11+
*/
12+
public class HeapImplemention {
13+
public static void main(String[] args) {
14+
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
15+
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
16+
17+
minHeap.add(1);
18+
minHeap.add(2);
19+
minHeap.add(3);
20+
21+
System.out.println(minHeap.poll());
22+
maxHeap.add(1);
23+
maxHeap.add(2);
24+
maxHeap.add(3);
25+
26+
System.out.println(maxHeap.poll());
27+
}
28+
}

‎src/main/java/company/amazon/InterviewTask.java‎

Lines changed: 80 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,80 @@
1+
package company.amazon;
2+
3+
public class InterviewTask {
4+
class Node {
5+
int x;
6+
int y;
7+
public Node(int x, int y) {
8+
this.x = x;
9+
this.y = y;
10+
}
11+
}
12+
13+
public boolean findString(char[][] data, String target) {
14+
if (target == null || data == null) return false;
15+
Character begin = target.charAt(0);
16+
17+
for (int i = 0; i < data.length; i++) {
18+
for (int j = 0; j < data[0].length; j++) {
19+
if (data[i][j] == begin) {
20+
//search the node
21+
if (searchNode(data, i, j, target)) {
22+
return true;
23+
}
24+
}
25+
}
26+
}
27+
28+
return false;
29+
30+
}
31+
32+
private boolean searchNode(char[][] data, int curX, int curY, String target) {
33+
if (target.length() <= 1) return true; // as the target just like "a", "b"
34+
Character sec = target.charAt(1);
35+
// get the direction
36+
boolean findDir = false;
37+
for (int dirX = -1; dirX <=1 ;dirX++) {
38+
if (curX + dirX < 0 || curX + dirX >= data.length) continue;
39+
for (int dirY = -1; dirY <=1 ;dirY++) {
40+
if (curY + dirY < 0 || curY + dirY >= data[0].length) continue;
41+
if (dirX == 0 && dirY == 0) continue;
42+
if (data[curX + dirX][curY + dirY] == sec) {
43+
int tempX = curX + dirX;
44+
int tempY = curY + dirY;
45+
findDir = true;
46+
for (int k = 2; k < target.length(); k++) {
47+
// this is the edge condition I missed!!!!
48+
if (tempX + dirX < 0 || tempX + dirX >= data.length
49+
|| tempY + dirY < 0 || tempY + dirY >= data[0].length) {
50+
findDir = false;
51+
break;
52+
}
53+
if (data[tempX + dirX][tempY + dirY] != target.charAt(k)) {
54+
// search not OK
55+
findDir = false;
56+
break;
57+
}
58+
tempX += dirX;
59+
tempY += dirY;
60+
}
61+
if(findDir) {
62+
return true;
63+
}
64+
}
65+
}
66+
67+
}
68+
69+
return false;
70+
}
71+
72+
public static void main(String[] args) {
73+
char[][] data = {{'a', 'b', 'c'}, {'d', 'e', 'f'},{'g','h','i'}};
74+
InterviewTask sample = new InterviewTask();
75+
System.out.println(sample.findString(data, "abcd"));
76+
System.out.println(sample.findString(data, "efg"));
77+
System.out.println(sample.findString(data, "a"));
78+
System.out.println(sample.findString(data, "aa"));
79+
}
80+
}

‎src/main/java/company/amazon/amazon126/FindTheLeastCommonAncestor.java‎

Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,22 @@
1+
package company.amazon.amazon126;
2+
3+
import leetcode.SumOfLeftLeaves;
4+
5+
/**
6+
* LCA
7+
*/
8+
public class FindTheLeastCommonAncestor {
9+
public SumOfLeftLeaves.TreeNode findLCA(SumOfLeftLeaves.TreeNode root,
10+
SumOfLeftLeaves.TreeNode nodeA,
11+
SumOfLeftLeaves.TreeNode nodeB) {
12+
if (root == null) return null;
13+
if (root == nodeA || root == nodeB) return root;
14+
SumOfLeftLeaves.TreeNode leftLCA = findLCA(root.left, nodeA, nodeB);
15+
SumOfLeftLeaves.TreeNode rightLCA = findLCA(root.right, nodeA, nodeB);
16+
17+
if (leftLCA != null && rightLCA != null) {
18+
return root;
19+
}
20+
return leftLCA != null ? leftLCA : rightLCA;
21+
}
22+
}

‎src/main/java/company/amazon/amazon126/Findthedistancebetween2nodes.java‎

Lines changed: 62 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,62 @@
1+
package company.amazon.amazon126;
2+
3+
/**
4+
* Given a Binary Search Tree, Find the distance between 2 nodes
5+
*
6+
* 1 Least common ancestor.
7+
*/
8+
9+
import leetcode.SumOfLeftLeaves;
10+
11+
/**
12+
*
13+
*/
14+
public class Findthedistancebetween2nodes {
15+
public static int Distance(SumOfLeftLeaves.TreeNode root,
16+
SumOfLeftLeaves.TreeNode node1, SumOfLeftLeaves.TreeNode node2)
17+
{
18+
SumOfLeftLeaves.TreeNode node = findLeastCommonAncestor(root, node1, node2);
19+
int distLCA = findLevel(root, node);
20+
int dist1 = findLevel(root, node1);
21+
int dist2 = findLevel(root, node2);
22+
23+
return dist1 + dist2 - 2 * distLCA;
24+
}
25+
26+
private static SumOfLeftLeaves.TreeNode findLeastCommonAncestor(SumOfLeftLeaves.TreeNode root,
27+
SumOfLeftLeaves.TreeNode node1,
28+
SumOfLeftLeaves.TreeNode node2)
29+
{
30+
if (root == null) return null;
31+
//找到两个节点中的一个就返回
32+
if (root.val == node1.val || root.val== node2.val)
33+
return root;
34+
//分别在左右子树查找两个节点
35+
36+
SumOfLeftLeaves.TreeNode left_lca = findLeastCommonAncestor(root.left, node1, node2);
37+
SumOfLeftLeaves.TreeNode right_lca = findLeastCommonAncestor(root.right, node1, node2);
38+
39+
if (left_lca != null && right_lca != null)
40+
//此时说明，两个节点肯定是分别在左右子树中，当前节点比为LCA
41+
return root;
42+
return left_lca != null ? left_lca : right_lca;
43+
}
44+
45+
private static int findLevel(SumOfLeftLeaves.TreeNode root, SumOfLeftLeaves.TreeNode node)
46+
{
47+
if (root == null)
48+
return -1;
49+
if(root.val == node.val)
50+
return 0;
51+
52+
int level = findLevel(root.left, node);
53+
54+
if (level == -1)
55+
level = findLevel(root.right, node);
56+
57+
if(level != -1)
58+
return level + 1;
59+
60+
return -1;
61+
}
62+
}

‎src/main/java/company/amazon/amazon126/JosephProblem.java‎

Lines changed: 20 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,20 @@
1+
package company.amazon.amazon126;
2+
3+
/**
4+
* http://blog.csdn.net/wlqingwei/article/details/44037693
5+
*
6+
* the conclusion:
7+
*
8+
* 固定m, 视n为变量。定义F(n)为: n人时，胜利者的编号。
9+
则n 人时，胜利者编号为
10+
0, 1, 2, 3, ..., m-1(*), m, m+1, ..., n-1;
11+
去掉一人后，还剩余n-1人。 且这n - 1 人与n人时的index对应关系如下：
12+
m, m+1, ...., n-1, 0, 1, 2, 3, ....., m -2
13+
0, 1, ..., ..., ......... , n-2. (总共n-1个人)
14+
则F(n) = F(n-1) + m;
15+
16+
最后再考虑 m与n的关系， m可能会大于n. 所以需要取模
17+
F(n) = ( F(n-1) + m ) %n.
18+
*/
19+
public class JosephProblem {
20+
}

‎src/main/java/company/amazon/amazon126/LFU_Design.java‎

Lines changed: 49 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,49 @@
1+
package company.amazon.amazon126;
2+
3+
public class LFU_Design {
4+
/**
5+
*
6+
* http://stackoverflow.com/questions/17759560/what-is-the-difference-between-lru-and-lfu
7+
*
8+
*
9+
* Let's consider a constant stream of cache requests with a cache capacity of 3, see below:
10+
11+
A, B, C, A, A, A, A, A, A, A, A, A, A, A, B, C, D
12+
If we just consider a Least Recently Used (LRU) cache with a HashMap + doubly linked list
13+
implementation with O(1) eviction time and O(1) load time, we would have the following elements
14+
cached while processing the caching requests as mentioned above.
15+
16+
[A]
17+
[A, B]
18+
[A, B, C]
19+
[B, C, A] <- a stream of As keeps A at the head of the list.
20+
[C, A, B]
21+
[A, B, C]
22+
[B, C, D] <- here, we evict A, we can do better!
23+
24+
25+
*/
26+
27+
28+
/**
29+
* for LRU, use HaspMap + double linked list
30+
* LRU : http://gogole.iteye.com/blog/692103
31+
*
32+
* LFU:
33+
* LFU is a cache eviction algorithm called least frequently used cache.
34+
35+
It requires three data structures. One is a hash table which is used to cache the key/values so that given
36+
a key we can retrieve the cache entry at O(1). Second one is a double linked list for each frequency of access.
37+
The max frequency is capped at the cache size to avoid creating more and more frequency list entries.
38+
If we have a cache of max size 4 then we will end up with 4 different frequencies.
39+
Each frequency will have a double linked list to keep track of the cache entries belonging to that particular
40+
frequency. The third data structure would be to somehow link these frequencies lists.
41+
It can be either an array or another linked list so that on accessing a cache entry it can be easily
42+
promoted to the next frequency list in time O(1).
43+
44+
http://ju.outofmemory.cn/entry/50447
45+
46+
47+
*/
48+
49+
}

‎src/main/java/company/amazon/amazon126/Serializeanddeserializebinarysearchtree.java‎

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,5 @@
1+
package company.amazon.amazon126;
2+
3+
//PreOrder traversal
4+
public class Serializeanddeserializebinarysearchtree {
5+
}

‎src/main/java/company/amazon/amazon126/shortestpathinbinarysearchtree.java‎

Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,39 @@
1+
package company.amazon.amazon126;
2+
3+
/**
4+
* A node in a binary search tree always has a higher key at its right child compared to its left
5+
* child. There are many path running from the roots to the leaves. When we add up the key values along a path,
6+
* it will sum up to some number NUM1.
7+
* We need to find such a path where NUM1 is equal to K. Point worth noting is that,
8+
* we might have many paths summing up to K. We need to return the shortest of them all.
9+
* If there are multiple paths of the same length satisfying our condition then return any.
10+
*/
11+
12+
/**
13+
* boolean findShortestPathToK(Node node,Stack stack,int sum,int currentSum){
14+
if(node == null){
15+
return false;
16+
}
17+
stack.push(node);
18+
currentSum +=node.data;
19+
if(currentSum > sum){
20+
stack.pop();
21+
return false;
22+
}
23+
if(currentSum == sum && node.right==null && node.left==null){
24+
return true;
25+
}
26+
if(findShortestPathToK(node.right, stack, sum, currentSum) || findShortestPathToK(node.left, stack, sum, currentSum)){
27+
return true;
28+
}
29+
stack.pop();
30+
return false;
31+
}
32+
33+
*/
34+
/**
35+
solution:
36+
http://techieme.in/shortest-path-in-binary-search-tree/
37+
*/
38+
public class shortestpathinbinarysearchtree {
39+
}

‎src/main/java/designSolution/LFU_Design.java‎

Lines changed: 49 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,49 @@
1+
package designSolution;
2+
3+
public class LFU_Design {
4+
/**
5+
*
6+
* http://stackoverflow.com/questions/17759560/what-is-the-difference-between-lru-and-lfu
7+
*
8+
*
9+
* Let's consider a constant stream of cache requests with a cache capacity of 3, see below:
10+
11+
A, B, C, A, A, A, A, A, A, A, A, A, A, A, B, C, D
12+
If we just consider a Least Recently Used (LRU) cache with a HashMap + doubly linked list
13+
implementation with O(1) eviction time and O(1) load time, we would have the following elements
14+
cached while processing the caching requests as mentioned above.
15+
16+
[A]
17+
[A, B]
18+
[A, B, C]
19+
[B, C, A] <- a stream of As keeps A at the head of the list.
20+
[C, A, B]
21+
[A, B, C]
22+
[B, C, D] <- here, we evict A, we can do better!
23+
24+
25+
*/
26+
27+
28+
/**
29+
* for LRU, use HaspMap + double linked list
30+
* LRU : http://gogole.iteye.com/blog/692103
31+
*
32+
* LFU:
33+
* LFU is a cache eviction algorithm called least frequently used cache.
34+
35+
It requires three data structures. One is a hash table which is used to cache the key/values so that given
36+
a key we can retrieve the cache entry at O(1). Second one is a double linked list for each frequency of access.
37+
The max frequency is capped at the cache size to avoid creating more and more frequency list entries.
38+
If we have a cache of max size 4 then we will end up with 4 different frequencies.
39+
Each frequency will have a double linked list to keep track of the cache entries belonging to that particular
40+
frequency. The third data structure would be to somehow link these frequencies lists.
41+
It can be either an array or another linked list so that on accessing a cache entry it can be easily
42+
promoted to the next frequency list in time O(1).
43+
44+
http://ju.outofmemory.cn/entry/50447
45+
46+
47+
*/
48+
49+
}

0 commit comments

Comments
 (0)