Panda Guru LogoPanda
Guru

Amazon Problems (Online Rounds)

Round 1

Questions:

  1. You are given a mystical tree with w nodes. Each node is connected to at least one other node by one edge. Your task is to sever one or more edges in the tree to split it into subtrees. The goal is to maximize the product of the sizes of these subtrees. The size of a subtree is defined as the number of nodes it contains. The product of subtree sizes is calculated by multiplying the sizes of all subtrees together.

    Input Format: The first line of input contains an integer N, representing the number of nodes in the mystical tree.
    The next N-1 lines each contain two space-separated integers U and V, signifying an edge between the respective nodes.
    Output Format: Print a number X, representing the maximum product of subtree sizes achievable after edge deletions.

    Input:

    5 1 2 2 3 3 4 4 5

    Output: 6 cut 3-4 edge subtrees form 1-2-3 and 4-5 so product is 6.

Candidate's Approach

No approach provided.

Interviewer's Feedback

No feedback provided.


Round 2

Questions: 2) You are given a string S, consisting of lowercase Latin letters and/or question marks (?), your goal is to replace each question mark with any lowercase Latin letter (from 'a' to 'z') in such a way that the length of the longest repeated substring is maximized. A repeated substring is a segment/substring of even length within the string where the first half is identical to the second half. A substring is any contiguous portion of the string.

Objective: Replace each question mark in the string S with lowercase Latin letters to create the longest possible repeated substring.
Input Format: The only line of input contains a string S, consisting only of lowercase Latin letters and/or question marks.
Output Format: print a single integer, the maximum length of the longest repeated substring as you replace each question mark in the string with some lowercase Latin letter.

Sample Testcase Input:

a??a 

Output:

4
Candidate's Approach

No approach provided.

Interviewer's Feedback

No feedback provided.


Round 3

Questions: 3) Bob has N bags in a row. Each bag has a weight (Wi). Bob can collect bags from either the leftmost or rightmost position, but there are energy costs:

Find the strategy that minimizes the total energy cost Bob spends to collect all the bags and display the minimum cost Bob has to pay.
Input Format: The first line of input contains five space-separated integers: N (number of bags), X, Y, El, Er (energy costs). The second line of input contains N space-separated integers representing the weight of each bag (Wi).
Output Format: Display the minimum energy cost expenditure for Bob.

Sample Testcase:

Input: 3 4 4 19 1 42 3 99

Output: 576

Candidate's Approach

No approach provided.

Interviewer's Feedback

No feedback provided.


Round 4

Questions: 4) You work at a company that has 5 offices, each with a distinct salary level and a priority ranking from lowest to highest as follows: Office A ($1)<Office B($10)< Office C ($100)<Office D($1,000)< Office E($10,000). Your work schedule is represented by a string, where each character corresponds to an office (e.g., 'D' for Office D) you work on the ith day. Your salary is calculated based on the following rule:

The company allows you to change the office you work in, on any one day to maximize your total salary. Your task is to determine the maximum possible salary after making at most one such change.
Input Format: The first and only line contains a string S representing the sequence offices you worked in.
Output Format: Print the max salary you can get after changing at most one office to another office.

Input: ABCDEEDCBA
Output: 31000

Candidate's Approach

No approach provided.

Interviewer's Feedback

No feedback provided.


Round 5

Questions: 5) In the Optimal Interval Difference problem, you are given an array of intervals, where each interval is represented as [start[i], end[i]]. Your task is to find the minimum difference between the start and end points of the common overlapping intervals. That is from the set of intervals obtained after merging the overlapping intervals, compute the difference between the start [i-1] and end[i] points for each interval after sorting and return the minimum of those differences. For eg, if intervals are (1,5),(7,9) and (2,4), then after merging the intervals we get (1,5) and (7,9). And the minimum difference between them is 7-5=2.
Input Format: The first line of input contains an integer N, denoting the number of intervals. The next N lines contain two space-separated integers each, representing the start and end points of the intervals.
Output Format: Print a single integer representing the minimum difference between the start and end points of the common overlapping intervals.

Input:

3 1 4 2 5 8 11

Output: 3

Candidate's Approach

No approach provided.

Interviewer's Feedback

No feedback provided.


Round 6

Questions: 6) Given an array A and two values x, M. We can choose a subsequence such that the sum of elements in the subsequence and x is divisible by M, find the minimum such possible length subsequence.

Candidate's Approach

No approach provided.

Interviewer's Feedback

No feedback provided.