一亩三分地论坛

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

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

Google 4月12 技术电面 面经

[复制链接] |试试Instant~ |关注本帖
xtpmgzn 发表于 2016-4-13 03:17:43 | 显示全部楼层 |阅读模式

2016(4-6月) 码农类 硕士 全职@Google - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
本人小白,这次电面对本人来说挺难的,很紧张。对面是个白人小哥,感觉是第一次当面试官,听得出他也挺紧张。我是一路跟着小哥的提示走的,最后写了伪代码,还不一定对。目测已跪。
.鐣欏璁哄潧-涓浜-涓夊垎鍦
给出一个 list of int, the target, 输出这个 list 中所用的数能否通过4则运算 得到 target。

boolean EvaluatesTo(list numbers, int target)

[2 3 6 9] → 75
(2+3)*(6+9) = 75 return true

[2 3 6 9] -> 11 return false

顺便求米,谢谢

. From 1point 3acres bbs

评分

4

查看全部评分

本帖被以下淘专辑推荐:

  • · Google|主题: 54, 订阅: 45
waikai 发表于 2016-4-13 05:30:23 | 显示全部楼层
难呀,lz题目的意思是可以用括号但是不能改变数字的顺序么
回复 支持 反对

使用道具 举报

Alice0701 发表于 2016-4-13 05:39:26 | 显示全部楼层
这题做电面挺难的啊!!
回复 支持 反对

使用道具 举报

adiggo 发表于 2016-4-13 06:09:41 | 显示全部楼层
楼主, 问个问题, list 所有的数 只能用一遍?
回复 支持 反对

使用道具 举报

prodigalr 发表于 2016-4-13 07:25:32 | 显示全部楼层
电面都这么难。。。。感觉应该用DP做。
回复 支持 反对

使用道具 举报

superbeet 发表于 2016-4-13 08:01:12 | 显示全部楼层
多谢楼主分享。

感觉这题应该有不需要DP的解法,如果数字的位置不能变那符号组合只可能有4*4*4种,括号的可能性是6种,一共加起来小于500种。然后可以再进一步剪枝,例如如果括号里面的符号的优先级(* /)全部大于括号外的(+ -),那么不用计算,因为在没加括号前已经算过了。

DP的方法就从左到右扫一遍,然后从右到左再来一遍。因为只有四个数,不一定速度比不用DP快多少。

欢迎各位大牛一起讨论~
回复 支持 反对

使用道具 举报

caiqi8877 发表于 2016-4-13 08:59:10 | 显示全部楼层
楼主能说下你当时是什么思路吗?
回复 支持 反对

使用道具 举报

justinlee 发表于 2016-4-13 09:15:15 | 显示全部楼层
应该是用DPS吧,只是写起来应该不简单
回复 支持 反对

使用道具 举报

yueliu2366 发表于 2016-4-13 09:46:41 | 显示全部楼层
我感觉应该不管怎么样都是NP问题吧,时间上最多剪剪枝优化吧? 这里定一个递归函数HashSet<Integer> dfs(int nums[], int i, int j),它将会返回用[i,j]范围内(inclusive for both i and j)的所有数进行四则运算的结果,因为结果可能重复,所以用HashSet而不用list来存所有的结果。然后在递归函数中分别求出  list1 = dfs(nums, i, k) 和list2 = dfs(nums, k + 1, j),其中k的范围是[i,j],最后对list1和list2的所有数两两进行四则运算,这样k从i到j后,就会有所有的结果。欢迎大家讨论指正,或者有什么更好的办法。
boolean EvaluatesTo(int nums[], int target) {. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
        HashSet<Integer> ret = dfs(nums, 0, nums.length - 1);. visit 1point3acres.com for more.
        for(int t : ret) {
            if (t == target) {
                return true;
            }
        }
        return false;
    }
    . 鍥磋鎴戜滑@1point 3 acres
    HashSet<Integer> dfs(int nums[], int i, int j) {
        HashSet<Integer> ret = new HashSet<Integer>();
        if(i == j) {. 1point 3acres 璁哄潧
            ret.add(nums);. more info on 1point3acres.com
            return ret;
        }
        for(int k = i; k <= j - 1; k++) {
            HashSet<Integer> list1 = dfs(nums, i, k);
            HashSet<Integer> list2 = dfs(nums, k + 1, j);
            for(int opt1 : list1) {
                for(int opt2 : list2) {. from: 1point3acres.com/bbs
                    ret.add(opt1 * opt2);
                    ret.add(opt1 + opt2);
                    ret.add(opt1 - opt2);
                    ret.add(opt2 - opt1);. Waral 鍗氬鏈夋洿澶氭枃绔,
                    if (opt2 != 0) ret.add(opt1 / opt2);
                    if (opt1 != 0) ret.add(opt2 / opt1);
                }
            }
        }
        return ret;
    }.1point3acres缃

补充内容 (2016-4-13 09:49):. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
DP的做法实在想不到,求教
回复 支持 反对

使用道具 举报

zwj1991 发表于 2016-4-13 10:26:28 | 显示全部楼层
2-(3*(6-9)) = 11应该是true吧?
回复 支持 反对

使用道具 举报

caiqi8877 发表于 2016-4-13 13:02:54 | 显示全部楼层
yueliu2366 发表于 2016-4-13 09:46
我感觉应该不管怎么样都是NP问题吧,时间上最多剪剪枝优化吧? 这里定一个递归函数HashSet dfs(int nums[], ...

暂时也只想到这种方法
回复 支持 反对

使用道具 举报

superbeet 发表于 2016-4-13 14:08:25 | 显示全部楼层
yueliu2366 发表于 2016-4-13 09:46
我感觉应该不管怎么样都是NP问题吧,时间上最多剪剪枝优化吧? 这里定一个递归函数HashSet dfs(int nums[], ...

你这个解法应该可以。这题应该就是24点的变种,解法一样。DP解法就是把任意两个数组合成一个,等于把四个数变成了三个数。以此递归,直到只剩下一个数,比较一下这个数是否等于target。我楼下贴个Python版的,欢迎大家comment。
回复 支持 反对

使用道具 举报

superbeet 发表于 2016-4-13 14:09:58 | 显示全部楼层
class Solution():
    def check_points(self, nums, target):
        self.sol = []
        res = self.search(nums, len(nums), target). 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
        return self.sol.1point3acres缃

    def search(self, nums, n, target):
        if n==1:
            if nums[0] == target:
                return True
            else:
                return False

        for i in xrange(0, n):
            for j in xrange(i+1, n):
                a = nums. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                b = nums[j]
                nums[j] = nums[n-1]

                nums = a + b
                if self.search(nums, n-1, target):
                    return True.鐣欏璁哄潧-涓浜-涓夊垎鍦

                nums = a - b
                if self.search(nums, n-1, target):. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                    return True

                nums = b - a
                if self.search(nums, n-1, target):
                    return True

                nums = a*b. From 1point 3acres bbs
                if self.search(nums, n-1, target):. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                    return True

                if b!= 0:
                    nums = int(a/b)
                    if self.search(nums, n-1, target):
                        return True. Waral 鍗氬鏈夋洿澶氭枃绔,
. 1point3acres.com/bbs
                if a!= 0:.鐣欏璁哄潧-涓浜-涓夊垎鍦
                    nums = int(b/a)
                    if self.search(nums, n-1, target):
                        return True

                nums = a.鏈枃鍘熷垱鑷1point3acres璁哄潧
                nums[j] = b

        return False



补充内容 (2016-4-13 14:15):
"a = nums" =》 "a = nums
"nums = a" =》 "nums = a“
这两个地方改一下
回复 支持 反对

使用道具 举报

yueliu2366 发表于 2016-4-13 21:41:08 | 显示全部楼层
superbeet 发表于 2016-4-13 14:09
class Solution():
    def check_points(self, nums, target):
        self.sol = []
. From 1point 3acres bbs
python不会,看不懂。但是请问下,你这个方法时间复杂度是多少呢?
回复 支持 反对

使用道具 举报

头像被屏蔽
holyzz 发表于 2016-4-14 03:03:16 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

curious88323 发表于 2016-4-14 03:51:15 | 显示全部楼层
这题要是我可能就用backtracking做了。。。。
回复 支持 反对

使用道具 举报

lookbackinanger 发表于 2016-4-14 03:58:47 | 显示全部楼层
测例不对吧,两个都可以得到啊,是不是还有其他限制?
回复 支持 反对

使用道具 举报

xzt8350 发表于 2016-4-14 05:06:14 | 显示全部楼层
楼主 你给的第二个例子应该return true 吧 [2 3 6 9] ->  2 + (3*6) - 9 = 11

这是我的做法
public boolean EvaluatesTo(List<Integer> nums, int target) {
                List<Integer> solutions = allSolutions(0,nums.size() - 1,nums);       

                for (Integer k : solutions) {
                        if (k == target) {. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                                return true;
                        }. 1point3acres.com/bbs
                }

                return false;
        }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

        private List<Integer> allSolutions(int left, int right, List<Integer> nums) {
                List<Integer> ret = new ArrayList<Integer>();. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                if (left > right) {
                        return ret;.鏈枃鍘熷垱鑷1point3acres璁哄潧
                } else if (left == right) {
                        ret.add(nums.get(left));
                        return ret;
                }

                for (int i = left; i < right; i++) {
                        List<Integer> leftSols = allSolutions(left, i,nums);
                        List<Integer> rightSols = allSolutions(i+1, right,nums);
                        for (Integer a: leftSols) {
                                for (Integer b: rightSols) {
                                        ret.add(a+b);
                                        ret.add(a-b);. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                                        ret.add(a*b);
                                        if (b != 0) ret.add(a/b);
                                }
                        }
                }
               
                return ret;
        }
回复 支持 反对

使用道具 举报

superbeet 发表于 2016-4-14 06:16:48 | 显示全部楼层
yueliu2366 发表于 2016-4-13 21:41. more info on 1point3acres.com
python不会,看不懂。但是请问下,你这个方法时间复杂度是多少呢?

我感觉是NP问题,没什么办法降低复杂度级别。只能剪枝稍微优化一下,怎么看都觉得是24点。网上搜一下就可以看到常用解法,就是优化版的穷举。
回复 支持 反对

使用道具 举报

lookbackinanger 发表于 2016-4-14 10:34:14 | 显示全部楼层
xzt8350 发表于 2016-4-14 05:06
楼主 你给的第二个例子应该return true 吧 [2 3 6 9] ->  2 + (3*6) - 9 = 11 -google 1point3acres

这是我的做法

需要用float吧,除法以后会有误差
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 06:12

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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