Latest Questions | Page 8

Recursive Land Division

A country consists of N regions, each containing a specific number of towns. The government has decided to split the country into two separate nations in a way that minimizes the absolute difference between the total number of towns in each new nation.

Each region is connected to another region through roads, forming a tree structure (i.e., an undirected connected gra ph with N-1 edges and no cycles).

Your task is to determine the minimum possible absolute difference in the number of towns between the two new nations.I represents a bidirectional road connecting region u and region v.

Returns

int → The minimum absolute difference in the number of towns
between the two new nations after removing exactly one road.

Input Format

- The first line contains one integer, N (the number of regions).
- The second line contains N space-separated integers representing the towns array.
- The next N-1 lines each contain two integers, u and v,
representing a bidirectional road between regions u and v.

Output Format

A single integer representing the minimum possible absolute difference
in the number of towns between the two new nations.

Constraints Show More

Task
Calculate the number of pairs of investment (i, j) such that the return is a perfect square.
Example 1
Assumptions
Input
N = 4
Output: 6

Approach
(1, 1), (1, 4), (2, 2), (3, 3), (4, 1), and (4, 4) are the possible pairs.
Square Investment
Bob and John both have N dollars each and want to invest some money in Jack.
They will invest amounts i, j (1 ≤ i, j ≤ N). Jack has promised th em a return of i * j.
Bob and John will be happy if the return is a perfect square.
Function Description
Complete the function solution(). The function takes the following parameter and returns the solution:
- N: Represents the total amount.

Input Format for Custom Testing
Note: Use this input format if you are testing against custom input or writing code in a language where we don't provide boilerplate code.
- The first linecontains N, denoting the total amount.
Output Format
Return an integer representing the number of possible pairs. Show More

Your team at Amazon is working on a system that divides applications to a mixed cluster of computing devices. Each application is identified by an integer ID, requires a fixed non-zero amount of memory to execute, and is defined to be either a foreground or background application. IDs are guaranteed to be unique within their own application type, but not across types.

Each device should be assi gned two applications at once, one foreground application and one background application. Devices have limited amounts of memory and cannot execute applications that require more memory than the available memory. The goal of the system is to maximize the total utilization of the memory of a given device. A foreground/background application pair is considered to be optimal if there does not exist another pair that uses more memory than this pair, and also has a total less than or equal to the total memory of the device. For example, if the device has 10MB memory, a foreground/background pair using a sum total of 9MB memory would be optimal if there does not exist a pair that uses a sum total of 10MB, but would not be optimal if such a pair did exist.

Write an algorithm to find the sets of foreground and background application pairs that optimally utilize the given device for a given list of foreground applications and a given list of background applications.

Input
The input to the function/method consists of three arguments:
deviceCapacity, an integer representing the maximum capacity of the given device;
foregroundAppList, a list of pairs of integers where the first integer represents the unique ID of a foreground application and the second integer represents the amount of memory required by this application;
backgroundAppList, a list of pairs of integers where the first integer represents the unique ID of a background application and the second integer represents the amount of memory required by this application.

Output
Return a list of pairs of integers representing the pairs of IDs of foreground and background applications that optimally utilize the given device [foregroundAppID, backgroundAppID]. If no pair is possible, return a list with empty pair - not just an empty list.

Examples

Example 1:
Input:
deviceCapacity = 7
foregroundAppList = [[1,2], [2,4], [3,6]]
backgroundAppList = [[1,2]]

Output:
[[2,1]]

Explanation:
There are only three combinations, [1,1], [2,1], and [3,1], which use a total of 4, 6, and 8MB memory, respectively. Since 6 is the largest use that does not exceed 7, [2,1] is the only optimal pair.

Example 2:
Input:
deviceCapacity = 10
foregroundAppList = [[1, 3], [2, 5], [3, 7], [4, 10]]
backgroundAppList = [[1, 2], [2, 3], [3, 4], [4, 5]]

Output:
[[2, 4], [3, 2]]

Explanation:
There are two pairs of foreground and background applications possible that optimally utilize the given device.
Application 2 from foregroundAppList uses 5 memory units, and application 4 from backgroundAppList also uses 5 memory units. Combined, they add up to 10 units of memory.
Similarly, application 3 from foregroundAppList uses... Show More

Amazon's Alexa team is working on optimizing the customer experience for scenarios where customers ask generic questions.
One example of a generic question is "What are good vegetarian restaurants nearby?"

In this example, Alexa would then search for a list of vegetarian restaurants in the city and select the nearest X vegetarian
restaurants relative to the customer's location. Given an ar ray representing the locations of N vegetarian restaurants in
the city, implement an algorithm to find the nearest X vegetarian restaurants to the customer's location.

Input
The input to the function/method consists of two arguments:
- allLocations: a list of elements where each element consists of a pair of integers representing the x and y coordinates of
the vegetarian restaurant in the city
- numRestaurants: an integer representing the number of nearby vegetarian restaurants that would be returned to the customer (X)

Output
Return a list of elements where each element of the list represents the x and y integer coordinates of the nearest recommended
vegetarian restaurant relative to customer's location. If there is one tie, use the location with the closest X coordinate.
If no location is possible, return a list with an empty location - not just an empty list.

Constraints
numRestaurants ≤ size(allLocations)

Note
The customer begins at the location [0, 0].
The distance from the customer's current location to a recommended vegetarian restaurant location (x, y) is the square root of x² + y².
If there are ties then return any of the locations as long as you satisfy returning exactly X nearby vegetarian restaurants.
The returned output can be in any order.

Example
Input:
allLocations = [[1, 2], [3, 4], [1, -1]]
numRestaurants = 2

Output:
[[1, -1], [1, 2]]

Explanation:
The distance of the customer's current location from location [1, 2] is √5 ≈ 2.236
The distance from location [3, 4] is √25 = 5
The distance from location [1, -1] is √2 ≈ 1.414

The required number of vegetarian restaurants is 2, hence the output is [1, -1] and [1, 2]. Show More

A student is preparing for a scholarship test which is organized on the Amazon Academy platform and scheduled for next month.
There are n chapters to be studied where the ith chapter has pages[i] pages. In one day, the student decides to read up to p of the remaining pages, each from some k consecutive chapters. Thus, the number of pages remaining to be read is reduced by p from each of these cha pters. If a chapter has less than p pages remaining, the student reads the remaining pages, and the remaining page count is set to 0 for subsequent days.
Find the minimum number of days the student needs to read all the chapters completely, i.e., the remaining page count of all chapters is 0.
Note: The chapters read must be contiguous.

Example
The number of chapters is n = 3, the number of chapters read in a day is k = 2, the number of pages read from each chapter is p = 2, and the page counts of each chapter are pages = [3, 1, 4].

The chapters can be read as follows:
Chapters read must be contiguous.
- Choose chapters 1 and 2, remaining pages to be read = [1, 0, 4].
- Choose chapters 1 and 2, remaining pages to be read = [0, 0, 4].
- Choose chapters 2 and 3, remaining pages to be read = [0, 0, 2].
- Finally, choose chapters 2 and 3, remaining pages to be read = [0, 0, 0].
The chapters cannot be read in less than 4 days.

Function Description
Complete the function findMinimumDays in the editor below.

findMinimumDays has the following parameters:
int pages[n]: the number of pages in each chapter
int k: the number of chapters chosen each day
int p: the maximum number of pages read from

Returns
long_int: the minimum number of days to read all pages of all chapters

Constraints
- 1 ≤ n ≤ 10^5
- 1 ≤ pages[i] ≤ 10^9
- 1 ≤ k ≤ n
- 1 ≤ p ≤ 10^9

Input Format For Custom Testing

Sample Case 0
Sample Input For Custom Testing
STDIN
2
FUNCTION
3
4
1
2

pages[] size n = 2
pages = [3, 4]
k = 1
p = 2

Sample Output
4

Explanation
Read the first chapter for the first two days,
and the second chapter for the next two days.

Sample Case 1
Sample Input For Custom Testing
STDIN
FUNCTION
3
5

pages[] size n = 3
pages = [5, 1, 2]
1
2
3
3

k = 3
p = 3

Sample Output
2

Explanation
After 1st day, the number of pages remaining = [2, 0, 0].
After 2nd day, the number of pages remaining = [0, 0, 0]. Show More

Database security and authentication have become vital due to the increasing number of cyberattacks every day.
Amazon has created a team for the analysis of various types of cyberattacks. In one such analysis, the team finds
a virus that attacks the user passwords. The virus designed has an attacking rule defined by attackOrder, which is
a permutation of length n. In the ith second of the at tack, the virus attacks at the attackOrder[i]th character of
the password, replacing it with the malicious character '*', i.e., password[attackOrder[i]] = '*' after the ith second.

The password is said to be irrecoverable when the number of substrings of the password containing at least one
malicious character '*' becomes greater than or equal to m. In order to estimate the threat posed by the virus,
the team wishes to find the minimum time after which the password becomes irrecoverable.

Note:
- If the password is irrecoverable at the start, report 1 as the answer.
- A substring of a string s is a contiguous segment of that string.

Example:
There is a password of length n = 5, password = "bcced".
The 1-based indices where characters will be replaced: attackOrder = [2, 3, 1, 4, 5]
The recoverability parameter m = 10.

After the 1st second, the password becomes:
The 8 substrings that contain at least one malicious character are:
["b*", "b*c", "b*ce", "b*ced", "*", "*c", "*ce", "*ced"]
and 8 is less than m.

After the 2nd second, the password becomes:
The 11 substrings that contain at least one malicious character are:
["b*", "b**", "b**e", "b**ed", "*", "**", "**e", "**ed", "*", "*e", "*ed"]
This is greater than or equal to m.

After the replacement at second 2, the number of substrings is at least m.
The answer is 2.

Function Description:
Complete the function findMinimumTime in the editor below.

findMinimumTime has the following parameters:
string password: the initial password
int attackOrder[n]: permutation array of integers [1, 2, ..., n], the attack order of the virus
int m: the recoverability parameter

Returns:
int: the minimum time after which the password becomes irrecoverable.

Constraints:
- 1 ≤ n ≤ 8 * 10^5
- String password consists of lowercase English characters
- 1 ≤ attackOrder[i] ≤ n
- 0 ≤ m ≤ n * (n + 1) / 2

Input Format For Custom Testing

Sample Case 0

Sample Input For Custom Testing:
STDIN
--
abc
3
1
2
3

FUNCTION

password = "abc"
attackOrder[] size n = 3
attackOrder = [1, 2, 3] Show More

Given two servers and the time taken to upgrade each server in seconds, denoted by t1 and t2 respectively, in one second, one server undergoes the upgrade process. The servers receive requests at certain time intervals and pause upgrades during those seconds. The servers receive requests at multiples of req1 and req2 respectively. Determine the minimum total time (in seconds) required to upgrade both servers.

Notes:
. Only one server undergoes the upgrade process at any given second.
. There may be seconds during which no server is undergoing an upgrade.

Example:
req1 = 2
t1 = 3
req2 = 3
t2 = 1

The 1st server takes 3 seconds to upgrade, and it receives requests on seconds that are multiples of 2. Similarly, the 2nd server upgrades in 1 second and receives requests on seconds that are multiples of 3.
The 1st server upgrades in the 1st, 3rd, and 5th seconds, while the 2nd server upgrades in the 2nd second. Note that none of the numbers from [1, 3, 5] is divisible by req1 = 2. Similarly, [2] is not divisible by req2 = 3. Thus, the minimum time required is 5 seconds.

Function Description:
Complete the function getMinUpgradationTime in the editor below.

getMinUpgradationTime takes the following parameter(s):
int req1: indicates that the first server receives requests at multiples of req1
int t1: the total time in seconds to upgrade the first server
int req2: indicates that the second server receives requests at multiples of req2
int t2: the total time in seconds to upgrade the second server

Returns:
long: the minimum total time (in seconds) required to upgrade both servers

Constraints:
· 2 ≤ req1, req2 ≤ 3 * 10^4
· 1 ≤ t1, t2 ≤ 10^9

Sample Input:
2
1

FUNCTION

req1 = 2
t1 = 1

Input Format For Custom Testing:

Sample Case 0
Sample Input For Custom Testing:
STDIN Show More

Given a set of nodes and a list of connected pairs, determine the order (number of nodes) in each connected component in the graph. For each component, calculate the ceiling of the square root of its order, and return the sum of these values across all connected components.

Example
graph_nodes = 10
graph_from = [1, 1, 2, 3, 7]
graph_to = [2, 3, 4, 5, 8]

There are graph_edges = 5 ed ges to consider. There are 2 isolated sets with more than one node: {1, 2, 3, 4, 5} and {7, 8}. The ceilings of their square roots are: √5 ≈ 2.236 and ceil(2.236) = 3 √2 ≈ 1.414 and ceil(1.414) = 2

The other three isolated nodes are separate, and the square root of their orders is √1 = 1 respectively. The sum is 3 + 2 + (3 * 1) = 8.

Function Description
Complete the function `connectedSum` in the editor below.
connectedSum has the following parameter(s):
- int graph_nodes: the number of nodes
- int graph_from[graph_edges]: an array of integers that represent one end of an edge
- int graph_to[graph_edges]: an array of integers that represent the other end of an edge

Returns:
- int: an integer that denotes the sum of the values calculated

Constraints
- 2 ≤ graph_nodes ≤ 10^5
- 1 ≤ graph_edges ≤ 10^5
- 1 ≤ graph_from[i], graph_to[i] ≤ n
- graph_from[i] ≠ graph_to[i]

Input Format for Custom Testing
Sample Input 0
STDIN
12 >
4 2
graph_edges = 2 edges
graph_from[] = [1, 1]
graph_to[] = [2, 4]
14

Sample Output 0
graph_nodes = 4 nodes,
3
The values to sum are:
1. Set {1, 2, 4}: ceil(sqrt(3)) = 2
2. Set {3}: ceil(sqrt(1)) = 1
2 + 1 = 3 Show More

Amazon is working on optimizing its delivery zones to ensure efficient and timely delivery of packages.
Each delivery zone is represented as an interval indicating the range of house numbers it covers.
The delivery zones can overlap.

Given is a list of n delivery zones, where the i-th zone covers the interval (a[i], b[i]) (inclusive).
Additionally, given is a maximum allowed length, k, for any new delivery zone that can be added.

Your task is to add exactly one new delivery zone (a, b) such that the length of this new zone (b - a)
is less than or equal to k. The goal is to minimize the number of disconnected delivery zones after
adding the new delivery zone.

A set of delivery zones [ (a[1], b[1]), (a[2], b[2]), ..., (a[n], b[n])] is considered connected if every
house number in the range (min(a[1], a[2], ..., a[n]), max(b[1], b[2], ..., b[n])) is covered by at least
one of the delivery zones (a[i], b[i]) in the set.

For an instance:

- The set [(1, 2), (2, 3), (1, 5)] is connected because every house number in the interval
(min(1, 2, 1), max(2, 3, 5)) = (1, 5) is covered by at least one of the delivery zones.

- The set [(2, 2), (3, 4)] is not connected because the delivery zones (2, 2) and (3, 4) do not overlap
each other and hence is disconnected.

Note: The arrays 'a' and 'b' used above are considered to follow 1-based indexing.

Example
Consider the delivery zones:
[(1, 5), (2, 4), (6, 6), (7, 14), (16, 19)] and k = 2.

If you add a new delivery zone (5, 7) to the list, you can separate the zones into 2 connected sets:

- [(1, 5), (2, 4), (5, 7), (6, 6), (7, 14)]
- [(16, 19)]

However, if you add a new delivery zone (14, 16), you will end up with 3 connected sets:

- [(1, 5), (2, 4)]
- [(6, 6)]
- [(14, 16), (16, 19)] Show More

The Amazon Alexa development team needs to analyze request logs across numSkills different Alexa skills to ensure optimal performance and user engagement.

The skills are indexed from 1 to numSkills, and the logs are provided as a 2D array requestLogs of size m, where requestLogs[i] = [skill_ID, timeStamp] denotes that a request was made to the skill with ID skill_ID at the time timeStamp.

Yo u are given an integer numSkills, a 2D integer array requestLogs, an integer timeWindow (representing a lookback period), and an array of queryTimes containing q queries.

For each queryTime[i], determine the number of skills that did not receive a request in the time interval [queryTime[i] - timeWindow, queryTime[i]]. Return an array of length q containing the result of each of the queries.

Note: If for some query all the numSkills received request in the given time interval for that query, then answer is 0.

Example:
Suppose numSkills = 3, timeWindow = 5, requestLogs = [[1, 3], [2, 6], [1, 5]], and queryTime = [10, 11]

queryTime = 10
Time Interval = [10 - 5, 10] = [5, 10]
Skills that received a request in the given interval = 1, 2
Skills not receiving a request in the given interval = 2

queryTime = 11
Time Interval = [11 - 5, 11] = [6, 11]
Skills that received a request in the given interval = 1, 3
Skills not receiving a request in the given interval = 1, 3 Show More