一亩三分地论坛

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

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

twitter面经(原创,本站首发:-)

[复制链接] |试试Instant~ |关注本帖
gooc 发表于 2014-4-12 15:18:17 | 显示全部楼层 |阅读模式

2014(1-3月) 码农类 博士 全职@Twitter - 猎头 - Onsite |Other

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

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

x
首先问一下,如何才能提高自己的阅读权限啊?有些帖子要50权限,一直看不了。新手入门贴貌似只能涨积分

前段时间去T家面试,2个烙印,1个同胞,2个白人,白人问的是design和项目相关。下面是记得的几道coding题目
. 鍥磋鎴戜滑@1point 3 acres1. 给b个盒子,有K种颜色的球,共有N(很大的数)个球。a)如何吧这些球尽量平均的分到盒子里,盒子之间的球数目最多差1.b)如何避免这种情况 -- 多个盒子有相同的颜色配置。 即b1 = (red, blue, green), b2 = (red, blue, green) b3 = (red, blue). 这种分配是不好的,因为b1 和b2的颜色组合相同,求算法避免多个盒子共享一个组合,同时保持尽量平均。

2. partition数组  implement  int partition (int a[], int k) so that all a <= k will be in the left side of the array, and a > k will be on the right side.
And return the position of the first element which is greater than k. Note K might not be in the array.
. more info on 1point3acres.com
3. Implement function call

void schedule(Callable callable, int timeToRun). So that the "callable" will be called in a future time specified by "timeToRun".  the 'schedule' function can be called by multiple thread, multiple times.  Need to chose the right data structure.



评分

2

查看全部评分

zxzczvb 发表于 2014-4-12 15:31:47 | 显示全部楼层
lz面的是哪个组?
回复 支持 反对

使用道具 举报

rhozou 发表于 2014-4-13 01:24:05 | 显示全部楼层
请问lz第三题选择right data structure的思路是怎么样的?thx
回复 支持 反对

使用道具 举报

Linzertorte 发表于 2014-4-13 03:27:11 | 显示全部楼层
回复 支持 反对

使用道具 举报

Linzertorte 发表于 2014-4-13 03:31:04 | 显示全部楼层
Prob 2. is the partition step of quick sort. In "Introduction to algorithms", there is a very nice implementation and a proof that handles corner cases elegantly.
  1. int j=-1,i=0;
  2. for(;;i<n;i++).鐣欏璁哄潧-涓浜-涓夊垎鍦
  3. {
  4.     if(A[i]<=k) swap(A[i],A[++j]);
  5. }-google 1point3acres
  6. return j+1;
复制代码
回复 支持 反对

使用道具 举报

Linzertorte 发表于 2014-4-13 03:32:28 | 显示全部楼层
Prob 2. is the partition step of quick sort. In "Introduction to algorithms", there is a very nice implementation and a proof that handles corner cases elegantly.
  1. int j=-1,i=0;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  2. for(;;i<n;i++)
  3. {
  4.     if(A[i]<=k) swap(A[i],A[++j]);
  5. }
  6. return j+1;
复制代码
回复 支持 反对

使用道具 举报

Linzertorte 发表于 2014-4-13 03:32:45 | 显示全部楼层
Prob 2. is the partition step of quick sort. In "Introduction to algorithms", there is a very nice implementation and a proof that handles corner cases elegantly.
  1. int j=-1,i=0;
  2. for(;;i<n;i++)
  3. {
  4.     if(A[i]<=k) swap(A[i],A[++j]); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  5. }
  6. return j+1;
复制代码
回复 支持 反对

使用道具 举报

walnutti 发表于 2014-4-19 02:09:29 | 显示全部楼层
楼主可以展开讲下第一题和第三题么?多谢。
回复 支持 反对

使用道具 举报

NdrZmansN 发表于 2015-2-13 16:50:56 | 显示全部楼层
不知道楼主现在还会不会经常来这里逛.
第一题有人知道解法么?
谢谢,
回复 支持 反对

使用道具 举报

enicloom 发表于 2015-4-12 02:18:53 | 显示全部楼层
看到这个帖子一直没有人回复 我觉得大家可以讨论一下第一题的解法:

每个箱子最多装(n / b) + 1个球
首先算出m个箱子需要多装一个球的:m = n % b
然后把所有球按照color sort一遍(确实 时间复杂度就上去了)
然后一个箱子一个箱子的装 一个箱子装满再装下一个

不知道是否有人能够有更高效的办法
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 01:08

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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