找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

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

[Google] Google Interview Question for

[复制链接]

1206

主题

184

精华

3720

积分

神级会员

Rank: 7Rank: 7Rank: 7

积分
3720
发表于 9-12-2017 10:22 AM | 显示全部楼层 |阅读模式

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

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

x

People enter and leave a room over the course of a day. Each person has a badge with a unique integer id, which is logged by the security system on enter/exit. Each log entry is an enter record (“E ”) or and leave record (“L ”) for the given badge id. / H, ?4 I/ o7 U4 e
The room is empty at the beginning and ending of the day, and there are no other ways into or out of the room.+ x7 T. B5 M ^# r+ C
E: Enters the room/ i7 R" U% g1 A$ b: S
L: Leaves the room. V2 p7 T. t* k: X* n# [! J( r
1 v3 a& s3 A2 i
Well formed log: 2 w( S* w. Y0 V9 B3 I* ~+ Z
E 1118 N+ F( M/ d4 p! D! }9 a
E 222 ! q. p, I6 I% T8 y
L 1112 Y" T8 F7 ?+ B% W* ]" p& ]
E 1113 s7 S3 d n5 [
L 222 4 S& N9 j* \2 g
L 111/ i: p: |- C# i
8 I, p7 G, ~* k' [2 t9 P, W
Question: You have a log and write a function to check is it the well formed log or not.

1173

主题

182

精华

3657

积分

神级会员

Rank: 7Rank: 7Rank: 7

积分
3657
发表于 9-12-2017 10:22 AM | 显示全部楼层

struct RoomLog {% D; P! \, \' Q6 p+ m
    let log: String
. i. e  M5 w+ e, H7 F! |}
* C# b+ S4 E# M4 t; g* f  Y% a
* T8 ?8 X/ u) w; l4 ~9 ]var log = [
! V, F3 |3 L+ W9 f# [6 H; b4 L    RoomLog(log: "E 111"),
2 T1 d! }- Y! U# r# Z+ d7 r8 G    RoomLog(log: "E 222"),; c( b" \. t! r" B) o
    RoomLog(log: "L 111"),
) g, _$ k( `& V3 S' f    RoomLog(log: "E 111"),
/ N) A% s3 J% T    RoomLog(log: "L 222"),* \% [7 U. _: l1 T. l1 U' x
    RoomLog(log: "L 111"),. n# W' Y- |$ k- q# Q/ n- q* g
]& N! k, B3 e1 e& q4 z1 _- v
2 ?7 m4 E: m* k
func isLogWellFormed(_ log: [RoomLog]) -> Bool {
/ {& |* N0 }" Z) f3 \' h    var set = Set<String>()
# M4 o; d# X3 f& A4 R6 w    for item in log {5 W+ \) F3 Q3 y% e
        if item.log.hasPrefix("E ") {
& M/ m/ z1 j" \            let key = item.log.replace("E ", with: "")
( g" o1 N4 ^" }& S$ Y$ e            if set.contains(key) { return false } // alrady entered
" _# ], a+ A$ t            set.insert(key)
, ]4 i# `/ L, l3 ~        }
3 ^. }+ B8 Y" {0 @        else if item.log.hasPrefix("L ") {. M  z& X  _) }; O
            let key = item.log.replace("L ", with: "")
7 v" B# b9 k# V: `1 j            set.remove(key)7 X9 b3 y2 c* i! n4 D$ \! g
        }
. \* R3 Q7 X6 ]9 l! g& w        else {; {0 q3 j0 v" J, u- Y
            return false// incorrect log record
# t5 V) @5 i+ U. k# }1 ]4 C- j        }
( @5 w" u6 |- R9 S0 P4 \' w    }
- r. j! S( {! O- P& m: W    return true8 \0 r' n6 T$ W1 i
}
" p$ H' {* G  ^2 m
6 |* i  w6 O) ?* K& fextension String {, T7 V  F6 K0 l" H5 P/ {
      b! {- K- ^2 Q0 ]) |
    func replace(_ str: String, with newString: String) -> String {
6 j& _) @/ J8 J8 M; K$ Q        return self.replacingOccurrences(of: str, with: newString)' G4 O. t0 V' Y- v) i9 S& ]5 t
    }
! s1 e- f, U6 S}
8 {7 l# h) A* Sprint("well formed: \(isLogWellFormed(log))") // well formed: true

1183

主题

200

精华

3760

积分

神级会员

Rank: 7Rank: 7Rank: 7

积分
3760
发表于 9-12-2017 10:22 AM | 显示全部楼层

Create a hash table, go through each element and:
1) if starts with 'E' insert if such element isn't there, otherwise return invalid error
2) if starts with 'L' remove element with a key 'L {number}', otherwise return invalid error
Finally, if there are any keys left, that means building isn't empty, return invalid list error

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

本版积分规则

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