[八我司] Expedia一年半遊:这是一個特別適合養老待退的地方

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货

最近看过此主题的会员

H1B/绿卡遥遥无期
又不想回国
来东南亚最大的互联网集团工作?
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
查看: 6129|回复: 23
收起左侧

Google 4月12 技术电面 面经

[复制链接] |试试Instant~ |关注本帖
我的人缘0
xtpmgzn 发表于 2016-4-13 03:17:43 | 显示全部楼层 |阅读模式
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】

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

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

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

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
. 围观我们@1point 3 acres
顺便求米,谢谢

. 一亩-三分-地,独家发布

评分

参与人数 4大米 +41 收起 理由
stephaniede + 5 欢迎来介绍你知道的情况
yueliu2366 + 1 题目很好
edcent + 5 感谢分享!
candy_shmily + 30

查看全部评分


上一篇:Jump Trading 电面 (继上次OA帖子之后)
下一篇:Yelp onsite面经

本帖被以下淘专辑推荐:

  • · Google|主题: 54, 订阅: 47
我的人缘0
waikai 发表于 2016-4-13 05:30:23 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
难呀,lz题目的意思是可以用括号但是不能改变数字的顺序么
回复 支持 反对

使用道具 举报

我的人缘0
Alice0701 发表于 2016-4-13 05:39:26 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
这题做电面挺难的啊!!
回复 支持 反对

使用道具 举报

我的人缘0
adiggo 发表于 2016-4-13 06:09:41 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
楼主, 问个问题, list 所有的数 只能用一遍?
回复 支持 反对

使用道具 举报

我的人缘0
prodigalr 发表于 2016-4-13 07:25:32 | 显示全部楼层
  此人我要顶:
 
100% (1) 【我投】
  此人我要踩:
 
0% (0) 【我投】
电面都这么难。。。。感觉应该用DP做。
回复 支持 反对

使用道具 举报

我的人缘0
superbeet 发表于 2016-4-13 08:01:12 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
多谢楼主分享。

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

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

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

使用道具 举报

我的人缘0
caiqi8877 发表于 2016-4-13 08:59:10 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
楼主能说下你当时是什么思路吗?
回复 支持 反对

使用道具 举报

我的人缘0
justinlee 发表于 2016-4-13 09:15:15 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
应该是用DPS吧,只是写起来应该不简单
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

我的人缘0
yueliu2366 发表于 2016-4-13 09:46:41 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
我感觉应该不管怎么样都是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);
        for(int t : ret) {. 一亩-三分-地,独家发布
            if (t == target) {
                return true;
            }. 围观我们@1point 3 acres
        }
        return false;. visit 1point3acres for more.
    }
   
    HashSet<Integer> dfs(int nums[], int i, int j) {
        HashSet<Integer> ret = new HashSet<Integer>();
        if(i == j) {
            ret.add(nums);
            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);.本文原创自1point3acres论坛
            for(int opt1 : list1) {
                for(int opt2 : list2) {
                    ret.add(opt1 * opt2);
                    ret.add(opt1 + opt2);
                    ret.add(opt1 - opt2);
                    ret.add(opt2 - opt1);
                    if (opt2 != 0) ret.add(opt1 / opt2);
                    if (opt1 != 0) ret.add(opt2 / opt1);
                }. visit 1point3acres for more.
            }
        }
. From 1point 3acres bbs        return ret;
    }

补充内容 (2016-4-13 09:49):
DP的做法实在想不到,求教
回复 支持 反对

使用道具 举报

我的人缘0
zwj1991 发表于 2016-4-13 10:26:28 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
2-(3*(6-9)) = 11应该是true吧?
回复 支持 反对

使用道具 举报

我的人缘0
caiqi8877 发表于 2016-4-13 13:02:54 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
yueliu2366 发表于 2016-4-13 09:46
我感觉应该不管怎么样都是NP问题吧,时间上最多剪剪枝优化吧? 这里定一个递归函数HashSet dfs(int nums[], ...

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

使用道具 举报

我的人缘0
superbeet 发表于 2016-4-13 14:08:25 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
yueliu2366 发表于 2016-4-13 09:46
我感觉应该不管怎么样都是NP问题吧,时间上最多剪剪枝优化吧? 这里定一个递归函数HashSet dfs(int nums[], ...

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

使用道具 举报

我的人缘0
superbeet 发表于 2016-4-13 14:09:58 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
class Solution():
    def check_points(self, nums, target):
        self.sol = []-google 1point3acres
        res = self.search(nums, len(nums), target)
        return self.sol
. 牛人云集,一亩三分地
    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]. more info on 1point3acres
                nums[j] = nums[n-1]

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

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

                nums = a*b
                if self.search(nums, n-1, target):
                    return True. 围观我们@1point 3 acres
.留学论坛-一亩-三分地
                if b!= 0:
                    nums = int(a/b)
                    if self.search(nums, n-1, target):
                        return True

                if a!= 0:
                    nums = int(b/a). 围观我们@1point 3 acres
                    if self.search(nums, n-1, target):
                        return True 来源一亩.三分地论坛.

                nums = a
                nums[j] = b

        return False



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

使用道具 举报

我的人缘0
yueliu2366 发表于 2016-4-13 21:41:08 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
superbeet 发表于 2016-4-13 14:09
class Solution():
    def check_points(self, nums, target):
        self.sol = []

python不会,看不懂。但是请问下,你这个方法时间复杂度是多少呢?
回复 支持 反对

使用道具 举报

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

使用道具 举报

我的人缘0
curious88323 发表于 2016-4-14 03:51:15 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
这题要是我可能就用backtracking做了。。。。
回复 支持 反对

使用道具 举报

我的人缘0
lookbackinanger 发表于 2016-4-14 03:58:47 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
测例不对吧,两个都可以得到啊,是不是还有其他限制?
回复 支持 反对

使用道具 举报

我的人缘0
xzt8350 发表于 2016-4-14 05:06:14 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
楼主 你给的第二个例子应该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);       
. 1point 3acres 论坛
                for (Integer k : solutions) {
                        if (k == target) {
                                return true;-google 1point3acres
                        }
                }

                return false;. 留学申请论坛-一亩三分地
        }

        private List<Integer> allSolutions(int left, int right, List<Integer> nums) {
                List<Integer> ret = new ArrayList<Integer>();
                if (left > right) {
                        return ret; 来源一亩.三分地论坛.
                } else if (left == right) {
                        ret.add(nums.get(left));
                        return ret;
                }

                for (int i = left; i < right; i++) {. From 1point 3acres bbs
                        List<Integer> leftSols = allSolutions(left, i,nums);
                        List<Integer> rightSols = allSolutions(i+1, right,nums);
                        for (Integer a: leftSols) {. 留学申请论坛-一亩三分地
                                for (Integer b: rightSols) {. Waral 博客有更多文章,
                                        ret.add(a+b);
. visit 1point3acres for more.                                        ret.add(a-b);
                                        ret.add(a*b);
                                        if (b != 0) ret.add(a/b);
                                }
                        }
                }
               
                return ret;
        }
回复 支持 反对

使用道具 举报

我的人缘0
superbeet 发表于 2016-4-14 06:16:48 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
yueliu2366 发表于 2016-4-13 21:41
python不会,看不懂。但是请问下,你这个方法时间复杂度是多少呢?

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

使用道具 举报

我的人缘0
lookbackinanger 发表于 2016-4-14 10:34:14 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
xzt8350 发表于 2016-4-14 05:06
楼主 你给的第二个例子应该return true 吧 [2 3 6 9] ->  2 + (3*6) - 9 = 11

这是我的做法
. 一亩-三分-地,独家发布
需要用float吧,除法以后会有误差
回复 支持 反对

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

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

custom counter

GMT+8, 2018-6-20 00:37

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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