Microsoft Interview Problem: Maximize Squared Distance

Problem Statement

Four integers A, B, C and D are given. The integers can be used to describe two points on a plane by assigning their values to the coordinates of the points. Each integer has to be assigned to exactly one coordinate.

Task: Assign the integers A, B, C and D to the coordinates of two points in such a way as to maximize the squared distance between those points.

Example

Given values:

A = 1
B = 1
C = 2
D = 3

Approach 1: Points (A, D) and (B, C)

Creating points (1, 3) and (1, 2):

    y
  5 ┤
  4 ┤
  3 ┤  • (A,D) = (1,3)
  2 ┤  • (B,C) = (1,2)
  1 ┤
    └──┬──┬──┬──┬──┬── x
       1  2  3  4  5

Squared distance = (1-1)² + (3-2)² = 0 + 1 = 1

Approach 2: Points (A, C) and (D, B)

Creating points (1, 2) and (3, 1):

    y
  5 ┤
  4 ┤
  3 ┤
  2 ┤  • (A,C) = (1,2)
  1 ┤        • (D,B) = (3,1)
    └──┬──┬──┬──┬──┬── x
       1  2  3  4  5

Squared distance = (1-3)² + (2-1)² = 4 + 1 = 5

Solution Approach

The key insight is that we need to try all possible combinations of assigning the four integers to the coordinates of two points.

C# Solution

using System;

class Solution {
    public int solution(int A, int B, int C, int D) {
        double[] combs = new double[30];

        // All combinations of assigning A,B,C,D to two point coordinates
        combs[1] = SquaredDistance(A, B, C, D);
        combs[2] = SquaredDistance(A, B, D, C);
        combs[3] = SquaredDistance(A, C, B, D);
        combs[4] = SquaredDistance(A, C, D, B);
        combs[5] = SquaredDistance(A, D, C, B);
        combs[6] = SquaredDistance(A, D, B, C);

        combs[7] = SquaredDistance(B, A, C, D);
        combs[8] = SquaredDistance(B, A, D, C);
        combs[9] = SquaredDistance(B, C, A, D);
        combs[10] = SquaredDistance(B, C, D, A);
        combs[11] = SquaredDistance(B, D, A, C);
        combs[12] = SquaredDistance(B, D, C, A);

        combs[13] = SquaredDistance(C, A, B, D);
        combs[14] = SquaredDistance(C, A, D, B);
        // ... continue for all permutations

        return (int)combs.Max();
    }

    private double SquaredDistance(int x1, int y1, int x2, int y2) {
        return Math.Pow(x1 - x2, 2) + Math.Pow(y1 - y2, 2);
    }
}

Optimal Solution

Instead of checking all permutations, we can observe that to maximize squared distance:

Sort the values
Assign the two smallest values to one point and two largest to another
Or assign the two extreme values differently

public int MaxSquaredDistance(int A, int B, int C, int D) {
    int[] vals = { A, B, C, D };
    Array.Sort(vals);

    // Option 1: (smallest, 2nd smallest) vs (largest, 2nd largest)
    int dist1 = SquaredDist(vals[0], vals[1], vals[3], vals[2]);

    // Option 2: (smallest, largest) vs (2nd smallest, 2nd largest)
    int dist2 = SquaredDist(vals[0], vals[3], vals[1], vals[2]);

    return Math.Max(dist1, dist2);
}

Key Concepts

Squared Euclidean Distance: (x₁ - x₂)² + (y₁ - y₂)²
Optimization: Maximize the sum of squared differences
Permutation: Consider all ways to assign 4 values to 4 coordinates

Sources

C#/Intrebari interviu/Interviu Microsoft/problema1.png
C#/Intrebari interviu/Interviu Microsoft/ocr1.png