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

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() {
     }
     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++;
                 }
             }
             while(colors[j].c == 'g') j++;
             for(int i = j + 1; i < colors.length && i > j; i++) {
                if(colors[i].c == 'g') {
                        exch(colors, i, j);
                        while(colors[j].c == 'g') j++;
                }
             }
      }
      private void exch(PocketColor[] colors, int i, int j) {
            

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

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;
                        }
                        else {
                                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");
        }

}

swap one pass也可以解决啊。。。

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

拍拍， 楼主。 move on。 有时， 和面试官气场不和。 这事常有。

楼主，我也做了那个跟你一样的sort color，也是只能用swap做，不过我没楼主厉害，折腾了好久，没时间再来一题，直接挂了。。。感觉面试官是故意要坑你的，patpat，继续加油

请问对时间空间复杂度有要求吗？

感觉这个公司面试， 碰上什么样 的面试官 很有影响。 多谢分享。 lz提到过的题， 之前电面都遇到

我一面刚刚跪了。。。都是老题，全答出来了。。结果还是给跪了。。非常不理解。。

test case, 有时会让写JUNIT test case 吗？

1. sort colors用swap不影响一遍通过的啊。 2. main function那里print的地方建议用循环来写。。。 3. next largest那个题没有parent指针的情况下，建立路径利用binary search tree特性只要O(lgN) 就可以建好了，不用DFS的。 多谢楼主分享啦，我也是这期求职，祝大家都找到心仪工作~~~