狗家Fall Intern电面

knight0clk 发表于 2017-7-11 12:24
问下，楼主当时把第二题A掉了？

啥叫A掉了，并没有做对，所以跪了。。

knight0clk 发表于 2017-7-11 12:27
谢谢，分析的很好，但是楼主说了一个条件，“但骰子数量可以很多”，那是不是说每一种骰子有任意多个？如 ...

不一定的，她给我举的例子，有同样的好几个骰子，也有只有一个的

knight0clk 发表于 2017-7-11 12:27
谢谢，分析的很好，但是楼主说了一个条件，“但骰子数量可以很多”，那是不是说每一种骰子有任意多个？如 ...

不一定的，她给我举的例子里面有同样的骰子好几个的，也有都不一样的，我说数量可以很多的意思是，骰子的数量可能会比target word的字母长度数量多

vegito2002 发表于 2017-7-12 11:20
秋季 intern 的题居然也这么难, 摸摸

是的，跪的心服口服

第一道题目有个疑问就是汇率之间会不会有矛盾？

比如说是否同时存在两组数据：
X, Y, R1
Y, X, R2
使得R1不等于1/R2？

或者是有三组数据：
X, Y, R1
Y, Z, R2
X, Z, R3
使得R1 * R2不等于R3？

如果没有矛盾的话就比较简单，可以建一个空间复杂度为O(n)的索引（n为币种数量）：
--------
建立一个有向图，每个币种为图上一个顶点。对于每一组数据 (X, Y, R)，建立一条有向边X -> Y，权值定为log(R)；再建一条反向的边Y -> X，权值定为-log(R)。

接下来，不妨设图是全联通的，不然我们可以用O(n)时间把图分成各个联通子图再处理。
任意选取图上一点S，用DFS或者BFS（时间为O(n)）求得S到图上所有点T的距离（S到它自己的距离为0），记在一个大小为n的数组dist里。

然后对于查询“X到Y的汇率”，结果就是exp(dist[S, Y] - dist[S, X])，使用O(1)时间。
--------


一点扩展的知识是这个问题非常适合用逻辑式语言来表达。
我们知道早期程序语言有“三大范式”：命令式、函数式和逻辑式（后来它们互相混合再混入OO）。
典型的逻辑式语言有Prolog/Datalog，非典型的但内核是逻辑模型的有SQL，混入其他语言的有list comprehension和进一步的for comprehension。

而这个问题用Datalog语言表达是这样的：

1. <p># 所有的已知事实放在这里</p><p>exchange_fact('USD', 'EUR', 0.87).</p><p>exchange_fact('USD', 'CNY', 6.79).</p><p>exchange_fact('CNY', 'JPY', 16.71).</p><p>exchange_fact('GBP', 'EUR', 1.12).</p><p>...</p><p>
   
2. </p><p># 推理规则</p><p># 规则1：如果已知事实中写了X到Y的汇率为R，那么X到Y的汇率就定为R。</p><p>exchange(X, Y, R) :- exchange_fact(X, Y, R).</p><p># 规则2：如果已知X到Y的汇率为S，那么Y到X的汇率就定为1/S。</p><p>exchange(X, Y, R) :- exchange(Y, X, S),</p><p>                     R is 1.0 / S.</p><p># 规则3：如果已知X到Z的汇率为S、Z到Y的汇率为T，那么X到Y的汇率就定为S*T。</p><p>exchange(X, Y, R) :- exchange(X, Z, S),</p><p>                     exchange(Z, Y, T),</p><p>                     R is R0 * R1.</p><p>
   
3. </p><p># 查询</p><p>? exchange('GBP', 'CNY', R).</p><p>? exchange('EUR', 'JPY', R).</p><p>...</p>

复制代码

magicsets 发表于 2017-7-12 12:59
第一道题目有个疑问就是汇率之间会不会有矛盾？

比如说是否同时存在两组数据：

代码排版出问题了 ，重发一下..

# 所有的已知事实放在这里
exchange_fact('USD', 'EUR', 0.87).
exchange_fact('USD', 'CNY', 6.79).
exchange_fact('CNY', 'JPY', 16.71).
exchange_fact('GBP', 'EUR', 1.12).
...

# 推理规则

# 规则1：如果已知事实中写了X到Y的汇率为R，那么X到Y的汇率就定为R。
exchange(X, Y, R) :- exchange_fact(X, Y, R).

# 规则2：如果已知X到Y的汇率为S，那么Y到X的汇率就定为1/S。
exchange(X, Y, R) :- exchange(Y, X, S), R is 1.0 / S.

# 规则3：如果已知X到Z的汇率为S、Z到Y的汇率为T，那么X到Y的汇率就定为S*T。
exchange(X, Y, R) :- exchange(X, Z, S), exchange(Z, Y, T), R is R0 * R1.

# 查询
? exchange('GBP', 'CNY', R).
? exchange('EUR', 'JPY', R).
...

magicsets 发表于 2017-7-12 12:59
第一道题目有个疑问就是汇率之间会不会有矛盾？

比如说是否同时存在两组数据：

我看第一题的第一反应也是用dijastra求最优汇率，而不是求是不是这种钱可以换成那种钱

magicsets 发表于 2017-7-12 12:59
第一道题目有个疑问就是汇率之间会不会有矛盾？

比如说是否同时存在两组数据：

我当时听她的意思是不会有这种矛盾的，只需要search到然后计算出来就行

楼主面试之后多久给的回复呀。～

fengqi1994 发表于 2017-7-13 06:47
楼主面试之后多久给的回复呀。～

快一周的时间，挺快的