近期论坛无法登录的解决方案


一亩三分地论坛

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

一亩三分地官方iOS手机应用下载
查看: 1048|回复: 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!! .鏈枃鍘熷垱鑷1point3acres璁哄潧

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.

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. 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  5. A session is a series of Events. Each session is identified by a number, the sessionId. Events have this structure:

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

  11. 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.
  12. #input=[event1,event2,.....]
  13. #linear space and linear time
  14. #time1 12:00PM
  15. #hashtable
  16. def solve(events):
    .1point3acres缃
  17.         dict={}# key: sessionID, value would be eventname sorted by timestamp
  18. for elem in events:       
  19.                 if elem.sessionId not in dict:
  20.                         dict[elem.sessionId]=elem
  21.                 elif elem.timestamp>dict[elem.sessionId].timestamp:
  22.                         dict[elem.sessionId]=elem. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  23. res=[]. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  24. for elem in dict:
  25.         res.append(dict[elem])
  26. return res


  27. . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  28. 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  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.         . 1point 3acres 璁哄潧

  33. .鐣欏璁哄潧-涓浜-涓夊垎鍦
  34. hand: 5 cards
  35. Write a function to detect whether a poker hand contains a “pair” (exactly 2 cards with the same value).. visit 1point3acres.com for more.
  36. ## given 5 cards

  37. class card:
  38.         def __init__(self,value,suit):
  39.                 self.value=value
  40.                 self.suit=suit
  41. #class hand:
  42. #        def __init__(self,n):. 鍥磋鎴戜滑@1point 3 acres
  43. #                self.n=n. 1point 3acres 璁哄潧
  44. #                self.hand=[]
  45. #        def getcard(self,card):
  46. #                self.hand.append(card)
  47.        
  48. #list of cards=>hand. 1point3acres.com/bbs
  49. #nlog(n) time sort by its value  give me the result 3, 8 eight?
  50. #hash
  51. # linear time and space
  52. def check(hand):
  53.         dict={}
  54.         for card in hand:
  55.                 if card.value not in dict:
  56.                         dict[card.value]=1
  57.                 else:
  58.                         dict[card.value]+=1
  59.         ## check whether  I have a pair
  60.         for elem in dict:
  61.                 if dict[elem]==2:. From 1point 3acres bbs
  62.                         return True
  63.         return False
  64. . Waral 鍗氬鏈夋洿澶氭枃绔,
  65. # determine whether the hand contains a “straight”: values are consecutive. 鍥磋鎴戜滑@1point 3 acres
  66. # Ace can be high or low. 1point3acres.com/bbs
  67. # A, 2, 3, 4, 5 is a straight
  68. # 4, 5, 6, 7, 8 is a straight.鐣欏璁哄潧-涓浜-涓夊垎鍦
  69. # 10, J, Q, K, A is also a straight       
  70. # replace A with both 1 and 14
  71. # sort nlog(n)
  72. # 7,8,9,10,A -> 7,8,9,10,1,14
  73. # 10,11,12,13,A-> 10,11,12,13,14,1
  74. # go through the sorted array of cards to check whether they are consecutive
  75. # this take nlogn time
  76. # hash to detect consecutive cards

  77. -google 1point3acres



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

  81. for cardelem in hand:
  82.         ## first step deal with A
  83. if cardelem.value=’A’: 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  84.         newcard=card(14,’spade’)
  85.         cardelem.value=1
  86. hand.append(newcard)
  87. dict={}
  88. -google 1point3acres
  89. for cardelem in dict:
  90.         if cardelem not in dict:
  91.                 dict[cardelem.value]=True       
  92.                      count=1
  93.                 maxlen=1 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  94.                 for key in dict:
  95.                         count=1
  96.                         pre=key-1. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  97.                         while pre in dict and dict[pre]:
  98.                                 count+=1
  99.                                 dict[pre]=False
  100.                                 pre-=1. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  101.         ## 6,7<-8 ->9 10
  102.                         post=key+1. 1point3acres.com/bbs
  103.                         while post in dict and dict[post]:
  104.                                 count+=1.鏈枃鍘熷垱鑷1point3acres璁哄潧
  105.                                 dict[post]=False
  106.                                 post+=1. more info on 1point3acres.com
  107.                         maxlen=max(maxlen,count)
  108.         if maxlen==5:.1point3acres缃
  109.                 return True
  110.         else:       
  111.                 return False
  112.                
  113. #linear time and space. from: 1point3acres.com/bbs
  114. #

  115. . more info on 1point3acres.com
  116.        
  117. Ace of Spades. visit 1point3acres.com for more.
  118. 3 of diamonds
  119. 8 of clubs
  120. 8 of hearts. From 1point 3acres bbs
  121. J of diamonds
复制代码
. 1point 3acres 璁哄潧
补充内容 (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 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
第三题 可以 这么办
一个boolean A, A是否出现. 1point3acres.com/bbs
一个max,一个min
A不计入max,min,length
一圈下来. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
if(A){
    if((min == 2 || max == 13) && max-min +1 == 4) return true;
    else return false;
}
else{.鏈枃鍘熷垱鑷1point3acres璁哄潧
  if(max-min +1 == 5) return true;. 1point 3acres 璁哄潧
  else return false;
}. visit 1point3acres.com for more.

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

评分

1

查看全部评分

回复 支持 3 反对 0

使用道具 举报

fishyuze 发表于 2015-3-18 09:21:01 | 显示全部楼层
关注一亩三分地微博:
Warald
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. 1point 3acres 璁哄潧
                        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
跪求lz解释这段代码

              for key in dict:

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

使用道具 举报

Reborn2beCoder 发表于 2015-3-18 08:56:46 | 显示全部楼层
池大侠 发表于 2015-3-18 08:47. 1point 3acres 璁哄潧
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.
that's y its linear
回复 支持 反对

使用道具 举报

Reborn2beCoder 发表于 2015-3-18 09:37:50 | 显示全部楼层
池大侠 发表于 2015-3-18 09:22. from: 1point3acres.com/bbs
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-6-29 01:56

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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