 # [Vmware] VMware 第一轮 OA

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

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

x

4 s8 ]  D1 B% \; g1 i

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.
From 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!
: 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,
that means he first made a horizontal move, then a vertical move, then a horizontal move again and finally a vertical move.
HVVH can be another possible way but HVHV is lexicographically smaller that HVVH.) |' C( I1 m# f  m( A% q5 M

Given 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
to 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
in the form "x y k".
* X& R* ^- H% v0 G3 h; W8 U  h
Return Value:
Return an array of string, ith element of the array should contain answer of ith test case.* e7 g6 N/ D# l# A0 o

Constraints
1 <= |inp| <=100000
1 <= x <= 10
1 <= y <= 105 p! k2 q4 M4 N' Z# L: m
0 <= k < number of paths
. [\$ t4 g% j) F  l& N" u
Sample Input
inp={"2 2 2", "2 2 3",}
Sample Output5 C" y+ I. w2 {+ O& b: w" h
{"HVVH","VHHV"}; L  B# _' t. l
Explanation
All the paths of going to (2,2) from (0,0) in lexicographically increasing order:

0. 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
4. VHVH) @( Q& ]/ J8 T# F" W
5. VVHH

0 g; }( |( f7 ^# _5 l5 S

A 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.

There 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.
+ ^- 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
type '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
n D
R1 R2 ... Rn' l0 J! U, s3 I: |
C1 Cr ... Cn

Output" W, c" r: }# c\$ O) z
T1 T2 ... Tn
+ f/ s# g. ^2 h8 p: t+ T/ `
\$ k) g2 p* s3 z" H

### 评分

781主题 5670积分   5670    发表于 11-24-2015 10:15 AM 来自美国米群网手机版 | 显示全部楼层
 感谢您这么详细的面经分享~~~精华积分满满送上了~~~也祝福您拿下dream offer~~~
 本版积分规则 回帖后跳转到最后一页   