《数据科学面试40+真题讲解》,K神本年度最后一次开课


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 1212|回复: 10
收起左侧

google phone ...bless

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

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

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

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

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

first question:
1.find the latest events. visit 1point3acres.com for more.
2.find pairs in hands  need to define data structure by myself
3.find straight in hands

all problem can be done in linear time.
below are questions and my solution.

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.
  2. . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  3. Best,
  4. Google Staffing


  5. A session is a series of Events. Each session is identified by a number, the sessionId. Events have this structure:
  6. . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  7. class Event {
  8.   public int sessionId;  // identities the session this Event belongs to. Waral 鍗氬鏈夋洿澶氭枃绔,
  9.   public int timestamp;  // time the Event occurred
  10.   [...]
  11. }

  12. 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.
  13. #input=[event1,event2,.....]
  14. #linear space and linear time
  15. #time1 12:00PM. 鍥磋鎴戜滑@1point 3 acres
  16. #hashtable
  17. def solve(events):
  18.         dict={}# key: sessionID, value would be eventname sorted by timestamp
  19. for elem in events:       
  20.                 if elem.sessionId not in dict:
  21.                         dict[elem.sessionId]=elem. from: 1point3acres.com/bbs
  22.                 elif elem.timestamp>dict[elem.sessionId].timestamp:
  23.                         dict[elem.sessionId]=elem
  24. res=[]
  25. for elem in dict:
  26.         res.append(dict[elem])
  27. return res



  28. .鏈枃鍘熷垱鑷1point3acres璁哄潧
  29. 52-card deck
  30. 4 suits: spades, hearts, diamonds, clubs
  31. 13 values: A, 2, 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K
  32.        

  33. hand: 5 cards
  34. Write a function to detect whether a poker hand contains a “pair” (exactly 2 cards with the same value).
  35. ## given 5 cards

  36. class card:
  37.         def __init__(self,value,suit):
  38.                 self.value=value
  39.                 self.suit=suit. visit 1point3acres.com for more.
  40. #class hand:
  41. #        def __init__(self,n):
  42. #                self.n=n
  43. #                self.hand=[]
  44. #        def getcard(self,card):.鏈枃鍘熷垱鑷1point3acres璁哄潧
  45. #                self.hand.append(card)
  46.        
  47. #list of cards=>hand
  48. #nlog(n) time sort by its value  give me the result 3, 8 eight?
  49. #hash
  50. # linear time and space
  51. def check(hand):
  52.         dict={}-google 1point3acres
  53.         for card in hand:-google 1point3acres
  54.                 if card.value not in dict:
  55.                         dict[card.value]=1 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  56.                 else:
  57.                         dict[card.value]+=1
  58.         ## check whether  I have a pair
  59.         for elem in dict:
  60.                 if dict[elem]==2:
  61.                         return True. 鍥磋鎴戜滑@1point 3 acres
  62.         return False.鏈枃鍘熷垱鑷1point3acres璁哄潧

  63. # determine whether the hand contains a “straight”: values are consecutive. 1point 3acres 璁哄潧
  64. # Ace can be high or low
  65. # A, 2, 3, 4, 5 is a straight
  66. # 4, 5, 6, 7, 8 is a straight
  67. # 10, J, Q, K, A is also a straight       
  68. # replace A with both 1 and 14
  69. # sort nlog(n)
  70. # 7,8,9,10,A -> 7,8,9,10,1,14
  71. # 10,11,12,13,A-> 10,11,12,13,14,1. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  72. # go through the sorted array of cards to check whether they are consecutive
  73. # this take nlogn time
  74. # hash to detect consecutive cards





  75. def check(hand):
  76.         ## deal with A first -> replace A with 1 and 14
  77.         ## ‘J’:11, ‘K’:13####. 鍥磋鎴戜滑@1point 3 acres

  78. for cardelem in hand:
  79.         ## first step deal with A
  80. if cardelem.value=’A’:
  81.         newcard=card(14,’spade’)
  82.         cardelem.value=1
  83. hand.append(newcard)
  84. dict={}. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

  85. for cardelem in dict:
  86.         if cardelem not in dict:
  87.                 dict[cardelem.value]=True       
  88.                      count=1.1point3acres缃
  89.                 maxlen=1
  90.                 for key in dict:
  91.                         count=1
  92.                         pre=key-1
  93.                         while pre in dict and dict[pre]:
  94.                                 count+=1
  95.                                 dict[pre]=False
  96.                                 pre-=1.鐣欏璁哄潧-涓浜-涓夊垎鍦
  97.         ## 6,7<-8 ->9 10
  98.                         post=key+1
  99.                         while post in dict and dict[post]:
  100.                                 count+=1
  101.                                 dict[post]=False
  102.                                 post+=1
  103.                         maxlen=max(maxlen,count).1point3acres缃
  104.         if maxlen==5:
  105.                 return True. from: 1point3acres.com/bbs
  106.         else:       
  107.                 return False
  108.                
  109. #linear time and space
  110. #

  111.        
  112. Ace of Spades.鐣欏璁哄潧-涓浜-涓夊垎鍦
  113. 3 of diamonds
  114. 8 of clubs
  115. 8 of hearts 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  116. 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 | 显示全部楼层
第三题 可以 这么办. 鍥磋鎴戜滑@1point 3 acres
一个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
                        post=key+1. 1point 3acres 璁哄潧
                        while post in dict and dict[post]:
                                count+=1
                                dict[post]=False
                                post+=1
鏉ユ簮涓浜.涓夊垎鍦拌鍧.                         maxlen=max(maxlen,count)
回复 支持 反对

使用道具 举报

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

              for key in dict:

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

使用道具 举报

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

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

使用道具 举报

 楼主| 池大侠 发表于 2015-3-18 09:22:43 | 显示全部楼层
Reborn2beCoder 发表于 2015-3-17 23:56. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
可是pre 跟 post 都只加一次就被false了呀。。还会继续运行吗>

yes.. just need to check once . if they are consecutive it doesnt matter.
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-11-22 20:50

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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