10月28,K神开课讲数据科学,你来吗?


一亩三分地论坛

 找回密码
 获取更多干活,快来注册
Babeltime游戏工作室招工程师、美术和策划
Tubi TV招安卓、前端和机器学习工程师
把贵司招聘信息放这里
查看: 2464|回复: 15
收起左侧

Yahoo两次电面

[复制链接] |试试Instant~ |关注本帖
unicorn2016 发表于 2016-11-18 10:24:10 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 硕士 全职@Yahoo - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
据说yahoo经常跳过hr,直接senior manager一个邮件发过来说要聊聊,是yahoo search team。这一聊一个小时,暂且算做第一轮电面。
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
一面:印度阿姨,因为实在是工作了好多年,人很nice。聊她聊我聊简历,就得有25分钟。然后是好多java概念问题。abstract class vs. interface,thread vs. process,lockarraylist vs. linkedlist,static,final,lock。还好有所准备,阿姨还算满意。于是有了第二次电面。

二面:和一面隔两星期。印度哥哥,迟到35分钟。直接贴题目。

Input Array {3, -10, -2, -5, 10, 4, 5, -1, 10, 2, -4} Output Array {3, 10, 4, 5, 10, 2, -10, -2, -5, -1 , -4 }.
Order is maintained and –ve numbers are sent to rightmost in order. (Write a pseudo code to do it in single iteration and in-place.)
.鐣欏璁哄潧-涓浜-涓夊垎鍦
写了一通没做出来,说可不可以给个小hint呀,小哥说single iteration和in-place就是hint。囧 就是因为您这俩hint我才不会做啊。已跪没得说,求地里大神指点solution。

aangel 发表于 2016-11-18 10:51:07 | 显示全部楼层
多谢楼主分享,请问你内推后多久收到电面啊?
回复 支持 反对

使用道具 举报

 楼主| unicorn2016 发表于 2016-11-18 12:40:28 | 显示全部楼层
aangel 发表于 2016-11-18 10:51
多谢楼主分享,请问你内推后多久收到电面啊?

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

使用道具 举报

johnjavabean 发表于 2016-11-18 13:42:41 | 显示全部楼层
记录个从后面开始的index,遇到负数和index的那个数交换,index-1,最后reverse从index到末尾的所有数
回复 支持 反对

使用道具 举报

aangel 发表于 2016-11-18 14:50:11 | 显示全部楼层
unicorn2016 发表于 2016-11-18 12:40
他家比较奇葩。13号内推,然后系统会陆陆续续发些open position给你,感兴趣的话就自己apply。随手投了几 ...
.鐣欏璁哄潧-涓浜-涓夊垎鍦
好的,你是10月13号内推的吗?内推的是yahoo的new grad吗?
现在的这个电面不是你最初投的那个职位吗? 我昨天也收到yahoo系统发过来的一些open job position, 说和我match, 看到是senior的,再犹豫要不要投
回复 支持 反对

使用道具 举报

 楼主| unicorn2016 发表于 2016-11-19 03:00:31 | 显示全部楼层
aangel 发表于 2016-11-18 14:50
好的,你是10月13号内推的吗?内推的是yahoo的new grad吗?
现在的这个电面不是你最初投的那个职位吗?  ...

10.13。面的不是最初投的
回复 支持 反对

使用道具 举报

喵灿灿 发表于 2016-11-19 03:40:56 | 显示全部楼层
你这个是什么时候二面的,是AD组吗?
回复 支持 反对

使用道具 举报

 楼主| unicorn2016 发表于 2016-11-19 13:02:07 | 显示全部楼层
喵灿灿 发表于 2016-11-19 03:40. 1point 3acres 璁哄潧
你这个是什么时候二面的,是AD组吗?
.1point3acres缃
昨天 yahoo search组
回复 支持 反对

使用道具 举报

类与对象tju 发表于 2016-11-20 02:37:33 | 显示全部楼层
我不知道是不是严格的要求你one-pass,我的想法是两个指针从头开始,遇到正数就继续。然后遇到负数,i就指向当前负数,j就往前挪,知道第一个正数。然后j和i交换,i++,再交换,直到i和j相等,再一起往前。
回复 支持 反对

使用道具 举报

axlwu 发表于 2016-11-20 15:50:36 | 显示全部楼层
我去google了一下 发现好像大家提的算法很少有one pass + O(1) space的 有一个是说 从array的最左边开始 遇到负数就记录连续区间 然后接着往右走 遇到正数 也记录连续区间 然后区间翻转 里面的元素顺序不变。 但好像被证明这个算法worst case是 n^2 感觉这个hint把难度加剧了好多
回复 支持 反对

使用道具 举报

喵灿灿 发表于 2016-11-20 15:54:02 | 显示全部楼层
axlwu 发表于 2016-11-20 15:50
我去google了一下 发现好像大家提的算法很少有one pass + O(1) space的 有一个是说 从array的最左边开始 遇 ...
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
这个算法好像 是nlogn的
回复 支持 反对

使用道具 举报

aangel 发表于 2016-11-22 02:41:52 | 显示全部楼层
axlwu 发表于 2016-11-20 15:50
我去google了一下 发现好像大家提的算法很少有one pass + O(1) space的 有一个是说 从array的最左边开始 遇 ...

按照题目的要求的话,用冒泡排序(类似)就好了,先从头往右边找到第一段连续负数区间,然后让负数一个一个通过交换沉下去,直到碰到下一个负数,接着继续同样的操作在下一段更大的负数区间
回复 支持 反对

使用道具 举报

hbybaby 发表于 2016-12-8 06:13:46 | 显示全部楼层
求问楼主后来有消息了吗?
回复 支持 反对

使用道具 举报

pkugoodspeed 发表于 2017-1-20 11:23:41 | 显示全部楼层
johnjavabean 发表于 2016-11-18 13:42
记录个从后面开始的index,遇到负数和index的那个数交换,index-1,最后reverse从index到末尾的所有数

这是错的吧,正数没法保证顺序,1,2,-4,4,5,-3
结果是1,2,5,4,-4,-5
回复 支持 反对

使用道具 举报

yuhaoz3 发表于 2017-1-22 06:10:19 | 显示全部楼层
我觉得要求既然是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;         nums = nums[j];         nums[j] = t;     } }  我的指针j就是唯一的一次pass, i 实际上是没有iterate的,只用来记录而已。

补充内容 (2017-1-22 06:10):
格式不对,见下一楼
回复 支持 反对

使用道具 举报

yuhaoz3 发表于 2017-1-22 06:10:33 | 显示全部楼层
格式不对 重发一下
我觉得要求既然是inorder inplace onepass,那么复杂度肯定不是O(n),而且题目也没要求复杂度O(n)。代码贴上了,没有完整的test,但是至少能pass楼主给的input


public class ArraySplitBySign {.鏈枃鍘熷垱鑷1point3acres璁哄潧
    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};. from: 1point3acres.com/bbs
        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++;.1point3acres缃
            }
            if (i == -1) i = j;
            while (j < len && nums[j] < 0) {
. more info on 1point3acres.com                j++;
            }
            int end = j - 1;
            while (j < len && nums[j] > 0) {
                j++;
            }
            if (i != -1) {
                int times = j - end - 1;.1point3acres缃
                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);
        }
    }. 1point3acres.com/bbs

    private static void swap(int[] nums, int i, int j) {
        int t = nums[i];. 1point3acres.com/bbs
        nums[i] = nums[j];. 1point3acres.com/bbs
        nums[j] = t;
    }
}. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

我的指针j就是唯一的一次pass, i 实际上是没有iterate的,只用来记录而已。
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-9-20 22:59

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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