In Microsoft campus recuitment contest, there is a problem which could use Dijkstra shortest path algorithm to solve. And I write a version whose time complexity is O(n2) in the contest, however, that makes me feel not very good. So I decide to have a good review of some ...
read moreThere are comments.
一共有4个题，时间是2个半小时。题目都在这儿。比赛时，只做了前面两道，第三道一直TLE。比赛结束后，经一个同学的指点，明白了第三题的原理。第四题的解答在这里，是一道还比较复杂的动态规划，我之后如果理解并且敲出来了，在和大家分享，这边先简单介绍一下前三道题的解题思路。
时间限制:10000ms 单点时限:1000ms 内存限制:256MB
The circus clown Sunny has a magic box. When the circus is performing, Sunny puts some balls into the box one by one. The ...
read moreThere are comments.
一道在蜻蜓FM面试的时候，出的算法题。题目是让在Young氏矩阵中查询一个数，并把他们的坐标都返回。
一个m x n的Young氏矩阵（Young tableau）是一个m x n的矩阵，其中每一行的数据都从左到右排序，每一列的数据都从上到下排序。Young氏矩阵中可能会有一些∞数据项，表示不存在的元素。所以，Young氏矩阵可以用来存放 r ≦ mn 个有限的数。
在面试的时候，我只想到了大致的思路，并没有写出完整的程序。之后思考了下，当时的思路还不够完整，许多方面都没有考虑到。接下来，我讲给出我之后想通了的两种解法。
题目很明显是可以用二分查找来做的，但是关键是如何二分。最先想到的合理方式是，通过左对角线找到的中点arr[n / 2][n / 2]，可以将矩阵分为4个部分。
如果 ...
read moreThere are comments.
北京时间2015年3月28日晚上9:00到12:00参加了一个由Bucknell University举办的编程比赛。在三个小时的过程中，我们队伍一共做出了8道题中的3道，得到Expert组第二名的好成绩。比赛的题目总体上不是很难，比较考验对算法的熟练程度和英文的阅读理解能力。很感谢有两位队友(沈多，仇晓逢)在比赛中的精彩发挥。
You are deep in the lair of guitar-loving Master Villain Guattery, better known as The Ax, and you’ve reached a chamber full of 16 safes. You’ve heard ...
read moreThere are comments.
在大规模数据集中寻找关系：
如何定量地定义关系？如何定义频繁？
以啤酒，尿布的故事为例，
支持度：数据集中包含该项集的记录所占的比例。比如一共有5条交易记录，其中4条出现了{尿布}，则尿布的支持度就为4/5。再比如，如果数据集中有3条同时出现了{尿布，啤酒}，则项集{尿布，啤酒}的支持度就为3/5。
置信度：针对关联规则定义。我们现在知道了{尿布}的支持度为4/5，{尿布，啤酒}的支持度为3/5，呢么{尿布}->{啤酒}的关联规则的可信度可以被定义为“支持度({尿布，啤酒})/支持度({尿布 ...
There are comments.
Page 1 / 1