找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 6290|回复: 1
收起左侧

[Vmware] VMware 第一轮 OA

[复制链接]

5

主题

2

精华

95

积分

资深会员

Rank: 2

积分
95
发表于 11-24-2015 02:35 AM | 显示全部楼层 |阅读模式

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

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

x
本帖最后由 Sophia 于 11-24-2015 11:39 AM 编辑
( h" R* X! c2 G. h4 s8 ]  D1 B% \; g1 i
第一题:
0 t& C. d( \7 s2 Z% F/ j) X. @Bob just reached Gridland, a 2D world divided in many cells. Each cell is denoted by a pair (r,c) where r>=0 and c>=0.
/ H0 Q( Y8 T' W& C! |( U, AFrom a cell (r,c) one can move to (r+1,c), (r,c+1),(r-1,c) and (r,c-1). 2 F% _; j; n" \' e# O9 t, f
" q; H1 G: |+ v# u/ v: P* n
Bob is standing at cell (0,0) and he wants to go to cell(x,y) in the smallest number of moves. But there are so many possible shortest path and in some : r- _+ ^: R' Q1 e1 d! u
of the path there are dangerous dragons. But Bob knows that if he uses the lexicographically kth shortest path, he will be able to avoid the dragons!
! v5 n: M4 J3 L  U$ u) U: D, A% R6 w. S. y+ }7 w2 e
All possible shortest ways consist of some horizontal and some vertical moves, lets denote the moves by H and V.  A possible way to go from (0,0) to (2,2) is HVHV,
* S% C; \6 |1 w) P1 {4 _that means he first made a horizontal move, then a vertical move, then a horizontal move again and finally a vertical move.
) W- r& S: W: |1 Z6 oHVVH can be another possible way but HVHV is lexicographically smaller that HVVH.) |' C( I1 m# f  m( A% q5 M

) P& T, w* j7 J# }2 X! @' L  j$ WGiven the value of k find the lexicographically kth path to go from (0,0) to (x,y) using smallest number of moves. Note that k is numbered from 0
/ E8 K# `) G/ _0 `# R( y2 Mto P-1 where P is number of possible paths. So for the example above HHVV is the lexicograpically 0th path.3 V) }+ n: L( V3 p, b" Y
5 T# {2 h7 a4 D% o& B) Y
Input Parameters:6 f+ S( l* ~; X: L. m
You need to complete a function gridLand. If will take an array of string inp as parameter. Each element of the inp will represent a single case
. J  s2 {0 H' ^" H+ ]2 P9 r- Iin the form "x y k".
! m- k: Y' R6 V* N% R. y% e1 T- Q# @$ f* X& R* ^- H% v0 G3 h; W8 U  h
Return Value:
4 B3 t5 I% r4 s/ V# c( S9 y0 xReturn an array of string, ith element of the array should contain answer of ith test case.* e7 g6 N/ D# l# A0 o

: B4 S( i, K' b7 Q: JConstraints
0 O  Q. M# U6 w, t) ^2 ~1 <= |inp| <=100000
! c2 i- t" ?- n" x+ ^$ X& Z1 <= x <= 10
7 p$ s9 P1 c. @! t1 <= y <= 105 p! k2 q4 M4 N' Z# L: m
0 <= k < number of paths
  W( P# c& f0 Q% ]* a) K. [$ t4 g% j) F  l& N" u
Sample Input
& H. F" Q4 h% [5 B0 R0 Z9 }inp={"2 2 2", "2 2 3",}
  R" U0 B" V. {4 K6 f$ k( x/ |% GSample Output5 C" y+ I. w2 {+ O& b: w" h
{"HVVH","VHHV"}; L  B# _' t. l
Explanation
% G6 A, D9 C' KAll the paths of going to (2,2) from (0,0) in lexicographically increasing order:
1 `" O) ~3 g0 \4 w" `
/ [2 K8 m+ r; O0 d# j! Q4 D0. HHVV8 ?$ V8 W  @5 E, b6 N
1. HVHV6 w) W7 ^3 K9 Z" M
2. HVVH7 ]5 C2 w2 |" e0 o/ b
3. VHHV
; p+ [8 ?0 h& X9 c% C0 r# H+ C4. VHVH) @( Q& ]/ J8 T# F" W
5. VVHH
( [5 B4 W. H8 \% p5 Z2 J2 I- V
0 R- a9 J4 z/ J8 ]7 Q简单来说就是计算当前问题总共有几种可能性,判断出向右还是向上走一步,进而变成解子问题。
% B# g/ N* Q2 Z1 x( N' J
4 Q1 h: y0 O4 u7 P& P5 E: U0 g; }( |( f7 ^# _5 l5 S
第二题:
" Z6 O. X; u; @" d' zA mechanical engineer is writing a design specification for two gears to transmit motion between two  S- h; Y$ d4 w% a
parts, A and B, in a machine shie is designing. The distance between A and B is equal to D.
7 y5 t* _& _  x1 `  I) d
/ X6 ~6 ]3 c/ W! xThere are n Types of gears, a gear type of j has a raius Rj and cost Cj. The two gears specified, i and j, must have 6 [0 D/ O6 i1 L9 i$ \
Ri+Rj >= D, in order for there to be a way of placing them so that they touch and work together. The objective is. A7 r  D  p$ G# r
to find the pair which costs the least.
! x/ \) z5 W- A6 j1 A+ ^- b/ a  G- S! E8 d" c3 Y2 T' v( M
You need to produce a design table that gives the most suitable match for every gear type in the list. For every gear
$ R; Q7 C# a1 l0 ?6 T- Ttype 'i', you need to consider its desciption (Ri,Ci) and list the gear type 'j' to pair with 'i' in table position T【i】.8 B4 b: J7 c+ m, q/ Q- s
The best map might be the same type(Ti=i). If there are multiple solutions with the same cost, choose the gear with the largest radius.1 s. d1 d+ C: v1 y/ o: b
If both the cost and radius you need are found in more than one gear type, choose the type with the smallest index j.  L$ L; V2 f) x" r7 m* G
If no radius can be found that allow the distance D to be covered, table should contain 0.! t! K7 F. t3 f& V; |' a- E# F
! Q/ T5 g0 z: Y
Input
& {1 H) k" `! `) ~. [n D
$ [2 n; ]" c" `$ V. a3 a: HR1 R2 ... Rn' l0 J! U, s3 I: |
C1 Cr ... Cn
( v  S  |2 l2 v" a
3 K0 H+ \( _- xOutput" W, c" r: }# c$ O) z
T1 T2 ... Tn
1 t  Q+ z5 }0 s- c- Z! k+ f/ s# g. ^2 h8 p: t+ T/ `
$ k) g2 p* s3 z" H
两个for循环可以出来,不知道有没有更优的解法1 s5 T) l" Y1 ]$ e8 ^1 m6 ^/ U: }

. R0 N. Y) O) I) \! ^5 C
' m* }4 Z4 N, X# l4 U# ?4 J

评分

参与人数 1金钱 +3 收起 理由
Sophia + 3 精华帖子!大赞!

查看全部评分

781

主题

575

精华

5670

积分

顶级版主

Rank: 9Rank: 9Rank: 9

积分
5670

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

发表于 11-24-2015 10:15 AM 来自美国米群网手机版 | 显示全部楼层
感谢您这么详细的面经分享~~~精华积分满满送上了~~~也祝福您拿下dream offer~~~
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

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