amazon_hook+3fe78c41-e4ea-43b5-a6f9-4094d3c6bd20@hook.
com
70
amazon_hook+3fe78c41-e4ea-43b5- PDF generated at: 7 Feb 2025 05:56:31 UTC
Score
70% • 21 / 30
scored in The Amazon Coding Challenge in 89 min 28 sec on 6 Feb 2025 20:24:55 PST
Candidate Information
Email [email protected]
Test The Amazon Coding Challenge
Candidate Packet View
Taken on 6 Feb 2025 20:24:55 PST
Time taken 89 min 28 sec/ 90 min
Invited by Alex
Invited on 3 Feb 2025 21:54:53 PST
Skill Distribution
There is no associated skills data that can be shown for this assessment
Candidate Report Page 1 of 19
[email protected] Tags Distribution
1343570 100% 1716625 40%
Questions
CQ1 • 15 / 15
Time
Status No. Question Skill Score
Taken
8 min
Code Question 1
1 52 - 15/15
Coding
sec
CQ2 • 6 / 15
Time
Status No. Question Skill Score
Taken
1
hour
Code Question 2 20
2 - 6/15
Coding min
26
sec
1. Code Question 1 Correct
Coding 1343570
Question description
Candidate Report Page 2 of 19
[email protected]Data analysts at Amazon are analyzing the information gained when a model is trained with different
arrangements of the same data. For an array of n integers, data, an arrangement is represented using a
permutation of the integers from 1 to n. They observed that the information gained for some permutation
p of n integers for the array data is equal to the sum of i * data[p[i]]. For example, if data = [2, 4, 5, 3] and p =
[2, 1, 3, 4], then the information gained is 1 * data[2] + 2 * data[1] + 3 * data[3] + 4 * data[4] = 1 * 4 + 2 * 2 + 3
* 5 + 4 * 3 = 4 + 4 + 15 + 12 = 35.
Given the array data, find the lexicographically smallest permutation p such that the information gained
for the given data is maximum.
Note: A permutation p is considered lexicographically smaller than a permutation q, if the first index i
where p[i] ≠ q[i], p[i] < q[i].
Example
Suppose n = 3 and data = [2, 1, 2].
Permutation Information Gain
[1, 2, 3] 1 * 2 + 2 * 1 + 3 * 2 = 10
[2, 1, 3] 1 * 1 + 2 * 2 + 3 * 2 = 11
[1, 3, 2] 1*2+2*2+3*1=9
[3, 1, 2] 1*2+2*2+3*1=9
[2, 3, 1] 1 * 1 + 2 * 2 + 3 * 2 = 11
[3, 2, 1] 1 * 2 + 2 * 1 + 3 * 2 = 10
The maximum information is gained for permutations [2, 1, 3] and [2, 3, 1]. The lexicographically smaller
permutation of the two is [2, 1, 3]. Hence the answer is [2, 1, 3].
Function Description
Complete the function findOptimalPermutation in the editor below.
findOptimalPermutation takes the following arguments:
int data[n]: the given data points
Candidate Report Page 3 of 19
[email protected]Returns
int[n]: the lexicographically smallest permutation for which information gain is maximum
Constraints
1 ≤ n ≤ 105
1 ≤ data[i] ≤ 109
INPUT FORMAT FOR CUSTOM TESTING
The first line contains an integer, n, the number of elements in data.
Each of the next n lines contains an integer, data[i].
SAMPLE CASE 0
Sample Input For Custom Testing
STDIN FUNCTION
----- --------
4 → data[] size n = 4
2 → data = [2, 1, 2, 3]
1
2
3
Sample Output
2
1
3
4
Explanation
The information gain is maximum for [2, 1, 3, 4] which is equal to 1 * 1 + 2 * 2 + 3 * 2 + 4 * 3 = 23.
SAMPLE CASE 1
Sample Input For Custom Testing
STDIN FUNCTION
----- --------
5 → data[] size n = 5
5 → data = [5, 6, 1, 4, 4]
6
1
Candidate Report Page 4 of 19
[email protected] 4
4
Sample Output
3
4
5
1
2
Explanation
The information gain is maximum for [3, 4, 5, 1, 2] which is equal to 1 * 1 + 2 * 4 + 3 * 4 + 4 * 5 + 5 * 6 =
71.
Candidate's Solution Language used: C++14
1 #include <bits/stdc++.h>
2
3 using namespace std;
4
5 string ltrim(const string &);
6 string rtrim(const string &);
7
8
9 /*
10 * Complete the 'findOptimalPermutation' function below.
11 *
12 * The function is expected to return an INTEGER_ARRAY.
13 * The function accepts INTEGER_ARRAY data as parameter.
14 */
15
16 bool comp(pair<int, int> &p1, pair<int, int> &p2){
17 if(p1.second==p2.second) return p1.first<p2.first;
18 return p1.second<p2.second;
19 }
20
21 vector<int> findOptimalPermutation(vector<int> data) {
22 int n=data.size();
23 vector<pair<int, int>> nums;
24 for(int i=0;i<n;i++) nums.push_back({i, data[i]});
25 sort(nums.begin(), nums.end(), comp);
26 vector<int> ans;
27 for(int i=0;i<n;i++) ans.push_back(nums[i].first+1);
28 return ans;
Candidate Report Page 5 of 19
[email protected]29 }
30 // (1, 1), (2, 2)
31
32 int main()
33 {
34 ofstream fout(getenv("OUTPUT_PATH"));
35
36 string data_count_temp;
37 getline(cin, data_count_temp);
38
39 int data_count = stoi(ltrim(rtrim(data_count_temp)));
40
41 vector<int> data(data_count);
42
43 for (int i = 0; i < data_count; i++) {
44 string data_item_temp;
45 getline(cin, data_item_temp);
46
47 int data_item = stoi(ltrim(rtrim(data_item_temp)));
48
49 data[i] = data_item;
50 }
51
52 vector<int> result = findOptimalPermutation(data);
53
54 for (size_t i = 0; i < result.size(); i++) {
55 fout << result[i];
56
57 if (i != result.size() - 1) {
58 fout << "\n";
59 }
60 }
61
62 fout << "\n";
63
64 fout.close();
65
66 return 0;
67 }
68
69 string ltrim(const string &str) {
70 string s(str);
71
72 s.erase(
73 s.begin(),
74 find_if(s.begin(), s.end(), not1(ptr_fun<int, int>(isspace)))
Candidate Report Page 6 of 19
[email protected]75 );
76
77 return s;
78 }
79
80 string rtrim(const string &str) {
81 string s(str);
82
83 s.erase(
84 find_if(s.rbegin(), s.rend(), not1(ptr_fun<int, int>
(isspace))).base(),
85 s.end()
86 );
87
88 return s;
89 }
90
TIME MEMORY
TESTCASE DIFFICULTY TYPE STATUS SCORE
TAKEN USED
TestCase 0:
O(Polynomial) - 0.0094
Easy Sample Success 1 9 KB
Basic - Sample sec
Case
TestCase 1:
O(Polynomial) - 0.0094
Easy Sample Success 1 8.82 KB
Basic - Sample sec
Case
TestCase 2:
0.0089
O(Polynomial) - Easy Hidden Success 1 8.77 KB
sec
Basic
TestCase 3:
0.0091
O(Polynomial) - Easy Hidden Success 1 9.06 KB
sec
Basic - n = 1
Candidate Report Page 7 of 19
[email protected] TestCase 4: O(n2) -
0.0098
Advanced - Medium Hidden Success 1 9.04 KB
sec
Random Input
TestCase 5: O(n2) -
0.0101
Advanced - Medium Hidden Success 1 9.04 KB
sec
Random Input
TestCase 6: O(n2) -
0.0106
Advanced - Medium Hidden Success 1 8.77 KB
sec
Random Input
TestCase 7: O(n2) -
0.0104
Advanced - Medium Hidden Success 1 9.03 KB
sec
Random Input
TestCase 8: O(n2) -
0.01
Advanced - Medium Hidden Success 1 8.77 KB
sec
Random Input
Testcase 9: O(n .
log(n)) - Edge - 0.0541
Hard Hidden Success 1 10.5 KB
Large Random sec
Input + n = 1e5
TestCase 10: O(n .
log(n)) - Edge - 0.0461
Hard Hidden Success 1 10.3 KB
Large Random sec
Input + n = 1e5
TestCase 11: O(n .
log(n)) - Edge - 0.0477
Hard Hidden Success 1 10.4 KB
Large Random sec
Input + n = 1e5
Candidate Report Page 8 of 19
[email protected] TestCase 12: O(n .
log(n)) - Edge - 0.0459
Hard Hidden Success 1 10.4 KB
Large Random sec
Input + n = 1e5
TestCase 13: O(n .
log(n)) - Edge - 0.0489
Hard Hidden Success 1 10.4 KB
Large Random sec
Input + n = 1e5
TestCase 14: O(n .
log(n)) - Edge - 0.0509
Hard Hidden Success 1 10.4 KB
Large Random sec
Input + n = 1e5
No comments.
2. Code Question 2 Partially correct
Coding 1716625
Question description
In Amazon's massive warehouse inventory, there are n different types of products. You are given an
array products of size n, where products[i] represents the number of items of product type i (where i
ranges from 0 to n-1). These products need to be packed into batches for shipping.
The batch packing must adhere to the following conditions:
1. No two items in the same batch can be of the same product type, meaning all items in a batch must
be of distinct types.
2. The number of items packed in the current batch must be strictly greater than the number packed in
the previous batch.
Additionally, note that each item can be packed only once, and it is not required to pack every item.
Candidate Report Page 9 of 19
[email protected]Determine the maximum number of batches that can be prepared for shipment.
Note: The product types are numbered from 0 to n-1. Thus, the number of items of product type i (0 ≤
i ≤ n-1) is given by products[i].
Example
n=5
products = [2, 3, 1, 4, 2]
An optimal way to prepare the batches is :
1. The first batch contains 1 item of product type 4. The remaining items = [2, 3, 1, 4, 1].
2. The second batch contains 2 items of product types: 0 and 1. The remaining items = [1, 2, 1, 4, 1].
3. The third batch contains 3 items of product types: 0, 1, and 3. The remaining items = [0, 1, 1, 3, 1].
4. The fourth batch contains 4 items of product types: 1, 2, 3, and 4. The remaining items = [0, 0, 0, 2, 0].
Even though 2 items remain, a batch requires 5 items of different product types. Therefore, only 4
batches can be prepared, which is the maximum possible.
Hence, the answer is 4.
Function Description
Complete the function maximizeGroups in the editor below.
maximizeGroups has the following parameters:
int products[n]: the number of items of each product type.
Returns
int: the maximum number of batches that can be prepared for shipment.
Constraints
1 ≤ n ≤ 105
0 ≤ products[i] ≤ 109
INPUT FORMAT FOR CUSTOM TESTING
Candidate Report Page 10 of 19
[email protected]The first line contains an integer, n, denoting the size of the array products.
Each of the next n lines contains an integer describing products[i].
SAMPLE CASE 0
Sample Input For Custom Testing
STDIN FUNCTION
----- --------
3 → the size of products n = 3
1 → products = [1, 2, 7]
2
7
Sample Output
Explanation
The optimal way to prepare the batches is :
1. The first batch contains 1 item of product type 2, with the remaining items: [1, 2, 6].
2. The second batch contains 2 items of product types: 1 and 2, with the remaining items: [1, 1, 5].
3. The third batch contains 3 items of product types: 0, 1, and 2, with the remaining items: [0, 0, 4].
Four items are required for the next batch, all remaining are of the same product types. Therefore, 3
batches can be prepared.
Hence, the answer is 3.
SAMPLE CASE 1
Sample Input For Custom Testing
STDIN FUNCTION
----- --------
4 → the size of products n = 4
1 → products = [1, 2, 8, 9]
2
8
9
Sample Output
Candidate Report Page 11 of 19
[email protected] Explanation
The optimal way to prepare the batches is as follows:
1. The first batch contains 1 item of product type 3, with the remaining items: [1, 2, 8, 8].
2. The second batch contains 2 items of product types: 2 and 3, with the remaining items: [1, 2, 7, 7].
3. The third batch contains 3 items of product types: 1, 2, and 3, with the remaining items: [1, 1, 6, 6].
4. The fourth batch contains 4 items of product types: 0, 1, 2, and 3, with the remaining items: [0, 0, 5,
5].
Even though the next batch requires 5 items of different product types, only items of 2 distinct
product types are left. Hence, no more batches can be prepared.
Thus, the answer is 4.
Candidate's Solution Language used: C++14
1 #include <bits/stdc++.h>
2
3 using namespace std;
4
5 string ltrim(const string &);
6 string rtrim(const string &);
7
8
9 #include <bits/stdc++.h>
10 #include <numeric>
11 #include <set>
12
13 using namespace std;
14
15 string ltrim(const string &);
16 string rtrim(const string &);
17
18
19
20 /*
21 * Complete the 'maximizeGroups' function below.
Candidate Report Page 12 of 19
[email protected]22 *
23 * The function is expected to return an INTEGER.
24 * The function accepts INTEGER_ARRAY products as parameter.
25 */
26
27 bool isSatisfing(vector<int> &nums, int p){
28 multiset<int> s(nums.begin(), nums.end());
29 for(int k=p;k>=1;k--){
30 if(s.empty()) return false;
31 auto it=s.end();
32 it--;
33 if(*it<k){
34 auto upper=s.lower_bound(k-*it);
35 if(upper==s.end() || upper==it) return false;
36 s.erase(upper);
37 }
38 s.erase(it);
39 }
40 return true;
41 }
42 // nums[i]>=limit -> use and add all
43 // nums[i]<limit ->
44
45 int maximizeGroups(vector<int> nums) {
46 int n=nums.size();
47 sort(nums.begin(), nums.end());
48 int start=1, end=n, ans=0;
49 while(start<=end){
50 int mid=start+(end-start)/2;
51 if(isSatisfing(nums, mid)){
52 ans=max(ans, mid);start=mid+1;
53 }else end=mid-1;
54 }
55 return ans;
56 }
57 // [2, 3, 1, 4, 2]
58 // k -> max(k*(k+1)/2) -> sum(products[i])
59 // binary search? p -> 1, 2, 3, 4... p -> p len of elements -> (a1,
a2,...ap)
60 // suppress to p len such that ai>=i
61
62 // [2, 3, 1, 4, 1] => [2, 3, 1, 3, 1] => [2, 2, 1, 2, 1] => [1, 1, 1, 1, 1]
-> [0, 0, 0, 0, 1]
63
64 int main()
65 {
Candidate Report Page 13 of 19
[email protected] 66 ofstream fout(getenv("OUTPUT_PATH"));
67
68 string products_count_temp;
69 getline(cin, products_count_temp);
70
71 int products_count = stoi(ltrim(rtrim(products_count_temp)));
72
73 vector<int> products(products_count);
74
75 for (int i = 0; i < products_count; i++) {
76 string products_item_temp;
77 getline(cin, products_item_temp);
78
79 int products_item = stoi(ltrim(rtrim(products_item_temp)));
80
81 products[i] = products_item;
82 }
83
84 int result = maximizeGroups(products);
85
86 fout << result << "\n";
87
88 fout.close();
89
90 return 0;
91 }
92
93 string ltrim(const string &str) {
94 string s(str);
95
96 s.erase(
97 s.begin(),
98 find_if(s.begin(), s.end(), not1(ptr_fun<int, int>(isspace)))
99 );
100
101 return s;
102 }
103
104 string rtrim(const string &str) {
105 string s(str);
106
107 s.erase(
108 find_if(s.rbegin(), s.rend(), not1(ptr_fun<int, int>
(isspace))).base(),
109 s.end()
110 );
Candidate Report Page 14 of 19
[email protected]111
112 return s;
113 }
114
115 int main()
116 {
117 ofstream fout(getenv("OUTPUT_PATH"));
118
119 string products_count_temp;
120 getline(cin, products_count_temp);
121
122 int products_count = stoi(ltrim(rtrim(products_count_temp)));
123
124 vector<int> products(products_count);
125
126 for (int i = 0; i < products_count; i++) {
127 string products_item_temp;
128 getline(cin, products_item_temp);
129
130 int products_item = stoi(ltrim(rtrim(products_item_temp)));
131
132 products[i] = products_item;
133 }
134
135 int result = maximizeGroups(products);
136
137 fout << result << "\n";
138
139 fout.close();
140
141 return 0;
142 }
143
144 string ltrim(const string &str) {
145 string s(str);
146
147 s.erase(
148 s.begin(),
149 find_if(s.begin(), s.end(), not1(ptr_fun<int, int>(isspace)))
150 );
151
152 return s;
153 }
154
155 string rtrim(const string &str) {
156 string s(str);
Candidate Report Page 15 of 19
[email protected]157
158 s.erase(
159 find_if(s.rbegin(), s.rend(), not1(ptr_fun<int, int>
(isspace))).base(),
160 s.end()
161 );
162
163 return s;
164 }
165
TIME MEMORY
TESTCASE DIFFICULTY TYPE STATUS SCORE
TAKEN USED
testcase 0 - basic -
O(n^3 * log(n)) - 0.0096
Easy Sample Success 1 8.96 KB
size 3, Smallsize 3, sec
Small values
testcase 1 - basic -
O(n^3 * log(n)) - 0.009
Easy Sample Success 1 8.78 KB
size 4, n batches sec
possible
testcase 2 - basic -
0.0089
O(n^3 * log(n)) - Easy Hidden Success 1 8.78 KB
sec
size 7, Small values
testcase 3 - basic -
O(n^3 * log(n)) - 0.0089
Easy Hidden Success 1 8.87 KB
size 1 (minimum), sec
1 batch possible
testcase 4 - basic - Easy Hidden Success 1 0.0092 8.78 KB
O(n^3 * log(n)) - sec
size 2, Identical
Candidate Report Page 16 of 19
[email protected] values, No batch
possible
testcase 5 - basic -
O(n^3 * log(n)) - Wrong 0.0094
Easy Hidden 0 8.92 KB
size 50, Random Answer sec
Input
testcase 6 -
advanced - O(n*n)
Wrong 0.011
- size 5000, 708 Medium Hidden 0 9.29 KB
Answer sec
batches possible,
Random Input
testcase 7 -
advanced - O(n*n)
Wrong 0.0149
- size 7500, 1619 Medium Hidden 0 9.25 KB
Answer sec
Batches possible,
Random Input
testcase 8 -
advanced - O(n*n)
Wrong 0.0172
- size 10000, 2819 Medium Hidden 0 9.33 KB
Answer sec
Batches possible,
Random Input
testcase 9 -
advanced - O(n*n)
Wrong 0.0151
- size 10000, 5565 Medium Hidden 0 9.37 KB
Answer sec
Batches possible,
Random Input
testcase 10 - edge Hard Hidden Wrong 0 0.0833 13.4 KB
- O(n*log(n)) - size Answer sec
100000
(maximum), 44831
batches possible,
Candidate Report Page 17 of 19
[email protected] Random Large
Input
testcase 11 - edge
- O(n*log(n)) - size
100000
Wrong 0.0884
(maximum), 24325 Hard Hidden 0 13.4 KB
Answer sec
batches possible,
Random Large
Input
testcase 12 - edge
- O(n*log(n)) - size
100000
Wrong 0.0991
(maximum), 33468 Hard Hidden 0 13.5 KB
Answer sec
batches possible,
Random Large
Input
testcase 13 - edge
- O(n*log(n)) - size
100000
Wrong 0.1104
(maximum), 90552 Hard Hidden 0 13.4 KB
Answer sec
batches possible,
Random Large
Input
testcase 14 - edge
- O(n*log(n)) - size
100000
(maximum), 0.0968
Hard Hidden Success 1 13.5 KB
100000 batches sec
possible,
maximum possible
answer,
No comments.
Candidate Report Page 18 of 19
[email protected]Candidate Report Page 19 of 19
