一亩三分地论坛

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

扫码关注一亩三分地公众号
查看: 720|回复: 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;
        }
}
.1point3acres缃

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

唉,反正作为男屌丝,从来没有面试官问我这中难度的题。。. Waral 鍗氬鏈夋洿澶氭枃绔,

补充内容 (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 | 显示全部楼层
对的,如果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) {-google 1point3acres
                int len = 0;
                if (nums == null || (len = nums.length) <= 1) {
                        return len;
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴                }

                int duplicateCount = 0;
                Set<Integer> set = new HashSet<>(len);-google 1point3acres
                for (int i = 0; i < len; i++) {
                        if (set.add(nums[i])) {
                                nums[i - duplicateCount] = nums[i];
                        } else {
                                duplicateCount++;
                        }
                }

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

        public static void main(String[] args) {
                // TODO Auto-generated method stub
                // int[] nums = new int[] { 1, 3, 3 };.鏈枃鍘熷垱鑷1point3acres璁哄潧
                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();
        }
回复 支持 反对

使用道具 举报

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;
  5.                 }

  6.                 Set<Integer> set = new HashSet<>();. 1point 3acres 璁哄潧
  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.                 }
  14.                 return Arrays.copyOfRange(nums, 0, index);
  15.         }

  16.         public static void main(String[] args) {
  17.                 // TODO Auto-generated method stub
  18.                 // int[] nums = new int[] { 1, 3, 3 };
  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.                 }
  24.                 System.out.println();
  25.         }
  26. }
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 04:20

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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