當了一年的 Facebook Rotational Software Engineer 心得分享

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 1395|回复: 10
收起左侧

google phone ...bless

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

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

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

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

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

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. 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,.....]
  12. #linear space and linear time
  13. #time1 12:00PM. 围观我们@1point 3 acres
  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:
  19.                         dict[elem.sessionId]=elem
  20.                 elif elem.timestamp>dict[elem.sessionId].timestamp:
  21.                         dict[elem.sessionId]=elem
  22. res=[]
  23. for elem in dict:
  24.         res.append(dict[elem])
  25. return res

  26. .本文原创自1point3acres论坛


  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.        
    . 1point3acres

  31. hand: 5 cards.1point3acres网
  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)
  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
  49. def check(hand):
  50.         dict={}
  51.         for card in hand:
  52.                 if card.value not in dict:
  53.                         dict[card.value]=1. from: 1point3acres
  54.                 else:
  55.                         dict[card.value]+=1. from: 1point3acres
  56.         ## check whether  I have a pair
  57.         for elem in dict:
  58.                 if dict[elem]==2:
  59.                         return True
  60.         return False
  61. . 留学申请论坛-一亩三分地
  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
  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)-google 1point3acres
  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. from: 1point3acres
  72. # this take nlogn time
  73. # hash to detect consecutive cards. 1point 3acres 论坛





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

  77. for cardelem in hand:
  78.         ## first step deal with A
  79. if cardelem.value=’A’:.本文原创自1point3acres论坛
  80.         newcard=card(14,’spade’). 围观我们@1point 3 acres
  81.         cardelem.value=1
  82. hand.append(newcard)
  83. dict={}
  84. . from: 1point3acres
  85. for cardelem in dict:
  86.         if cardelem not in dict:
  87.                 dict[cardelem.value]=True       
  88.                      count=1
  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]:. From 1point 3acres bbs
  100.                                 count+=1
  101.                                 dict[post]=False. From 1point 3acres bbs
  102.                                 post+=1
  103.                         maxlen=max(maxlen,count)
  104.         if maxlen==5:
  105.                 return True
  106.         else:       
  107.                 return False. 1point3acres
  108.                
  109. #linear time and space
  110. #.本文原创自1point3acres论坛

  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 | 显示全部楼层
第三题 可以 这么办. From 1point 3acres bbs
一个boolean A, A是否出现. visit 1point3acres for more.
一个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;
}
. 1point 3acres 论坛
这样的话,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]:. Waral 博客有更多文章,
                                count+=1. Waral 博客有更多文章,
                                dict[pre]=False
                                pre-=1. visit 1point3acres for more.
        ## 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). 围观我们@1point 3 acres
回复 支持 反对

使用道具 举报

 楼主| 池大侠 发表于 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了呀。。还会继续运行吗>
. 一亩-三分-地,独家发布
yes.. just need to check once . if they are consecutive it doesnt matter.
that's y its linear
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

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 ?
回复 支持 反对

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-5-20 18:11

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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