一亩三分地论坛

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

一亩三分地官方iOS手机应用下载
查看: 1227|回复: 8
收起左侧

开个帖子google一道真题求讨论(附加代码)

[复制链接] |试试Instant~ |关注本帖
qiuxuxing007 发表于 2015-10-30 12:39:16 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 全职@Google - Other - Onsite |Otherfresh grad应届毕业生

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

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

x
第三轮,白人大哥,在谷歌做了11年了。。。先问challenging project,然后出题:remove duplicate。比如[1,3,3]输出[1,3],[5,5,6,5,4] 输出 [5,6,4]。原帖在http://www.1point3acres.com/bbs/ ... p;page=1#pid2037194

我用java写的,不知道用entry 来做可不可这道题目我在面某小公司的时候出现过, 我觉得我这种做法是可以要保留原有array的顺序的,但是面试宫觉得倒到hashmap里面了,就变得乱序了,我觉得虽然hashmap是乱序的,但是对entry来说是有序的,根据加入hashmap的顺序来做的,不止大家觉得这种方法可以嘛?求各位大神讨论代码在下面,顺便求点积分

public int[] removeDup(int[] num){
           HashMap<Integer,Integer> map=new HashMap<Integer,Integer>();
           for(int i=0;i<num.length;i++){
                   if(map.containsKey(num)){
                           map.put(num,map.get(num)+1);
                   }
                   else{
                           map.put(num,1);
                   }
           }
          
           ArrayList<Integer> list=new ArrayList<Integer>();
           for(Entry<Integer, Integer> entry:map.entrySet()){
                   list.add(entry.getKey());
           }
          
           int[] res=new int[list.size()];
           for(int i=0;i<list.size();i++){
                   res=list.get(i);
           }//convert arraylist to array
           return res;
        }
}


marthew777 发表于 2015-10-30 13:13:11 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
我不是大神。我的想法是这样的。
如果这题你想用space trade time, 都已经用了map了。倒不如用set,反正都是扫一遍,set还自动帮你去duplicates了是吧,
如果你想用time trade space, in place sort了吧这题转变为LC原题了,remove duplicates from sorted arrayI, . 1point3acres.com/bbs

唉,反正作为男屌丝,从来没有面试官问我这中难度的题。。

补充内容 (2015-10-30 13:32):
LZ大人,我刚才没看到stable的要求。。刚看到[5,5,6,5,4] 输出 [5,6,4]的例子,
有这个要求就用set扫+去重。。不可以用hashmap, entry顺序不是stable的哦!如果你依然想用map,可以用LinkedHashMap =)
回复 支持 反对

使用道具 举报

 楼主| qiuxuxing007 发表于 2015-11-8 02:53:42 | 显示全部楼层
关注一亩三分地微博:
Warald
对的,如果entry 要有序的话,只能用linkedhashmap ,多谢了
回复 支持 反对

使用道具 举报

yucheyang2 发表于 2016-1-16 14:11:44 | 显示全部楼层
这样的,你用HashSet,维护一个DuplicateCount,每Duplicate一次后面数字++
回复 支持 反对

使用道具 举报

yucheyang2 发表于 2016-1-16 14:18:50 | 显示全部楼层
        public static int removeDuplicate(int[] nums) {
                int len = 0;
                if (nums == null || (len = nums.length) <= 1) {
                        return len;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                }

                int duplicateCount = 0;. visit 1point3acres.com for more.
                Set<Integer> set = new HashSet<>(len);
                for (int i = 0; i < len; i++) {
                        if (set.add(nums[i])) {.鏈枃鍘熷垱鑷1point3acres璁哄潧
                                nums[i - duplicateCount] = nums[i];
                        } else {
                                duplicateCount++;
. 1point 3acres 璁哄潧                        }
                }

                return len - duplicateCount;
        }
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
        public static void main(String[] args) {
                // TODO Auto-generated method stub
                // int[] nums = new int[] { 1, 3, 3 };. from: 1point3acres.com/bbs
                int[] nums = new int[] { 5, 5, 6, 6, 5, 4 };
                int len = removeDuplicate(nums);
                for (int i = 0; i < len; i++) {
                        System.out.print(nums[i]);. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                }
                System.out.println();
        }
求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 反对

使用道具 举报

yucheyang2 发表于 2016-1-16 14:20:43 | 显示全部楼层
有道题目,貌似是BB的面经,就是一个数组怎么Inplace Remove Zero,就是用类似方法的。
回复 支持 反对

使用道具 举报

yucheyang2 发表于 2016-1-16 14:21:37 | 显示全部楼层
你如果想用HashMap,你用LinkedHashMap,这个是LinkedList + HashMap,保留插入的顺序的。
回复 支持 反对

使用道具 举报

 楼主| qiuxuxing007 发表于 2016-1-16 14:34:57 | 显示全部楼层
多谢了, 我懂了
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-1-21 12:32:42 | 显示全部楼层
写了下代码
  1. public class RemoveDuplicateII {
  2.         public static int[] removeDuplicate(int[] nums) {
  3.                 if (nums == null || nums.length <= 1) {
  4.                         return nums;. 鍥磋鎴戜滑@1point 3 acres
  5.                 }

  6.                 Set<Integer> set = new HashSet<>();
  7.                 int index = 0;
  8.                 for (int i = 0; i < nums.length; i++) {
  9.                         if (!set.contains(nums[i])) {
  10.                                 nums[index++] = nums[i];
  11.                                 set.add(nums[i]);
  12.                         }
  13.                 }. From 1point 3acres bbs
  14.                 return Arrays.copyOfRange(nums, 0, index);
  15.         }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

  16.         public static void main(String[] args) {
  17.                 // TODO Auto-generated method stub-google 1point3acres
  18.                 // int[] nums = new int[] { 1, 3, 3 };. From 1point 3acres bbs
  19.                 int[] nums = new int[] { 5, 5, 6, 6, 5, 4 };
  20.                 int[] res = removeDuplicate(nums);
  21.                 for (int i = 0; i < res.length; i++) {
  22.                         System.out.print(res[i] + " ");. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  23.                 }. 1point3acres.com/bbs
  24.                 System.out.println();
  25.         }. more info on 1point3acres.com
  26. }
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2017-4-24 17:03

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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