Oct 06 2007
一道google面试题
同学去google面试，有一道题是这样的：
(1)一副扑克牌，去掉大小王，然后从中抽取出一张牌，请用最小的时间复杂度和空间复杂度算出抽出的牌的值是多大，不考虑花色。
我的解法最小是，时间复杂度是o(n)，空间复杂度是1。
把剩下的51张牌的值加起来，保存在变量a中，然后，364-a就得到被抽出的牌的值了。
(2)如果从这副牌中抽取出两张，请用最小的时间复杂度和空间复杂度算出抽出的牌的值是多大，不考虑花色。
这个题的时间复杂度是o(n)，空间复杂度是2。
把剩下的50张牌的值加起来，保存在变量a中。把这50张牌的乘积保存在变量b中。
然后我们得到了一个二元方程组：
设被抽出的两张牌的值是x和y，则
x+y=364-a
x*y=(13!)^4-b (13的阶乘的4次方减b)
x,y为整数，并且 1 <= x,y <= 13
然后解这个方程组就得到两张牌的值了。
题不难，关键是能不能在面试的压力下快速做出。
随机文章 | Random Posts
上一篇：« 一道google笔试题
下一篇：UC Berkeley开放视频课程 »
GNote.Net | 记笔记
Orz，还题不难，关键是能不能在面试的压力下快速做出呢…你后面那个都要用到大整数乘法和除法了，
一个替换的方案，一个算和，一个算平方和就好了。其实一样的，但考虑到整数范围就不一样了。
btw，你同学没钱过ＯＤＥ么？面试题目一年之内是不能公开和讨论的。
多谢指出问题，用平方和是好办法