一亩三分地论坛

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

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

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

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

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

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

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

x
Pocket gem店面被坑
楼主昨晚面的pocket gem二面,今天中午就收到拒信,真心感觉被坑出翔。这个公司题全部是面经上的题,100年都不带换的,不知道他们公司的技术部门到底在想些什么?
楼组店面一面很顺利,二面就坑爹了,楼主面之前也看了一下面经,大致心里有个数。面试官是个说话快的不行,我都听不清楚。
第一题是sort color的变种. 1point 3acres 璁哄潧
这题的精髓不是应该在one-pass就解决,O(1)的复杂度么?好吧,这哥们给了我一个类(他当时还没有给出object的中的结构,我就根本不知道不可以change object中char c的值,你要是让我设计类你就直说啊)。下面的类结构是我自己写的(data纯属打酱油,char代表颜色)但这样onepass就不能实现,也根本不是count sort了,完全就只能用swap来解,楼主给出的答案, 要求sort的顺序r, g, b
class PocketColor {-google 1point3acres
     int data
     char c;
     PocketColor() {. From 1point 3acres bbs
     }
     PocketColor(int data, char c) {
           this.data = data;. From 1point 3acres bbs
           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++) {. visit 1point3acres.com for more.
                if(colors[i].c == 'g') {
                        exch(colors, i, j);
                        while(colors[j].c == 'g') j++;
                }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
             }
      }. 鍥磋鎴戜滑@1point 3 acres
      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,晕
public static void main(String[] args) {
     PocketColor p1 = new PocketColor(3, 'g');
     PocketColor p2 = new PocketColor(1, 'r'); . more info on 1point3acres.com
     PocketColor p3 = new PocketColor(0, 'b');
     PocketColor p4 = new PocketColor(2, 'r');
     PocketColor p5 = new PocketColor(5, 'g');
     PocketColor p6 = new PocketColor(4, 'r');.鐣欏璁哄潧-涓浜-涓夊垎鍦
     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 + " ");. 鍥磋鎴戜滑@1point 3 acres
     System.out.print(colors[2].c + " ");
     System.out.print(colors[3].c + " ");
     System.out.print(colors[4].c + " ");
     System.out.print(colors[5].c + " ");
}. From 1point 3acres bbs
楼主打印结果完全正确,但这题我耗了不少时间来理解他到底是要干什么。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
第二题毫无新意,next largest Node in BST,有parent pointer 和无parent pointer
TreeNode {
    int val;
    TreeNode left,right, parent;
    TreeNode(int x) {
        val = x;
    }
}
这个复杂度是O(lgN), 最差情况就是全部树是一条直线,复杂度O(N)
public class Solution {
. visit 1point3acres.com for more.    public TreeNode nextLargest(TreeNode t) {
                TreeNode temp = t; //没有最大值返回本身
                if(t.right != null) return getLeftMost(t.right);
                while(t != null && t.parent != null) {. Waral 鍗氬鏈夋洿澶氭枃绔,
                        TreeNode parent = t.parent;
                        if(parent.left == t) return parent;
                        t = t.parent;. Waral 鍗氬鏈夋洿澶氭枃绔,
                }
                return temp;
        }
        .鐣欏璁哄潧-涓浜-涓夊垎鍦
        private TreeNode getLeftMost(TreeNode root) {
                // TODO Auto-generated method stub
                TreeNode p = root;
                while(p.left != null) {
                        p = p.left;.1point3acres缃
                }
                return p;
        }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
}

TreeNode没有parent pointer但是给了root

public class Solution {. Waral 鍗氬鏈夋洿澶氭枃绔,
        public TreeNode nextLargest(TreeNode root, TreeNode t) {
                TreeNode temp = t;
                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++;
                }
                return temp;
        }
这个用了回溯来求根节点到t点的路径
        private List<TreeNode> getAncenssor(TreeNode root, TreeNode t) {
                // TODO Auto-generated method stub
                List<TreeNode> res = new ArrayList<TreeNode>();.鏈枃鍘熷垱鑷1point3acres璁哄潧
                helper(root, t, new ArrayList<TreeNode>(), res);
                return res;. From 1point 3acres bbs
        }

        private void helper(TreeNode root, TreeNode t, List<TreeNode> list, List<TreeNode> res) {
                // TODO Auto-generated method stub.1point3acres缃
                if(root == null) return;
                list.add(root);.1point3acres缃
                if(root == t) {
                        res.addAll(new ArrayList<TreeNode>(list));
                        return;
                }
. 鍥磋鎴戜滑@1point 3 acres                helper(root.left, t, list, res);
                helper(root.right, t, list, res);
                list.remove(list.size() - 1);
        }

        private TreeNode getLeftMost(TreeNode root) {
                // TODO Auto-generated method stub
                TreeNode p = root;
                while(p.left != null) {
                        p = p.left;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                }
                return p;
        }
}


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


public class Solution {
        public TreeNode convert(String s) {
                Map<Integer, TreeNode> map = new HashMap<Integer, TreeNode>();
                for(int i = 0; i < s.length(); i += 2) {. 鍥磋鎴戜滑@1point 3 acres
                        map.put(i, new TreeNode(s.charAt(i)));
                }
                int i = 1, N = s.length();
                Stack<TreeNode> stack = new Stack<TreeNode>();
                while(i < N) {
                        if(i < N && s.charAt(i) == '?') {
                                TreeNode p = getNode(map, i - 1);-google 1point3acres
                                if(i - 2 > -1 && !stack.isEmpty() && s.charAt(i - 2) != ':') {
                                        stack.peek().left = p;
                                }. more info on 1point3acres.com
                                stack.push(p);
                                i += 2;
                        }.鐣欏璁哄潧-涓浜-涓夊垎鍦
                        else {. 1point 3acres 璁哄潧
                                TreeNode top = stack.pop();
                                TreeNode right = getNode(map, i + 1);
. more info on 1point3acres.com                                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) {. from: 1point3acres.com/bbs
                // TODO Auto-generated method stub
                return map.get(k);
        }

        public static void main(String[] args) {. 鍥磋鎴戜滑@1point 3 acres
                // TODO Auto-generated method stub
                Solution s = new Solution();
                s.convert("a?b?d?f:g?h:i:e:c?j?k:l:m");
        }

}.鏈枃鍘熷垱鑷1point3acres璁哄潧


.鐣欏璁哄潧-涓浜-涓夊垎鍦

评分

2

查看全部评分

hulahu 发表于 2015-9-5 03:21:52 | 显示全部楼层
拍拍, 楼主。 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);-google 1point3acres
.鏈枃鍘熷垱鑷1point3acres璁哄潧

回复 支持 反对

使用道具 举报

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) {. 鍥磋鎴戜滑@1point 3 acres
  7.           this.data = data;
  8.           this.c = c;
  9.     }
  10. }. 1point3acres.com/bbs
  11. public class Solution {
  12.         public void sort(PocketColor[] colors) {
  13.                 int left = 0;
  14.                 int right = colors.length-1;
  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--);
  20.                 }
  21.         }
  22.        
  23.     private void swap(PocketColor []colors, int i, int j){
  24.             PocketColor temp = colors[i];
  25.             colors[i] = colors[j];
  26.             colors[j] = temp;. 鍥磋鎴戜滑@1point 3 acres
  27.     }
  28. }
复制代码

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

使用道具 举报

randomusername 发表于 2015-12-18 15:38:49 | 显示全部楼层
天啊 楼主你第二题 也是suboptimal的做法啊.... leetcode难道是白刷的?
回复 支持 反对

使用道具 举报

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

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 04:59

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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