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.

Advertisements

Pages: 1 2

15 Responses to “What Is S?”

  1. Milbrae said

    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.

  2. programmingpraxis said

    @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)))))))
    > (s 2 4 6)
    14

    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

    (define (f x y z) ...)

    that produces the same result as s but without performing loops; it should operate in time O(1) instead of O(xyz).

  3. Serge said

    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.

  4. programmingpraxis said

    @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)))
    > (f 2 4 6)
    -66

    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.

  5. Serge said

    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.

  6. Serge said

    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))/6
    

    And is you execute this

    mystery_s_1(2,4,6)
    14
    
  7. programmingpraxis said

    @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))
    > (f 2 4 6)
    14

    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.

  8. Serge said

    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 :-)

  9. programmingpraxis said

    @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.

  10. Paul said

    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.

  11. Jussi Piitulainen said

    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.

    s(3.000000, 1.000000) == 0 == 0 == 0 == 0
    s(3.000000, 14.000000) == 1 == 1 == 1 == 1
    s(3.100000, 4.000000) == 4 == 4 == 4 == 4
    s(31.000000, 4.100000) == 270 == 270 == 270 == 270
    s(31.000000, 5.000000) == 270 == 270 == 270 == 270
    s(31.000000, 41.000000) == 4495 == 4495 == 4495 == 4495
    s(41.000000, 31.000000) == 9145 == 9145 == 9145 == 9145
    
  12. Paul said

    So, apparently you have to do y = min(y, z) and x = min(x, y). Then it works great. I missed that.

  13. Jussi Piitulainen said

    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;
    }
    
  14. Jussi Piitulainen said

    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)
    
  15. dltw said

    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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: