一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推多家公司面试
Airbnb 数据科学职位
in analytics and inference
游戏初创公司
招聘工程师、Designer和游戏策划
游戏初创公司DreamCraft招聘工程师、UIUX Designer和游戏策划
电商初创公司Good Days
招聘SDE/UI/TPM实习生
把贵司招聘信息放这里
查看: 1289|回复: 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:.1point3acres缃
1.find the latest events
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.. From 1point 3acres 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.

  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,.....]
    . more info on 1point3acres.com
  12. #linear space and linear time
  13. #time1 12:00PM
  14. #hashtable. from: 1point3acres.com/bbs
  15. def solve(events):
  16.         dict={}# key: sessionID, value would be eventname sorted by timestamp. 1point 3acres 璁哄潧
  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
    . visit 1point3acres.com for more.
  22. res=[]
  23. for elem in dict:.鐣欏璁哄潧-涓浜-涓夊垎鍦
  24.         res.append(dict[elem])
  25. return res

  26. . more info on 1point3acres.com


  27. 52-card deck
  28. 4 suits: spades, hearts, diamonds, clubs
  29. 13 values: A, 2, 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K
  30.        

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

  34. . From 1point 3acres bbs
  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
    . Waral 鍗氬鏈夋洿澶氭枃绔,
  49. # linear time and space
  50. def check(hand):
  51.         dict={}
  52.         for card in hand:
  53.                 if card.value not in dict:
    . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  54.                         dict[card.value]=1 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  55.                 else:
  56.                         dict[card.value]+=1. 1point 3acres 璁哄潧
  57.         ## check whether  I have a pair
  58.         for elem in dict:.1point3acres缃
  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. 1point 3acres 璁哄潧
  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.鐣欏璁哄潧-涓浜-涓夊垎鍦
  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
  73. # hash to detect consecutive cards




  74. . more info on 1point3acres.com
  75. def check(hand):
  76.         ## deal with A first -> replace A with 1 and 14
  77.         ## ‘J’:11, ‘K’:13####

  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:. more info on 1point3acres.com
  87.                 dict[cardelem.value]=True       
  88.                      count=1. more info on 1point3acres.com
  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. 1point 3acres 璁哄潧
  95.                                 dict[pre]=False
  96.                                 pre-=1. more info on 1point3acres.com
  97.         ## 6,7<-8 ->9 10
  98.                         post=key+1. 1point3acres.com/bbs
  99.                         while post in dict and dict[post]:
  100.                                 count+=1
  101.                                 dict[post]=False
  102.                                 post+=1
  103.                         maxlen=max(maxlen,count)
  104.         if maxlen==5:
  105.                 return True
  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 | 显示全部楼层
第三题 可以 这么办
一个boolean A, A是否出现
一个max,一个min
A不计入max,min,length
一圈下来
if(A){.1point3acres缃
    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. From 1point 3acres bbs
                                pre-=1
        ## 6,7<-8 ->9 10.鏈枃鍘熷垱鑷1point3acres璁哄潧
                        post=key+1. 1point 3acres 璁哄潧
                        while post in dict and dict[post]:
                                count+=1
                                dict[post]=False. 1point3acres.com/bbs
                                post+=1
                        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了呀。。还会继续运行吗>
-google 1point3acres
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, 2018-1-23 16:07

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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