推荐:数据科学课程和书籍清单以及培训讲座


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

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

Pocket Gem我已被坑,贴出面经答案(完整代码)

[复制链接] |试试Instant~ |关注本帖
lby1989825 发表于 2015-9-5 02:58:02 | 显示全部楼层 |阅读模式

2015(7-9月) 码农类 硕士 全职@PoketGem - 网上海投 - 技术电面 |Failfresh grad应届毕业生

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

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

x
Pocket gem店面被坑
楼主昨晚面的pocket gem二面,今天中午就收到拒信,真心感觉被坑出翔。这个公司题全部是面经上的题,100年都不带换的,不知道他们公司的技术部门到底在想些什么?
楼组店面一面很顺利,二面就坑爹了,楼主面之前也看了一下面经,大致心里有个数。面试官是个说话快的不行,我都听不清楚。
第一题是sort color的变种
这题的精髓不是应该在one-pass就解决,O(1)的复杂度么?好吧,这哥们给了我一个类(他当时还没有给出object的中的结构,我就根本不知道不可以change object中char c的值,你要是让我设计类你就直说啊)。下面的类结构是我自己写的(data纯属打酱油,char代表颜色)但这样onepass就不能实现,也根本不是count sort了,完全就只能用swap来解,楼主给出的答案, 要求sort的顺序r, g, b. 1point3acres.com/bbs
class PocketColor {
     int data.鏈枃鍘熷垱鑷1point3acres璁哄潧
     char c;
     PocketColor() {
     }
     PocketColor(int data, char c) {
           this.data = data;
           this.c = c;
     }
}

public class Solution {
      public void sort(PocketColor[] colors) {
             if(colors.length == 0 || colors == null) return;
             int j = 0;
             while(colors[j].c == 'r') j++;
             for(int i = j + 1; i < colors.length; i++) {
                 if(colors[i].c == 'r') {
                        exch(colors, i, j);
                        while(colors[j].c == 'r') j++;
                 }. more info on 1point3acres.com
             }
             while(colors[j].c == 'g') j++;
             for(int i = j + 1; i < colors.length && i > j; i++) {
                if(colors[i].c == 'g') {.1point3acres缃
                        exch(colors, i, j);
                        while(colors[j].c == 'g') j++;
                }
             }
      }
      private void exch(PocketColor[] colors, int i, int j) {
              PocketColor temp = new PocketColor();
              temp = colors[i];
              colors[i] = colors[j];
              colors[j] = temp;
      }
}
楼主搞出这个之后,他让我写test case,结果居然不是要test case,而是要我写出main function,晕. more info on 1point3acres.com
public static void main(String[] args) {
     PocketColor p1 = new PocketColor(3, 'g');
     PocketColor p2 = new PocketColor(1, 'r');
     PocketColor p3 = new PocketColor(0, 'b');
     PocketColor p4 = new PocketColor(2, 'r');
     PocketColor p5 = new PocketColor(5, 'g');. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
     PocketColor p6 = new PocketColor(4, 'r');.鏈枃鍘熷垱鑷1point3acres璁哄潧
     PocketColor[] colors = new PocketColor[]{p1, p2, p3, p4, p5, p6};
     Solution s = new Solution();
     s.sort(colors);
     System.out.print(colors[0].c + " ");
     System.out.print(colors[1].c + " ");
     System.out.print(colors[2].c + " ");
     System.out.print(colors[3].c + " ");
     System.out.print(colors[4].c + " ");
     System.out.print(colors[5].c + " ");
}
楼主打印结果完全正确,但这题我耗了不少时间来理解他到底是要干什么。
第二题毫无新意,next largest Node in BST,有parent pointer 和无parent pointer. more info on 1point3acres.com
TreeNode {
    int val;
    TreeNode left,right, parent;
    TreeNode(int x) {
        val = x;
    }
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷}. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
这个复杂度是O(lgN), 最差情况就是全部树是一条直线,复杂度O(N)
public class Solution {
    public TreeNode nextLargest(TreeNode t) {
                TreeNode temp = t; //没有最大值返回本身
                if(t.right != null) return getLeftMost(t.right);
                while(t != null && t.parent != null) {-google 1point3acres
                        TreeNode parent = t.parent;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                        if(parent.left == t) return parent;
                        t = t.parent;
                }. From 1point 3acres bbs
                return temp;.1point3acres缃
        }
       
        private TreeNode getLeftMost(TreeNode root) {. Waral 鍗氬鏈夋洿澶氭枃绔,
                // TODO Auto-generated method stub
                TreeNode p = root;
                while(p.left != null) {
                        p = p.left;. 鍥磋鎴戜滑@1point 3 acres
                }. Waral 鍗氬鏈夋洿澶氭枃绔,
                return p; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
        }
}. 1point3acres.com/bbs
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
TreeNode没有parent pointer但是给了root

public class Solution {
        public TreeNode nextLargest(TreeNode root, TreeNode t) {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                TreeNode temp = t;. more info on 1point3acres.com
                if(t != null && t.right != null) return getLeftMost(t.right);
                List<TreeNode> list = getAncenssor(root, t);
                int i = 2;
                while (list.size() - i > -1) {
                        TreeNode parent = list.get(list.size() - i);
                        if(parent.left == t) return parent;
                        t = parent;
                        i++;
. From 1point 3acres bbs                }.鏈枃鍘熷垱鑷1point3acres璁哄潧
                return temp;
        }
这个用了回溯来求根节点到t点的路径
        private List<TreeNode> getAncenssor(TreeNode root, TreeNode t) {. Waral 鍗氬鏈夋洿澶氭枃绔,
                // TODO Auto-generated method stub. 1point 3acres 璁哄潧
                List<TreeNode> res = new ArrayList<TreeNode>();
                helper(root, t, new ArrayList<TreeNode>(), res);
                return res;. visit 1point3acres.com for more.
        }

        private void helper(TreeNode root, TreeNode t, List<TreeNode> list, List<TreeNode> res) {
                // TODO Auto-generated method stub.鐣欏璁哄潧-涓浜-涓夊垎鍦
                if(root == null) return;
                list.add(root);. from: 1point3acres.com/bbs
                if(root == t) {-google 1point3acres
                        res.addAll(new ArrayList<TreeNode>(list));
                        return;
                }
                helper(root.left, t, list, res);. from: 1point3acres.com/bbs
                helper(root.right, t, list, res);
                list.remove(list.size() - 1);
        }. visit 1point3acres.com for more.

        private TreeNode getLeftMost(TreeNode root) {
                // TODO Auto-generated method stub
. visit 1point3acres.com for more.                TreeNode p = root;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                while(p.left != null) {
                        p = p.left;
                }
                return p;
        }
}. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

. 鍥磋鎴戜滑@1point 3 acres
这就是我给出了全部代码,面试官和我的交流不是很好,代码全部可以通过测试。第二天就收到拒信,早就听说过他家坑爹,果然如此。HR态度也不好,从来不回复我邮件,所以我一怒之下贴了他家的代码
希望对以后的人有所帮助,楼主真的是有认真准备过他家,结果居然这样!楼主现在只剩下zenefit,google(已onsite完等结果)两家了,工作真心不好找。希望大家顺利吧,哎!好伤心
对了,二轮店面tenary的代码我也贴出来希望对大家有所帮助(我没考到) stack非递归只扫一遍,不对之处大家海涵,我毕竟水平有限。
class TreeNode {
        char val;
        TreeNode left;-google 1point3acres
        TreeNode right;
        TreeNode(char x){
                val = x;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
        }
}. 1point 3acres 璁哄潧


public class Solution {
        public TreeNode convert(String s) {. visit 1point3acres.com for more.
                Map<Integer, TreeNode> map = new HashMap<Integer, TreeNode>();
                for(int i = 0; i < s.length(); i += 2) {
                        map.put(i, new TreeNode(s.charAt(i)));. visit 1point3acres.com for more.
                }
                int i = 1, N = s.length();
                Stack<TreeNode> stack = new Stack<TreeNode>();
                while(i < N) {
                        if(i < N && s.charAt(i) == '?') {. from: 1point3acres.com/bbs
                                TreeNode p = getNode(map, i - 1);
                                if(i - 2 > -1 && !stack.isEmpty() && s.charAt(i - 2) != ':') {-google 1point3acres
                                        stack.peek().left = p;
                                }-google 1point3acres
                                stack.push(p);
                                i += 2;
                        }
                        else {.1point3acres缃
                                TreeNode top = stack.pop();
                                TreeNode right = getNode(map, i + 1);
                                top.right = right;
                                if(i - 2 > -1 && s.charAt(i - 2) != ':') {
                                        TreeNode left = getNode(map, i - 1);
                                        top.left = left;
                                }
                                i += 2;
                        }
                }
                return map.get(0);
        }

        private TreeNode getNode(Map<Integer, TreeNode> map, int k) { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                // TODO Auto-generated method stub.鐣欏璁哄潧-涓浜-涓夊垎鍦
                return map.get(k);
        }

        public static void main(String[] args) {
                // TODO Auto-generated method stub
                Solution s = new Solution();
                s.convert("a?b?d?f:g?h:i:e:c?j?k:l:m");
. more info on 1point3acres.com        }

}. 鍥磋鎴戜滑@1point 3 acres


评分

2

查看全部评分

randomusername 发表于 2015-12-18 15:38:49 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
天啊 楼主你第二题 也是suboptimal的做法啊.... leetcode难道是白刷的?
回复 支持 1 反对 0

使用道具 举报

hulahu 发表于 2015-9-5 03:21:52 | 显示全部楼层
关注一亩三分地微博:
Warald
拍拍, 楼主。 move on。 有时, 和面试官气场不和。 这事常有。
回复 支持 反对

使用道具 举报

rainny 发表于 2015-9-5 03:53:20 | 显示全部楼层
楼主,我也做了那个跟你一样的sort color,也是只能用swap做,不过我没楼主厉害,折腾了好久,没时间再来一题,直接挂了。。。感觉面试官是故意要坑你的,patpat,继续加油
回复 支持 反对

使用道具 举报

slayer 发表于 2015-9-5 05:02:07 | 显示全部楼层
请问对时间空间复杂度有要求吗?
回复 支持 反对

使用道具 举报

lichenga2404 发表于 2015-9-7 06:19:37 | 显示全部楼层
感觉这个公司面试, 碰上什么样 的面试官 很有影响。 多谢分享。 lz提到过的题, 之前电面都遇到
回复 支持 反对

使用道具 举报

swx1031 发表于 2015-9-22 07:52:15 | 显示全部楼层
我一面刚刚跪了。。。都是老题,全答出来了。。结果还是给跪了。。非常不理解。。
回复 支持 反对

使用道具 举报

mkcing 发表于 2015-9-22 08:06:06 | 显示全部楼层
test case, 有时会让写JUNIT test case 吗?
回复 支持 反对

使用道具 举报

mkcing 发表于 2015-9-22 08:13:33 | 显示全部楼层
private void helper(TreeNode root, TreeNode t, List<TreeNode> list, List<TreeNode> res) ;

可以换成 private boolean helper(TreeNode root, TreeNode t, List<TreeNode> list, List<TreeNode> res)

helper(root.left, t, list, res); //在这个分支已经找到了 t,  那就不用继续找root.right 了啊
helper(root.right, t, list, res);


回复 支持 反对

使用道具 举报

xiaoyucool 发表于 2015-9-22 23:42:35 | 显示全部楼层
swap one pass也可以解决啊。。。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
回复 支持 反对

使用道具 举报

面假空虚 发表于 2015-10-24 04:38:09 | 显示全部楼层
1. sort colors用swap不影响一遍通过的啊。 2. main function那里print的地方建议用循环来写。。。 3. next largest那个题没有parent指针的情况下,建立路径利用binary search tree特性只要O(lgN) 就可以建好了,不用DFS的。 多谢楼主分享啦,我也是这期求职,祝大家都找到心仪工作~~~
回复 支持 反对

使用道具 举报

randomusername 发表于 2015-12-18 15:15:12 | 显示全部楼层
我觉得第一题就算是object array也完全可以one pass做掉啊
回复 支持 反对

使用道具 举报

randomusername 发表于 2015-12-18 15:22:03 | 显示全部楼层
  1. class PocketColor {
  2.     int data;
  3.     char c;
  4.     PocketColor() {
  5.     }
  6.     PocketColor(int data, char c) {
  7.           this.data = data;
  8.           this.c = c;
  9.     }.鏈枃鍘熷垱鑷1point3acres璁哄潧
  10. }
  11. public class Solution {. 鍥磋鎴戜滑@1point 3 acres
  12.         public void sort(PocketColor[] colors) {
  13.                 int left = 0;
  14.                 int right = colors.length-1;. Waral 鍗氬鏈夋洿澶氭枃绔,
  15.                 int i = 0;
  16.                 while (i <= right){
  17.                         if (colors[i].c == 'r') swap(colors, i++, left++);
  18.                         else if(colors[i].c == 'g') i++;
  19.                         else swap(colors, i, right--);. Waral 鍗氬鏈夋洿澶氭枃绔,
  20.                 } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  21.         }
  22.        
  23.     private void swap(PocketColor []colors, int i, int j){. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  24.             PocketColor temp = colors[i];
  25.             colors[i] = colors[j];.1point3acres缃
  26.             colors[j] = temp;
  27.     }
  28. }
复制代码

这样做one pass直接搞掂了啊
回复 支持 反对

使用道具 举报

yimingzi 发表于 2015-12-19 16:53:28 | 显示全部楼层
很明显, 楼主给的都不是最好的方法...
回复 支持 反对

使用道具 举报

newgod2500 发表于 2017-6-29 11:04:40 | 显示全部楼层
Sort color我面过了....但是4色这个我是最后一个follow up,没时间写,之前解了快3个follow up,估计面试官也理解 所以没为难我。

Tenary这题其实楼主有一个小缺漏。 你的解法是建立在 a ? b : c, 所有符号的位置都是恒定的情况下的,包括LC上很多解法也是assume是这样的..如果遇到" a  ?        b:c"这样的话...这个solution就不work了.. 一些小改进。 而且这题楼上是1-pass O(N), space(2N)吧....其实有O(N), space O(N)的做法。不需要hash table 也可以
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-7-28 10:48

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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