Amazon OA Hackerrank

Round 1

Questions: There are n servers, where the power of the jth server is given by arr[j].

These servers are grouped into clusters of size three. The power of a cluster, denoted as cluster_power, is defined as the median of the power values of the three servers in the cluster. Each server can be part of at most one cluster, and some servers may remain unused.

The total system power, called max_result, is the sum of the power of all the clusters formed. The task is to find the maximum possible max_result.

Example: n = 7 arr = [8, 6, 3, 4, 4, 5, 6]

The maximum number of clusters that can be formed is 2, with one server remaining unused.

One possible way to form the clusters is to select the 1st, 2nd, and 3rd servers for the first cluster, and the 4th, 6th, and 7th servers for the second cluster. The cluster_power of the first cluster [8, 6, 3] will be 6 (the median), and the cluster_power of the second cluster [4, 5, 6] will be 5 (the median).

Thus, the system_throughput will be 6 + 5 = 11.

There are some test cases which did not pass:

[2, 2, 2, 2, 1, 1, 2, 2, 1, 1, 1, 2, 2, 2, 1, 2, 1, 2, 1, 2, 2, 2, 2, 2, 2, 1, 2, 1, 2, 1, 1, 1, 2, 2, 1, 1, 2, 2, 1, 2, 1, 2, 2, 2, 1, 2, 1, 1, 2, 1, 1, 2, 1, 1, 1, 1, 2, 2, 2, 2, 1, 2, 1, 1, 2, 1, 1, 1, 1, 1, 2, 2, 1, 2, 2, 2, 2, 1, 2, 2, 1, 2, 1, 2, 2, 1, 2, 2, 1] Incorrect Answer: 48

[461, 294, 705, 281, 249, 729, 972, 127, 818, 2, 398, 230, 516, 631, 474, 54, 291, 132, 341, 913, 476, 598, 666, 491, 216, 865, 398, 138, 802, 237, 264, 950, 457, 946, 466, 587, 841, 903, 253, 731, 204, 958, 583, 532, 777, 485, 189, 458, 554, 849, 581, 340, 323, 768, 552, 554, 485, 829, 307, 627, 45, 927, 970, 135, 363, 14, 581, 325, 729, 209, 337, 363, 958, 487, 84, 352, 257, 307, 885, 886, 427, 909, 269, 33, 561, 772, 698, 150, 204, 312, 910, 308, 785, 848, 940, 471, 281, 475, 784, 534, 448, 451, 58, 138, 158, 33, 322, 231, 342, 997, 203, 423, 635, 999, 313, 292, 147, 207, 463, 767, 361, 171, 244, 610, 758, 758, 209, 245, 324, 818, 495, 250, 430, 391, 764, 382, 388, 112, 216, 479, 516, 862, 16, 622, 960, 582, 895, 303, 642, 519, 844, 756, 252, 376, 308, 516, 507, 593, 428, 518, 619, 171, 639, 33, 356, 409, 222, 570, 552, 286, 368, 691, 602, 640, 361, 724, 603, 85, 612, 870, 719, 456, 243, 973, 483, 517, 199, 559, 808, 147, 508, 54, 467, 42, 578, 618, 600, 688, 394, 513, 751, 293, 997, 506, 662, 548, 902, 339, 559, 490, 857, 535, 769, 539, 36, 852, 376, 574, 217, 772, 480, 737, 123, 803, 844, 898, 785, 776, 660, 854, 281, 691, 786, 744, 245, 658, 799, 757, 876, 235, 909, 639, 753, 361, 606, 818, 525, 684, 217, 489, 706, 860, 229, 219, 499, 981, 200, 476, 403, 244, 204, 891, 143, 1000, 172, 407, 822, 914, 733, 918, 802, 862, 803, 85, 374, 390, 670, 513, 721, 331, 945, 109, 945, 284, 668, 979, 296, 363, 719, 588, 508, 194, 150, 961, 659, 862, 363, 582, 849, 976, 19, 309, 293, 765, 731, 359, 723, 807, 423, 345, 228, 547, 96, 964, 503, 500, 429, 89, 41, 540, 605, 371, 443, 382, 435, 18, 762, 205, 689, 74, 744, 498, 894, 351, 460, 766, 133, 74, 667, 714, 191, 410, 296, 937, 575, 110, 431, 582] Incorrect Answer: 62144