throttling request

就是user想要request车的arrival time。如果1s内多余5条request，就自动忽略，不然就执行

如果1s内多余5条request 就自动忽略--->这个是throttling request, 应该是类似Guava 的RateLimiter

---

作者: freemail165    时间: 2 小时前
public void getRequest() {
    private final static Queue<Date> q=new LinkedList<Date>();
    Date cur=new Date();. 鐣欏鐢宠璁哄潧-涓€浜╀笁鍒嗗湴
    q.offer(cur);
   if(q.size()>5) {
       Date head=q.poll();. more info on 1point3acres.com
       jf(cur-head<1) return;. From 1point 3acres bbs
   }
   // Response..
}
   
} 

是用circular buffer ? 多谢多谢 

嗯嗯~~~~~~~~~~~

sortList-use merge sort

 

Sort List -- LeetCode

分类： LeetCode2014-03-14 08:16 9133人阅读 评论(21) 收藏 举报

leetcode排序面试递归链表

原题链接: http://oj.leetcode.com/problems/sort-list/ 
这道题跟Insertion Sort List类似，要求我们用O(nlogn)算法对链表进行排序，但是并没有要求用哪一种排序算法，我们可以使用归并排序，快速排序，堆排序等满足要求的方法来实现。对于这道题比较容易想到的是归并排序，因为我们已经做过Merge Two Sorted Lists，这是归并排序的一个subroutine。剩下我们需要做的就是每次找到中点，然后对于左右进行递归，最后用Merge Two Sorted Lists把他们合并起来。代码如下：

[java] view plaincopy

1. public ListNode sortList(ListNode head) {  
2.     return mergeSort(head);  
3. }  
4. private ListNode mergeSort(ListNode head)  
5. {  
6.     if(head == null || head.next == null)  
7.         return head;  
8.     ListNode walker = head;  
9.     ListNode runner = head;  
10.     while(runner.next!=null && runner.next.next!=null)  
11.     {  
12.         walker = walker.next;  
13.         runner = runner.next.next;  
14.     }  
15.     ListNode head2 = walker.next;  
16.     walker.next = null;  
17.     ListNode head1 = head;  
18.     head1 = mergeSort(head1);  
19.     head2 = mergeSort(head2);  
20.     return merge(head1, head2);  
21. }  
22. private ListNode merge(ListNode head1, ListNode head2)  
23. {  
24.     ListNode helper = new ListNode(0);  
25.     helper.next = head1;  
26.     ListNode pre = helper;  
27.     while(head1!=null && head2!=null)  
28.     {  
29.         if(head1.val<head2.val)  
30.         {  
31.             head1 = head1.next;  
32.         }  
33.         else  
34.         {  
35.             ListNode next = head2.next;  
36.             head2.next = pre.next;  
37.             pre.next = head2;  
38.             head2 = next;  
39.         }  
40.         pre = pre.next;  
41.     }  
42.     if(head2!=null)  
43.     {  
44.         pre.next = head2;  
45.     }  
46.     return helper.next;  
47. }  

不过用归并排序有个问题就是这里如果把栈空间算上的话还是需要O(logn)的空间的。对于其他排序算法，用兴趣的同学可以实现一下哈。
排序是面试中比较基础的一个主题，所以对于各种常见的排序算法大家还是要熟悉，不了解的朋友可以参见排序算法 - Wiki。特别是算法的原理，很多题目虽然没有直接考察排序的实现，但是用到了其中的思想，比如非常经典的topK问题，就用到了快速排序的原理，关于这个问题在Median of Two Sorted Arrays中有提到，有兴趣的朋友可以看看。

Longest Substring Without Repeating Characters -- LeetCode

Longest Substring Without Repeating Characters -- LeetCode

维护一个窗口，[walker ,runner]
abcbdef
迭代1： walker =0=a，runner = 0 =a
runner 一直向右走，直到发现重复的字符。
当runner遇到重复的字符，walker走，
比如当runner到b，发现重复了。 walker需要右移到c，
并且set中的a被删除，
abcbdef

迭代2： walker =c， runner = b， set=(b,c)

edit distance

http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/MIT6_006F11_lec21_orig.pdf

nlp video

Multiply Strings

One Easy solution with C++

Word Ladder

Word Ladder -- LeetCode

public int ladderLength(String start, String end, HashSet dict) {
    if(start==null || end==null || start.length()==0 || end.length()==0 || start.length()!=end.length())
        return 0;
    LinkedList queue = new LinkedList();
    HashSet visited = new HashSet();
    int level= 1;
    int lastNum = 1; // 当前level还需要check的节点
    int curNum = 0; // next level 需要check的节点
    queue.offer(start);
    visited.add(start);

    while(!queue.isEmpty())
    {
        String cur = queue.poll(); //从queue拿出一个进行visit
        lastNum--;
        for(int i=0;i<cur.length();i++)
        {
            char[] charCur = cur.toCharArray();
            for(char c='a';c<='z';c++)
            {
                charCur[i] = c;
                String temp = new String(charCur);
                if(temp.equals(end))
                    return level+1;
                if(dict.contains(temp) && !visited.contains(temp))
                {
                    curNum++;//新的未visit的节点，
                    queue.offer(temp); // 加到下次check的行列
                    visited.add(temp); //标记为visited
                }
            }
        }
       //当前level已经check完成，进行下一个level
        if(lastNum==0)
        {
            lastNum = curNum;
            curNum = 0;
            level++;
        }
    }
    return 0;
}

树的求和

树的题目在LeetCode中还是有比较大的比例的，不过除了基本的递归和非递归的遍历之外，其他大部分题目都是用递归方式来求解特定量，

判断是否存在从根到叶子的路径和跟给定sum相同的

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.
For example:
Given the below binary tree and sum = 22,
              5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1


return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

public boolean hasPathSum(TreeNode root, int sum) {
    if(root == null)
        return false;
    if(root.left == null && root.right==null && root.val==sum)
        return true;
    return hasPathSum(root.left, sum-root.val) || hasPathSum(root.right, sum-root.val);
}

算法的时间复杂度是一次遍历O(n)，空间复杂度是栈的大小O(logn)。

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.
For example:
Given the below binary tree and sum = 22,
              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1


return
[
   [5,4,11,2],
   [5,8,4,5]
]

Sum Root to Leaf Numbers这道题多了两个变化，一个是每一个结点相当于位上的值，而不是本身有权重，不过其实没有太大变化，每一层乘以10加上自己的值就可以了。另一个变化就是要把所有路径累加起来，这个其实就是递归条件要进行调整，Path Sum中是判断左右子树有一个找到满足要求的路径即可，而这里则是把左右子树的结果相加返回作为当前节点的累加结果即可。

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path 1->2->3 which represents the number 123.

Find the total sum of all root-to-leaf numbers.

For example,
    1
   / \
  2   3




The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.

Return the sum = 12 + 13 = 25.

Binary Tree Maximum Path Sum

Given a binary tree, find the maximum path sum.

The path may start and end at any node in the tree.

For example:
Given the below binary tree,
       1
      / \
     2   3



Return 6.