找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 3129|回复: 5
收起左侧

[Zenefits] Zenefits OA 面经,衣柜

[复制链接]

1

主题

1

精华

32

积分

新米人

Rank: 1

积分
32
发表于 11-21-2015 02:12 AM | 显示全部楼层 |阅读模式

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

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

x
本帖最后由 Sophia 于 11-21-2015 10:40 PM 编辑 & D1 W$ _: W* b7 ?$ p! d9 v& _# [

! M* ]5 v# n, R- h7 V  x刚做了OA 4,第一题全过了,第二题过了4个test cases。第二天接到recruiter的信,说是组里讨论了,还是给据了。第二题其实被lint code给害了。我自己测试了其他OA题,只有这一道,lint code上有OJ,在lint code过了,但其实有bug。说一下题吧,. L7 r6 h2 ~1 q* V$ W: i  R& }
1. There are n ticket windows in the railway station. The ith window has a_i tickets available. The price
7 z; G: h* u3 s% e9 b, b" G   of a ticket is equal to the number of tickets remaining in that window at that time. What is the maximum# W* x) L* |# S6 \' x
   amount of money the railway station can earn form selling the first m tickets
+ R9 A+ Y* r! o, {- [   Input:! `5 d- J+ c' z& Y# z* ]+ D
   n m$ S9 i( n; n$ b7 S3 p
   a_1 a_2 ... a_n: x1 Y+ Q6 e0 r4 Z  i
   Output S
% X; J) \+ m& }5 q' h# ~: A. s9 g" @1 i
   Constraint2 g5 d* |6 r) e: W0 \
   1<=n<=100,000$ m7 h( V6 }* C; x
   1<=a_i<=100,000
" _6 A# v/ _1 U* {9 m0 u- ?. Y' p3 Z   1<=m<=a_1+a_2+...+a_n* }# Z! x  D* {' `- e7 {
! r, Y4 I8 Z: `5 S/ e
   sample input
8 B/ r( T( c3 b   2 4$ \* [7 w: H- x/ T' o0 a
   2 55 o7 ^0 `: h7 B" O' w
   sample output& m9 j, d% U# {  e: O( X% H' h, z
   14
# J1 A+ {$ q; s5 d1 d   Since all 4 tickets can just be sold at 2nd window, 5, 4, 3, 2
/ d  f+ t: t$ q" x2. 基本上是, Given a permutation which may contain repeated characters, find its index in all the permutations of these numbers, which are ordered in lexicographical order. The index begins at 0. Characters are in [a,z] only. Since the result could be very large, modular arithmetic should be used and mod by 10^9+7.
5 f/ z, A  k5 @* s
% `% S1 z+ |1 x6 `, G1 }6 k给个第一题的code,所有test cases passed. 第二题,我的code有bug,就不上了。7 J7 @5 E; y( N3 z; k  I# m9 p
long long sellTicket(string input)9 k" g2 J$ e( @2 }2 N
{4 S+ ]8 }: P8 |  h/ Q
        stringstream ss(input);( ?4 n# Z# H. y6 {
        int n = 0;
; l! @5 ^( z1 t" d8 m9 [        ss >> n;0 B6 z: }# F' S9 V, J$ j
5 N! D3 _! P* i
        if (n < 1) return 0; // Or assert$ q1 ]9 {: y* h, U4 ?

) T4 u& t) F- @        long long m = 0;3 f  h+ ~8 a( G- r0 a
        ss >> m;
5 L: K: a! u" r! W/ N9 b1 I+ L5 L
# I; p+ X9 e# P  |& j) ~# i4 u        if (m < 1) return 0;: G4 \( p. W4 O  G" j# A

6 Q* J8 w, L5 ]+ Q& Y/ g! x2 k        vector<int> a(n, 0);6 x' h0 Z% K& ]: O2 J
        for (int i = 0; i < n; i++)6 Z' F5 X1 c! \
        {
3 i# _! \) C& \/ S                ss >> a【i】;& [" Y0 g+ {" |' h& `5 x3 i# T
        }* L$ o6 @2 G" Y
& ?1 w% U4 ]. a2 p% g. r; x
        // Validate that m <= a_1+a_2+...+a_n9 Q/ D1 y7 k2 P

) O  Z  I% P: _% d3 l# V        // Sort a in descending order O(nlogn)2 `: T$ w: G7 n8 Q* w
        sort(a.begin(), a.end(), greater<int>());! G2 w: \7 @2 z' V5 M

7 Y8 L! }* R* p) e        // use one pointer right such that a_0==a_1==...a_(right-1)
& g5 T/ [! q4 F/ i  A% v+ Q        long long profit = 0;
. R7 V) r/ Q- q2 S$ S6 U  g* i7 W        int right = 1;
) {& ], e( ~7 ~- N- v$ A* J        int numTickets = a[0];
3 h8 n, X9 f. [  O8 H        while (m > 0)" b9 Q1 ]0 e- p' h% p
        {
; i: I  f& P. s" Q' f1 c1 }1 p                // Loop invariant a_i = numTickets, where 0<=i<right * x. a9 d  h4 C. l) N
                while (right < n && numTickets == a[right])$ X3 J" T- j% `  [" S% Q
                        right++;
4 E. n5 C. T* n" E) ~" e. F. s! V, x3 D* L+ F& W) m1 V/ F
                int low = right < n ? a[right] : 0;
; f7 T( Z+ a' B! r4 _. l. a                long long diff = numTickets - low;5 S2 e# H; W" v7 E
  N. L* t3 p0 D) J  A9 U6 A
                if (diff * right <= m)
6 b3 {% V7 Q1 }1 q7 g" b) o# |                {: \- l1 ^  U5 O) n2 N& E. l
                        // From window a_0 to a_(right-1), we can just sell diff number of tickets for each window.$ ]  J9 k! W/ m2 V. d% E/ F
                        profit += right * ((numTickets - low) * (numTickets + low + 1) / 2);    //((diff * low) + diff * (diff + 1) / 2);
8 S7 p' K  N. O, F2 w7 S                        m -= diff * right;
4 q. x  H; P' V8 f                        numTickets = low;
0 e1 o3 g! Q5 m; o                }" x) h5 L4 P8 m) K% n1 y
                else+ |( U$ u# z. S( D5 `5 V
                {; P* k) o: |* ^& o* L
                        diff = m / right;* }* S6 x3 \0 r- |- s2 U5 R
                        low = numTickets - diff;  B& k! J  k% x0 V$ U
                        profit += right * ((numTickets - low) * (numTickets + low + 1) / 2); // ((diff * low) + diff * (diff + 1) / 2);
3 v" j) T1 q6 r: V. e) o* ]                        profit += (m % right) * low;/ D) r% m  v7 }( ^* C
                        m = 0;
7 |* k1 J, y+ c4 h/ t                        break;3 ?, G/ x4 C2 w4 {
                }+ b4 _  U0 t9 d5 q* Y
        }# Y" v  g/ L1 v) h4 r
! @$ d6 d) x' x: @
        return profit;. U& J% H# d# q- K/ N
}
  P4 S! b& I) M( x; Q6 ^1 l' i( Q
, P. n: j3 r; G8 v2 z* x- n3 y  `0 }# d" h% b

评分

参与人数 1金钱 +6 收起 理由
Sophia + 6 感谢您的认真和用心的分享!大米满满送上!

查看全部评分

1

主题

1

精华

32

积分

新米人

Rank: 1

积分
32
 楼主| 发表于 11-21-2015 02:14 AM | 显示全部楼层
本帖最后由 Sophia 于 11-21-2015 10:39 PM 编辑
( k2 M3 o' P4 a. e! K
" ~; n" N% a" X9 O$ m  s* Q3 s是被lint_code给害了。

781

主题

575

精华

5670

积分

顶级版主

Rank: 9Rank: 9Rank: 9

积分
5670

活跃会员热心会员优秀版主

发表于 11-21-2015 10:41 PM | 显示全部楼层
感谢您的认真和用心的分享!大米满满送上!
我们始终相信IT会持续改造甚至创新传统行业,我们始终全面看好咱们的CS专业!
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

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