Question

Google | OA | Online Coding Test Questions and Solutions | Set - 36 | 2022

Answer 1

 

def solution(segments):
    if len(segments) < 4:
        return -1
    import collections
    hmap = collections.Counter(segments)
    result = []
    for k, v in hmap.items():
        result.extend([k] * (v // 2))
    
    if len(result) < 2:
        return -1
    result = sorted(result)
    smallest = float("+inf")
    for i in range(1, len(result)):
        smallest = min(smallest, result[i] - result[i - 1])
    return smallest

Answer 2

You are given an array segments consisting of N integers denoting the lengths of several segments. Your task is to find among them four segments from which a rectangle can be constructed. What is the minimum absolute difference between the side lengths of the constructed rectangle?

 

Write a function:
int solution(int[] segments);

 

that, given an array segments, returns the minimum absolute difference between the side lenaths of the constructed rectangle or -1 if no rectangle can be constructed.

 

Examples:

 

1. For segments = [2, 2, 2, 2, 2], we can construct only a 2 x2 rectangle out of the given segments. The function should return 0.
2. For segments = [911, 1, 3, 1000, 1000, 2, 2; 999,
   1000, 911], we can construct three rectangles: 2 x 911. 2x 1000, and 911 x 1000. Out of those three
   possibilities, the best one is 911 x 1000. The function should return 89.
3. For segments = [4, 1, 1, 1, 3], we cannot construct any rectangle out of the given segments. The
   function should return -1.
4. For segments = [1, 1, 11, we cannot construct any rectangle out of the given segments. The function should return -1.

 

Assume that:
• N is an integer within the range [1.30];
• each element of array segments is an integer within the range [1..,1000]. In your solution, focus on correctness. The performance of your solution will not be the focus of the assessment.