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

a6f9-4094d3c6bd20@hook.com View this report on HackerRank

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 amazon_hook+3fe78c41-e4ea-43b5-a6f9-4094d3c6bd20@hook.com

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

 amazon_hook+3fe78c41-e4ea-43b5-a6f9-4094d3c6bd20@hook.com

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

 amazon_hook+3fe78c41-e4ea-43b5-a6f9-4094d3c6bd20@hook.com

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

 amazon_hook+3fe78c41-e4ea-43b5-a6f9-4094d3c6bd20@hook.com

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

 amazon_hook+3fe78c41-e4ea-43b5-a6f9-4094d3c6bd20@hook.com

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

 amazon_hook+3fe78c41-e4ea-43b5-a6f9-4094d3c6bd20@hook.com

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

 amazon_hook+3fe78c41-e4ea-43b5-a6f9-4094d3c6bd20@hook.com

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

 amazon_hook+3fe78c41-e4ea-43b5-a6f9-4094d3c6bd20@hook.com

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

 amazon_hook+3fe78c41-e4ea-43b5-a6f9-4094d3c6bd20@hook.com

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

 amazon_hook+3fe78c41-e4ea-43b5-a6f9-4094d3c6bd20@hook.com

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

 amazon_hook+3fe78c41-e4ea-43b5-a6f9-4094d3c6bd20@hook.com

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

 amazon_hook+3fe78c41-e4ea-43b5-a6f9-4094d3c6bd20@hook.com

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

 amazon_hook+3fe78c41-e4ea-43b5-a6f9-4094d3c6bd20@hook.com

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

 amazon_hook+3fe78c41-e4ea-43b5-a6f9-4094d3c6bd20@hook.com

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

 amazon_hook+3fe78c41-e4ea-43b5-a6f9-4094d3c6bd20@hook.com

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

 amazon_hook+3fe78c41-e4ea-43b5-a6f9-4094d3c6bd20@hook.com

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

 amazon_hook+3fe78c41-e4ea-43b5-a6f9-4094d3c6bd20@hook.com

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

 amazon_hook+3fe78c41-e4ea-43b5-a6f9-4094d3c6bd20@hook.com

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

 amazon_hook+3fe78c41-e4ea-43b5-a6f9-4094d3c6bd20@hook.com

Candidate Report Page 19 of 19