Few days ago Amazon Hackon 1st round was conducted, i would like to discuss some of the problems(i have written what i have done in some the problems) which were given to us in our team . ↵
↵
↵
Problem 1: 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:↵
↵
Salary Calculation Rules:↵
- If you work in an office and no higher-priority office appears after it in the sequence, you add its salary to your total salary↵
- If you work in an office and a higher-priority office appears later in the sequence, you subtract its salary from your total salary↵
The company allows you to change the office you work in, on any one day to maximise 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.↵
↵
Sample Testcase 1:↵
Testease Input↵
ABCDEEDCBA↵
↵
Testcase Output↵
31000↵
↵
Replacing with E in the 4th index is the best(1 based) with score of -1-10-100+10000+10000+10000+1000+100+10+1 =31000↵
↵
Observations:↵
1)Any changes made will effect only the prefix part only before that ith pos.↵
2)Maybe better to store for each position i which is the index right of it where the maximum element is there from subarray starting from i+1↵
3)Now we will try rest 4 options available to us instead of one in the original string. for each position and take the best possible answer O(4*n^2)↵
Is this the optimised algo or it can be made better ? ↵
↵
Problem 2:↵
A company is organizing an internship program and categorizes interns into three types based on their referral capability:↵
- Type A interns each refer two new candidates.↵
- Type B interns each refer one new candidate.↵
- Type C interns do not refer any new candidates.↵
↵
Based on the above rule the interns form a binary tree like structure in which type A have two referred interns, type B have one referred intern and type C do not have any referred interns.↵
↵
The goal is to find the shortest path from the first intern who initiates referrals to the most recently referred intern, ensuring that all interns are included. If it's not possible to include all Interns within a certain numb: of referral steps, the solution should indicate that it's not feasible(-1).↵
↵
Input Format↵
First line contains T representing the number of test cases.↵
First line of each test case contain three numbers a,b,c representing the count of interns of each type:↵
- a represents the number of Type A interns who refer two candidates each.↵
- b represents the number of Type B interns who refer one candidate each.↵
- c represents the number of Type C interns who do not refer any candidates.↵
↵
Output Format↵
Print the length of the shortest referral chain that could be created or print -1 if it is not feasible.↵
↵
Observations:↵
First for tree to exist we have the condition that a+b+c=n and n-1=2*a+b↵
after that i think now it becomes a O(1) sol like for if b=0 answer would be log2(c)+ceiling(b/2) , other than this for non zero b i was not able to think of the answer. any help here ↵
↵
↵
Problem 3:↵
Given a array A and two values x ,M . We can choose a subsequence such that sum of elements in the subsequence and the x is divisible by M , find the minimum such possible length subsequence. ↵
Observation : tired dp but was not sure of the time complexity intended (as nothing was mentioned of constraints in the problem) what can be the optimised approach ? like maybe by assuming length of array is <=10^5 etc.↵
↵
Problem 4:↵
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:↵
- The cost of collecting a bag is the bag's weight (Wi) multiplied by X (if collecting from the left) or Y (if collecting from the right).↵
- If you are collecting a bag consecutively from the same side twice in a row, then there's an additional cost of El (it collected from the left side consecutively) or Er (if collected from the right side consecutively).↵
↵
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 beg (Wi).↵
output Format:↵
Display the minimum energy cost expenditure for Bob ↵
↵
↵
Sample Testcase :↵
Input:↵
↵
3 4 4 19 1↵
↵
42 3 99↵
↵
Output:↵
576↵
(collect from left then right and then left)↵
Observation:↵
Maybe range dp helps here? is a non dp way possible?↵
↵
Problem 5:↵
You are given a mystical tree with w nodes. Each node is connected to at least one other node by on 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.↵
↵
Write a program that takes as input the number of nodes in the tree and the edges between them, and outputs the maximum product of subtree sizes achievable after severing edges in the tree.↵
↵
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 it from the 3-4 edge we have subtrees 1-2-3 and 4-5 so product is 6↵
↵
Observation:↵
better to try cutting in forms of 3 and 2 pairs i think but how to do it whenever it was possible i was not able to conclude↵
↵
↵
Problem 6:↵
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 lath 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 hall.↵
- 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 ad you replace each question mark in the string with some lowercase Latin letter.↵
sample Testcase ↵
Input:↵
↵
a??a↵
Output:↵
↵
4↵
↵
Problem 7:↵
Bob has a collection of numbers and he loves to play a game with them. In this game, Bob counts the unique maximum numbers from his collection based on the following rules:↵
- A number is considered unique if it is the maximum number in the collection and it does not repeat.↵
↵
-If Bob finds a unique maximum number, he counts it, removes it from the collection, and then adds half of that number back into the collection (if the half is not zero).(If its odd then just the floor part)↵
↵
-If the maximum number is not unique (it repeats) , Bob removes all occurrences of that number from the collection.↵
↵
First Line contains a single integer N representing the size of the array.↵
The second line contains N integers representing elements of the array.↵
Output Format↵
Output a single integer representing the count of unique numbers that Bob will count by the end of the game.↵
↵
Obs:↵
We just did simulation on this but still turns out there maybe some edge cases as only partially i was getting the test cases correct. what might be the edge cases for this problem? (negative numbers were not in the sample test cases though i dont know if that caused the problem also maybe something to do with 0 as the number )↵
↵
↵
Problem 8:↵
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.↵
↵
3↵
↵
1 4↵
↵
2 5↵
↵
8 11↵
↵
Output:↵
3↵
↵
↵
↵
Would like everyone who gave the assessment can provide their ideas o(mainly this only) or what improvement in my ideas for better solutions if possible to the above problems and may share their problems too which were not same as mine ones? Rest of the community is wholeheartedly welcome to contribute to the discussions too .↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
Problem 1: 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:↵
↵
Salary Calculation Rules:↵
- If you work in an office and no higher-priority office appears after it in the sequence, you add its salary to your total salary↵
- If you work in an office and a higher-priority office appears later in the sequence, you subtract its salary from your total salary↵
The company allows you to change the office you work in, on any one day to maximise 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.↵
↵
Sample Testcase 1:↵
Testease Input↵
ABCDEEDCBA↵
↵
Testcase Output↵
31000↵
↵
Replacing with E in the 4th index is the best(1 based) with score of -1-10-100+10000+10000+10000+1000+100+10+1 =31000↵
↵
Observations:↵
1)Any changes made will effect only the prefix part only before that ith pos.↵
2)Maybe better to store for each position i which is the index right of it where the maximum element is there from subarray starting from i+1↵
3)Now we will try rest 4 options available to us instead of one in the original string. for each position and take the best possible answer O(4*n^2)↵
Is this the optimised algo or it can be made better ? ↵
↵
Problem 2:↵
A company is organizing an internship program and categorizes interns into three types based on their referral capability:↵
- Type A interns each refer two new candidates.↵
- Type B interns each refer one new candidate.↵
- Type C interns do not refer any new candidates.↵
↵
Based on the above rule the interns form a binary tree like structure in which type A have two referred interns, type B have one referred intern and type C do not have any referred interns.↵
↵
The goal is to find the shortest path from the first intern who initiates referrals to the most recently referred intern, ensuring that all interns are included. If it's not possible to include all Interns within a certain numb: of referral steps, the solution should indicate that it's not feasible(-1).↵
↵
Input Format↵
First line contains T representing the number of test cases.↵
First line of each test case contain three numbers a,b,c representing the count of interns of each type:↵
- a represents the number of Type A interns who refer two candidates each.↵
- b represents the number of Type B interns who refer one candidate each.↵
- c represents the number of Type C interns who do not refer any candidates.↵
↵
Output Format↵
Print the length of the shortest referral chain that could be created or print -1 if it is not feasible.↵
↵
Observations:↵
First for tree to exist we have the condition that a+b+c=n and n-1=2*a+b↵
after that i think now it becomes a O(1) sol like for if b=0 answer would be log2(c)+ceiling(b/2) , other than this for non zero b i was not able to think of the answer. any help here ↵
↵
↵
Problem 3:↵
Given a array A and two values x ,M . We can choose a subsequence such that sum of elements in the subsequence and the x is divisible by M , find the minimum such possible length subsequence. ↵
Observation : tired dp but was not sure of the time complexity intended (as nothing was mentioned of constraints in the problem) what can be the optimised approach ? like maybe by assuming length of array is <=10^5 etc.↵
↵
Problem 4:↵
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:↵
- The cost of collecting a bag is the bag's weight (Wi) multiplied by X (if collecting from the left) or Y (if collecting from the right).↵
- If you are collecting a bag consecutively from the same side twice in a row, then there's an additional cost of El (it collected from the left side consecutively) or Er (if collected from the right side consecutively).↵
↵
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 beg (Wi).↵
output Format:↵
Display the minimum energy cost expenditure for Bob ↵
↵
↵
Sample Testcase :↵
Input:↵
↵
3 4 4 19 1↵
↵
42 3 99↵
↵
Output:↵
576↵
(collect from left then right and then left)↵
Observation:↵
Maybe range dp helps here? is a non dp way possible?↵
↵
Problem 5:↵
You are given a mystical tree with w nodes. Each node is connected to at least one other node by on 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.↵
↵
Write a program that takes as input the number of nodes in the tree and the edges between them, and outputs the maximum product of subtree sizes achievable after severing edges in the tree.↵
↵
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 it from the 3-4 edge we have subtrees 1-2-3 and 4-5 so product is 6↵
↵
Observation:↵
better to try cutting in forms of 3 and 2 pairs i think but how to do it whenever it was possible i was not able to conclude↵
↵
↵
Problem 6:↵
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 lath 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 hall.↵
- 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 ad you replace each question mark in the string with some lowercase Latin letter.↵
sample Testcase ↵
Input:↵
↵
a??a↵
Output:↵
↵
4↵
↵
Problem 7:↵
Bob has a collection of numbers and he loves to play a game with them. In this game, Bob counts the unique maximum numbers from his collection based on the following rules:↵
- A number is considered unique if it is the maximum number in the collection and it does not repeat.↵
↵
-If Bob finds a unique maximum number, he counts it, removes it from the collection, and then adds half of that number back into the collection (if the half is not zero).(If its odd then just the floor part)↵
↵
-If the maximum number is not unique (it repeats) , Bob removes all occurrences of that number from the collection.↵
↵
First Line contains a single integer N representing the size of the array.↵
The second line contains N integers representing elements of the array.↵
Output Format↵
Output a single integer representing the count of unique numbers that Bob will count by the end of the game.↵
↵
Obs:↵
We just did simulation on this but still turns out there maybe some edge cases as only partially i was getting the test cases correct. what might be the edge cases for this problem? (negative numbers were not in the sample test cases though i dont know if that caused the problem also maybe something to do with 0 as the number )↵
↵
↵
Problem 8:↵
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.↵
↵
3↵
↵
1 4↵
↵
2 5↵
↵
8 11↵
↵
Output:↵
3↵
↵
↵
↵
Would like everyone who gave the assessment can provide their ideas
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
