找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 10224|回复: 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.题目是这样的:
& U% e' R) e9 t4 kinput:3 t# T- s7 _, z! T! J$ M1 B
quintiles的个数,比如2就是求中位数,3就是把数组分成3等分的那两个数的值。
- ~; D* D+ t+ k& F& k数值是用Pair给出的,(value count)值和个数的Pair, 比如(1, 3)表示数组中有3个1.+ X% \! m7 Z/ Q# [
Pair的顺序不是sorted.* p$ H) _+ W$ f6 r, q
还有就是Pair的个数。
$ M" E) y/ b* \. _题目的示例:
' @; r9 r$ C9 g9 ^8 ]+ k3 三等分
& s/ [2 T7 @* ]% s0 t  \3 三个Pair4 p5 _, ?+ k3 S2 m7 x3 M! s8 u# z" u
7 2 数组中有2个7! N9 N9 w* o3 o: x/ y
6 2 数组中有2个67 l, N7 f' @' }! n( y2 Z: r5 B" V  R
5 2 数组中有2个5" I+ Z3 F! m" }' d
$ _. l# e4 v# ^/ h9 c
9 k0 V: C' I1 {3 ]# a8 P3 o
输出应该是:8 K: u; X/ F& s4 u! r
5: X* g% c3 `9 N8 g- i' j4 i* N) u1 E
6
6 i' ~" l/ H& l. P, r8 m8 D整个数组是5,5,6,6,7,7, Index 从1到6, 第一个quintile是6*1/3=2, 第二个是6*2/3=4,所以是5和6.+ A* q3 k  P3 J+ k* o* Q. |
我用的Java,定义了一个Pair class来store所有的Pair数据,这个类实现了comparable接口,这样可以直接用Arrays.sort来排序。) c* `4 T; o/ p+ g
第一步当然是读取所有的input, pair 放到一个数组内。
  }# b7 n2 ?" Y' l. h9 T9 C第二步用Array.sort对所有的Pair排序,value小的在前。6 o+ ?1 U# h6 ^" a
第三步计算所有的quintiles的index, k-th quintiles的index是N*k/Q. (N是数组长度,在第一步时对所有Pair中count求和就是了),Q是quintiles的个数。Note:公式内的k是从1开始的,如果用数组记得调整。. B4 s! w$ j2 V  e$ p/ X, V
第四步就是根据上一步的index来求其对应的value了,因为我们在第二步已经对Pair排序过了,就一个一个加吧:$ r" b* P' L  E& p# x& Q8 `
以例子来说:8 b6 e! C! c2 f! b. |" |: w
5 2) m/ F, y  a) p
6 27 F1 k9 f; C/ h1 M6 q
7 2
' z3 Y( @0 u/ `' [9 w" j; G( d求index为2, 4的value,很容易看到2和2之前的element都是5, 4(2+2)和4之前的element都是6, 6(2+2+2)和6之前的都是7.
8 d' J7 Z7 }, L2 ]0 k: A+ m7 K% a# u5 v7 J( T) M5 y2 {
一共时间是50分钟,用了25分钟来写代码,剩下的时间在debug.最后一步的index还真不容易弄清楚。还差2分钟搞定,通过所有test cases.8 n' X* [4 B  s: h" `( |
Advice:
  P$ m9 L5 b8 j# K% g% Y5 ^先用用hackerrank,至少在上面做几道题,熟悉STDIN,STDOUT.. L! _. `& \) S# y$ o5 l! D( k+ u" ^* n* e
使用java的话了解一下toString和Arrays.toString,对debug很有帮助。7 n; k* ^/ _  G

) |1 _! B$ G9 F# ]祝大家offer多多。8 z/ T, {0 ?3 H* L; I4 l2 S

8 a8 {) c+ E9 W

13

主题

4

精华

213

积分

高级会员

Rank: 3Rank: 3

积分
213
发表于 3-25-2015 04:32 PM | 显示全部楼层
本帖最后由 Sophia 于 5-19-2015 12:28 PM 编辑
8 L" m4 e) f% F* b$ T5 V8 I$ T  Z3 t9 j" C, P
给LZ赞一个。。。
回复 支持 反对

使用道具 举报

0

主题

0

精华

301

积分

高级会员

Rank: 3Rank: 3

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

使用道具 举报

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

本版积分规则

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