找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

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

[Zenefits] Zenefits OA 面经,衣柜

[复制链接]

1

主题

1

精华

32

积分

新米人

Rank: 1

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

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

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

x
本帖最后由 Sophia 于 11-21-2015 10:40 PM 编辑 0 d. ~7 S2 g7 ~& B3 Q2 y

8 Z* {+ h4 u+ F6 M2 w刚做了OA 4,第一题全过了,第二题过了4个test cases。第二天接到recruiter的信,说是组里讨论了,还是给据了。第二题其实被lint code给害了。我自己测试了其他OA题,只有这一道,lint code上有OJ,在lint code过了,但其实有bug。说一下题吧,! J0 A/ t$ v4 Z. ]& L! A$ m+ K) X
1. There are n ticket windows in the railway station. The ith window has a_i tickets available. The price+ P9 \# z+ U8 X7 C5 r4 B7 E
   of a ticket is equal to the number of tickets remaining in that window at that time. What is the maximum- F1 c3 V. R- h  b% H8 I2 `2 v3 P
   amount of money the railway station can earn form selling the first m tickets% k8 h1 H1 b, Y, Y
   Input:
9 e3 v+ B! G8 s* z   n m
2 }3 y% A% m4 B1 k' b- P$ Z   a_1 a_2 ... a_n
; S5 q/ K6 `' I9 d4 J   Output S, O1 P4 [* C1 o8 m# F3 v7 w

: K: F( M2 B9 x# |7 N" A   Constraint
% ^6 E4 w+ t, `! R0 V4 [- O3 `9 S   1<=n<=100,000; b0 e% L0 Q  p+ N$ o
   1<=a_i<=100,0001 q: X% M. h+ p0 z% C
   1<=m<=a_1+a_2+...+a_n
3 a" Z1 p, s5 g7 D- e
3 a- e. g$ W. v# s) T: U   sample input
  D8 L3 I6 k- ^% n   2 4, w2 q4 I/ S* Y$ s7 u. r8 F$ S
   2 5$ V) v3 V, w1 q5 [7 }3 Q' T/ [
   sample output
5 R7 Q6 X& l8 v3 y3 K   14" ~5 t- q, Q: Q% B3 A8 [( r
   Since all 4 tickets can just be sold at 2nd window, 5, 4, 3, 20 m! Z! v. s/ @) E
2. 基本上是, 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.3 y! `  I5 p  t% u: @- O" z
1 _( z4 o: j3 U2 w# x- t$ y
给个第一题的code,所有test cases passed. 第二题,我的code有bug,就不上了。
& S/ `- ~7 S8 g6 L' klong long sellTicket(string input), \! Z: i) ^8 V3 z7 [* o) r9 b
{
& [4 ^6 W* C: U4 U  a        stringstream ss(input);
& B" U+ T0 O, K5 ^5 Y        int n = 0;# Q1 w2 ~0 Q  v8 Q  ~
        ss >> n;- z- r1 a7 i# z
2 P( d0 N, K, d
        if (n < 1) return 0; // Or assert
6 Q+ Z$ j3 L6 h. ^5 c+ x
& V7 y& e2 j( j# _. G3 |- k, ^        long long m = 0;1 Y$ X5 b- M! ?  R% F. }$ I( b
        ss >> m;
$ l; H; P+ P: n  V* p+ A1 D
) ^) A: u" x3 v1 ?( I% f$ Y: T  k6 d        if (m < 1) return 0;8 C8 X  m9 ^/ J" H8 C' @' G

7 ?2 k: b2 l: w. o7 L2 q        vector<int> a(n, 0);
! q# Q# Q3 r, J7 d1 n        for (int i = 0; i < n; i++)% y+ f  i$ j  V3 D# E
        {& e9 U  @/ t5 q8 T5 f! Y2 \/ j  m
                ss >> a【i】;! r9 W9 _" ~! _1 x$ k
        }
) P. D/ I0 ~8 p, ?  e8 z; E) i- o, F( H- }5 w( h
        // Validate that m <= a_1+a_2+...+a_n# z" y" W% ~3 T5 _6 C

2 O! l( x9 O* B, \* ~0 V: ^        // Sort a in descending order O(nlogn)( y) A( C+ c% H% ]0 S8 p
        sort(a.begin(), a.end(), greater<int>());! u; l, l; _; m4 `6 G
2 J8 u, P* n: V" Z% p* T
        // use one pointer right such that a_0==a_1==...a_(right-1), k6 L8 k! {; N
        long long profit = 0;
" T5 V6 g* b4 _9 @" F8 z' I        int right = 1;$ t9 v" I: W! F7 }: h* d  r  h
        int numTickets = a[0];1 Y1 X6 l6 S' n* ^0 e9 Y, L7 U
        while (m > 0), a+ H  [* |" G! H; ]: G
        {2 r2 [7 e" \: G* H* s/ S" Q
                // Loop invariant a_i = numTickets, where 0<=i<right ( s( }/ C& `' R) k8 E+ _; t( c; V
                while (right < n && numTickets == a[right])
- O& k' X) f9 f' x9 H                        right++;
0 ?0 z& h! G3 W; j, J. o7 D( ~5 ^5 n
                int low = right < n ? a[right] : 0;5 b2 c1 {. Q# f, F2 ]- g
                long long diff = numTickets - low;- V9 i5 \/ [" J. {# ^# f/ D
( Z4 N0 q5 ?8 i0 Y7 R8 O
                if (diff * right <= m)
5 a+ w6 F; F+ B                {0 `, L6 G& ?# x2 m* d1 o
                        // From window a_0 to a_(right-1), we can just sell diff number of tickets for each window.8 Q; R  e+ `' g2 O8 N
                        profit += right * ((numTickets - low) * (numTickets + low + 1) / 2);    //((diff * low) + diff * (diff + 1) / 2);
) b# l/ a5 Y8 b7 U6 X, F, Z7 ?                        m -= diff * right;7 v& k) @% v6 C7 \, U; z
                        numTickets = low;* z/ [8 M6 r0 n; o" y8 E0 A
                }
1 Z( ~3 L0 X, g                else
% M2 J, B9 m1 A, p                {9 i4 T: J: U; X& r6 q) L
                        diff = m / right;
  L0 P* w1 U7 h$ N7 S3 c+ y% H                        low = numTickets - diff;0 c$ x4 v* v3 G
                        profit += right * ((numTickets - low) * (numTickets + low + 1) / 2); // ((diff * low) + diff * (diff + 1) / 2);3 M2 O9 N* e) T! C4 ^) W  Z
                        profit += (m % right) * low;2 h( `  n$ F$ w  D1 |: p! _0 T* t, S8 O
                        m = 0;& ?4 i; S5 g, z$ Z
                        break;" c- \, H, {6 {: D
                }' i" [8 Z$ O) B
        }
8 k6 `; q7 E5 b$ \: m/ `9 A0 M" w$ P7 {! z5 D! u
        return profit;+ p+ |1 I+ `4 m
}
9 G3 `" g& o: H: I. w
- f) \3 i  u5 d3 b6 r, |; y$ k" J( N  V+ w& I4 _5 f7 r, h6 h

评分

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

查看全部评分

1

主题

1

精华

32

积分

新米人

Rank: 1

积分
32
 楼主| 发表于 11-21-2015 02:14 AM | 显示全部楼层
本帖最后由 Sophia 于 11-21-2015 10:39 PM 编辑 ' L1 O* x+ _" t

/ j. n; \' G4 z' ^是被lint_code给害了。

781

主题

575

精华

5670

积分

顶级版主

Rank: 9Rank: 9Rank: 9

积分
5670

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

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

本版积分规则

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