一亩三分地论坛

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

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

4月29日谷歌家onsite新鲜面经来了

  [复制链接] |试试Instant~ |关注本帖
wobujupa 发表于 2016-5-1 03:57:56 | 显示全部楼层 |阅读模式

2016(4-6月) 码农类 本科 全职@Google - 内推 - Onsite |Other在职跳槽

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

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

x
昨天刚刚面的,共五轮面试,幸运的没有遇到烙印。五轮面试官,有一个是中国大哥,其他的都是白人。来地里跟大家分享一下,希望大家都有好offer。
第一轮,Graph题,给的是一个有方向的Graph,每个node都有颜色,有黑绿红三种颜色,制定的patten是以任意颜色的node开始,接着是大于等于一个绿色的node,以红色的node结尾,找出所有符合这种pattern的path的head node。
面试官画出来的是一个有序的Graph,所以是在有序Graph基础上加上颜色的属性。因为我对于Graph的掌握不是特别好,面试官讲说我可以从Tree这个角度下手,所以我先用Tree试着去做。
我的理解这个题目应该采用DFS,根据在dfs中传入color,去check当前的path是否符合pattern。写的过程中不是特别顺利,不过一直在跟面试官沟通,最终写了一版出来。面试官针对一些case提出疑问,然后就在code的基础上进行了一定的修改,最终的版本也没有去跑test case。不过时间也剩没几分钟,就简单的聊了几句后第二个面试官便来敲门了。
第二轮,判断这个数字是否可以用两个数字的平方加和而成。题目清晰之后,我跟面试官check了一下input的情况。便写出了一个简单的版本,时间复杂度为0(n) 。
public boolean isSumOfTwoSquares(int n){
                for(int i = 0; i * i <= n; i++){
                        for(int j = 0; j * j <= n; j++){
                                if(i * i + j * j == n) return true;
                        }
                }
                return false;
        }
因为input n是一个Integer,所以这个overflow的情况就是当i * i + j * j > n的情况,其实里边的循环改成j * j <= n - i会好一些。然后面试官的问题是当n = Integer.MAX_VALUE, I * i <= n is always true, so the loop will be like while true. 这个我跟面试官讲说,如果i * i 已经超出最大值的情况下,我不太清楚这个<=的结果是true还是false,(刚刚试了一下果然是true)。所以针对这个问题,我就将i * i <= n 改成了i <= Math.sqrt(n), j也是一样。这样的话有效的避免了这个问题。面试官问我接下来能不能优化,那我就从里层的循环下手,时间复杂度为o(sqrt(n))
public boolean isSumOfTwoSquares(int n){
                for(int i = 0; i <= Math.sqrt(n); i++){
                        if(isSqrt(n - i * i)) return true;
                }
                return false;
        }
       
        public boolean isSqrt(int n){
                int sqrt = (int)Math.sqrt(n);
                if(sqrt * sqrt == n) return true;
                return false;
        }
面试官对于这个时间复杂度还比较满意,接下来的follow up就是面试官认为这个Math.sqrt方法不够efficient。问有没有可以不用这个方法的。可以用一次,然后将这个结果N储存下来作为一个变量。那这个其实就是可以用一个数据结构去存储所有的square value,然后将第二个方法改成check 数据结构中是否存在当前值。我当时不晓得脑子怎么秀逗了,竟然想用一个array,后来跟面试官聊了一会之后恍然大悟,为什么不用set,然后就用set写了一版。
public boolean isSumOfTwoSquares(int n){
                int N = (int)Math.sqrt(n);
                initialSet(N);
                for(int i = 0; i <= N; i++){
                        if(isSqrt(n - i * i)) return true;
                }
                return false;
        }
       
        public boolean isSqrt(int n){
                if(set.contains(n)) return true;
                return false;
        }
       
        private Set<Integer> set = new HashSet<>();
         
        public void initialSet(int N){
                for(int i = 0; i <= N; i++){
                        set.add(i * i);
                }
        }
写到这里之后,针对于这个的时间复杂度,我们有进行了一点讨论,所以结果是依然是o(sqrt(n)),针对于这个set的contains的复杂度,因为有HashSet和TreeSet,我就讲到肯定HashSet,操作复杂度为o(1),又问了我下这俩set的区别,我就提到我基本上没有用过TreeSet,巴拉巴拉什么的。面试官开始跟我讨论test case。因为最开始出题的时候,我隐约听到了他提到n是正数,所以没有去check是否为负数。这时候加上了负数的check。还有跟面试官讨论了下0的return value的期望值,他认为是true。然后我就写了几个test case可以cover所有的corner case
isSumOfTwoSquares(-1);
        isSumOfTwoSquares(0);
        isSumOfTwoSquares(Integer.MAX_VALUE);
        isSumOfTwoSquares(13);
        isSumOfTwoSquares(3);
面试官对这个还比较满意。然后给我时间问问题,首先是问了些工作的问题,然后我就问道,在你的实际工作中,有什么应用到TreeSet的场景么,结果是no,从来没用过,哈哈。然后又聊了一会,第三个面试官迟到了,所以第二个面试官在回答问题的时候一直在瞅外边,好像着急要走的样子。
第三轮,华人大哥,全程黑脸, I don’t know why. 因为迟到了,所以上来没有握手寒暄,没有自我介绍,啪就把题甩出来了。
第一题input是两个数组,求数组A中存在但是B中不存在的,以及B中存在A中不存在的。
A [1,2,3,5]
        B [2,2,4]
        in A not in B [1,2,3,5]
        in B not in A [2,4]
我的思路就是现将两个数组排序之后,从头进行比较,我用手动的方式展示了一下我的思路,得出来指定的结果,结果每次我给面试官投去眼光的时候,都发现他没有在看我。后来面试官讲到这其实把两个input调个个,就可以得出两个结果,一个helper方法就够了,然后让我在assume数组都已经排序的基础上进行处理。那我就开始code。
public List<Integer> helper(int[] arr1, int[] arr2){
                List<Integer> res = new ArrayList<>();
                int index = 0;
                for(int i = 0; i < arr1.length; i++){
                        if(index >= arr2.length){
                                res.add(arr1);
                        }
                        if(arr1 < arr2[index]){
                                res.add(arr1);
                        }else{
                                index++;
                        }
                }
                return res;
        }
写完之后,面试官看了一眼,没有问什么问题,就接着出题了。
第二题input是一个 integer数组, 求smallest  subset sum bigger than target,target是全部数字求和的1%。
拿到题目之后,我当时首先想到的是难道可以用two sum或者什么的,结果发现不对付。那我首先思路是先排序,然后从大的开始找,当sum大于target的时候,这一定就是最短的subset。我用手写的方式展示了,第一个版本的代码是这样的。
public int minSubSet(int[] nums){
                int sum = 0;
                for(int num : nums){
                        sum += num;
                }
                int target = sum / 100;
                int len = 0;
                Arrays.sort(nums);
                int length = nums.length - 1;
                sum = 0;
                for(int i = length - 1; i >= 0; i--){
                        sum += nums;
                        len++;
                        if(sum > target){
                                return len;
                        }
                }
                return len;
        }
时间复杂度是o(nlogn),面试官提到这个OK,但是可以优化到o(n),当时确实一时没什么思路,思考了一会之后,还是向面试官求思路。给的思路是,从数组中随机取一个数字,然后将取出比这个数字大的subset,然后对这个subset求和与target比较,如果大的话就迭代操作。如果小的话,从小的数组里再取一部分。思考了一段时间,便开始编码。代码是这样的。
public List<Integer> minSubSet(int[] nums){
                List<Integer> list = new ArrayList<>();
                int sum = 0;
                for(int num : nums){
                        list.add(num);
                        sum += num;
                }
                int target = sum / 100;
                return helper(list, target);
        }
       
        public List<Integer> helper(List<Integer> list, int target){
                int size = list.size();
                Random random = new Random();
                int n = list.get(random.nextInt(size));
                List<Integer> biglist = new ArrayList<>();
                List<Integer> smalllist = new ArrayList<>();
                int sum = 0;
                for(int num : list){
                        if(num > n){
                                biglist.add(num);
                                sum += num;
                        }else{
                                smalllist.add(num);
                        }
                }
                if(sum > target){
                        if(biglist.size() == 1) return biglist;
                        return helper(biglist, target);
                }else{
                        List<Integer> tmp = helper(smalllist, target - sum);
                        for(int num : tmp){
                                biglist.add(num);
                        }
                        return biglist;
                }
        }
代码一开始不是bug free的,然后面试官也是给各种case,讨论执行过程。最后优化代码。然后到我问问题的时间,我就咨询了下加入谷歌后需要多少时间适应整个环境,实际上手这样。聊了一会下个面试官就来敲门了。
第四轮,面试小哥是做安卓的。上来先来了几个java 的基础问题,什么是abstract class,怎么用abstract class,interface与abstract class的区别。然后给了一个算是设计的题目。要求是给一个apply方法,有两个参数一个是list<T>,另外一个算是一个function,要求不管传入什么样的操作都可以实现,比如list<Integer>, funtion is times two,那返回的结果就是所有list的元素加倍。这个是最简单的例子,还有比如square或者pow各种各样的要求都要满足。一开始我的理解与题目有偏差,没有特别好的给出一个满意的解答。最后还是咨询了一下面试小哥,他的解答是用interface去实现。瞬间明了。一开始思考的方向就完全错了。接下来出题了。
第一题:给一个integer的数组,求数组中是否存在两个数字,一个是另一个的两倍。前边有用到set,所以此处我也采用set,跟小哥交流之后,讨论了可行性。然后开始编码。同时包括case 0的情况。
public boolean isDoubleExists(int[] nums){
                Set<Integer> set = new HashSet<>();
                for(int num : nums){
                        if(num == 0) return true;
                        if(set.contains(num * 2)) return true;
                        if(set.contains(num / 2) && num / 2 * 2 == num){
                                return true;
                        }
                        set.add(num);
                }
                Iterator<Integer> iter = set.iterator();
                while(iter.hasNext()){
                        Integer num = iter.next();
                        if(set.contains(num * 2)) return true;
                        if(set.contains(num / 2) && num / 2 * 2 == num) return true;
                }
                return false;
        }
Follow up是两倍的chain比如1 2 4,找最长的chain。这个题最开始的话我建议先排序,这样从小到大,会比较容易一些(现在一想,可能不排序分两倍和二分之一一样可以实现)。然后同样还是用set去做,但是是dfs的思路,不断更新max len的值。
int max = 0;
        public int maxDoubleChain(int[] nums){
                Arrays.sort(nums);
                Set<Integer> set = new HashSet<>();
                for(int num : nums){
                        set.add(num);
                }
                for(int num : set){
                        dfs(set, num, 1);
                }
                return max;
        }
       
        public void dfs(Set<Integer> set, int num, int len){
                if(set.contains(num * 2)){
                        len++;
                        dfs(set, num * 2, len);
                }else{
                        max = Math.max(max, len);
                }
        }

代码实现之后,小哥提问是否可以进一步优化,省去重复访问一些已经走过的值。我提到可以用map记录已经访问过的值,如果已经访问到的话,就直接return.
int max = 0;
public int maxDoubleChain(int[] nums){
                Arrays.sort(nums);
                Map<Integer, Boolean> map = new HashMap<>();
                Set<Integer> set = new HashSet<>();
                for(int num : nums){
                        set.add(num);
                }
                for(int num : set){
                        dfs(set, num, 1, map);
                }
                return max;
        }
       
        public void dfs(Set<Integer> set, int num, int len, Map<Integer, Boolean> map){
                if(map.get(num)){
                        return;
                }
                map.put(num, true);
                if(set.contains(num * 2)){
                        len++;
                        dfs(set, num * 2, len, map);
                }else{
                        max = Math.max(max, len);
                }
        }
最后针对时间复杂度讨论了好久,最后我讲说因为sort是最大的所以是o(nlogn),小哥说,对,我就是在等这个。然后后来又聊了一会,最后一个面试小哥来敲门了。
第五轮,上来就寒暄一阵。小哥上来先针对我的简历问了几个问题,关于系统的维护已经如果有效的避免再次出现同样的问题。然后上题。题目是给一个String数组(我不晓得我怎么就跟数组杠上了),求最长的keyword。keyword的定义是,移除一个字符,剩下的字符串依然在数组中,一直移直到最后只剩下一个字符。拿到题目之后,思考一会之后沟通了下我的思路,因为要求最长,所以我建议先根据长度进行排序(又是排序)。还有一个提前break的情况是如果最短的字符串长度大于1,那没有keyword出现的可能性。这时候跟面试小哥沟通的结果是这个可以返回””.
public String findKeyword(String[] dics){
                List<String> list = new ArrayList<>();
                for(String word : dics){
                        list.add(word);
                }
                Collections.sort(list, new Comparator<String>() {
                        @Override
                        public int compare(String o1, String o2) {
                                if(o1.length() > o2.length()){
                                        return -1;
                                }else if(o1.length() < o2.length()){
                                        return 1;
                                }else{
                                        return 0;
                                }
                        }
                });
                if(list.get(list.size() - 1).length() > 1) return "";
                for(String word : list){
                        if(dfs(list, word)) return word;
                }
                return "";
        }
        public boolean dfs(List<String> list, String word){
                if(word.length() == 1){
                        if(list.contains(word)) return true;
                        return false;
                }
                for(int i = 0; i < word.length(); i++){
                        String newword = word.substring(0, i) + word.substring(i + 1);
                        if(dfs(list, newword)){
                                return true;
                        }
                }
                return false;
        }
第一次写出来的也不是bug free的,小哥也是给我提供各种case,然后不断改进代码,最后能满足需求。follow up就是如何去进行优化,避免重复check同样的字符串,比如有两个元素一个goat,一个boat,如何避免oat的重复check。那这里我就讲说用map去维护当前元素是否visited。
Map<String, Boolean> map = new HashMap<>();
        public String findKeyword(String[] dics){
                List<String> list = new ArrayList<>();
                for(String word : dics){
                        list.add(word);
                }
                Collections.sort(list, new Comparator<String>() {
                        @Override
                        public int compare(String o1, String o2) {
                                if(o1.length() > o2.length()){
                                        return -1;
                                }else if(o1.length() < o2.length()){
                                        return 1;
                                }else{
                                        return 0;
                                }
                        }
                });
                if(list.get(list.size() - 1).length() > 1) return "";
                for(String word : list){
                        if(map.containsKey(word)){
                                if(map.get(word)) return word;
                        }else{
                                if(dfs(list, word)) return word;
                        }
                }
                return "";
        }
        public boolean dfs(List<String> list, String word){
                if(word.length() == 1){
                        if(list.contains(word)){
                                map.put(word, true);
                                return true;
                        }
                        map.put(word, false);
                        return false;
                }
                for(int i = 0; i < word.length(); i++){
                        String newword = word.substring(0, i) + word.substring(i + 1);
                        boolean flag = dfs(list, newword);
                        if(flag){
                                map.put(newword, true);
                                return true;
                        }
                        map.put(newword, false);
                }
                return false;
        }
解答完毕,然后可能有点超出时间,不过还是跟面试小哥愉快的交流了好半天,然后小哥送我出公司,开开心心的聊了一路。然后他就回去上班了。
中午的lunch一定要提一下了,中午没有去那个据说超级赞的亚洲餐厅,就在面试的楼下的餐厅吃的,带我吃饭的是一个中国小哥,真心赞。跟我讲说中午吃饭可以讲中文的,哈哈,一边吃饭一边瞎扯。吃完了小哥带我在园区里逛了一圈然后去游戏室玩了一下。再一次给小哥赞。
.鏈枃鍘熷垱鑷1point3acres璁哄潧
来面试之前,做了好多的准备,leetcode面经都有好好在看,但是这次面试一个原题我也没碰上,不过出乎意料的没有出现太难的题目,当然第一个我没有答好,但是总归是一直努力的和面试官在沟通。谷歌的整体环境太赞了,我会回来的!!!
晚点我再把第一个题的code完善一下发上来,虽然不一定争取。. Waral 鍗氬鏈夋洿澶氭枃绔,
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

补充内容 (2016-5-12 08:32):. visit 1point3acres.com for more.
今下午谷歌小哥打电话来告知刚刚收齐feedback,明天HC,应该这几天会有结果出来,然后问了下有没有deadline,然后因为现在我在麻省工作了,又要了新的简历过去。希望明天HC顺利!

补充内容 (2016-5-18 12:17):
昨晚上刚刚接到Recruiter电话,说虽然did well,但是不move forward了,今天再邮件follow up一下。不过跟小哥商量能不能有其他的role比如sdet之类的可以再试一下,小哥说可以,不过需要联系其他的recruiter。祝好...

评分

11

查看全部评分

duduhaha 发表于 2016-5-1 05:34:38 | 显示全部楼层
感谢楼主面经,非常详细!. more info on 1point3acres.com

isSumOfTwoSquares 这题应该可以先得到sqrt(n), 然后用 two sum的双指针思想就行了。

最长的keyword的那题好像BFS好些,建立一个all string 的hash_set  和一个visited的 hashset, 先把长度为1的string全部放进queue里,然后用
BFS的思想应该可以找到最长的。
回复 支持 2 反对 0

使用道具 举报

hkc593 发表于 2016-5-4 04:32:02 | 显示全部楼层
wobujupa 发表于 2016-5-3 10:31
第一个Graph我用Tree去做大概是这么个样子,当时写的没有这个完整一点。大家一起看看对不对的。
. 1point 3acres 璁哄潧
应该可以加个cache,已经走过的node,不需要再重复走了

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

stevez 发表于 2016-5-1 05:19:08 | 显示全部楼层
感谢lz分享,这是最近看的最详尽的Google面经了
回复 支持 反对

使用道具 举报

 楼主| wobujupa 发表于 2016-5-1 05:48:42 | 显示全部楼层
stevez 发表于 2016-5-1 05:19
感谢lz分享,这是最近看的最详尽的Google面经了

哈哈,希望能有所帮助了,也祝我自己能拿下
回复 支持 反对

使用道具 举报

 楼主| wobujupa 发表于 2016-5-1 05:53:07 | 显示全部楼层
duduhaha 发表于 2016-5-1 05:34. Waral 鍗氬鏈夋洿澶氭枃绔,
感谢楼主面经,非常详细!
.鏈枃鍘熷垱鑷1point3acres璁哄潧
isSumOfTwoSquares 这题应该可以先得到sqrt(n), 然后用 two sum的双指针思想 ...

bfs确实应该也可行,但是我觉得bfs也是需要找到多个keyword然后进行比较,看哪个最长找出来,为什么我感觉时间和dfs相比应该不相上下嘞
回复 支持 反对

使用道具 举报

duduhaha 发表于 2016-5-1 06:17:27 | 显示全部楼层
wobujupa 发表于 2016-5-1 05:53
bfs确实应该也可行,但是我觉得bfs也是需要找到多个keyword然后进行比较,看哪个最长找出来,为什么我感 ...

时间上是差不多,甚至DFS会好些。我是感觉BFS比较直观,而且不用担心stack overflow due to recursion.
回复 支持 反对

使用道具 举报

mzli1989 发表于 2016-5-1 07:42:36 | 显示全部楼层
感谢楼主分享。
楼主是在职跳槽,也没考system design么?
回复 支持 反对

使用道具 举报

 楼主| wobujupa 发表于 2016-5-1 07:45:21 | 显示全部楼层
mzli1989 发表于 2016-5-1 07:42
感谢楼主分享。
楼主是在职跳槽,也没考system design么?

是这么个情况,我找朋友内推是去年十一月还是十二月的事情了,中间间隔好久才来的第一轮电话面试。所以我不晓得给我内推的具体是什么情况,只知道有个内推机会就美得不行不行的。所以我不太清楚这边面试的时候是什么一个标准来面试的。
回复 支持 反对

使用道具 举报

mzli1989 发表于 2016-5-1 08:20:39 | 显示全部楼层
wobujupa 发表于 2016-5-1 07:45. 1point 3acres 璁哄潧
是这么个情况,我找朋友内推是去年十一月还是十二月的事情了,中间间隔好久才来的第一轮电话面试。所以我 ...

嗯了解。。祝好运祝拿offer!!
回复 支持 反对

使用道具 举报

 楼主| wobujupa 发表于 2016-5-1 14:41:02 | 显示全部楼层
mzli1989 发表于 2016-5-1 08:20
嗯了解。。祝好运祝拿offer!!

谢谢,也祝你一切顺利!
回复 支持 反对

使用道具 举报

duduhaha 发表于 2016-5-1 14:51:59 | 显示全部楼层
Follow up是两倍的chain比如1 2 4,找最长的chain   刚才想了下应该有O(n)的解法,下面这样。

int longestDoubleChain(int a[], int n) {
  unordered_set<int> m;
  int result = 0, zero_counter = 0;
  
  for (int i = 0; i < n; i++) {
    if (a[i] == 0)
      zero_counter++;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
    else
      m.insert(a[i]);
  }
   
  while (!m.empty()) {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
    auto iter = m.begin();
    int num = *iter, saved = num;
    m.erase(num);
    . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
    int chain_len = 0;
    //find the smaller chain from num
    while ( num / 2 > 0 && (num / 2 * 2 == num) && m.count(num / 2)) {
      chain_len++;
      m.erase(num / 2);
      num /= 2;
    }
   
    //find the greater chain from num
    num = saved;
    while (m.count(num * 2)) {
. 鍥磋鎴戜滑@1point 3 acres      chain_len++;
      m.erase(num * 2);
      num *= 2;
    }
   
    result = max(result, chain_len);
  }
  
  return max(result, zero_counter - 1);. 1point 3acres 璁哄潧
}
回复 支持 反对

使用道具 举报

Gordoxd 发表于 2016-5-1 18:57:57 | 显示全部楼层
感谢楼主。好好学习一下。
回复 支持 反对

使用道具 举报

 楼主| wobujupa 发表于 2016-5-1 23:39:12 | 显示全部楼层
duduhaha 发表于 2016-5-1 14:51
Follow up是两倍的chain比如1 2 4,找最长的chain   刚才想了下应该有O(n)的解法,下面这样。

int longe ...
. 1point 3acres 璁哄潧
恩恩,这个我赞同。理论上loop一遍也是可以实现的。我当时就是跟面试官说了一下,这样做起来方便些,他倒是没有太纠结这个o(nlogn)的复杂度。
回复 支持 反对

使用道具 举报

 楼主| wobujupa 发表于 2016-5-1 23:39:32 | 显示全部楼层
Gordoxd 发表于 2016-5-1 18:57
感谢楼主。好好学习一下。

哈哈,大家互相学习,都有好运气咯
回复 支持 反对

使用道具 举报

tcomein2009 发表于 2016-5-2 00:19:37 | 显示全部楼层
wobujupa 发表于 2016-5-1 05:48
哈哈,希望能有所帮助了,也祝我自己能拿下

感谢楼主分享。

请问平方和那道题,第一种方法是不是应该是n^2
因为0到n的循环嵌套
回复 支持 反对

使用道具 举报

 楼主| wobujupa 发表于 2016-5-2 00:31:35 | 显示全部楼层
tcomein2009 发表于 2016-5-2 00:19
感谢楼主分享。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

请问平方和那道题,第一种方法是不是应该是n^2

因为外循环是i = 0; i * i <= n; i++,内循环是 j = 0; j * j <= n; j++ 所以 i j都是0到sqrt(n), 所以两层循环一乘就是o(n)了。不晓得是不是这个意思。
回复 支持 反对

使用道具 举报

Gordoxd 发表于 2016-5-2 07:08:32 | 显示全部楼层
wobujupa 发表于 2016-5-1 23:39
哈哈,大家互相学习,都有好运气咯

好的。祝你早日拿到满意的offer!
回复 支持 反对

使用道具 举报

woaibai 发表于 2016-5-2 09:17:39 | 显示全部楼层
多谢lz分享
第一题input是两个数组,求数组A中存在但是B中不存在的,以及B中存在A中不存在的。
. from: 1point3acres.com/bbs
这个用hashset就可以吧,不需要排序,线性时间。
回复 支持 反对

使用道具 举报

woaibai 发表于 2016-5-2 09:33:11 | 显示全部楼层
第二题input是一个 integer数组, 求smallest  subset sum bigger than target,target是全部数字求和的1%。. from: 1point3acres.com/bbs
拿到题目之后,我当时首先想到的是难道可以用two sum或者什么的,结果发现不对付。那我首先思路是先排序,然后从大的开始找,当sum大于target的时候,这一定就是最短的subset。我用手写的方式展示了,第一个版本的代码是这样的。


这个没太明白,smallest是subset的长度还是subset里的元素和?. from: 1point3acres.com/bbs
如果input [2,1,3,4,5].鐣欏璁哄潧-涓浜-涓夊垎鍦
target = 0.15
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
按你的方法排完序[1,2,3,4,5]
. visit 1point3acres.com for more.从右边开始比较,返回的结果是5?应该都符合吧,长度都是1

还有
     int target = sum / 100;

这个target变量是不是要用double呢?

多谢~
回复 支持 反对

使用道具 举报

 楼主| wobujupa 发表于 2016-5-2 10:34:59 | 显示全部楼层
woaibai 发表于 2016-5-2 09:17.鐣欏璁哄潧-涓浜-涓夊垎鍦
多谢lz分享

这个用hashset就可以吧,不需要排序,线性时间。

这个不能用set,原因就是如果存在重复得值,假如数组1中俩2,数组2中一个2,那这个2也要算是两个数组的差别,如果用set的话你该怎么找出这个2来呢
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-10 05:18

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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