facebook 实习面经

新鲜热乎的面经印度小哥
1. magic number like:
f(n) = f(n-1) + 2*f(n-3)


follow up
f(n, k) = f(n - 1) + 2 * f(n - k)

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

轮team match 重在交流，ML的组几乎都会问和组内项目相关的design问题，楼主有交流障碍，感觉不是很好，大家好好准备，轻松聊天就好。

第一题用dp还是不难，可以用rolling array达到O(k) 空间，第二题开一个size为k的max priorityQueue , 遍历所有点，先装pq，满了后，如果新的距离小于pq中最大距离，就pop掉装新的

第二题

1. public class Solution {
   
2.   int dist(Point p1, Point p2) {
   
3.     int dx = p1.x - p2.x;
   
4.     int dy = p1.y - p2.y;
   
5.     return dx * dx + dy * dy;
   
6.   }
   
7. 
   
8.   int qs(Point[] arr, Point target, int start, int end) {
   
9.     Point pivot = arr[end]; // end out
   
10.     int targetdist = dist(pivot, target);
    
11.     while (start < end) {
    
12.       while (start < end && dist(arr[start], target) < targetdist) {
    
13.         start++;
    
14.       }
    
15.       arr[end] = arr[start]; // into end
    
16.       while (start < end && dist(arr[end], target) > targetdist) {
    
17.         end--;
    
18.       }
    
19.       arr[start] = arr[end]; // into start, end empty
    
20.     }
    
21.     arr[end] = pivot; // into end
    
22.     return end;
    
23.   }
    
24. 
    
25.   public Point[] kn(Point[] arr, Point target, int k) {
    
26.     int mid = -1;
    
27.     int low = 0;
    
28.     int high = arr.length - 1;
    
29.     do {
    
30.       mid = qs(arr, target, low, high);
    
31.       if (mid < k) {
    
32.         low = mid + 1;
    
33.       } else if (mid > k) {
    
34.         high = mid - 1;
    
35.       }
    
36.     } while (mid != k);
    
37.     return Arrays.copyOfRange(arr, 0, k);
    
38.   }
    
39. 
    
40.   public static void main(String[] args) {
    
41.     Solution s = new Solution();
    
42.     for (Point p : s.kn(new Point[] {new Point(0, 0), new Point(1, 0), new Point(0, 1),
    
43.         new Point(0, 2), new Point(2, 0), new Point(1, 2), new Point(2, 1)}, new Point(3, 0), 5))
    
44.       System.out.println(p);
    
45.   }
    
46. }
    

复制代码

写了一下第一题的 follow up，欢迎指正。
    public static void countK(int n, int k) {
        int[] dp = new int[k];
        int j;
        for (int i = 0; i <= n; i++) {
            int tmp = dp[0];
            j = 0;
            for (; j < dp.length - 1; j++) {
                dp[j] = dp[j + 1];
            }
            if (i <= 0) dp[j] = 1;
            else if (i < k) dp[j] = 2 + dp[j - 1];
            else dp[j] = tmp * 2  + dp[j - 1];
        }
        System.out.print(dp[k - 1]);
    }

楼主会有好运的!!
能不能问一下 第一题那个f(n,k)是什么意思 最后要求的是什么?

还有第二题n特别大的时候 感觉不管是heap还是quickselect 都需要遍历整个N 有什么好的思路吗~

今天大米加完了=   =   明天补上

哎，估计挂了。FB效率和快，一般过了当天就说了。。。
1. f(n, k) = f(n - 1) + 2 * f(n - k)
if(n <=0) f(n) = 1
2. quick select做就行, 但是我时间不够，没有写完代码。。。。。。。


补充内容 (2016-2-20 10:29):
返回f(n, k )的值，比如 f(100, 10)

byq 发表于 2016-2-20 10:28
哎，估计挂了。FB效率和快，一般过了当天就说了。。。
1. f(n, k) = f(n - 1) + 2 * f(n - k)
if(n

谢谢楼主~! 祝好运~~~

一亩三分地严打"顶""好贴""收藏了"之类的垃圾回复帖！被警告三次，系统会自动封杀ID！

想支持楼主，请点击帖子下方的"好苗""分享""收藏"键，酌情给楼主加大米（系统不扣你自己的分）。
积分不够看不了帖子，请参考论坛导航里的"帮助"，"新手提纲"里有攒积分指南

LZ 第一题是这个意思吗？

1. public int f(int n) {
   
2.    if (n <= 0) return 1;
   
3.    return f(n-1) + 2*f(n-3);
   
4. }
   
5. 
   
6. Follow up:
   
7. 
   
8. public int fun(int n, int k) {
   
9.    return f(n - 1) + 2 * f(n-k);
   
10. }
    
11. 
    
12. private int f(int n) {
    
13.    if (n <= 0) return 1;
    
14.    return f(n-1) + 2*f(n-3);
    
15. }

复制代码

jasonsfk 发表于 2016-2-21 05:26
一亩三分地严打"顶""好贴""收藏了"之类的垃圾回复帖！被警告三次，系统会自动封杀ID！

想支持楼主，请点 ...

论坛好神奇。。。

jasonsfk 发表于 2016-2-21 05:31
LZ 第一题是这个意思吗？

line 14 is 2 * f(n - k)

补充内容 (2016-2-22 23:50):
我改错了，你的follow up 写的不太对, 1. 斐波那契数列不是和前两个相关么，2.magic number是和前一个和前三个相关，3followup是与前一个和前k个相关,空间复杂度分别O(1), O(1),O(k), 时间复杂度O(n)

byq 发表于 2016-2-20 10:28
哎，估计挂了。FB效率和快，一般过了当天就说了。。。
1. f(n, k) = f(n - 1) + 2 * f(n - k)
if(n

2. quick select is O(n), k quick select is O(kn). quick sort is nlogn.
when n is a million and k is a 100, O(kn) = 100n and nlogn is 20n. quick sort is better.
Can make the change to quick select by select the Kth number first and recursively select the rest numbers in the left partitioned array but the code needs to be modified.

iwofr 发表于 2016-2-23 00:19
2. quick select is O(n), k quick select is O(kn). quick sort is nlogn.
when n is a million and k  ...

quick select的话 只用调用一次 选出来第k个就行了吧  
当你选出来第k个的时候 比k小已经都在它前面了