推荐:数据科学课程和书籍清单以及培训讲座


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 6436|回复: 26
收起左侧

facebook 实习 面经

[复制链接] |试试Instant~ |关注本帖
stanleyyyyy 发表于 2016-1-27 11:35:00 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 实习@Facebook - 内推 - 技术电面 |Failfresh grad应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

x
一个月前的fb一面

第一题:plus one原题

第二题:一个数组内要是存在至少三个升序的数(array[x] < array[y] < array[z], x < y < z)就返回true,否则返回false。lc上有类似题。

大米~~~~~

评分

3

查看全部评分

本帖被以下淘专辑推荐:

woshixuyoudan 发表于 2016-2-19 04:48:32 | 显示全部楼层
第二题不是leetcode原题么,O(n), O(1)
话说怎么贴代码...


public boolean increasingTriplet(int[] nums) {
        if (nums == null || nums.length < 3) {return false;}
        int min = Integer.MAX_VALUE, max = Integer.MAX_VALUE;
        for (int n : nums) {
            if (n > max) { return true;}
            if (n > min) {. 鍥磋鎴戜滑@1point 3 acres
                max = n;
            } else { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                min = n;
            }
        }
        return false;
    }
回复 支持 3 反对 0

使用道具 举报

xiaozhuxiaozhu 发表于 2016-1-27 11:43:30 | 显示全部楼层
lz是内推么?还是自己网投的,大概多久能收到预约电话。
回复 支持 反对

使用道具 举报

 楼主| stanleyyyyy 发表于 2016-1-27 12:02:42 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-1-27 11:43
lz是内推么?还是自己网投的,大概多久能收到预约电话。

内推的 大概一两周
回复 支持 反对

使用道具 举报

singku 发表于 2016-1-27 13:38:44 | 显示全部楼层
实现了一下第二题的代码 应该可以跑
  1. int a, b, c, least;
  2. bool three_inscreasing(std::vector<int> nums)
  3. {
  4.     int n = nums.size(); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  5.     if (n <= 2) return false;

  6.     int i = 1;
  7.     while (i < n && nums[i] < nums[i-1]) {
  8.         i++;
  9.     }

  10.     if (i == n-1) {
  11.         return false;. Waral 鍗氬鏈夋洿澶氭枃绔,
  12.     }

  13.     a = i-1;
  14.     b = i;
  15.     least = i-1;

  16.     for (i = i+1; i < n; i++) {
  17.         if (nums[i] < nums[least]) {.鐣欏璁哄潧-涓浜-涓夊垎鍦
  18.             least = i;
  19.         }
  20.         if (nums[i] > nums[b]) {
  21.             c = i;
  22.             return true;
  23.         }
  24.         if (nums[i] < nums[b] && nums[i] > nums[a]) {. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  25.             b = i;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  26.         } else if (nums[i] > nums[least] && nums[i] < nums[b]) {. 鍥磋鎴戜滑@1point 3 acres
  27.             a = least;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  28.             b = i;. more info on 1point3acres.com
  29.         }
  30.     }
  31.     return false;
  32. }
复制代码
回复 支持 反对

使用道具 举报

aangel 发表于 2016-1-27 16:22:28 | 显示全部楼层
singku 发表于 2016-1-27 13:38
实现了一下第二题的代码 应该可以跑

while (i < n && nums < nums[i-1]) {
        i++;
    }

应改为 nums<=nums[i-1]吧

补充内容 (2016-1-27 16:23):.1point3acres缃
nums<=nums[i-1]
回复 支持 反对

使用道具 举报

singku 发表于 2016-1-27 21:59:01 | 显示全部楼层
aangel 发表于 2016-1-27 16:22. more info on 1point3acres.com
while (i < n && nums < nums) {
        i++;
    }
. 鍥磋鎴戜滑@1point 3 acres
你说得没错
回复 支持 反对

使用道具 举报

goodluck888 发表于 2016-1-28 02:13:14 | 显示全部楼层
请问LZ, 是不连续的x y z吗?要求O(n)解法?
回复 支持 反对

使用道具 举报

 楼主| stanleyyyyy 发表于 2016-1-28 07:03:35 | 显示全部楼层
可以不连续的 应该用dp吧
回复 支持 反对

使用道具 举报

aangel 发表于 2016-1-29 02:13:35 | 显示全部楼层
stanleyyyyy 发表于 2016-1-28 07:03
可以不连续的 应该用dp吧
. visit 1point3acres.com for more.
从左到右扫一遍,记下最小值,从右到左扫一遍,记下最大值
最后再从头到尾扫一遍,以每个点作为分割线, 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
也是O(n)时间,但是需要O(n)空间,. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
DP怎么做?
回复 支持 反对

使用道具 举报

songty11 发表于 2016-1-30 01:34:56 | 显示全部楼层
第二题这样是o(n)
  1. // bool lengthOfLIS(vector<int>& nums) {
  2. //     vector<int> res;
  3. //     for(int i=0; i<nums.size(); i++) {
  4. //         auto it = std::lower_bound(res.begin(), res.end(), nums[i]);
  5. //         if(it==res.end()) res.push_back(nums[i]);
  6. //         else *it = nums[i];
  7. //         if(res.size()>=3)
  8. //         return true;
  9. //     }
  10. //     return false;
  11. // }
复制代码
回复 支持 反对

使用道具 举报

小海 发表于 2016-2-4 08:49:38 | 显示全部楼层
songty11 发表于 2016-1-29 11:34
第二题这样是o(n)

你这个是nlogn 因为Lower_bound 是 “On average, logarithmic in the distance between first and last: Performs approximately log2(N)+1 element comparisons (where N is this distance).”. visit 1point3acres.com for more.
http://www.cplusplus.com/reference/algorithm/lower_bound/
回复 支持 反对

使用道具 举报

songty11 发表于 2016-2-4 11:47:54 | 显示全部楼层
小海 发表于 2016-2-4 08:49. 鍥磋鎴戜滑@1point 3 acres
你这个是nlogn 因为Lower_bound 是 “On average, logarithmic in the distance between first and last: ...

多谢指正!那就不用lower_bound,可以自己写一个比较的~因为数组里的元素不会多于3个...
回复 支持 反对

使用道具 举报

a598165394 发表于 2016-2-10 23:11:44 | 显示全部楼层
singku 发表于 2016-1-27 13:38. more info on 1point3acres.com
实现了一下第二题的代码 应该可以跑

你好,打扰一下,能不能问一下为什么会需要这个条件判断语句啊. 1point3acres.com/bbs
else if (nums > nums[least] && nums < nums) {
回复 支持 反对

使用道具 举报

singku 发表于 2016-2-11 01:08:26 | 显示全部楼层
a598165394 发表于 2016-2-10 23:11
你好,打扰一下,能不能问一下为什么会需要这个条件判断语句啊.鐣欏璁哄潧-涓浜-涓夊垎鍦
else if (nums &gt; nums[least] &amp;&amp; nums &lt;  ...

因为least记录了最小值的位置,这个位置可能在ab这个升序对的后面,如果当前值大于最小值,而且小于b 需要更新升序对。ab始终是一个最低的升序对。
回复 支持 反对

使用道具 举报

a598165394 发表于 2016-2-11 02:08:46 | 显示全部楼层
singku 发表于 2016-2-11 01:08.1point3acres缃
因为least记录了最小值的位置,这个位置可能在ab这个升序对的后面,如果当前值大于最小值,而且小于b 需 ...

. 1point 3acres 璁哄潧我觉得或许用一个b和least两个变量应该就够了吧?
  1.         public boolean secfind(int[] nums){
  2.             int b,least;
  3.             int i=0;
  4.             while(i<nums.length-1&& nums[i]>nums[i+1]){
  5.                 i++;
  6.             }-google 1point3acres
  7.             if(i>=nums.length-2) return false;
  8.             b = i+1;. 鍥磋鎴戜滑@1point 3 acres
  9.             least = i;-google 1point3acres
  10.             for(i=i+2;i<nums.length;i++){. From 1point 3acres bbs
  11.                 if(nums[i]>nums[b]) return true;
  12.                 if(nums[i]<nums[least]) least = i;
  13.                 if(nums[i]> nums[least] && nums[i]<nums[b]) b=i;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

  14.             }
  15.             return false;
  16.         }
复制代码
回复 支持 反对

使用道具 举报

singku 发表于 2016-2-12 08:02:45 | 显示全部楼层
a598165394 发表于 2016-2-11 02:08
我觉得或许用一个b和least两个变量应该就够了吧?
. more info on 1point3acres.com
你这样写是对的 不过第一个while里还是要 nums >= nums[i+1].1point3acres缃

我的做法额外用了一个a存升序的位置 你没存
回复 支持 反对

使用道具 举报

a598165394 发表于 2016-2-12 08:08:21 | 显示全部楼层
singku 发表于 2016-2-12 08:02
你这样写是对的 不过第一个while里还是要 nums >= nums
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
我的做法额外用了一个a存升序的位置 你没存

好的嗯,谢谢了啊!祝找工作顺利!
回复 支持 反对

使用道具 举报

木易wen 发表于 2016-2-14 07:10:21 | 显示全部楼层
第二题用一个空间为3的栈就行吧?
将第一个元素进栈,loop一遍数组,如果当前元素比栈顶小的话就退栈知道栈顶元素比当前元素小或栈空并将该元素进栈。当栈满表示已经有三个升序元素,返回true就行,复杂度O(n), O(1)
回复 支持 反对

使用道具 举报

tmaconfire 发表于 2016-2-18 05:47:48 | 显示全部楼层
木易wen 发表于 2016-2-14 07:10. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
第二题用一个空间为3的栈就行吧?
将第一个元素进栈,loop一遍数组,如果当前元素比栈顶小的话就退栈知道 ...

这个是正解
回复 支持 反对

使用道具 举报

endofunctor 发表于 2016-2-18 18:29:17 | 显示全部楼层
小海 发表于 2016-2-4 08:49
你这个是nlogn 因为Lower_bound 是 “On average, logarithmic in the distance between first and last: ...

个人认为还是O(n) time complexity, 因为对于这里的log2(N) + 1, N永远小于3,所以可以认为是constant time
回复 支持 反对

使用道具 举报

本版积分规则

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-8-23 08:49

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表