G onsite 2015/02/09

楼主，麻烦透露下第一题的思路吧

tianyangche 发表于 2015-2-10 12:59
对的~我是用的recursion解法~

楼主啊, 第一题我想了想, recursive好像是挺直接的. 那么先比如没有括号, 也就是加减乘除四个运算符号，每次开4个分支. 最后时间复杂度就变成了4^n, n = list.length. 面试官有说这样不行必须优化么？

其次...他有没有给提示, 加括号的时候怎么想啊, 我一下子没有琢磨出来.

谢谢！

TsenAlex 发表于 2015-2-11 04:33
LZ几轮电面拿到的onsite 电面是什么水平的题目啊？ 从内推到电面到onsite分别花了多少时间？
多谢啦！！！

一轮电面拿到的onsite。电面是一道很简单的题，一个矩阵，有些数是零，有些数不是零。不是零的那些数代表一个岛屿的高度，然后找出有几个岛。第二问是找出高度大于指定要求的岛有几个。第三问难一些，是问如果这个矩阵特别大，用mapreduce怎么做。

yapingchen1990 发表于 2015-2-11 04:41
楼主，麻烦透露下第一题的思路吧

我刚开始想错了，后来经他提示想出了解法。用分治法来做。for循环从0开始，每次分成左右两边，左边的结果是一个list，右边的结果也是个list。然后每次从左边的list和右边的list中各取出一个数字，进行加减乘除，看看能不能得到target。for循环里面求左右两个list也是同样的函数，这样的话就是递归。其实我这道题没写完，他们刚开始给我安排到了一个building，但是面试却在另一个building，我走过去半个小时，面试开始都十点二十了。第一轮少了十几分钟。面试官最后确定懂了我的思路就走了。

shwanfan 发表于 2015-2-11 05:01
楼主啊, 第一题我想了想, recursive好像是挺直接的. 那么先比如没有括号, 也就是加减乘除四个运算符号， ...

你说的是对的，如果只用一个单纯的dfs，类似于permutation那样子的是会出现问题。其实我刚开始写了一个类似与permutation的解法，后来发现(1 + 2) * (3 + 4)这种情况处理不了。他提示我用分治法来做，我就用了23楼的那个解法。

tianyangche 发表于 2015-2-11 06:42
一轮电面拿到的onsite。电面是一道很简单的题，一个矩阵，有些数是零，有些数不是零。不是零的那些数代表 ...

多谢分享~ 投的是new grad的职位吗？这么还问mapreduce。。。

tianyangche 发表于 2015-2-11 06:42
一轮电面拿到的onsite。电面是一道很简单的题，一个矩阵，有些数是零，有些数不是零。不是零的那些数代表 ...

多谢分享~ 投的是new grad的职位吗？这么还问mapreduce。。。

tianyangche 发表于 2015-2-11 06:46
我刚开始想错了，后来经他提示想出了解法。用分治法来做。for循环从0开始，每次分成左右两边，左边的结果 ...

点个赞！不错

TsenAlex 发表于 2015-2-11 07:58
多谢分享~ 投的是new grad的职位吗？这么还问mapreduce。。。

是new grad=。=不知道为什么会问map reduce。我说我不会，他说没关系，我告诉你什么叫map reduce……

tianyangche 发表于 2015-2-11 06:46
我刚开始想错了，后来经他提示想出了解法。用分治法来做。for循环从0开始，每次分成左右两边，左边的结果 ...

楼主。刚才想了下。如果input是1,2,3,4,四个integer的话， 这道题的意思是这四个数必须按顺序么。因为如果不是按照顺序进行计算的话，好像会比较复杂。 比如（1 * 4） - （2 / 3）