2007-05-13
Another Google question - drop glassballs from a building 5
关键字: glass ball building
Here are some results are the testcases:
1. PathFindTest.test4Ball100Floors():
The result is like this:
path=(f=56, b=3, whole, tried)-->(f=91, b=3, broken, tried)-->(f=71, b=2, broken, tried)-->(f=61, b=1, whole, tried)-->(f=65, b=1, whole, tried)-->(f=68, b=1, whole, tried)-- ...
- 04:01
- 浏览 (286)
- 评论 (0)
- 分类: algorithms
2007-05-13
Another Google question - drop glassballs from a building 4
关键字: glass ball building
The test cases are divided into 3 classes.
The first one is just a pinpoint test class that contains some corner cases:
java 代码
package glassball;
import junit.framework.TestCase;
import java.util.List; &n ...
- 03:42
- 浏览 (247)
- 评论 (0)
- 分类: algorithms
2007-05-13
Another Google question - drop glassballs from a building 3
关键字: glass ball building
The next step is to find the actually path of floors that we are going through to find the breaking floor. Here is the code to do that.
java 代码
package glassball;
import java.util.List;
import java.util.ArrayList; ...
- 03:33
- 浏览 (286)
- 评论 (0)
- 分类: algorithms
2007-05-13
Another Google question - drop glassballs from a building 2
关键字: glass ball building
Here is the code following the logic from the previous post:
java 代码
package glassball;
import java.util.List;
import java.util.ArrayList;
/**
* Google ...
- 03:02
- 浏览 (270)
- 评论 (0)
- 分类: algorithms
2007-05-12
Another Google question - drop glassballs from a building 1
关键字: glass ball building
Here is the question:
原题: 有一个100层高的大厦,你手中有两个相同的玻璃围棋子。从这个大厦的某一层扔下围棋子就会碎,用你手中的这两个玻璃围棋子,找出一个最优的策略,来得知那个临界层面。
I copied and pasted the above since I can't type Chinese most of the time. A google yield a few articles that I copied too:
为了得到两个棋子的最优策略，我们先简化问题，看看一个棋子的情况。如果手中只有一个棋子，为了得知临界层面，你只有一 ...
- 04:43
- 浏览 (313)
- 评论 (0)
- 分类: algorithms
The Utils class is composed of some common methods:
java 代码
package solve;
import scale.Ball;
import scale.Scale;
import java.util.Iterator;
import jav ...
- 05:54
- 浏览 (325)
- 评论 (0)
- 分类: algorithms
In the 1-ball case, if the status flag is already set, then we don't need to weight anymore. Otherwise, we need to find a good ball to compare.
java 代码
package solve;
import scale.Ball;
import scale.Scale; &nbs ...
- 05:50
- 浏览 (344)
- 评论 (0)
- 分类: algorithms
Now it comes to the Scale class. The main job of it is to weight both sides. So the class is pretty simple, sum the weights of balls and compare.
Now based on these classes, the translation of the algorithm is straight forward:
java 代码
package solve;
&nbs ...
- 05:29
- 浏览 (355)
- 评论 (0)
- 分类: algorithms
The problem is:
There is one counterfeit coin among 12 coins. It is unknown whether the counterfeit is lighter or heavier than a genuine coin(all genuine coins weigh the same). Using 3 weighings on a pan balance, how can the counterfeit be identified and determined to be lighter or heavier than ...
- 04:49
- 浏览 (296)
- 评论 (0)
- 分类: algorithms
The roadmap to compute all fixed points of f(x) is to start from boundaries 1, or 10^10, and keep acting f on it. If x is a boundary point, first compare x and f(x) to see whether we should generate the series using f or f inverse. Once we know which one to use, then keep doing that until we get a f ...
- 02:36
- 浏览 (287)
- 评论 (0)
- 分类: algorithms
The entire class is as follows:
java 代码
/**
* GOOGLE GLAT question #20:
* Consider a function which, for a given whole number n, returns the number
* of o ...
- 02:36
- 浏览 (328)
- 评论 (0)
- 分类: algorithms
Now, we can deduct the recursion formula on digits
Lemma 4
Let
n = a_k * 10^k + a_(k-1) * 10^(k-1) + ....... + a_1 * 10 + a_0
denote the base 10 expansion, then
when a_k = 1
(A) f(n) = f(n - 10^k) + (n - 10^k) + f(10^k) = f(n - 10^k) + (n - 10^k) + k * 10^ ...
- 02:24
- 浏览 (293)
- 评论 (0)
- 分类: algorithms
Question:
Consider a function which, for a given whole number n, returns the number of ones required when writing out all numbers between 0 and n. For example, f(13) = 6. Notice that f(1) = 1. What's the next largest n such that f(n) = n?
As always, start with simple cases:
f(1) = 1,
f(2 ...
- 02:22
- 浏览 (313)
- 评论 (0)
- 分类: algorithms
评论排行榜