传说中的谷歌招聘委员会成员之一,从幕后走出来,教你学系统设计!


一亩三分地论坛

 找回密码
 获取更多干活,快来注册
天天打游戏、照样领工资、还办H1B
这份工作你要不要?
把贵司招聘信息放这里
查看: 1135|回复: 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!! . more info on 1point3acres.com

first question:
1.find the latest events
2.find pairs in hands  need to define data structure by myself 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
3.find straight in hands
. 鍥磋鎴戜滑@1point 3 acres
all problem can be done in linear time.. 1point3acres.com/bbs
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. 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. visit 1point3acres.com for more.
  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.1point3acres缃
  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:. visit 1point3acres.com for more.
  19.                         dict[elem.sessionId]=elem
  20.                 elif elem.timestamp>dict[elem.sessionId].timestamp:
  21.                         dict[elem.sessionId]=elem. From 1point 3acres bbs
  22. res=[]
  23. for elem in dict:
  24.         res.append(dict[elem])
  25. return res

  26. . 1point 3acres 璁哄潧


  27. 52-card deck. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  28. 4 suits: spades, hearts, diamonds, clubs. visit 1point3acres.com for more.
  29. 13 values: A, 2, 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K
  30.        
  31. -google 1point3acres
  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:. visit 1point3acres.com for more.
  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={}
  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:. 1point3acres.com/bbs
  59.                 if dict[elem]==2:
  60.                         return True
  61.         return False
  62. .鐣欏璁哄潧-涓浜-涓夊垎鍦
  63. # determine whether the hand contains a “straight”: values are consecutive
  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.鏈枃鍘熷垱鑷1point3acres璁哄潧
  67. # 10, J, Q, K, A is also a straight       
  68. # replace A with both 1 and 14 .鏈枃鍘熷垱鑷1point3acres璁哄潧
  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. .1point3acres缃

  76. .1point3acres缃


  77. def check(hand):
  78.         ## deal with A first -> replace A with 1 and 14
  79.         ## ‘J’:11, ‘K’:13####

  80. for cardelem in hand:
  81.         ## first step deal with A
  82. if cardelem.value=’A’:. 1point3acres.com/bbs
  83.         newcard=card(14,’spade’)
  84.         cardelem.value=1
  85. hand.append(newcard). 1point3acres.com/bbs
  86. dict={}

  87. for cardelem in dict:
    .鏈枃鍘熷垱鑷1point3acres璁哄潧
  88.         if cardelem not in dict:
  89.                 dict[cardelem.value]=True       
  90.                      count=1
  91.                 maxlen=1
  92.                 for key in dict:
  93.                         count=1
  94.                         pre=key-1
  95.                         while pre in dict and dict[pre]:. From 1point 3acres bbs
  96.                                 count+=1
  97.                                 dict[pre]=False
    . From 1point 3acres bbs
  98.                                 pre-=1
  99.         ## 6,7<-8 ->9 10
  100.                         post=key+1
  101.                         while post in dict and dict[post]:
  102.                                 count+=1
  103.                                 dict[post]=False
  104.                                 post+=1
    .1point3acres缃
  105.                         maxlen=max(maxlen,count)
  106.         if maxlen==5:
  107.                 return True. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  108.         else:       
  109.                 return False
  110.                 .鐣欏璁哄潧-涓浜-涓夊垎鍦
  111. #linear time and space
  112. #
  113. .鐣欏璁哄潧-涓浜-涓夊垎鍦
  114.        
    .1point3acres缃
  115. Ace of Spades
  116. 3 of diamonds
  117. 8 of clubs
  118. 8 of hearts
  119. 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;. 1point3acres.com/bbs
}
else{
  if(max-min +1 == 5) return true;
  else return false;. 鍥磋鎴戜滑@1point 3 acres
}

这样的话,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~. 鍥磋鎴戜滑@1point 3 acres
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. 1point 3acres 璁哄潧
                                dict[post]=False
                                post+=1. Waral 鍗氬鏈夋洿澶氭枃绔,
                        maxlen=max(maxlen,count) 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
回复 支持 反对

使用道具 举报

 楼主| 池大侠 发表于 2015-3-18 08:47:09 | 显示全部楼层
Reborn2beCoder 发表于 2015-3-17 22:25
跪求lz解释这段代码
. From 1point 3acres bbs
              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了呀。。还会继续运行吗>

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.. Waral 鍗氬鏈夋洿澶氭枃绔,
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-9-22 14:36

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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