《数据科学面试40+真题讲解》,K神本年度最后一次开课


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 6821|回复: 14
收起左侧

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

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

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

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

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

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

TreeNode没有parent pointer但是给了root. 1point 3acres 璁哄潧
. Waral 鍗氬鏈夋洿澶氭枃绔,
public class Solution {
        public TreeNode nextLargest(TreeNode root, TreeNode t) {.1point3acres缃
                TreeNode temp = t;
                if(t != null && t.right != null) return getLeftMost(t.right);
                List<TreeNode> list = getAncenssor(root, t);. 1point3acres.com/bbs
                int i = 2;
                while (list.size() - i > -1) {
                        TreeNode parent = list.get(list.size() - i);. more info on 1point3acres.com
                        if(parent.left == t) return parent;
                        t = parent;
                        i++;
                }. From 1point 3acres bbs
                return temp;
        }
这个用了回溯来求根节点到t点的路径
        private List<TreeNode> getAncenssor(TreeNode root, TreeNode t) {
                // TODO Auto-generated method stub
                List<TreeNode> res = new ArrayList<TreeNode>();
                helper(root, t, new ArrayList<TreeNode>(), res);
                return res;
        }

        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);
                if(root == t) {. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                        res.addAll(new ArrayList<TreeNode>(list));. Waral 鍗氬鏈夋洿澶氭枃绔,
                        return;
                }
                helper(root.left, t, list, res);
                helper(root.right, t, list, res);
                list.remove(list.size() - 1);
        }
. 鍥磋鎴戜滑@1point 3 acres
        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;
        }
}


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

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) {
                        map.put(i, new TreeNode(s.charAt(i)));
                }-google 1point3acres
                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);
                                if(i - 2 > -1 && !stack.isEmpty() && s.charAt(i - 2) != ':') {
                                        stack.peek().left = p;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                                }
                                stack.push(p);
                                i += 2;
                        }. more info on 1point3acres.com
                        else {
.鐣欏璁哄潧-涓浜-涓夊垎鍦                                TreeNode top = stack.pop();. 鍥磋鎴戜滑@1point 3 acres
                                TreeNode right = getNode(map, i + 1);
                                top.right = right;
                                if(i - 2 > -1 && s.charAt(i - 2) != ':') {. from: 1point3acres.com/bbs
                                        TreeNode left = getNode(map, i - 1);-google 1point3acres
                                        top.left = left;
                                }
                                i += 2;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                        }. 1point3acres.com/bbs
                }. From 1point 3acres bbs
                return map.get(0); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
        }

        private TreeNode getNode(Map<Integer, TreeNode> map, int k) {.1point3acres缃
                // TODO Auto-generated method stub
                return map.get(k);. Waral 鍗氬鏈夋洿澶氭枃绔,
        }

        public static void main(String[] args) {. Waral 鍗氬鏈夋洿澶氭枃绔,
                // TODO Auto-generated method stub
                Solution s = new Solution();. visit 1point3acres.com for more.
                s.convert("a?b?d?f:g?h:i:e:c?j?k:l:m");
        }

}


评分

2

查看全部评分

xiaoyucool 发表于 2015-9-22 23:42:35 | 显示全部楼层
swap one pass也可以解决啊。。。
回复 支持 1 反对 0

使用道具 举报

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

使用道具 举报

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);
.鏈枃鍘熷垱鑷1point3acres璁哄潧

回复 支持 反对

使用道具 举报

面假空虚 发表于 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.     }
  10. }
  11. public class Solution {
  12.         public void sort(PocketColor[] colors) {.鐣欏璁哄潧-涓浜-涓夊垎鍦
  13.                 int left = 0;. 1point3acres.com/bbs
  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++;.1point3acres缃
  19.                         else swap(colors, i, right--);
  20.                 }
  21.         }
  22.        
  23.     private void swap(PocketColor []colors, int i, int j){
  24.             PocketColor temp = colors[i];.1point3acres缃
  25.             colors[i] = colors[j];. from: 1point3acres.com/bbs
  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-11-19 13:06

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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