找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 10022|回复: 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.题目是这样的:! L) A+ I# e( s& R& ~5 X
input:
5 X* \7 U2 ]* E+ X: equintiles的个数,比如2就是求中位数,3就是把数组分成3等分的那两个数的值。
+ }+ \& l4 Q! M+ l$ ]) k  G数值是用Pair给出的,(value count)值和个数的Pair, 比如(1, 3)表示数组中有3个1.8 {1 a) G9 A9 G2 r+ z
Pair的顺序不是sorted., T% ]; `7 g0 y7 G2 h" X
还有就是Pair的个数。
: _$ y& P  M6 `1 \; \题目的示例:
; r% g- O6 q# e3 K5 i3 三等分
/ g* z0 d/ r) O. g. q( @$ t) w3 三个Pair
# i+ J6 U9 W- i7 t$ }7 2 数组中有2个78 K' p, u/ ?/ }# W) [0 T0 `
6 2 数组中有2个6  `2 i* a. r; h! e7 a0 x* L
5 2 数组中有2个5
5 k* b6 n, m! \$ Y' q$ L' n
! C) z$ T" Q/ v0 u/ x8 _
; ]- H7 @6 q, w! j, f2 m输出应该是:2 F" I+ s8 m" t5 n) ^
5
; k+ g0 H* p$ B' x2 m; c64 r' c& z/ I3 X5 d4 K
整个数组是5,5,6,6,7,7, Index 从1到6, 第一个quintile是6*1/3=2, 第二个是6*2/3=4,所以是5和6./ g& ]% s3 M9 x
我用的Java,定义了一个Pair class来store所有的Pair数据,这个类实现了comparable接口,这样可以直接用Arrays.sort来排序。
; T1 u/ u* R6 x) {0 {8 r) E2 d  m" \+ x& O第一步当然是读取所有的input, pair 放到一个数组内。7 S4 f. Q, F- I* B# X# b
第二步用Array.sort对所有的Pair排序,value小的在前。
& Y7 E. D5 n7 q, n6 B+ V4 c第三步计算所有的quintiles的index, k-th quintiles的index是N*k/Q. (N是数组长度,在第一步时对所有Pair中count求和就是了),Q是quintiles的个数。Note:公式内的k是从1开始的,如果用数组记得调整。' J7 [! K% S+ {7 r2 \+ z+ p
第四步就是根据上一步的index来求其对应的value了,因为我们在第二步已经对Pair排序过了,就一个一个加吧:0 l5 f' [5 I' [9 E: E
以例子来说:7 ?6 n1 b6 \* o: r. I
5 2
1 V6 J2 F8 e# d+ X6 2
5 U3 [9 f1 t( y6 c. k7 2
8 n7 ~; z# m* U% m9 m& ?) E  U! b+ t求index为2, 4的value,很容易看到2和2之前的element都是5, 4(2+2)和4之前的element都是6, 6(2+2+2)和6之前的都是7.) U+ o; b; i. |

) i: d( Q- _; [一共时间是50分钟,用了25分钟来写代码,剩下的时间在debug.最后一步的index还真不容易弄清楚。还差2分钟搞定,通过所有test cases.- z$ J$ |+ B) x/ c: R2 u
Advice:
5 I. H1 B3 I3 B& Z; m! o6 D先用用hackerrank,至少在上面做几道题,熟悉STDIN,STDOUT.
4 h+ t9 I5 q% r/ R3 X, ^/ q1 w使用java的话了解一下toString和Arrays.toString,对debug很有帮助。: e$ Z$ h+ N: G5 K* q, {

$ r$ k  m. v* U# J8 Y祝大家offer多多。
9 y  }/ X# p5 }/ h# J! ?/ o5 l
2 `  Y. O4 }: U# B' o

13

主题

4

精华

213

积分

高级会员

Rank: 3Rank: 3

积分
213
发表于 3-25-2015 04:32 PM | 显示全部楼层
本帖最后由 Sophia 于 5-19-2015 12:28 PM 编辑 1 {  h, G0 V0 M7 {, N
/ l( ^, A% D: V9 s3 ~
给LZ赞一个。。。
回复 支持 反对

使用道具 举报

0

主题

0

精华

301

积分

高级会员

Rank: 3Rank: 3

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

使用道具 举报

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

本版积分规则

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