传说中的谷歌招聘委员会成员之一,从幕后走出来,教你学系统设计!


一亩三分地论坛

 找回密码
 获取更多干活,快来注册
天天打游戏、照样领工资、还办H1B
这份工作你要不要?
把贵司招聘信息放这里
查看: 2288|回复: 6
收起左侧

[找工就业] 小众公司Visa OA 求大神指点第一题解法

[复制链接] |试试Instant~ |关注本帖
luochenhuan 发表于 2016-10-31 10:07:09 | 显示全部楼层 |阅读模式

2017(10-12月)-[14]CS硕士+<3个月短暂实习/全职 - 校园招聘会| 码农类全职@Visafresh grad应届毕业生

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

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

x
90min 3道coding 4道单选,真心被虐了。。。. visit 1point3acres.com for more.

Q1: 原题见图。其实就一个包含0和1的array, 需要把1放到一边 0放到一边,只能邻接element交换 求最小steps。
e.g. 011001 -> 4 (011001 -> 010101 -> 001101 -> 001011 -> 000111)
当时没做出来,后来想想,因为不确定0和1各放在哪边解最优,
就先0放左,two pointer,左边指向第一个非0的,右边指向第一个非1的,然后算距离,swap;直到指针相遇;
再把1放左,重复算法;
最后取2个的最小值

不知道有没有更好的解法。
FullSizeRender-min (1).jpg


Q2: http://stackoverflow.com/questio ... -they-are-all-equal
不造为啥好多test case没过也是醉了。。。

Q3: 本质求一个数的derangement count,然而不知道为啥只过了2个test case,用的recursion+memorization

选择题有一道是 use circular linked list to implement queue, min pointers for deque and enque. 然而我并不造怎么用 circular linked list to implement queue。。。


评分

1

查看全部评分

zfrancica 发表于 2016-11-15 16:02:43 | 显示全部楼层
顺带问下lz收到后续了吗0 0
回复 支持 0 反对 1

使用道具 举报

zfrancica 发表于 2016-11-15 16:00:21 | 显示全部楼层
q3你们居然都看懂了。。。我想了半天根本没看懂题。。。
q1 q2test case倒是都过了
回复 支持 反对

使用道具 举报

woshiduga 发表于 2016-11-20 00:52:27 | 显示全部楼层
这个距离题目楼主做出来了么,
可以这么个思路吗,
求出所有的1或者0的下标的和,然后放到左边或者右边,分别求出他们的差值,然后取两者最小值,遍历一次即可。
不知道对不对啊 楼主-google 1point3acres
int sum = 0; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
int count = 0;.1point3acres缃
for(int i = 0; i < length; i++){. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
    if(a == 1){. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
      sum+= i;//记录下标的和
      count++;
    }
}
int dis1 = (length + length - count + 1)*count/2//都放到右边
int dis2 = (count - 1 + 0)*count/2;
int res = Math.min(dis1, dis2);
return res

补充内容 (2016-11-20 00:54):
res Math.min(sum - dis1, dis2 - sum)
回复 支持 反对

使用道具 举报

spiritrhy 发表于 2017-2-2 18:01:05 | 显示全部楼层
请问lz有拿到onsite吗
回复 支持 反对

使用道具 举报

Love--my-life 发表于 2017-7-25 09:10:51 | 显示全部楼层
请问楼主OA之前有电面吗?能否透露下面经呢?多谢多谢了!
回复 支持 反对

使用道具 举报

hzlzu4213 发表于 2017-7-25 21:39:27 | 显示全部楼层
楼主最后一个题 自己去看一下LRU. 就是用一个 double linkedlist去implement。 思路不好想但是代码很好写。
1和0 分类有点像 sort color或者说是把非0 放到左边 two pointer也有这个题
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-9-25 12:40

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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