A Google's Interview Question - GLAT #20 series 3 博客分类: algorithms GoogleF#RESTGoperformance
程序员文章站
2024-03-07 12:30:15
...
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 fixed point. Then start from the next integer again.
In order to do these, we need a few functions:
1. function f:
This is basically a direct translate of the formula (A) and (B) in Lemma 4.
2. inverse of f:
Obviously the next one is f inverse. Since f is not single valued, we have to have a better definition on the inverse. We define the inverse of f for a given y as the smallest x such that x < y <= f(x), so we could step as far as possible.
The tricky part here is to figure out the power k. Here in order to know whether we should use formula (A) or (B), we need to check whether the to-be-found x has leading 1. So the helper function is
where we define the following
The other missing piece is the function foundRoot(). This is used in formula (A), which can be simplified in the form x + f(x) = y, with unknown x. We need a function to find the root x.
Two other small functions are:
which computes the number of 1's in x, and
which computes the power for the performance reason. With all of these in places, the only thing left is a "conductor" method:
The result is:
-----> found a fixed point: x=1111111110
-----> found a fixed point: x=535200001
-----> found a fixed point: x=535200000
-----> found a fixed point: x=535199990
-----> found a fixed point: x=535199989
-----> found a fixed point: x=535199988
-----> found a fixed point: x=535199987
-----> found a fixed point: x=535199986
-----> found a fixed point: x=535199985
-----> found a fixed point: x=535199984
-----> found a fixed point: x=535199983
-----> found a fixed point: x=535199982
-----> found a fixed point: x=535199981
-----> found a fixed point: x=535000001
-----> found a fixed point: x=535000000
-----> found a fixed point: x=513199998
-----> found a fixed point: x=502600001
-----> found a fixed point: x=502600000
-----> found a fixed point: x=501599990
-----> found a fixed point: x=501599989
-----> found a fixed point: x=501599988
-----> found a fixed point: x=501599987
-----> found a fixed point: x=501599986
-----> found a fixed point: x=501599985
-----> found a fixed point: x=501599984
-----> found a fixed point: x=501599983
-----> found a fixed point: x=501599982
-----> found a fixed point: x=501599981
-----> found a fixed point: x=500200001
-----> found a fixed point: x=500200000
-----> found a fixed point: x=500199990
-----> found a fixed point: x=500199989
-----> found a fixed point: x=500199988
-----> found a fixed point: x=500199987
-----> found a fixed point: x=500199986
-----> found a fixed point: x=500199985
-----> found a fixed point: x=500199984
-----> found a fixed point: x=500199983
-----> found a fixed point: x=500199982
-----> found a fixed point: x=500199981
-----> found a fixed point: x=500000001
-----> found a fixed point: x=500000000
-----> found a fixed point: x=117463825
-----> found a fixed point: x=35200001
-----> found a fixed point: x=35200000
-----> found a fixed point: x=35199990
-----> found a fixed point: x=35199989
-----> found a fixed point: x=35199988
-----> found a fixed point: x=35199987
-----> found a fixed point: x=35199986
-----> found a fixed point: x=35199985
-----> found a fixed point: x=35199984
-----> found a fixed point: x=35199983
-----> found a fixed point: x=35199982
-----> found a fixed point: x=35199981
-----> found a fixed point: x=35000001
-----> found a fixed point: x=35000000
-----> found a fixed point: x=13199998
-----> found a fixed point: x=2600001
-----> found a fixed point: x=2600000
-----> found a fixed point: x=1599990
-----> found a fixed point: x=1599989
-----> found a fixed point: x=1599988
-----> found a fixed point: x=1599987
-----> found a fixed point: x=1599986
-----> found a fixed point: x=1599985
-----> found a fixed point: x=1599984
-----> found a fixed point: x=1599983
-----> found a fixed point: x=1599982
-----> found a fixed point: x=1599981
-----> found a fixed point: x=200001
-----> found a fixed point: x=200000
-----> found a fixed point: x=199990
-----> found a fixed point: x=199989
-----> found a fixed point: x=199988
-----> found a fixed point: x=199987
-----> found a fixed point: x=199986
-----> found a fixed point: x=199985
-----> found a fixed point: x=199984
-----> found a fixed point: x=199983
-----> found a fixed point: x=199982
-----> found a fixed point: x=199981
-----> found a fixed point: x=1
It takes 62 milli
It takes 1139 iterations.
This is a typical fixed point problem, start from some arbitrary number and keep acting f on it. Several outputs of the series are:
1. It goes to infinity.
2. It goes to some fixed point.
3. It keeps bouncing back and forth(going nowhere).
Two types of fixed points are attractors and opposite attractors. Attractors are attracting nearby points, i.e., if we start from some point "close" enough to the attractor, the series will converge to the attractor. Opposite attractor is just the opposite, the series will go away from the opposite attractor.
In order to do these, we need a few functions:
1. function f:
java 代码
- private long numOfOnes(long x)
- {
- // recursion stops
- if (x <= 0) return 0;
- if (x == 1) return 1;
- int powerk = 0;
- long tenPowers = 1;
- long leadingDigit = x;
- while (leadingDigit >= 10)
- {
- leadingDigit /= 10;
- powerk++;
- tenPowers *= 10;
- }
- long reminder = x - leadingDigit * tenPowers;
- if (leadingDigit == 1)
- {
- return powerk * tenPowers / 10 + 1 + reminder + numOfOnes(reminder);
- }
- else
- {
- return leadingDigit * powerk * tenPowers / 10 + tenPowers + numOfOnes(reminder);
- }
- }
This is basically a direct translate of the formula (A) and (B) in Lemma 4.
2. inverse of f:
Obviously the next one is f inverse. Since f is not single valued, we have to have a better definition on the inverse. We define the inverse of f for a given y as the smallest x such that x < y <= f(x), so we could step as far as possible.
java 代码
- public long inverseFunc(long y)
- {
- // recursion default.
- if (y <= 0) return 0;
- if (y == 1) return 1;
- if (y == 2) return 10;
- // check whether y is in 1's range
- int m = isInOneRange(y);
- if (m != -1)
- {
- long tmp = y - (m + 1) * power(10, m) - 1;
- long inc = findRoot(tmp);
- return power(10, m + 1) + inc;
- }
- else
- {
- int k = numOfDigits(y) - 1;
- long tmp = y - power(10, k);
- long ak = tmp / (k * power(10, k - 1));
- if (ak > 9) ak = 9; // leave the rest to the recursion
- long remainder = tmp - ak * k * power(10, k - 1);
- long xRemainder = inverseFunc(remainder);
- return ak * power(10, k) + xRemainder;
- }
- }
The tricky part here is to figure out the power k. Here in order to know whether we should use formula (A) or (B), we need to check whether the to-be-found x has leading 1. So the helper function is
java 代码
- private int isInOneRange(long y)
- {
- // This is to check whether the func value is between the function
- // values of 10^n and 2*10^n.
- // this can be done faster since it's sorted, but again I am lazy
- int k=-1;
- for (int i=0; i<9; i++)
- {
- if (y <= y2[i])
- {
- k = i;
- break; // first smaller, break out
- }
- }
- if (k==-1) return -1;
- if (y >= y1[k]) return k;
- else return -1;
- }
where we define the following
java 代码
- long[] x1 = new long[9];
- long[] x2 = new long[9];
- long[] y1 = new long[9];
- long[] y2 = new long[9];
- for (int i=1; i<10; i++)
- {
- x1[i-1] = power(10, i);
- x2[i-1] = 2 * x1[i-1] - 1;
- y1[i-1] = numOfOnes(x1[i-1]);
- y2[i-1] = numOfOnes(x2[i-1]);
- }
- If we print out them:
- x range=[10, 19] y range=[2, 12]
- x range=[100, 199] y range=[21, 140]
- x range=[1000, 1999] y range=[301, 1600]
- x range=[10000, 19999] y range=[4001, 18000]
- x range=[100000, 199999] y range=[50001, 200000]
- x range=[1000000, 1999999] y range=[600001, 2200000]
- x range=[10000000, 19999999] y range=[7000001, 24000000]
- x range=[100000000, 199999999] y range=[80000001, 260000000]
- x range=[1000000000, 1999999999] y range=[900000001, 2800000000]
The other missing piece is the function foundRoot(). This is used in formula (A), which can be simplified in the form x + f(x) = y, with unknown x. We need a function to find the root x.
java 代码
- public long findRoot(long y)
- {
- // find a root for x + f(x) = y, where f is the number of one's function
- // in the above.
- // we need a x such that x + f(x)>=y, the largest x.
- // Note that x + f(x) is a mononically increasing function.
- long x0 = 0;
- long x1 = y;
- long x;
- while (x1 - x0 > 1)
- {
- x = x0 + (x1 - x0) / 2;
- long func = numOfOnes(x) + x;
- if (func == y) return x;
- if (func < y)
- {
- x0 = x;
- }
- else
- {
- x1 = x;
- }
- }
- if (x0 + numOfOnes(x0) == y) return x0;
- else return x1;
- }
Two other small functions are:
java 代码
- private static int numOfDigits(long x)
- {
- int i = 0;
- while (x > 0)
- {
- x /= 10;
- i++;
- }
- return i;
- }
which computes the number of 1's in x, and
java 代码
- private static long power(long base, int power)
- {
- long ret = 1;
- for (int i=1; i<=power; i++) ret *= base;
- return ret;
- }
which computes the power for the performance reason. With all of these in places, the only thing left is a "conductor" method:
java 代码
- public void countDigitOne()
- {
- long begin = System.currentTimeMillis();
- long loop = 10000000000L;
- int iterationTimes = 1;
- while (loop > 0 && iterationTimes < ITERATION_LIMIT)
- {
- long func = numOfOnes(loop);
- if (func == loop)
- {
- System.out.println("-----> found a fixed point: x=" + loop);
- // now skip this one and keep going for the next one.
- loop--;
- }
- else
- {
- if (func < loop) // we force this to go to the left.
- {
- loop = func;
- }
- else // func > loop
- {
- func = inverseFunc(loop);
- if (func < loop && numOfOnes(func) >= loop)
- {
- loop = func;
- }
- else
- {
- loop --; // if we can't find one, just decrement it.
- }
- }
- }
- iterationTimes++;
- }
- System.out.println("It takes " + (System.currentTimeMillis() - begin) + " milli");
- System.out.println("It takes " + iterationTimes + " iterations");
- }
The result is:
-----> found a fixed point: x=1111111110
-----> found a fixed point: x=535200001
-----> found a fixed point: x=535200000
-----> found a fixed point: x=535199990
-----> found a fixed point: x=535199989
-----> found a fixed point: x=535199988
-----> found a fixed point: x=535199987
-----> found a fixed point: x=535199986
-----> found a fixed point: x=535199985
-----> found a fixed point: x=535199984
-----> found a fixed point: x=535199983
-----> found a fixed point: x=535199982
-----> found a fixed point: x=535199981
-----> found a fixed point: x=535000001
-----> found a fixed point: x=535000000
-----> found a fixed point: x=513199998
-----> found a fixed point: x=502600001
-----> found a fixed point: x=502600000
-----> found a fixed point: x=501599990
-----> found a fixed point: x=501599989
-----> found a fixed point: x=501599988
-----> found a fixed point: x=501599987
-----> found a fixed point: x=501599986
-----> found a fixed point: x=501599985
-----> found a fixed point: x=501599984
-----> found a fixed point: x=501599983
-----> found a fixed point: x=501599982
-----> found a fixed point: x=501599981
-----> found a fixed point: x=500200001
-----> found a fixed point: x=500200000
-----> found a fixed point: x=500199990
-----> found a fixed point: x=500199989
-----> found a fixed point: x=500199988
-----> found a fixed point: x=500199987
-----> found a fixed point: x=500199986
-----> found a fixed point: x=500199985
-----> found a fixed point: x=500199984
-----> found a fixed point: x=500199983
-----> found a fixed point: x=500199982
-----> found a fixed point: x=500199981
-----> found a fixed point: x=500000001
-----> found a fixed point: x=500000000
-----> found a fixed point: x=117463825
-----> found a fixed point: x=35200001
-----> found a fixed point: x=35200000
-----> found a fixed point: x=35199990
-----> found a fixed point: x=35199989
-----> found a fixed point: x=35199988
-----> found a fixed point: x=35199987
-----> found a fixed point: x=35199986
-----> found a fixed point: x=35199985
-----> found a fixed point: x=35199984
-----> found a fixed point: x=35199983
-----> found a fixed point: x=35199982
-----> found a fixed point: x=35199981
-----> found a fixed point: x=35000001
-----> found a fixed point: x=35000000
-----> found a fixed point: x=13199998
-----> found a fixed point: x=2600001
-----> found a fixed point: x=2600000
-----> found a fixed point: x=1599990
-----> found a fixed point: x=1599989
-----> found a fixed point: x=1599988
-----> found a fixed point: x=1599987
-----> found a fixed point: x=1599986
-----> found a fixed point: x=1599985
-----> found a fixed point: x=1599984
-----> found a fixed point: x=1599983
-----> found a fixed point: x=1599982
-----> found a fixed point: x=1599981
-----> found a fixed point: x=200001
-----> found a fixed point: x=200000
-----> found a fixed point: x=199990
-----> found a fixed point: x=199989
-----> found a fixed point: x=199988
-----> found a fixed point: x=199987
-----> found a fixed point: x=199986
-----> found a fixed point: x=199985
-----> found a fixed point: x=199984
-----> found a fixed point: x=199983
-----> found a fixed point: x=199982
-----> found a fixed point: x=199981
-----> found a fixed point: x=1
It takes 62 milli
It takes 1139 iterations.
This is a typical fixed point problem, start from some arbitrary number and keep acting f on it. Several outputs of the series are:
1. It goes to infinity.
2. It goes to some fixed point.
3. It keeps bouncing back and forth(going nowhere).
Two types of fixed points are attractors and opposite attractors. Attractors are attracting nearby points, i.e., if we start from some point "close" enough to the attractor, the series will converge to the attractor. Opposite attractor is just the opposite, the series will go away from the opposite attractor.
推荐阅读
-
A Google's Interview Question - GLAT #20 series 3 博客分类: algorithms GoogleF#RESTGoperformance
-
A Google's Interview Question - GLAT #20 series 1 博客分类: algorithms GoogleF#REST
-
A Google's Interview Question - GLAT #20 series 2 博客分类: algorithms GoogleF#UP
-
A Google's Interview Question - GLAT #20 series 2 博客分类: algorithms GoogleF#UP
-
A Google's Interview Question - GLAT #20 series 4 博客分类: algorithms GoogleF#RESTGoUP