What Is S?
June 27, 2017
We have something different today. Given this code:
int s = 0;
for (int i=0; i<x; i++)
for (int j=i+1; j<y; j++)
for (int k=j+1; k<z; k++)
s++;
What is s? What is a closed-form formula for computing s?
Your task is to compute s. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
So maybe I don’t qualify for an entry-level software engineer. But with x and y uninitialized, things are quite tacky. Anyhow, I’ve tried that code in ideone.com with x and y simply declared as int. The output was s = 0.
@Milbrae: I’m sorry, I obviously didn’t specify the question precisely. Here is a function s:
(define (s x y z) (let ((s 0)) (do ((i 0 (+ i 1))) ((<= x i) s) (do ((j (+ i 1) (+ j 1))) ((<= y j)) (do ((k (+ j 1) (+ k 1))) ((<= z k)) (set! s (+ s 1)))))))That works fine if x, y and z are small. But if they are large, the loops will never finish, and you won’t know the answer. Thus, you need to write a function
that produces the same result as s but without performing loops; it should operate in time O(1) instead of O(xyz).
I believe there is a typo in your problem statement. The bound for your third loop is x while your scheme code has a third loop bound of z. Since the latter is nicer and more symmetric, I will assume that it is correct. In that case, finding the closed form is a simple exercise in simplifying summations. Start from $\sum_{i=0}^{x-1}\sum_{j=i+1}^{y-1}\sum_{k=j+1}^{z-1} 1$ and push symbols around to get (2x + 3x^2 + x^3 – 3xy -3xy^2 + z(6xy-3x^2-3x))/6.
@Serge: z is correct. I fixed the problem statement. Thank you.
I think your solution is incorrect:
(define (f x y z) (+ (* 2 x) (* 3 x x) (* x x x) (- (* 3 x y)) (- (* 3 x y y)) (/ (* z (+ (* 6 x y) (- (* 3 x x)) (- (* 3 x)))) 6)))That doesn’t agree with the calculation of s in the previous comment. Your solution doesn’t use z, so I don’t see how it can be correct.
A slight amendment to my answer: I assumed that x<=y<=z in my closed form. Otherwise the returned value should be 0, of course.
Your division is at the wrong place. Here is a python version:
def mystery_s_1(x, y, z): return (2*x + 3*x**2 + x**3 - 3*x*y - 3*x*y**2 + z*(6*x*y-3*x**2-3*x))/6And is you execute this
@Serge: Fixed:
(define (f x y z) (/ (+ (* 2 x) (* 3 x x) (* x x x) (- (* 3 x y)) (- (* 3 x y y)) (* z (- (* 6 x y) (* 3 x x) (* 3 x)))) 6))Thank you. I knew the solution was a triple sum, and the final formula would be similar to the formulas for figurate numbers, but my math-fu wasn’t strong enough to work through the sum.
If this really is an interview question for software engineers, it is meant to eliminate a lot of people. The only type of place where this question makes sense is for a job at the MathWorks, or Maple, or Mathematica (or some place similar). And even then, it better be for a job working deep down in the bowels of the symbolic algebra engine. But, of course, if you want a job at Maple, you better know how to ask Maple to simplify the triple summation. Maybe that is the point of the question after all :-)
@Serge: I found the question at Career Cup, where it is titled “Amazon Interview Question for SDE1s”. None of the 40 answers at the page were correct, and I didn’t manage to solve it, either, though I think I would have given enough time; I knew the triple sum, but I couldn’t expand it properly. I agree it’s a very specific question useful only for hiring for a very specific position. Or else a sadistic interviewer wants to watch your stumbling attempt at a solution.
I’ll edit the solution page to include your solution.
Serge’s solution assumes x <= y <= z. There are however many non-zero solutions for cases where this condition does not hold. So I feel, the problem is not yet fully cracked.
Here’s four consecutive versions in C99. First the original copy-paste with tricky bounds. Second, index manipulation suggested that the sum counts distinct-index triples where the middle index has an extra bound that makes the obvious binomial coefficient useless, but the loops can be rearranged to have the middle index-index loop outermost; also replace the two limits with appropriate natural numbers, carefully. Third, the inner loops are independent of each other now, and they really count just the number of indices between their bounds, so they become a simple product, though again very carefully. Fourth, the remaining sum splits into two standard sums: the one that everyone knows to do the way Gauss did it in kindergarten, and the sum of squares that is best looked up, except remember to exclude the upper bound. That gives the closed form.
#include <stdio.h> #include <math.h> int s(double x, double y) { // original int s = 0; for (int i=0; i<x; i++) for (int j=i+1; j<y; j++) for (int k=j+1; k<x; k++) s++; return s; } int z(double x, double y) { // rearrangement int m = fmax(0, fmin(ceil(x), ceil(y))); int n = fmax(0, ceil(x)); int s = 0; for (int j=0 ; j < m ; ++j) for (int i=0 ; i < j ; ++i) for (int k = j + 1 ; k < n ; ++k) ++s; return s; } int u(double x, double y) { // combinatorics int m = fmax(0, fmin(ceil(x), ceil(y))); int n = fmax(0, ceil(x)); int s = 0; for (int j=0 ; j < m ; ++j) s += j * (n - 1 - j); return s; } int w(double x, double y) { // summanipulation int m = fmax(0, fmin(ceil(x), ceil(y))); int n = fmax(0, ceil(x)); return (n - 1) * m * (m - 1) / 2 - (m * (m + 1) * (2 * m + 1) / 6 - m * m); } void out(double x, double y) { // comparison printf("s(%f, %f) == %d == %d == %d == %d\n", x, y, s(x, y), z(x, y), u(x, y), w(x, y)); } int main() { out(3, 1); out(3, 14); out(3.1, 4); out(31, 4.1); out(31, 5); out(31, 41); out(41, 31); }Test shows that the four versions give the same results for the test cases. Output is like so.
So, apparently you have to do y = min(y, z) and x = min(x, y). Then it works great. I missed that.
So I just had to work it out for the updated version, too, with different bound for each index.
I analyze the original triple sum as two triple sums, with the middle index again outermost, that are easy to simplify because the inner sums do not depend on each other. The second triple sum deals with the case where the bound for the first index is stricter than for the middle index. It is empty if this is not the case.
The rest is rather mechanical if one knows something about sums but I couldn’t leave it be: here’s all four versions again, the fourth being the closed form, and then a somewhat extensive test function to show that the four versions seem to give the same results.
#include <stdio.h> #include <math.h> int s0(double x, double y, double z) { // new original int s = 0; for (int i=0; i<x; i++) for (int j=i+1; j<y; j++) for (int k=j+1; k<z; k++) s++; return s; } int s1(double x, double y, double z) { // analysis int m = fmax(0, fmin(ceil(x), fmin(ceil(y), ceil(z)))); int w = fmax(0, fmin(ceil(y), ceil(z))); int n = fmax(0, ceil(z)); int s = 0; for (int j = 0 ; j < m ; ++j) for (int i = 0 ; i < j ; ++i) for (int k = j + 1 ; k < n ; ++k) ++s; for (int j = m ; j < w ; ++j) for (int i = 0 ; i < m ; ++i) for (int k = j + 1 ; k < n ; ++k) ++s; return s; } int s2(double x, double y, double z) { // combinatorics int m = fmax(0, fmin(ceil(x), fmin(ceil(y), ceil(z)))); int w = fmax(0, fmin(ceil(y), ceil(z))); int n = fmax(0, ceil(z)); int s = 0; for (int j = 0 ; j < m ; ++j) s += j * (n - 1 - j); for (int j = m ; j < w ; ++j) s += m * (n - 1 - j); return s; } int s3(double x, double y, double z) { // summanipulation int m = fmax(0, fmin(ceil(x), fmin(ceil(y), ceil(z)))); int w = fmax(0, fmin(ceil(y), ceil(z))); int n = fmax(0, ceil(z)); int s = 0; s += (n - 1) * m * (m - 1) / 2; s -= m * (m + 1) * (2 * m + 1) / 6 - m * m; s += m * (w - m) * (2 * n - m - w - 1) / 2; return s; } void out(double x, double y, double z) { // comparison printf("s(%f, %f, %f) == %d == %d == %d == %d\n", x, y, z, s0(x, y, z), s1(x, y, z), s2(x, y, z), s3(x, y, z)); } int main() { for (int x = 0 ; x < 10 ; ++ x) for (int y = 0 ; y < 10 ; ++ y) for (int z = 0 ; z < 10 ; ++ z) for (double d = 0.0 ; d < 0.15 ; d += 0.1) out(x + d, y + d, z + d); return 0; }Same in Python, with the addition of a slightly simplified closed form, still in terms of the appropriate minima (and ceilings of fractional bounds, and negative bounds clamped to zero).
from math import ceil def s(x0, y0, z0): x, y, z = map(ceil, (x0, y0, z0)) s0 = sum(1 for i in range(0, x) for j in range(i + 1, y) for k in range(j + 1, z)) m, w, n = (max(0, u) for u in (min(x, y, z), min(y, z), z)) s1 = (sum(1 for j in range(0, m) for i in range(0, j) for k in range(j + 1, n)) + sum(1 for j in range(m, w) for i in range(0, m) for k in range(j + 1, n))) s2 = (sum(j * (n - 1 - j) for j in range(0, m)) + sum(m * (n - 1 - j) for j in range(m, w))) s3 = ((n - 1) * m * (m - 1) // 2 - (m * (m + 1) * (2 * m + 1) // 6 - m * m) + m * (w - m) * (2 * n - m - w - 1) // 2) s4 = m * (3 * n * (w - m - 1) + 3 * w * (n - w - 1) + m * (m + 3) + 2) // 6 return s0, s1, s2, s3, s4 # s(2, 4, 6) == (14, 14, 14, 14, 14) # s(4, 2, 6) == (4, 4, 4, 4, 4)This can be solved combinatorically, which provides another way to see the closed expression.
Visualize the number line as the following 3 parts, where the boundaries represents the limits 0, x, y, z.
| A | B | C |
—-x—y—z
Then the question becomes how many ways are there to choose three numbers such that at least 1 is <= x, 1 is <= y, 1 is <= z. Note that once three numbers are chosen, there is only one way to assign them to i, j, and k.
Next we count them by considering the different disjoint cases.
Case 1: all three are in block A = x choose 3
Case 2: 2 are in block A, one is B or C = (x choose 2) * (z-x)
Case 3: 1 is in block A, 2 is in B = x * ((y-x) choose 2)
Case 4: 1 is in block A, 1 in B and 1 in C = x * (y-x) * (z-y)
For a more visual form:
https://www.wolframalpha.com/input/?i=(x+choose+3)+%2B+(x+choose+2)+*+(z-x)+%2B+x+*+((y-x)+choose+2)+%2B+x+*+(y-x)+*+(z-y),+x%3D+2,+y+%3D+4,+z+%3D+6