Yahoo两次电面

据说yahoo经常跳过hr，直接senior manager一个邮件发过来说要聊聊，是yahoo search team。这一聊一个小时，暂且算做第一轮电面。

一面：印度阿姨，因为实在是工作了好多年，人很nice。聊她聊我聊简历，就得有25分钟。然后是好多java概念问题。abstract class vs. interface，thread vs. process，lockarrayl

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

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

了一通没做出来，说可不可以给个小hint呀，小哥说single iteration和in-place就是hint。囧 就是因为您这俩hint我才不会做啊。已跪没得说，求地里大神指点solution。

格式不对 重发一下
我觉得要求既然是inorder inplace onepass，那么复杂度肯定不是O(n)，而且题目也没要求复杂度O(n)。代码贴上了，没有完整的test，但是至少能pass楼主给的input


public class ArraySplitBySign {
    public static void main(String[] args) {
        int[] arr = new int[]{3, -10, -2, -5, 10, 4, 5, -1, 10, 2, -4};
        int[] arr1 = new int[]{-3, -10, -2, -5, 10, 4, 5, -1, 10, 2, -4};
        System.out.println(Arrays.toString(arr1));
        Solve(arr1);
        System.out.println(Arrays.toString(arr1));
    }

    public static void Solve(int[] nums) {
        int i = -1;
        int j = 0;
        int len = nums.length;
        while (j < len) {
            while (j < len && nums[j] > 0) {
                j++;
            }
            if (i == -1) i = j;
            while (j < len && nums[j] < 0) {
                j++;
            }
            int end = j - 1;
            while (j < len && nums[j] > 0) {
                j++;
            }
            if (i != -1) {
                int times = j - end - 1;
                for (int k = end; k >= i; k--) {
                    for (int t = 0; t < times; t++) {
                        swap(nums, k + t, k + t + 1);
                    }
                }
            }
            i = j - end + i - 1;
            System.out.println(i);
        }
    }

    private static void swap(int[] nums, int i, int j) {
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }
}

我的指针j就是唯一的一次pass， i 实际上是没有iterate的，只用来记录而已。

我觉得要求既然是inorder inplace onepass，那么复杂度肯定不是O(n)，而且题目也没要求复杂度O(n)。代码贴上了，没有完整的test，但是至少能pass楼主给的input   public class ArraySplitBySign {     public static void main(String[] args) {         int[] arr = new int[]{3, -10, -2, -5, 10, 4, 5, -1, 10, 2, -4};         int[] arr1 = new int[]{-3, -10, -2, -5, 10, 4, 5, -1, 10, 2, -4};         System.out.println(Arrays.toString(arr1));         Solve(arr1);         System.out.println(Arrays.toString(arr1));     }      public static void Solve(int[] nums) {         int i = -1;         int j = 0;         int len = nums.length;         while (j < len) {             while (j < len && nums[j] > 0) {                 j++;             }             if (i == -1) i = j;             while (j < len && nums[j] < 0) {                 j++;             }             int end = j - 1;             while (j < len && nums[j] > 0) {                 j++;             }             if (i != -1) {                 int times = j - end - 1;                 for (int k = end; k >= i; k--) {                     for (int t = 0; t < times; t++) {                         swap(nums, k + t, k + t + 1);                     }                 }             }             i = j - end + i - 1;             System.out.println(i);         }     }      private static void swap(int[] nums, int i, int j) {         int t = nums[i];         nums[i] = nums[j];         nums[j] = t;     } }  我的指针j就是唯一的一次pass， i 实际上是没有iterate的，只用来记录而已。

补充内容 (2017-1-22 06:10):
格式不对，见下一楼

多谢楼主分享，请问你内推后多久收到电面啊？

aangel 发表于 2016-11-18 10:51
多谢楼主分享，请问你内推后多久收到电面啊？

他家比较奇葩。13号内推，然后系统会陆陆续续发些open position给你，感兴趣的话就自己apply。随手投了几个，一个多礼拜后收到sr manager邮件问想不想电面

记录个从后面开始的index，遇到负数和index的那个数交换，index-1，最后reverse从index到末尾的所有数

unicorn2016 发表于 2016-11-18 12:40
他家比较奇葩。13号内推，然后系统会陆陆续续发些open position给你，感兴趣的话就自己apply。随手投了几 ...

好的，你是10月13号内推的吗？内推的是yahoo的new grad吗？
现在的这个电面不是你最初投的那个职位吗？ 我昨天也收到yahoo系统发过来的一些open job position, 说和我match, 看到是senior的,再犹豫要不要投

aangel 发表于 2016-11-18 14:50
好的，你是10月13号内推的吗？内推的是yahoo的new grad吗？
现在的这个电面不是你最初投的那个职位吗？  ...

10.13。面的不是最初投的

你这个是什么时候二面的，是AD组吗？

喵灿灿 发表于 2016-11-19 03:40
你这个是什么时候二面的，是AD组吗？

昨天 yahoo search组

我不知道是不是严格的要求你one-pass，我的想法是两个指针从头开始，遇到正数就继续。然后遇到负数，i就指向当前负数，j就往前挪，知道第一个正数。然后j和i交换，i++,再交换，直到i和j相等，再一起往前。

我去google了一下 发现好像大家提的算法很少有one pass + O(1) space的 有一个是说 从array的最左边开始 遇到负数就记录连续区间 然后接着往右走 遇到正数 也记录连续区间 然后区间翻转 里面的元素顺序不变。 但好像被证明这个算法worst case是 n^2 感觉这个hint把难度加剧了好多