《数据科学面试40+真题讲解》,K神本年度最后一次开课


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 1735|回复: 6
收起左侧

求问一道谷歌彩蛋题

[复制链接] |试试Instant~ |关注本帖
tank_z 发表于 2016-10-29 11:28:59 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 硕士 其他@Google - Other - 在线笔试 |Other其他

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

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

x
某日在谷歌搜索蹦出了个彩蛋叫foo.bar, 进去后让我做题有木有, 吓得我一愣一愣的。然后蹦出来这么一道题完全不知道怎么做。感觉像马尔科夫转移矩阵求stable state, 但是不会编啊 而且最后返回要求还是分数形式。。。 想了好久看是不是能用graph来做也不会。。。求问各位大神有没有思路。。
. From 1point 3acres bbs
Making fuel for the LAMBCHOP's reactor core is a tricky process because of the exotic matter involved. It starts as raw ore, then during processing, begins randomly changing between forms, eventually reaching a stable form. There may be multiple stable forms that a sample could ultimately reach, not all of which are useful as fuel.
. visit 1point3acres.com for more.
Commander Lambda has tasked you to help the scientists increase fuel creation efficiency by predicting the end state of a given ore sample. You have carefully studied the different structures that the ore can take and which transitions it undergoes. It appears that, while random, the probability of each structure transforming is fixed. That is, each time the ore is in 1 state, it has the same probabilities of entering the next state (which might be the same state).  You have recorded the observed transitions in a matrix. The others in the lab have hypothesized more exotic forms that the ore can become, but you haven't seen all of them.

Write a function answer(m) that takes an array of array of nonnegative ints representing how many times that state has gone to the next state and return an array of ints for each terminal state giving the exact probabilities of each terminal state, represented as the numerator for each state, then the denominator for all of them at the end and in simplest form. The matrix is at most 10 by 10. It is guaranteed that no matter which state the ore is in, there is a path from that state to a terminal state. That is, the processing will always eventually end in a stable state. The ore starts in state 0. The denominator will fit within a signed 32-bit integer during the calculation, as long as the fraction is simplified regularly.

For example, consider the matrix m:
[
  [0,1,0,0,0,1],  # s0, the initial state, goes to s1 and s5 with equal probability
  [4,0,0,3,2,0],  # s1 can become s0, s3, or s4, but with different probabilities
  [0,0,0,0,0,0],  # s2 is terminal, and unreachable (never observed in practice)
  [0,0,0,0,0,0],  # s3 is terminal
  [0,0,0,0,0,0],  # s4 is terminal
  [0,0,0,0,0,0],  # s5 is terminal
So, we can consider different paths to terminal states, such as:
s0 -> s1 -> s3
s0 -> s1 -> s0 -> s1 -> s0 -> s1 -> s4
s0 -> s1 -> s0 -> s5
Tracing the probabilities of each, we find that
s2 has probability 0
s3 has probability 3/14
s4 has probability 1/7
s5 has probability 9/14
So, putting that together, and making a common denominator, gives an answer in the form of
[s2.numerator, s3.numerator, s4.numerator, s5.numerator, denominator] which is
[0, 3, 2, 9, 14].

. 鍥磋鎴戜滑@1point 3 acres

本帖被以下淘专辑推荐:

weiwinn 发表于 2016-11-4 11:26:05 | 显示全部楼层
题主解决了吗,昨天也遇到这题,好像就是马尔科夫转移矩阵,感觉做起来好麻烦
回复 支持 反对

使用道具 举报

 楼主| tank_z 发表于 2016-11-4 11:50:01 | 显示全部楼层
做不出来 放弃了
回复 支持 反对

使用道具 举报

chasedream1 发表于 2017-9-13 13:05:44 | 显示全部楼层
这是第几关的题呀?
回复 支持 反对

使用道具 举报

crazytaxii 发表于 2017-9-20 09:37:41 | 显示全部楼层
chasedream1 发表于 2017-9-13 13:05. 1point 3acres 璁哄潧
这是第几关的题呀?
. visit 1point3acres.com for more.
我是在level 3遇到的
回复 支持 反对

使用道具 举报

crazytaxii 发表于 2017-9-20 09:37:53 | 显示全部楼层
一亩三分地严打"顶""好贴""收藏了"之类的垃圾回复帖!被警告三次,系统会自动封杀ID!
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
想支持楼主,请点击帖子下方的"好苗""分享""收藏"键,酌情给楼主加大米(系统不扣你自己的分)。
积分不够看不了帖子,请参考论坛导航里的"帮助","新手提纲"里有攒积分指南
回复 支持 反对

使用道具 举报

crazytaxii 发表于 2017-9-20 09:42:40 | 显示全部楼层
。。。不小心点到发表回复。说正题,这道题目的是求概率,难点在于如果S1有几率转换成S0,会陷入无限循环,但是这个也是可以通过列出表达式来计算的,可以简化成等比数列求和,当项数趋近于无穷时,自然会有0出现。
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-11-25 12:19

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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