一亩三分地论坛

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

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

[找工就业] akuna capital oa(选择题有两个新的,附我的解答)

[复制链接] |试试Instant~ |关注本帖
guoyixuan118 发表于 2016-2-25 04:37:29 | 显示全部楼层 |阅读模式

2016(7-9月)-[15]BME硕士+3个月-1年 - 网上海投| 码农类实习@akuna capital其他

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

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

x
昨天做了akuna capital家的OA, 网上海投,过了大概一礼拜给的OA链接,题目95%一模一样。因为听说这家公司挺小bar高,所以其实没抱太大希望,看了地里的OA心里有个底就直接点链接做题了。. 1point 3acres 璁哄潧
选择题基本一样,有两题稍微有变形 (顺序有点打乱了,我想起哪个就先写哪个的):. 1point 3acres 璁哄潧

鏉ユ簮涓浜.涓夊垎鍦拌鍧.
1. CAPITAL多少组合让元音在一起:
    720
2. 是个看图找规律题目,六幅图分别是 上6点下2点,上2点下5点,上4点下1点,上1点下3点,上2点下0点,上0点下1点,让你选择下一幅图片:
    地里大神给的解答:上下差值 4,-3,3,-2,2,-1, 。。。 所以选择的图片应该相差1, 我是选A
3. 比较 hash, binary 和 linkedlist 的平均查询速度(一个超大的数据集), 我认为是linkedlist  O(n/2)> binary tree O(log(n))> hash O(1),
4. 读程序写结果(有变形):. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
    def traverse(seq_len):
    idx = 1
    traversed = []

    while len(traversed) < seq_len:. more info on 1point3acres.com
        traversed.append(idx)
        traversed.append(2*len(traversed) + 1)
        idx += 2. Waral 鍗氬鏈夋洿澶氭枃绔,
        if idx > seq_len:
            idx -= seq_len. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴


    sum = 0
    for idx in traversed:   
        i = traversed.pop()
        sum += (i * idx)

    print(sum)

-google 1point3acrestraverse(7)

我没算错的话应该是104,


5. 给了一段递归程序,问干嘛了: A. find the max number in an array without changing the array
   程序大致是这样:  
int function(array, size){. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
    if(function(array, size-1) > array[size-1]){
        return function(array,size-1);
    }
    else{
        return array[size];
    }
}.鐣欏璁哄潧-涓浜-涓夊垎鍦

.1point3acres缃
6. (新题) 用cycle linked list 实现的queue 完成插入和删除,最少需要多少个指针:
    我觉得是一个,只需要指向queue的尾就可以了,尾->next = 头,从而可以找到头。
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

7. (新题)while loop 求complexity : log(N)
     if(i < N ) {i * = 2; }. from: 1point3acres.com/bbs


************************************************************编程***************************************************************


8. largest product of two numbers, 小一点的数必须在大一点的数前面,如6,4,5=> 20
这个我最后做的,没时间优化时间了,大神说用divide and conqure 可以nlog(n), 我用n2的最后一个case超时了 。。


9. 求两个string的common substr, 然后按字母顺序输出来(string里只会出现字母不会有特殊符号):
我用两个map<char, int>存s1, s2 各自的字母以及其出现次数,
然后a-zA-Z 52个字母依次循环一遍,找两个map的公共子序列,依次添加到结果字符串中

.1point3acres缃
10. counting bits.
我就是很简单的 input%2, 再 /2, 循环直到input == 0.鐣欏璁哄潧-涓浜-涓夊垎鍦

. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
11. 类似于2sum, 找两个数,各乘100后等于target, 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
先判断(target%100)不等于零直接返回false,. Waral 鍗氬鏈夋洿澶氭枃绔,
target /= 100
然后跟2sum一样



12. 删除序列中的重复出现的整数,最后倒序输出整数: 我是用map做的
. more info on 1point3acres.com









补充内容 (2016-2-25 10:36):
第八题是O(N), 感谢分享思路:维护一个suffix数组,第i个元素是原数组从i + 1到末尾的最大值。这样就是O(n)

评分

2

查看全部评分

xiaozhuxiaozhu 发表于 2016-2-25 04:57:24 | 显示全部楼层
大神说第8题 是nlog(n)?

我写的o(n)的。那我是上帝么。。

你那2题 不是新的,我的oa里面有。
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-2-25 05:04:27 | 显示全部楼层
你找规律那题错了。。我记得应该不是a.
是选一个上面为空的,应该是b
回复 支持 反对

使用道具 举报

josephdesire 发表于 2016-2-25 06:17:57 | 显示全部楼层
想问下12题不能任何built in class or function? 如果用hashset hashmap也不行咯?
回复 支持 反对

使用道具 举报

shiloh00 发表于 2016-2-25 06:47:30 | 显示全部楼层
BME硕士 lz和我以前一样!
回复 支持 反对

使用道具 举报

gjxwin 发表于 2016-2-25 07:35:08 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-2-25 04:57
大神说第8题 是nlog(n)?

我写的o(n)的。那我是上帝么。。

确实是O(n)
回复 支持 反对

使用道具 举报

gjxwin 发表于 2016-2-25 07:36:21 | 显示全部楼层
第8题,仔细想想其实不难,维护一个suffix数组,第i个元素是原数组从i + 1到末尾的最大值。这样就是O(n)
回复 支持 反对

使用道具 举报

 楼主| guoyixuan118 发表于 2016-2-25 10:33:18 | 显示全部楼层
shiloh00 发表于 2016-2-25 06:47
BME硕士 lz和我以前一样!
.鏈枃鍘熷垱鑷1point3acres璁哄潧
我是bmi (biomedical informatics),没有这个选项就选了个相似的
回复 支持 反对

使用道具 举报

 楼主| guoyixuan118 发表于 2016-2-25 10:34:23 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-2-25 05:04. 1point 3acres 璁哄潧
你找规律那题错了。。我记得应该不是a.
是选一个上面为空的,应该是b

上面为空的话,怎么差值为1呢?
回复 支持 反对

使用道具 举报

 楼主| guoyixuan118 发表于 2016-2-25 10:36:10 | 显示全部楼层
gjxwin 发表于 2016-2-25 07:36
第8题,仔细想想其实不难,维护一个suffix数组,第i个元素是原数组从i + 1到末尾的最大值。这样就是O(n)
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
原来可以这样,领教了,谢谢哈!
回复 支持 反对

使用道具 举报

Sayings 发表于 2016-3-2 05:34:09 | 显示全部楼层
12 题不能用build in class or function 做的话,应该先倒序sort, 然后再remove duplicate 吧? O(nlogn),想问下大家有更好的解么
回复 支持 反对

使用道具 举报

dajiang 发表于 2016-3-3 09:31:50 | 显示全部楼层
count bit 那个,如果数字是负数 ?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 08:15

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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