一亩三分地论坛

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

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

Twitter Online Test

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

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

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

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

x
Twitter online test 题目两道 一个小时,题目很简单,代码一道题就是10行吧,感觉像是数学题。1.. 鍥磋鎴戜滑@1point 3 acres

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
  A[3] = 8
  A[4] = 16
  A[5] = 17
Write a function:. 1point3acres.com/bbs
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.. 1point3acres.com/bbs
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.

Write a function:
. visit 1point3acres.com for more.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).
Assume that:.鏈枃鍘熷垱鑷1point3acres璁哄潧
N is an integer within the range [0..1,000,000];.1point3acres缃
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 | 显示全部楼层
这两道题确实相当easy啊。。。
回复 支持 反对

使用道具 举报

lhn9021 发表于 2014-2-16 13:33:07 | 显示全部楼层
第一题 原数/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么?
回复 支持 反对

使用道具 举报

 楼主| 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)空间
第二题 扫 ...

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

使用道具 举报

bradyfang 发表于 2014-3-6 03:13:03 | 显示全部楼层
lhn9021 发表于 2014-2-16 13:33 . From 1point 3acres bbs
第一题 原数/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, 2016-12-4 01:39

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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