一亩三分地论坛

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

一亩三分地官方iOS手机应用下载
查看: 1246|回复: 7
收起左侧

Twitter Online Test

[复制链接] |试试Instant~ |关注本帖
sumingche 发表于 2014-2-16 11:32:08 | 显示全部楼层 |阅读模式

2014(1-3月) 码农类 硕士 全职@twitter - 内推 - 在线笔试 |Other

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

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

x
Twitter online test 题目两道 一个小时,题目很简单,代码一道题就是10行吧,感觉像是数学题。1.
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
A positive integer N is given. The goal is to construct the shortest possible sequence of integers ending with N, using the following rules:
the first element of the sequence is 1; more specifically: A[0] = 1,
each of the following elements is generated by multiplying the previous element by 2 or increasing it by 1; more precisely: A[i] = A[i−1] * 2 or A[i] = A[i−1] + 1, for i ≥ 1.
For example, for N = 17, the shortest sequence is:
  A[0] = 1
  A[1] = 2
  A[2] = 4.1point3acres缃
  A[3] = 8. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  A[4] = 16
  A[5] = 17
Write a function:
class Solution { public int solution(int N); }
that, given a positive integer N, returns the length of the shortest possible sequence of integers satisfying the above conditions and ending with N.
For example, given N = 17, the function should return 6, as explained above. 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
Assume that: 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
N is an integer within the range [1..2,147,483,647].
Complexity:
expected worst-case time complexity is O(log(N));. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
expected worst-case space complexity is O(1).


2.. From 1point 3acres bbs

Write a function:
class Solution { public int solution(int[] A); }
that, given an array A consisting of N integers, returns the number of pairs (P, Q) such that 0 ≤ P < Q < N and (A[P] + A[Q]) is even. The function should return −1 if the number of such pairs exceeds 1,000,000,000.
For example, given array A such that:
A[0] = 2, A[1] = 1, A[2] = 5, A[3] = −6, A[4] = 9
the function should return 4, because there are four pairs that fulfill the above condition, namely (0,3), (1,2), (1,4), (2,4).. Waral 鍗氬鏈夋洿澶氭枃绔,
Assume that:
N is an integer within the range [0..1,000,000];
each element of array A is an integer within the range [−2,147,483,648..2,147,483,647].
Complexity:
expected worst-case time complexity is O(N);
expected worst-case space complexity is O(1), beyond input storage (not counting the storage required for input arguments).
Elements of input arrays can be modified.

评分

5

查看全部评分

cqx83 发表于 2014-2-16 12:37:44 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
这两道题确实相当easy啊。。。
回复 支持 反对

使用道具 举报

lhn9021 发表于 2014-2-16 13:33:07 | 显示全部楼层
关注一亩三分地微博:
Warald
第一题 原数/2 如果结果不为1 result+1 如果有余数 result+1 最后result+1 O(logn)时间 O(1)空间
第二题 扫描的时候记录奇数偶数的个数 如果遇到奇数 result+奇数的个数 更新奇数的个数 如果遇到偶数 result+偶数的个数 更新偶数的个数  O(N)时间 O(1)空间
回复 支持 反对

使用道具 举报

 楼主| sumingche 发表于 2014-2-17 05:13:33 | 显示全部楼层
回复 支持 反对

使用道具 举报

hmsun77 发表于 2014-3-4 08:42:45 | 显示全部楼层
感谢楼主分享!楼主电面都面的啥呢?也是正常算法题coding么?
求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 反对

使用道具 举报

 楼主| sumingche 发表于 2014-3-4 08:59:52 | 显示全部楼层
hmsun77 发表于 2014-3-3 19:42 . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
感谢楼主分享!楼主电面都面的啥呢?也是正常算法题coding么?
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
对啊 正常算法题
回复 支持 反对

使用道具 举报

bradyfang 发表于 2014-3-5 22:47:34 | 显示全部楼层
lhn9021 发表于 2014-2-16 13:33 . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
第一题 原数/2 如果结果不为1 result+1 如果有余数 result+1 最后result+1 O(logn)时间 O(1)空间. more info on 1point3acres.com
第二题 扫 ...

没有看懂第一题的解题思路,能用N=15演绎一下吗?
回复 支持 反对

使用道具 举报

bradyfang 发表于 2014-3-6 03:13:03 | 显示全部楼层
lhn9021 发表于 2014-2-16 13:33
第一题 原数/2 如果结果不为1 result+1 如果有余数 result+1 最后result+1 O(logn)时间 O(1)空间
第二题 扫 ...

晕,把第一题看复杂了!其实也是判断奇偶的一道简单小题。
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
int shortestSequence(int n) {
        int res = 0;
        while (n) {
                if (n & 1) --n;
                else n >>= 1;
                ++res;
        }
        return res;
}
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2017-4-25 06:36

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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