找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 2140|回复: 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.0 ]/ d" n# l& V5 m& ?& Y
The room is empty at the beginning and ending of the day, and there are no other ways into or out of the room. 7 m- ~9 F" |! P, s. h7 i* ]
E: Enters the room8 i! v( [! d. c
L: Leaves the room + x1 X1 G$ S, l7 U+ z
) ]. n0 U! w! G2 Q) b2 l% `1 k& H
Well formed log: 7 g8 J9 ^( P7 M. U9 S4 b
E 111 # t- M; _) d; x$ ]4 y
E 222 9 h. q! b' S4 r7 h; h; w# q9 k/ \4 Z
L 111 " |( O. G* X( x% N, |* Z4 b% x
E 111! V% j9 b! S0 a+ d7 D2 g5 `
L 2224 J# p" _5 e7 J- `
L 111 ( ^: o* \5 ~8 Y C M
' z( Q# k' V! k; b% V) P' R
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 {: Z5 s2 g7 `) \; D3 z0 p6 B
    let log: String
' n6 A7 I2 H- [}% G, H. f2 w$ B. \7 c

( O" P/ O' m& x: Q3 h# ?2 l7 Zvar log = [! o# s& @8 R: {
    RoomLog(log: "E 111"),
9 h! h3 c6 P2 `, \7 B    RoomLog(log: "E 222"),
4 r7 A  C+ P" `8 x    RoomLog(log: "L 111"),& k% K& [5 {( L8 F$ I
    RoomLog(log: "E 111"),
. f6 y2 w: F  v+ X    RoomLog(log: "L 222"),
/ k- C* @! I$ g' A" t' o2 ~" o    RoomLog(log: "L 111")," L4 J8 Y( h$ A( V- R& C4 e
]
( a) ]6 C1 h0 \  u4 k( q
8 q8 a9 D. w) m( ^3 bfunc isLogWellFormed(_ log: [RoomLog]) -> Bool {( F4 q: O) T. p. J# ~
    var set = Set<String>()" r- L2 F5 w! [( s
    for item in log {
! O8 y1 _& X: j  m1 T9 x        if item.log.hasPrefix("E ") {
9 H8 V5 L) R" z0 Y            let key = item.log.replace("E ", with: "")9 B/ w, |# {7 c+ I( m
            if set.contains(key) { return false } // alrady entered' u% k/ r) ]' Q7 n* j5 j) Q4 H
            set.insert(key)
; b7 o" D# d. z        }
5 g2 H; O' Q  l. E) V        else if item.log.hasPrefix("L ") {
5 ?0 R4 \8 g7 {( B( O$ `4 P4 L- y            let key = item.log.replace("L ", with: "")$ d- o! ]/ L+ B6 R3 L3 g
            set.remove(key)
$ a3 {; x3 B7 K, T' p. y/ s. T$ p        }* k5 ^+ ^% c% v8 B# {2 f$ [2 u
        else {
% V9 v4 k$ H% B3 K            return false// incorrect log record
! s% E* {; ]! ]6 \2 _8 N        }& C" n- b6 ^1 R. d7 U
    }/ }6 G# `% J6 _9 M/ C
    return true
+ g# N% V% S) N! ]3 q  r. a}' L+ P9 n9 j6 T. K0 [6 [1 g

2 Q- K# V$ b& ?5 e0 K! |extension String {
2 `; h. [( W$ v# j9 E* G    
* ^: e8 o! Q" H: y    func replace(_ str: String, with newString: String) -> String {
# n3 C6 J, _/ }# J: h  P. h3 t. ^        return self.replacingOccurrences(of: str, with: newString)# h0 }  r0 \& A9 c
    }& S4 W' t! E' y1 h
}
5 O' h% W9 u7 G, _. dprint("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

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

本版积分规则

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