一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 3103|回复: 26
收起左侧

facebook 实习 面经

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

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

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
一个月前的fb一面

第一题:plus one原题. from: 1point3acres.com/bbs

第二题:一个数组内要是存在至少三个升序的数(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) {
                max = n;
            } else {
                min = n;
            }.鐣欏璁哄潧-涓浜-涓夊垎鍦
        }
        return false;. more info on 1point3acres.com
    }
回复 支持 3 反对 0

使用道具 举报

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

使用道具 举报

 楼主| stanleyyyyy 发表于 2016-1-27 12:02:42 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-1-27 11:43. more info on 1point3acres.com
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.     }.鏈枃鍘熷垱鑷1point3acres璁哄潧

  10.     if (i == n-1) {
  11.         return false;
  12.     }
  13. . from: 1point3acres.com/bbs
  14.     a = i-1;
  15.     b = i;
  16.     least = i-1;. visit 1point3acres.com for more.

  17.     for (i = i+1; i < n; i++) {.鐣欏璁哄潧-涓浜-涓夊垎鍦
  18.         if (nums[i] < nums[least]) {-google 1point3acres
  19.             least = i;
  20.         }
  21.         if (nums[i] > nums[b]) {
  22.             c = i;
  23.             return true;
  24.         }
  25.         if (nums[i] < nums[b] && nums[i] > nums[a]) {
  26.             b = i;
  27.         } else if (nums[i] > nums[least] && nums[i] < nums[b]) {
  28.             a = least;
  29.             b = i;. visit 1point3acres.com for more.
  30.         }
  31.     }.1point3acres缃
  32.     return false;
  33. }
复制代码
回复 支持 反对

使用道具 举报

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):. From 1point 3acres bbs
nums<=nums[i-1]
回复 支持 反对

使用道具 举报

singku 发表于 2016-1-27 21:59:01 | 显示全部楼层
aangel 发表于 2016-1-27 16:22
while (i < n && nums < nums) {
        i++;
    }

你说得没错
回复 支持 反对

使用道具 举报

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吧

从左到右扫一遍,记下最小值,从右到左扫一遍,记下最大值
最后再从头到尾扫一遍,以每个点作为分割线,
也是O(n)时间,但是需要O(n)空间,
DP怎么做?
回复 支持 反对

使用道具 举报

songty11 发表于 2016-1-30 01:34:56 | 显示全部楼层
第二题这样是o(n)
  1. // bool lengthOfLIS(vector<int>& nums) {-google 1point3acres
  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]);.1point3acres缃
  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).”
http://www.cplusplus.com/reference/algorithm/lower_bound/
回复 支持 反对

使用道具 举报

songty11 发表于 2016-2-4 11:47:54 | 显示全部楼层
小海 发表于 2016-2-4 08:49
你这个是nlogn 因为Lower_bound 是 “On average, logarithmic in the distance between first and last: ...
. 1point3acres.com/bbs
多谢指正!那就不用lower_bound,可以自己写一个比较的~因为数组里的元素不会多于3个...
回复 支持 反对

使用道具 举报

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

你好,打扰一下,能不能问一下为什么会需要这个条件判断语句啊
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. Waral 鍗氬鏈夋洿澶氭枃绔,
因为least记录了最小值的位置,这个位置可能在ab这个升序对的后面,如果当前值大于最小值,而且小于b 需 ...

我觉得或许用一个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++;. from: 1point3acres.com/bbs
  6.             }
  7.             if(i>=nums.length-2) return false;
  8.             b = i+1;
  9.             least = i;
  10.             for(i=i+2;i<nums.length;i++){
  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. . 1point3acres.com/bbs
  15.             }
  16.             return false;
  17.         }
复制代码
回复 支持 反对

使用道具 举报

singku 发表于 2016-2-12 08:02:45 | 显示全部楼层
a598165394 发表于 2016-2-11 02:08
我觉得或许用一个b和least两个变量应该就够了吧?

你这样写是对的 不过第一个while里还是要 nums >= nums[i+1]
. more info on 1point3acres.com
我的做法额外用了一个a存升序的位置 你没存
回复 支持 反对

使用道具 举报

a598165394 发表于 2016-2-12 08:08:21 | 显示全部楼层
singku 发表于 2016-2-12 08:02
你这样写是对的 不过第一个while里还是要 nums >= nums. 1point3acres.com/bbs

我的做法额外用了一个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一遍数组,如果当前元素比栈顶小的话就退栈知道 ...
.鏈枃鍘熷垱鑷1point3acres璁哄潧
这个是正解
回复 支持 反对

使用道具 举报

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
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

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

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-3 22:12

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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