设计Payment Service
The user post payment request and backend compute the logic and return the result
访问量很大怎么办
Why Paypal
Paypal is used by majority of people nowadays. Whenever I am buying anything on Ebay, paypal makes me feel more secure than paying
with the credit card. I noticed that the sde role serves to scale out a data platform and improve stalibility and efficiency of the
platform. I am very interested in this area and it would be so excited if I could work for a company whose product are used by so
many people!
Coding
O(N) 空间O(LogN)
Iterative:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* in order traversal is increasing. Track the previous TreeNode instead of Previous value
* since the given treenode's value could be the Math.Min
* }
*/
public class Solution {
public boolean isValidBST(TreeNode root) {
TreeNode p = root;
TreeNode pre = null;
Stack<TreeNode> stack = new Stack<TreeNode>();
//Inorder Traversal
while(p != null || !stack.isEmpty()){
while(p != null){
stack.push(p);
p = p.left;
}
p = stack.pop();
if(pre != null && p.val <= pre.val){
return false;
}
pre = p;
p = p.right;
}
return true;
}
}
Recursive Way:
public boolean isValidBST(TreeNode root) {
ArrayList<Integer> pre = new ArrayList<Integer>();
pre.add(null);
return helper(root, pre);
}
private boolean helper(TreeNode root, ArrayList<Integer> pre)
{
if(root == null)
return true;
boolean left = helper(root.left,pre);
if(pre.get(0)!=null && root.val<=pre.get(0))
return false;
pre.set(0,root.val);
return left && helper(root.right,pre);
}
字符里数字的和
//3232sbfs3
public int countNum(String s){
int n = s.length;
int sum = 0;
int val = 0;
char[] arr = s.toCharArray();
for(int i = 0;i < n;i++){
char cur = arr[i];
if(cur >= '0' && cur <= '9'){
val += val * 10 + val - '0';
}
else{
sum += val;
val = 0;
}
}
//add the remain
sum = sum + val;
return sum;
}
2.Directed Graph TP Sort
Java Maven Build System ?
https://www.quora.com/What-are-some-real-world-applications-of-topological-sort
TP Sort Two Ways (1) BFS (2) DFS Check Circle
- Build the Graph and calculate the indegree
- Retrieve the nodes whose indegree == 0 and put into the queue
- Delete the edges of the popped node and add to the queue if a node's indegree is 0
http://www.lintcode.com/en/problem/topological-sorting/#
BFS
/**
* Definition for Directed graph.
* class DirectedGraphNode {
* int label;
* ArrayList<DirectedGraphNode> neighbors;
* DirectedGraphNode(int x) { label = x; neighbors = new ArrayList<DirectedGraphNode>(); }
* };
*/
public class Solution {
/**
* @param graph: A list of Directed graph node
* @return: Any topological order for the given graph.
*/
public ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph) {
// write your code here
ArrayList<DirectedGraphNode> list = new ArrayList<DirectedGraphNode>();
// Key : node
// Value : current in-degree count
HashMap<DirectedGraphNode, Integer> map = new HashMap<>();
for(DirectedGraphNode node : graph){
for(DirectedGraphNode neighbor : node.neighbors){
if(!map.containsKey(neighbor)){
map.put(neighbor, 1);
} else {
map.put(neighbor, map.get(neighbor) + 1);
}
}
}
// Now we know each node's in-degree (out is trivial)
Queue<DirectedGraphNode> queue = new LinkedList<>();
Iterator<DirectedGraphNode> iter = graph.iterator();
while(iter.hasNext()){
DirectedGraphNode node = iter.next();
// get all nodes without indegree
if(!map.containsKey(node)){
queue.offer(node);
list.add(node);
}
}
while(!queue.isEmpty()){
DirectedGraphNode node = queue.poll();
for(DirectedGraphNode next : node.neighbors){
// node "next"'s parent has been processed
map.put(next, map.get(next) - 1);
if(map.get(next) == 0){
list.add(next);
queue.offer(next);
}
}
}
return list;
}
}
DFS
public class Solution {
/**
* @param graph: A list of Directed graph node
* @return: Any topological order for the given graph.
*/
public ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph) {
// write your code here
LinkedList<DirectedGraphNode> res = new LinkedList<DirectedGraphNode>();
HashSet<DirectedGraphNode> visited = new HashSet<DirectedGraphNode>();
for(DirectedGraphNode node : graph){
dfs(node,res,visited);
}
//linkedlist --> ArrayList
return new ArrayList<DirectedGraphNode>(res);
}
public void dfs(DirectedGraphNode root,LinkedList<DirectedGraphNode> res,HashSet<DirectedGraphNode> visited){
if(visited.contains(root))return;
for(DirectedGraphNode next : root.neighbors){
dfs(next,res,visited);
}
//add to the front!
res.addFirst(root);
visited.add(root);
}
}
3. 定向图中是否有长度为K的环
NOT TESTED , BRUTE FORCE DFS
public boolean cycleKExist(HashMap<Integer,List<Integer>> graph,int k){
for(Integer node:graph.keySet()){
HashSet<Integer> visited = new HashSet();
List<Integer> num = new ArrayList<Integer>();
num.add(0);
if(dfs(num,graph,node,visited))return true;
}
return false;
}
public boolean dfs(List<Integer> size,HashMap<Integer,List<Integer>> graph,int node,HashSet<Integer> visited){
if(visited.contains(node) && size.get(0) == k)return true;
for(Integer neibor: graph.get(node)){
visited.add(neibor);
size.set(0,size.get(0) + 1);
dfs(size,graph,neigbor,visited);
visited.remove(neibor);
}
return false;
}
Three State DFS
public boolean cycleKExist(HashMap<Integer,List<Integer>> graph,int k){
HashSet<Integer> visited = new HashSet();
HashSet<Integer> onStack = new HashSet();
for(Integer node:graph.keySet()){
//if the node has not been finally visited
if(!visited.contains(node)){
List<Integer> size = new ArrayList<Integer>();
size.add(0);
if(dfs(size,graph,node,visited,onStack))return true;
}
}
return false;
}
public boolean dfs(List<Integer> size,HashMap<Integer,List<Integer>> graph,int node,HashSet<Integer> visited,HashSet<Integer> onStack,int target){
onStack.add(node);
visited.add(node);
for(Integer k: graph.get(node)){
if(!onStack.contains(k)){
size.set(0,size.get(0) + 1);
return dfs(size,graph,k,visited,onStack);
}
else if(onStack.contains(k)){
if(size.get(0) == target)return true;
}
}
onStack.remove(node);
return false;
}
4. 文本压缩
Many Algorithms Exist , one of them is Huffman Encoding
http://algs4.cs.princeton.edu/55compression/Huffman.java.html
系统设计
http://www.infoq.com/cn/articles/message-based-distributed-architecture
https://lxia.gitbooks.io/cmore/content/xitongsheji/xi_tong_she_ji_zi_yuan.html
Job Description knowledge point
Unstructured Data Files
Data which can be stored in traditional database systems in the form of rows and columns, for example the online purchase transactions can be referred to as Structured Data. Data which can be stored only partially in traditional database systems, for example, data in XML records can be referred to as semi structured data.
Flat Files
has no structure for indexing and there are usually no structural relationships between the records. A flat file can be a
plain text file or a binary file
XML Events
handle event in xml
Web services (rest, soap)
rest relies on the url http internal method such as get/put/ to deal with the messages while soap use xml to transfer messages
SOAP can use almost any transport to send the request, using everything from the afore mentioned to SMTP
Python