一亩三分地论坛

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

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

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

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

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

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

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

x
90min 3道coding 4道单选,真心被虐了。。。-google 1point3acres

Q1: 原题见图。其实就一个包含0和1的array, 需要把1放到一边 0放到一边,只能邻接element交换 求最小steps。
e.g. 011001 -> 4 (011001 -> 010101 -> 001101 -> 001011 -> 000111). 1point3acres.com/bbs
当时没做出来,后来想想,因为不确定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. from: 1point3acres.com/bbs

选择题有一道是 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:00:21 | 显示全部楼层
q3你们居然都看懂了。。。我想了半天根本没看懂题。。。
q1 q2test case倒是都过了
回复 支持 反对

使用道具 举报

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

使用道具 举报

woshiduga 发表于 2016-11-20 00:52:27 | 显示全部楼层
这个距离题目楼主做出来了么,
可以这么个思路吗,
求出所有的1或者0的下标的和,然后放到左边或者右边,分别求出他们的差值,然后取两者最小值,遍历一次即可。
不知道对不对啊 楼主. Waral 鍗氬鏈夋洿澶氭枃绔,
int sum = 0;
int count = 0;
for(int i = 0; i < length; i++){
    if(a == 1){
      sum+= i;//记录下标的和
      count++;
    }. 鍥磋鎴戜滑@1point 3 acres
}
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):. visit 1point3acres.com for more.
res Math.min(sum - dis1, dis2 - sum)
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 11:00

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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