找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 9560|回复: 3
收起左侧

[Indeed] Indeed online #4

[复制链接]

1

主题

0

精华

8

积分

新米人

Rank: 1

积分
8
发表于 11-28-2014 05:36 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
感恩节前突然收到indeed的online test通知,做之前适应了一下hackerrank,感觉不错,就是用System.in / out不太习惯,anyway,题目是找一个数组中所有的quintiles.做之前查了一下,知道是和这个有关,还上wiki确认了一下http://en.wikipedia.org/wiki/Quantile.题目是这样的:
6 }4 y2 u6 e7 z; q4 a2 p( T" oinput:
, D, O. o* e: X. mquintiles的个数,比如2就是求中位数,3就是把数组分成3等分的那两个数的值。
, X# s5 Q% ~4 h* t8 i! l数值是用Pair给出的,(value count)值和个数的Pair, 比如(1, 3)表示数组中有3个1.1 R% p1 U7 H1 t/ G9 u; @& _7 x
Pair的顺序不是sorted.
2 w, h6 o3 B3 o4 {, z# }还有就是Pair的个数。! K  `9 \* g# _% C% [
题目的示例:
5 c2 A3 w0 [! ^( h0 u2 k  {5 T3 三等分
" @3 l) a* w" u3 Y1 s0 K3 三个Pair: O' [1 ?# V/ j  b
7 2 数组中有2个7
$ j" e9 I0 L/ \' K0 R/ j2 {* J- v6 2 数组中有2个65 I8 {/ k: c( \: a) W
5 2 数组中有2个5
# @, Z: t4 v* m! I- l2 c
1 C6 S$ C2 Y& z9 A: [% Y& d9 B- D: m
输出应该是:; \2 b  S6 |- M  D2 T+ w; ^
57 N# H( q; N3 A1 e( b3 `( T
6) E2 U& B7 K/ Z- A
整个数组是5,5,6,6,7,7, Index 从1到6, 第一个quintile是6*1/3=2, 第二个是6*2/3=4,所以是5和6.' Q: b. o1 J' f: v# X
我用的Java,定义了一个Pair class来store所有的Pair数据,这个类实现了comparable接口,这样可以直接用Arrays.sort来排序。* C( H8 p; V6 t) H6 E
第一步当然是读取所有的input, pair 放到一个数组内。# D3 ?& \/ i/ e2 X& f# P4 S7 {6 |2 O
第二步用Array.sort对所有的Pair排序,value小的在前。2 R  e) j5 _" K1 B* o
第三步计算所有的quintiles的index, k-th quintiles的index是N*k/Q. (N是数组长度,在第一步时对所有Pair中count求和就是了),Q是quintiles的个数。Note:公式内的k是从1开始的,如果用数组记得调整。
5 ^! n# e8 R# z- ^0 {, [' ^3 g第四步就是根据上一步的index来求其对应的value了,因为我们在第二步已经对Pair排序过了,就一个一个加吧:
( {6 Z# \) H; u4 R4 v以例子来说:
4 x5 m* g" F) b& @5 2) B9 V0 M. I2 w/ m( O/ ]
6 2; K4 m: D6 _/ q  H7 ]0 R5 J
7 2, ]/ \7 V+ |) t! E) r+ \
求index为2, 4的value,很容易看到2和2之前的element都是5, 4(2+2)和4之前的element都是6, 6(2+2+2)和6之前的都是7.8 Z( V, p9 T( J$ r, b1 j8 _5 f8 {
9 u  u* o  G9 i! B
一共时间是50分钟,用了25分钟来写代码,剩下的时间在debug.最后一步的index还真不容易弄清楚。还差2分钟搞定,通过所有test cases.
1 I" W. u8 L* V, T* p, a2 _Advice:
3 d1 @) ?. h1 G, L先用用hackerrank,至少在上面做几道题,熟悉STDIN,STDOUT.
* T6 b- o# `" H, G( S使用java的话了解一下toString和Arrays.toString,对debug很有帮助。; o0 J9 p- _- {' {! Y3 @# E/ }
3 B3 V+ W0 i1 M. @* G2 B$ x, e
祝大家offer多多。
" ^1 {. x' \) F! B. r
- J2 m: n/ V. ]8 c5 h7 A

13

主题

4

精华

213

积分

高级会员

Rank: 3Rank: 3

积分
213
发表于 3-25-2015 04:32 PM | 显示全部楼层
本帖最后由 Sophia 于 5-19-2015 12:28 PM 编辑 0 F6 i  |0 e6 c5 V. x

1 U+ ]& K/ p3 j: x给LZ赞一个。。。
回复 支持 反对

使用道具 举报

0

主题

0

精华

301

积分

高级会员

Rank: 3Rank: 3

积分
301
发表于 5-2-2015 01:07 AM | 显示全部楼层
给LZ赞一个   thanks for sharing
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

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