Skip to content

MLSummerSchool2024.md

Latest commit

 

History

History
293 lines (197 loc) · 6.4 KB

MLSummerSchool2024.md

File metadata and controls

293 lines (197 loc) · 6.4 KB
Raw

Amazon ML Summer School 2024

Hands-On Programming Questions (Slot 4)

Amazon ML Summer School

Date: June 23, 2024


Question 1: Nearest Friend's House

View Question

You are given an integer array A of size N, where every element is distinct and represents the x-coordinate of a friend's house.

For example:

A = [1, 3, 8]

means there are friends living at:

  • x = 1
  • x = 3
  • x = 8

The array is guaranteed to be sorted in ascending order.

Problem Statement

Each friend's house has a maximum capacity of N - 1 people.

Every friend wants to host a gathering and invite exactly N - 2 friends.

To minimize overall travel, the host always invites the N - 2 closest friends, so that the total distance traveled by all invited friends is as small as possible.

For every friend, return the minimum total distance traveled by the invited guests.

Input

  • input1: Integer N
  • input2: Integer array A

Output

Return an integer array where the i-th value represents the minimum total distance traveled when the i-th friend is the host.

Example

Input

N = 5
A = [1, 2, 3, 4, 5]

Output

[6, 4, 4, 4, 6]

Explanation

Host = 1

Invites:

  • 2
  • 3
  • 4

Distance:

(2-1) + (3-1) + (4-1) = 6

Host = 2

Invites:

  • 1
  • 3
  • 4

Distance:

(2-1) + (3-2) + (4-2) = 4

Host = 3

Invites:

  • 1
  • 2
  • 4

Distance:

(3-1) + (3-2) + (4-3) = 4

Host = 4

Invites:

  • 2
  • 3
  • 5

Distance:

(4-2) + (4-3) + (5-4) = 4

Host = 5

Invites:

  • 2
  • 3
  • 4

Distance:

(5-2) + (5-3) + (5-4) = 6

Tip

To better understand how the algorithm chooses the closest N-2 friends and computes the minimum total distance, try the interactive visualization below.

Nearest Friend’s House Visualization

Similar Practice Problems

Platform Problem Why it is Similar
LeetCode 658. Find K Closest Elements Closest element selection around a target
LeetCode 2602. Minimum Operations to Make All Array Elements Equal Prefix sums and distance calculations
LeetCode 296. Best Meeting Point Distance minimization
LeetCode 849. Maximize Distance to Closest Person Distance-based reasoning
HackerRank Closest Numbers Adjacent distance computation
HackerRank Sherlock and MiniMax Distance optimization on a number line

Question 2: Pair Problem

View Question

Lucy has an integer array A of size N.

All elements are distinct.

She may perform the following operation any number of times:

Choose two elements x and y such that

LCM(x, y) × HCF(x, y)

is also present in the array.

Return the maximum number of valid ordered pairs (x, y).

Note

Using the identity:

LCM(x, y) × HCF(x, y) = x × y

the problem simplifies to:

Find all ordered pairs (x, y) such that

x × y

exists in the array.

Also note:

(x, y) ≠ (y, x)

Both are counted separately.

Input

  • input1: Integer N
  • input2: Integer array A

Output

Return the maximum number of valid ordered pairs.

Example

Input

N = 5
A = [1, 2, 3, 4, 5]

Output

10

Explanation

Valid ordered pairs are:

(1,1)
(1,2)
(2,1)
(1,3)
(3,1)
(1,4)
(4,1)
(1,5)
(5,1)
(2,2)

Hence,

Answer = 10

Similar Practice Problems

Platform Problem Why it is Similar
LeetCode 1726. Tuple with Same Product Product hashing (closest match)
LeetCode 2183. Count Array Pairs Divisible by K Pair counting using number theory
LeetCode 2001. Number of Pairs of Interchangeable Rectangles Hash map based pair counting
LeetCode 1497. Check If Array Pairs Are Divisible by k Pair formation using mathematical properties
HackerRank Pairs Efficient pair counting
HackerRank Count Triplets Hashing and frequency optimization

Important

For the complete 2024 Machine Learning Questions and additional 2024 Hands-On Programming Questions, refer to:

Amazon ML Summer School 2024 ML Assessment PDF

ML Summer School 2024