找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 9191|回复: 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.题目是这样的:  U8 f, l" E5 y
input:
/ m. C2 T& O" _5 p( Mquintiles的个数,比如2就是求中位数,3就是把数组分成3等分的那两个数的值。
) r+ T1 x: J3 e2 v# }0 z数值是用Pair给出的,(value count)值和个数的Pair, 比如(1, 3)表示数组中有3个1./ U) O  E  R2 a: X5 u2 a, H# _
Pair的顺序不是sorted.
( k6 W8 s7 i: }* y; B& f& g还有就是Pair的个数。. q: [) ~( ]  g/ P- F0 ~7 ~2 ]
题目的示例:
$ \2 a( R' e: b# f3 三等分5 Q( J& X4 l0 e4 h
3 三个Pair
# z0 Y7 ^4 c8 d4 f( @7 2 数组中有2个7
: u1 j+ H* b- N! T2 _: G$ \6 2 数组中有2个64 I" D% S: `& f  l
5 2 数组中有2个5
  V) o( [6 r8 \% s( q2 J0 {% d4 x1 k4 R( B
7 U7 m+ L. `" Q
输出应该是:
0 s# }# m  S/ ]8 N5# U5 _! m& `( @  P3 N
6( v1 {; [( S! W+ q
整个数组是5,5,6,6,7,7, Index 从1到6, 第一个quintile是6*1/3=2, 第二个是6*2/3=4,所以是5和6.* C0 I6 U; v. s, d; R. H
我用的Java,定义了一个Pair class来store所有的Pair数据,这个类实现了comparable接口,这样可以直接用Arrays.sort来排序。. A  s& s( r* u* {$ |( e9 b& _
第一步当然是读取所有的input, pair 放到一个数组内。% s* S8 Y* _7 G/ D: n$ M& ]
第二步用Array.sort对所有的Pair排序,value小的在前。
! v& @1 ^" ?  K第三步计算所有的quintiles的index, k-th quintiles的index是N*k/Q. (N是数组长度,在第一步时对所有Pair中count求和就是了),Q是quintiles的个数。Note:公式内的k是从1开始的,如果用数组记得调整。
1 Y% Y" Q. N2 v& _4 g第四步就是根据上一步的index来求其对应的value了,因为我们在第二步已经对Pair排序过了,就一个一个加吧:
/ w/ p( o+ b4 a以例子来说:
* t  z- R+ e4 X' ^* E# }, [- U2 S- J5 2
, M% f4 ^0 W' T/ R  D' V& }) K6 2% x' }2 W. d1 e6 s8 z+ S- @9 l
7 2
. h6 V- v" g9 e5 f/ e  }求index为2, 4的value,很容易看到2和2之前的element都是5, 4(2+2)和4之前的element都是6, 6(2+2+2)和6之前的都是7.5 [. V5 f1 Q7 p/ [
* ~5 j5 m! @% w8 S2 U  d5 S7 E& I
一共时间是50分钟,用了25分钟来写代码,剩下的时间在debug.最后一步的index还真不容易弄清楚。还差2分钟搞定,通过所有test cases.
) Q8 {1 ]" s# s' rAdvice:
3 Y3 q1 \% k( Y3 ?8 ^4 T! G先用用hackerrank,至少在上面做几道题,熟悉STDIN,STDOUT.
% N) G' r0 I8 Z使用java的话了解一下toString和Arrays.toString,对debug很有帮助。+ u6 [4 G; h: l4 Z; w$ T
) f+ `/ D* ]" g/ k7 P# j
祝大家offer多多。
( ]6 h* e" n$ d$ Z7 S4 L( Z
1 @8 I* P( {# Y, R% n  k

13

主题

4

精华

213

积分

高级会员

Rank: 3Rank: 3

积分
213
发表于 3-25-2015 04:32 PM | 显示全部楼层
本帖最后由 Sophia 于 5-19-2015 12:28 PM 编辑
5 E6 M# [  z- ^+ Z. Z4 W
9 z9 e0 x2 G7 v  @. ~给LZ赞一个。。。
回复 支持 反对

使用道具 举报

0

主题

0

精华

301

积分

高级会员

Rank: 3Rank: 3

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

使用道具 举报

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

本版积分规则

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