传说中的谷歌招聘委员会成员之一,从幕后走出来,教你学系统设计!


一亩三分地论坛

 找回密码
 获取更多干活,快来注册
Babeltime游戏工作室招工程师、美术和策划
Tubi TV招安卓、前端和机器学习工程师
把贵司招聘信息放这里
查看: 3309|回复: 48
收起左侧

脸家加面,似乎他家最近新题很多?

[复制链接] |试试Instant~ |关注本帖
cynthiazp 发表于 2017-8-4 07:05:53 | 显示全部楼层 |阅读模式

2017(7-9月) 码农类 硕士 全职@Facebook - 内推 - 技术电面 |Other在职跳槽

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

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

x
上次国人大哥给了个新题,想了一会给了解答,feedback是problem solving不够好。 这次加面还是国人面试官,似乎又一个新题。

简单自我介绍了一下直接上题:

1. 2个数组的交集,先写允许重复再写不允许重复的情况,要的是two pointer的做法。 然后就是各种LC上面讨论过的follow up。

2. 似乎是新题, 给一个排序好的数组,数一数有多少个子集(subset)使得子集里面的最大元素加上最小元素小于K。
A: [2, 3, 5, 7]  K: 8
=> # of subsets S: Max(S) + Min(S) < K
=> [2] , [2, 3], [2, 5], [2, 3, 5], [3] => #: 5

.鐣欏璁哄潧-涓浜-涓夊垎鍦
尽人事听天命了,唉~~. Waral 鍗氬鏈夋洿澶氭枃绔,

评分

2

查看全部评分

本帖被以下淘专辑推荐:

twosumii 发表于 2017-8-4 07:27:31 | 显示全部楼层
并不是新题,你刷的不够 ><。   其实吧,跟第一题有那么一点联系? 你排好序,然后two pointer, 当找到 a + a[j]  < k,  && i < j 的时候,包含i的子集有 2^(j-i) 个,他们都满足条件。 然后i++,继续看,否则j--, O(n)就够了

补充内容 (2017-8-4 07:28):
while (i < j)
   if (a + a[j] < k)   count += Math.pow(2, j-i); i++. visit 1point3acres.com for more.
   else j--
. visit 1point3acres.com for more.

补充内容 (2017-8-4 07:29):
是 a [ i ],   一亩三分地会吧 [ i ] 当成斜体,弄没掉了  a =  a/[i/]
回复 支持 3 反对 0

使用道具 举报

pomme2016 发表于 2017-8-5 13:27:48 | 显示全部楼层
我自己想一开始用的DP,然后发现真的可以双指针呢。
感觉下面写的代码是对的,跑了几个test case
-google 1point3acres
  1. public int subarraySum(int[] nums, int K) {
  2.         if (nums == null || nums.length == 0 || nums[0] * 2 >= K) {.1point3acres缃
  3.             return 0;
  4.         }
  5.         int sum = 0, i = 0, j = nums.length - 1;. 1point3acres.com/bbs
  6.         while (i <= j) {
  7.             if (nums[i] + nums[j] < K) {
  8.                 sum += (int)Math.pow(2, j - i);
  9.                 i++;
  10.             } else {
  11.                 j--;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  12.             }            
  13.         }
  14.         return sum;
  15.     }
复制代码
回复 支持 2 反对 0

使用道具 举报

mimighost007 发表于 2017-8-4 08:15:25 | 显示全部楼层
第二题和two sum一样的解法

首先window = [S[0], S[-1]],如果超了,那就缩小上限,直到满足条件;然后一个一个的递增下限,直到条件条件不满足为止. visit 1point3acres.com for more.

补充内容 (2017-8-4 08:18): 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
似乎有问题,这个是找出所有集合,那还是先暴力搜吧。

补充内容 (2017-8-4 08:25):
呃,two pointers依然可以做,实际上就是找出所有的满足(x, y), 其中x + y < K的数对就行了,因为数组是排序过的,所以找出这些pair之后,就可以算出,中间有多少数,然后subset的个数就是2^(ix - iy - 1)个。

补充内容 (2017-8-4 08:31):
要考虑一个元素时候的特殊情况
回复 支持 0 反对 1

使用道具 举报

pomme2016 发表于 2017-8-5 14:04:35 | 显示全部楼层
stealop 发表于 2017-8-4 22:34
双指针做不了吧, 需要 递归
比如 k = 10
. from: 1point3acres.com/bbs
这题感觉是subset变形。
1 2 3 8的 1+8<10的时候 2^3 = 8是有8个subset 1, 1 2, 1 3, 1 8, 1 2 3, 1 2 8, 1 3 8, 1 2 3 8
然后下一个2 + 3<10 的时候 2个解 2, 2 3
然后是 3 + 3 <10 的时候 3 一个解
一共11个subsets
回复 支持 1 反对 0

使用道具 举报

lidongze91 发表于 2017-8-4 07:15:24 | 显示全部楼层
第二道题backtracking嘛楼主?求解法
回复 支持 反对

使用道具 举报

edyyy 发表于 2017-8-4 07:27:35 | 显示全部楼层
第二题求所有最大windows, 然后计算子集而已. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
补充内容 (2017-8-4 07:32):
等一下看错题了,以为是最大元素,最小元素差要小于k
和小于k的话,可以用two pointers, 不是有道相似的计算pairs的题吗
回复 支持 反对

使用道具 举报

33847682 发表于 2017-8-4 07:32:11 | 显示全部楼层
其实这题也是面经题
回复 支持 反对

使用道具 举报

edyyy 发表于 2017-8-4 07:34:14 | 显示全部楼层
33847682 发表于 2017-8-4 07:32. 1point3acres.com/bbs
其实这题也是面经题

请问是哪里看到的,我也错过了
回复 支持 反对

使用道具 举报

33847682 发表于 2017-8-4 07:58:50 | 显示全部楼层
edyyy 发表于 2017-8-4 07:34
请问是哪里看到的,我也错过了

忘记是什么时候了 之前地里的面经
回复 支持 反对

使用道具 举报

schizism 发表于 2017-8-4 07:59:24 | 显示全部楼层
尝试了一下第二题, 思路就是分别数如果当前list最小数进subset or not 然后recur


class Solution():
        def nSubsets(self,nums,k):
                if nums==None or k==None or k<=min(nums):. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                        return -1
                def count(l):
                        if l==None:
                                return 0 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                        if 2*l[0]>=k:
                                return 0
                        i=1
                        while i<len(l) and l[0]+l<k:
                                i+=1. more info on 1point3acres.com
                        return 2**(i-1)
                def rec(nums):
                        if not nums:
                                return 0 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                        ans=0
                        ans+=count(nums)+rec(nums[1:])
                        return ans. Waral 鍗氬鏈夋洿澶氭枃绔,
                return rec(nums)
. 1point 3acres 璁哄潧

补充内容 (2017-8-4 08:02):.鐣欏璁哄潧-涓浜-涓夊垎鍦
看来不用这么麻烦 直接2pointers就够了 刷的还是不够熟练啊-.-
回复 支持 反对

使用道具 举报

mingzhou1987 发表于 2017-8-4 08:54:00 | 显示全部楼层
楼主第二题,result得加上5和7.
回复 支持 反对

使用道具 举报

mingzhou1987 发表于 2017-8-4 09:01:20 | 显示全部楼层
backtrack + dfs解法,算是subset的变种题把
void dfs(vector<int> nums, int idx, int &res, vector<int> &cur, int target)
{
    if(idx == nums.size())
    {
        return;
    }
    else
    {
        for(int i = idx; i < nums.size(); i++)
        {
            cur.push_back(nums);
            if((cur.size() == 1 && cur[0] < target) || (cur[0] + cur.back() < target))
            {
                for(auto it : cur).1point3acres缃
                {
                    cout<<it<<" ";
                }
                cout<<endl;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                res++;
                dfs(nums, i + 1, res, cur, target);
            }
            cur.pop_back();. from: 1point3acres.com/bbs
            while(i < nums.size() - 1 && nums == nums[i + 1])i++;
        }
    }
}
int count(vector<int> nums, int target).1point3acres缃
{
    int res = 0;
    vector<int> cur;. Waral 鍗氬鏈夋洿澶氭枃绔,
    dfs(nums, 0, res, cur, target);. more info on 1point3acres.com
    return res;
}

int main()
{
    vector<int> nums = {2, 2, 3, 5, 7};.1point3acres缃
    cout<<count(nums, 8)<<endl;
   
}

补充内容 (2017-8-4 10:30):
if condition里(cur.size() == 1 && cur[0] < target) 条件去掉才对
回复 支持 反对

使用道具 举报

flgt2014 发表于 2017-8-4 09:04:19 | 显示全部楼层
twosumii 发表于 2017-8-4 07:27
并不是新题,你刷的不够 >

应该是 while i <= j  ?
while i < j 的时候结果会少了一个[3] (比如用LZ给的例子)
回复 支持 反对

使用道具 举报

flgt2014 发表于 2017-8-4 09:19:41 | 显示全部楼层
mingzhou1987 发表于 2017-8-4 08:54
楼主第二题,result得加上5和7.
.1point3acres缃
[5] 和 [7] 不满足条件吧?最大最小值都是本身,相加大于K了
回复 支持 反对

使用道具 举报

熟狗脸 发表于 2017-8-4 09:29:45 | 显示全部楼层
楼主加面是电面后还是onsite后的加面啊?
回复 支持 反对

使用道具 举报

f1371342385 发表于 2017-8-4 09:41:39 | 显示全部楼层
LZ这都是原题 :(
回复 支持 反对

使用道具 举报

chris612ku 发表于 2017-8-4 10:00:59 | 显示全部楼层
楼主
第一题如果用two pointer的话,题目的两个数组应该是sorted的吧?
假如没sort好是不是用hashmap 或 hashset 才会比较好?

补充内容 (2017-8-4 10:11):
第二题应该就是用two pointer吧?两层循环=》O(n^2)
.鐣欏璁哄潧-涓浜-涓夊垎鍦
补充内容 (2017-8-4 10:16):
不对  第二题想了一想  O(n)应该就可以解出来了
回复 支持 反对

使用道具 举报

mingzhou1987 发表于 2017-8-4 10:26:10 | 显示全部楼层
flgt2014 发表于 2017-8-4 09:19
[5] 和 [7] 不满足条件吧?最大最小值都是本身,相加大于K了

我理解有误,sorry,楼主的例子是对的
回复 支持 反对

使用道具 举报

Darkduke68 发表于 2017-8-4 11:25:20 | 显示全部楼层
twosumii 发表于 2017-8-4 07:27
并不是新题,你刷的不够 >

two pointers 正解。 不过 while 条件我觉得应该是i <= j, 不然会漏掉单一元素的子集。

res = 0
i, j = 0, len(s)-1
while i <= j:
    if s +s[j] < k:
        res += pow(2, j-i)
        i += 1
    else:. Waral 鍗氬鏈夋洿澶氭枃绔,
        j -= 1
return res
回复 支持 反对

使用道具 举报

mingzhou1987 发表于 2017-8-4 11:48:54 | 显示全部楼层
如果用夹击求2次幂的解法遇到重复元素怎么破?譬如这个例子,{2, 3, 3, 5, 5, 7, 7} target为8,
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷2和5 range之间有两个3,如果都只包含一个3的子集,只能算一个

回复 支持 反对

使用道具 举报

scredwood 发表于 2017-8-4 13:13:09 | 显示全部楼层
mingzhou1987 发表于 2017-8-4 11:48. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
如果用夹击求2次幂的解法遇到重复元素怎么破?譬如这个例子,{2, 3, 3, 5, 5, 7, 7} target为8,. 1point3acres.com/bbs
2和5 ran ...

如果你实在想双指针,那么就先预处理把重复去掉咯。。。
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-9-22 07:25

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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