Amazon | SDE 1 | Phone Interview | Greatest Absolute Difference

Anonymous User

1452

Got two questions on OA, both at easy/mid level. Got invited into phone interview.
There i got asked to find in list of pairs, x greatest absolute differences between first and second value of the pair.
First I did nlogn solution, further improved to nlogx solution using heapq. After final solution there was time left only for one question.
Two days later got information about being rejected.

# Solution
from dataclasses import dataclass
import heapq


@dataclass
class node:
    a: float
    b: float

    def __le__(self, other):
        return abs(self.a - self.b) <= abs(other.a - other.b)

    def __ge__(self, other):
        return abs(self.a - self.b) >= abs(other.a - other.b)

    def __gt__(self, other):
        return abs(self.a - self.b) > abs(other.a - other.b)

    def __lt__(self, other):
        return abs(self.a - self.b) < abs(other.a - other.b)

    def __eq__(self, other):
        return abs(self.a - self.b) == abs(other.a - other.b)


class solution:
    @staticmethod
    def findGreatestPairs(nodes, k):
        if not nodes:
            return nodes
        arr_size = len(nodes)
        heapq.heapify(nodes)
        neg_idx = -1
        last_val = nodes[neg_idx]
        while k and abs(neg_idx) <= arr_size:
            if last_val != nodes[neg_idx]:
                k -= 1
            if k == 0:
                neg_idx += 1
                break
            last_val = nodes[neg_idx]
            neg_idx -= 1
        return heapq.nlargest(abs(neg_idx), nodes)
# Basic test
b = [node(9, 9), node(0, 2), node(4, 5), node(1, 3), node(7, 7)]
print(solution.findGreatestPairs(b, 2))
# should return in any order [node(a=1, b=3), node(a=0, b=2), node(a=4, b=5)]

Comments (1)