推荐:数据科学课程和书籍清单以及培训讲座


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 1105|回复: 10
收起左侧

google phone ...bless

[复制链接] |试试Instant~ |关注本帖
池大侠 发表于 2015-3-17 02:01:10 | 显示全部楼层 |阅读模式

2013(1-3月) 码农类 硕士 全职@Google - 内推 - 技术电面 |Other

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

x
just finished .. all three can be solve with hashing....
Bless!!

first question:
1.find the latest events
2.find pairs in hands  need to define data structure by myself-google 1point3acres
3.find straight in hands
. more info on 1point3acres.com
all problem can be done in linear time.
below are questions and my solution.. 1point3acres.com/bbs

bless!!!!!!!!!!! anyway....
  1. Please use this Google doc to code during your interview. To free your hands for coding, we recommend that you use a headset or a phone with speaker option.. Waral 鍗氬鏈夋洿澶氭枃绔,

  2. Best,
  3. Google Staffing


  4. A session is a series of Events. Each session is identified by a number, the sessionId. Events have this structure:

  5. class Event {
  6.   public int sessionId;  // identities the session this Event belongs to
  7.   public int timestamp;  // time the Event occurred
  8.   [...]
  9. }

  10. We have an unordered list of Events from multiple sessions intermixed. Given this list (List<Event>), construct a new list containing only the latest Event for each session.
  11. #input=[event1,event2,.....]
  12. #linear space and linear time
  13. #time1 12:00PM
  14. #hashtable
  15. def solve(events):
  16.         dict={}# key: sessionID, value would be eventname sorted by timestamp
  17. for elem in events:       
  18.                 if elem.sessionId not in dict:
  19.                         dict[elem.sessionId]=elem.鐣欏璁哄潧-涓浜-涓夊垎鍦
  20.                 elif elem.timestamp>dict[elem.sessionId].timestamp:
  21.                         dict[elem.sessionId]=elem. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  22. res=[]
  23. for elem in dict:
  24.         res.append(dict[elem])
  25. return res


  26. . Waral 鍗氬鏈夋洿澶氭枃绔,

  27. 52-card deck
  28. 4 suits: spades, hearts, diamonds, clubs.1point3acres缃
  29. 13 values: A, 2, 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K
  30.        
  31. 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  32. hand: 5 cards
  33. Write a function to detect whether a poker hand contains a “pair” (exactly 2 cards with the same value).
  34. ## given 5 cards

  35. class card:
  36.         def __init__(self,value,suit):
  37.                 self.value=value
  38.                 self.suit=suit
  39. #class hand:
  40. #        def __init__(self,n):
  41. #                self.n=n
  42. #                self.hand=[]
  43. #        def getcard(self,card):
  44. #                self.hand.append(card)
  45.        
  46. #list of cards=>hand
  47. #nlog(n) time sort by its value  give me the result 3, 8 eight?
  48. #hash
  49. # linear time and space
  50. def check(hand):
  51.         dict={}.1point3acres缃
  52.         for card in hand:
  53.                 if card.value not in dict:. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  54.                         dict[card.value]=1
  55.                 else:
  56.                         dict[card.value]+=1
  57.         ## check whether  I have a pair
  58.         for elem in dict:
  59.                 if dict[elem]==2:
  60.                         return True
  61.         return False

  62. # determine whether the hand contains a “straight”: values are consecutive
  63. # Ace can be high or low
  64. # A, 2, 3, 4, 5 is a straight
  65. # 4, 5, 6, 7, 8 is a straight
  66. # 10, J, Q, K, A is also a straight       
  67. # replace A with both 1 and 14
  68. # sort nlog(n)
  69. # 7,8,9,10,A -> 7,8,9,10,1,14. Waral 鍗氬鏈夋洿澶氭枃绔,
  70. # 10,11,12,13,A-> 10,11,12,13,14,1
  71. # go through the sorted array of cards to check whether they are consecutive
  72. # this take nlogn time. 1point 3acres 璁哄潧
  73. # hash to detect consecutive cards. from: 1point3acres.com/bbs


  74. .鐣欏璁哄潧-涓浜-涓夊垎鍦


  75. def check(hand):
  76.         ## deal with A first -> replace A with 1 and 14
  77.         ## ‘J’:11, ‘K’:13####
  78. . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  79. for cardelem in hand:
  80.         ## first step deal with A. 1point 3acres 璁哄潧
  81. if cardelem.value=’A’:
  82.         newcard=card(14,’spade’)
  83.         cardelem.value=1
  84. hand.append(newcard)
  85. dict={}

  86. for cardelem in dict:
  87.         if cardelem not in dict:
  88.                 dict[cardelem.value]=True       
  89.                      count=1
  90.                 maxlen=1
  91.                 for key in dict:
  92.                         count=1
  93.                         pre=key-1
  94.                         while pre in dict and dict[pre]:
  95.                                 count+=1
  96.                                 dict[pre]=False
  97.                                 pre-=1
  98.         ## 6,7<-8 ->9 10
  99.                         post=key+1
  100.                         while post in dict and dict[post]:-google 1point3acres
  101.                                 count+=1
  102.                                 dict[post]=False
  103.                                 post+=1
  104.                         maxlen=max(maxlen,count)
  105.         if maxlen==5:
  106.                 return True
  107.         else:       
  108.                 return False. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  109.                
  110. #linear time and space
  111. #

  112.        
  113. Ace of Spades
  114. 3 of diamonds
  115. 8 of clubs
  116. 8 of hearts. more info on 1point3acres.com
  117. J of diamonds
复制代码
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
补充内容 (2015-3-16 17:43):
some  problem in the code fomat cause jst copied from google doc.

评分

3

查看全部评分

jeager 发表于 2015-3-17 02:45:54 | 显示全部楼层
第三题 可以 这么办
一个boolean A, A是否出现
一个max,一个min
A不计入max,min,length
一圈下来
if(A){
    if((min == 2 || max == 13) && max-min +1 == 4) return true;
    else return false;
}
else{
.鐣欏璁哄潧-涓浜-涓夊垎鍦  if(max-min +1 == 5) return true;
  else return false;
}

这样的话,time O(n), space(1);

评分

1

查看全部评分

回复 支持 3 反对 0

使用道具 举报

fishyuze 发表于 2015-3-18 09:21:01 | 显示全部楼层
for the straight: why not just use a boolean array?
and what about J Q K A 2?
回复 支持 1 反对 0

使用道具 举报

houqingniao 发表于 2015-3-17 02:36:26 | 显示全部楼层
bless~
lz 没问题的
回复 支持 反对

使用道具 举报

Reborn2beCoder 发表于 2015-3-18 07:25:15 | 显示全部楼层
跪求lz解释这段代码

              for key in dict:
                        count=1
                        pre=key-1
                        while pre in dict and dict[pre]:
                                count+=1
                                dict[pre]=False
                                pre-=1
        ## 6,7<-8 ->9 10.1point3acres缃
                        post=key+1. 1point 3acres 璁哄潧. from: 1point3acres.com/bbs
                        while post in dict and dict[post]:
                                count+=1
                                dict[post]=False
                                post+=1. from: 1point3acres.com/bbs
                        maxlen=max(maxlen,count)
回复 支持 反对

使用道具 举报

 楼主| 池大侠 发表于 2015-3-18 08:47:09 | 显示全部楼层
Reborn2beCoder 发表于 2015-3-17 22:25
跪求lz解释这段代码

              for key in dict:

longest consecutive sequence...
回复 支持 反对

使用道具 举报

Reborn2beCoder 发表于 2015-3-18 08:56:46 | 显示全部楼层
池大侠 发表于 2015-3-18 08:47
longest consecutive sequence...

可是pre 跟 post 都只加一次就被false了呀。。还会继续运行吗><
回复 支持 反对

使用道具 举报

 楼主| 池大侠 发表于 2015-3-18 09:22:43 | 显示全部楼层
Reborn2beCoder 发表于 2015-3-17 23:56
可是pre 跟 post 都只加一次就被false了呀。。还会继续运行吗>
. From 1point 3acres bbs
yes.. just need to check once . if they are consecutive it doesnt matter.. more info on 1point3acres.com
that's y its linear
回复 支持 反对

使用道具 举报

Reborn2beCoder 发表于 2015-3-18 09:37:50 | 显示全部楼层
池大侠 发表于 2015-3-18 09:22
yes.. just need to check once . if they are consecutive it doesnt matter.
that's y its linear

看明白啦~~~ 不过其实如果只是连着的5个数的话只要判断没有重复而且dic[4] - dic[0] == 4就好了吧?有A的话就看 dic[4] - dic[0] ==4 || dic[5]-dic[1]==4 ?
回复 支持 反对

使用道具 举报

本版积分规则

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-8-18 20:58

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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