一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 880|回复: 10
收起左侧

google phone ...bless

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

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

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

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

x
just finished .. all three can be solve with hashing..... 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
Bless!! . 1point 3acres 璁哄潧
. visit 1point3acres.com for more.
first question:
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.. 鍥磋鎴戜滑@1point 3 acres

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,.....]. From 1point 3acres bbs
  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:. Waral 鍗氬鏈夋洿澶氭枃绔,
  19.                         dict[elem.sessionId]=elem. 1point3acres.com/bbs
  20.                 elif elem.timestamp>dict[elem.sessionId].timestamp:. visit 1point3acres.com for more.
  21.                         dict[elem.sessionId]=elem
  22. res=[]
    .1point3acres缃
  23. for elem in dict:
  24.         res.append(dict[elem])
  25. return res. 1point3acres.com/bbs



  26. . 鍥磋鎴戜滑@1point 3 acres
  27. 52-card deck
  28. 4 suits: spades, hearts, diamonds, clubs. Waral 鍗氬鏈夋洿澶氭枃绔,
  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. class card:
  35.         def __init__(self,value,suit):
  36.                 self.value=value
  37.                 self.suit=suit
  38. #class hand:
  39. #        def __init__(self,n):
  40. #                self.n=n
  41. #                self.hand=[]
  42. #        def getcard(self,card):
  43. #                self.hand.append(card)-google 1point3acres
  44.        
  45. #list of cards=>hand
  46. #nlog(n) time sort by its value  give me the result 3, 8 eight?
  47. #hash
  48. # linear time and space.鏈枃鍘熷垱鑷1point3acres璁哄潧
  49. def check(hand):.1point3acres缃
  50.         dict={}
  51.         for card in hand:
  52.                 if card.value not in dict:.鏈枃鍘熷垱鑷1point3acres璁哄潧
  53.                         dict[card.value]=1
  54.                 else:
  55.                         dict[card.value]+=1
  56.         ## check whether  I have a pair
  57.         for elem in dict: 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  58.                 if dict[elem]==2:
  59.                         return True.1point3acres缃
  60.         return False

  61. # determine whether the hand contains a “straight”: values are consecutive
  62. # Ace can be high or low
  63. # A, 2, 3, 4, 5 is a straight. 1point 3acres 璁哄潧
  64. # 4, 5, 6, 7, 8 is a straight
  65. # 10, J, Q, K, A is also a straight       
  66. # replace A with both 1 and 14
  67. # sort nlog(n). 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  68. # 7,8,9,10,A -> 7,8,9,10,1,14
  69. # 10,11,12,13,A-> 10,11,12,13,14,1
  70. # go through the sorted array of cards to check whether they are consecutive
  71. # this take nlogn time
  72. # hash to detect consecutive cards




  73. . 1point 3acres 璁哄潧
  74. . visit 1point3acres.com for more.
  75. def check(hand):
  76.         ## deal with A first -> replace A with 1 and 14
  77.         ## ‘J’:11, ‘K’:13####.鏈枃鍘熷垱鑷1point3acres璁哄潧
  78. .鏈枃鍘熷垱鑷1point3acres璁哄潧
  79. for cardelem in hand:
  80.         ## first step deal with A
  81. if cardelem.value=’A’:
  82.         newcard=card(14,’spade’). visit 1point3acres.com for more.
  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        . Waral 鍗氬鏈夋洿澶氭枃绔,
  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-google 1point3acres
  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]:
  101.                                 count+=1
  102.                                 dict[post]=False
  103.                                 post+=1. 1point3acres.com/bbs
  104.                         maxlen=max(maxlen,count)
  105.         if maxlen==5:
  106.                 return True
  107.         else:       
  108.                 return False
    . visit 1point3acres.com for more.
  109.                
  110. #linear time and space
  111. #

  112.        
  113. Ace of Spades
  114. 3 of diamonds.鏈枃鍘熷垱鑷1point3acres璁哄潧
  115. 8 of clubs
  116. 8 of hearts
  117. J of diamonds. from: 1point3acres.com/bbs
复制代码

补充内容 (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;.1point3acres缃
  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?. 1point 3acres 璁哄潧
and what about J Q K A 2?
求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 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. visit 1point3acres.com for more.
                                pre-=1
        ## 6,7<-8 ->9 10
                        post=key+1. 1point 3acres 璁哄潧. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                        while post in dict and dict[post]:.鏈枃鍘熷垱鑷1point3acres璁哄潧
                                count+=1
                                dict[post]=False-google 1point3acres
                                post+=1
                        maxlen=max(maxlen,count)
回复 支持 反对

使用道具 举报

 楼主| 池大侠 发表于 2015-3-18 08:47:09 | 显示全部楼层
Reborn2beCoder 发表于 2015-3-17 22:25
跪求lz解释这段代码. Waral 鍗氬鏈夋洿澶氭枃绔,

. from: 1point3acres.com/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.
that's y its linear

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

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

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

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2017-1-24 13:42

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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