Round 1
Questions:
Question
Mike is a logistics manager at a parcel delivery company. Each day, a fleet of delivery vans is assigned to deliver packages along various routes in the city. There are n delivery stops, each initially assigned a certain number of parcels represented by an array p. However, the company allows the vans to load additional parcels at each stop based on a permutation of the delivery stops from 1 to n.
Mike can choose exactly one permutation of stops, q1, q2, qn, and change the number of parcels at each stop according to the rule: p[i]:= p[i] + q[i]. After modifying the parcels with the permutation, Mike wants to maximize the number of stops that now have the same number of parcels.
Your task is to find the maximum possible number of stops that can have the same parcel count after this operation.
Here
- 1 <= q[i] <= n
- Each q[i] is unique.
Input
- The first line contains a single integer n (1 <= n <= 200000) - the number of delivery stops.
- The second line contains n integers p1, p2..... pn (1 <= pis<=10^9) the initial number of parcels at each delivery stop.
Output
- Output a single number the maximum number of delivery stops that can have the same number of parcels after adding the permutation.
Sample input
6 1 1 1 1 1 2
Sample output
2
Candidate's Approach
No approach provided.
Interviewer's Feedback
No feedback provided.
Round 2
Questions:
Question
The Kingdom's Rebellion
In the Kingdom of Arborvale, there is a hierarchical system of nobles, arranged in a tree-like structure. The kingdom has n nobles, each assigned a unique number from 1 to n. At the top of the hierarchy is the King, who is considered the root of the kingdom's structure.
Each noble has a parent, except for the King, who has no parent. The nobles have ancestral respect rules:
- Respects: A noble respects its ancestors if it is loyal to the King's rule.
- Rebels: Some nobles, however, do not respect their ancestors and openly defy them.
Given the tension in the kingdom, you decide to remove rebellious nobles one by one to restore peace. The process of removal is as follows:
- You select a non-root noble that is rebellious (does not respect its parent) and has no children that respect it. If there are multiple such nobles, select the one with the smallest number.
- When you remove a rebellious noble, all of its children are immediately re-assigned to its parent.
- The process continues until there are no more nobles that meet the removal criteria.
Your task is to determine the order in which you will remove the rebellious nobles, if possible.
Input
- The first line contains an integer n (1 <= n <= 100) the number of nobles in the kingdom.
- The next n lines describe the hierarchy of the nobles:
- The i-th line contains two integers; p_i and r_i, where:
p_i (1 <= p_i <= n or -1) is the parent of noble i. The King (root) has p_i = -1.
r_i (0 <= r_i <= 1) indicates whether the noble respects its parent:
- r_i = 0 means the noble respects its parent (loyal).
- r_i = 1 means the noble does not respect its parent (rebellious).
- The i-th line contains two integers; p_i and r_i, where:
p_i (1 <= p_i <= n or -1) is the parent of noble i. The King (root) has p_i = -1.
r_i (0 <= r_i <= 1) indicates whether the noble respects its parent:
It is guaranteed that the values of p_i define a valid hierarchical tree with n nobles.
Output
- If there is at least one rebellious noble that can be removed, print a single line containing the indices of the nobles in the order they will be removed.
- If no such noble exists, print -1.
Sample input:
6 -1 0 1 1 1 1 3 1 3 0 3 0
Sample output:
2 4
Candidate's Approach
No approach provided.
Interviewer's Feedback
No feedback provided.
Round 3
Questions:
Question
City Block Partition
In the city of Gridopolis, the city is arranged in a block formation with 2 parallel streets and n intersections (blocks) along each street. Some blocks are open and accessible (free) while others are closed for construction (blocked). A block is accessible if it has a free passage on at least one of the streets.
Residents of Gridopolis want to ensure that their neighborhoods remain connected. Two blocks are part of the same neighborhood if they are accessible and can be reached through adjacent blocks (either horizontally or vertically).
Your task is to identify the critical blocks in the city grid: the block that, if closed for construction, would divide the city into exactly 3 separate neighborhoods.
Input
- The first line contains a single integer n (1 <= n <= 200,000) the number of blocks along each of the two streets.
- The next two lines represent the city grid: Each line contains a string of length n, where each character is either (open block) or x (closed block due to construction).
Output
- Output a single integer the number of blocks that, if closed, would split the city into exactly 3 separate neighborhoods.
Additional Constraints
- Initially, there is at most 1 connected neighborhood in the city grid.
Sample input:
8 .......x .x.xx...
Candidate's Approach
No approach provided.
Interviewer's Feedback
No feedback provided.