9/8/2019 Programming problems and Competitions :: HackerRank

Kargil assessment from placement perspe…  abhishekyadav88846@gmail.com

Full Name: Abhishek Yadav

Email: abhishekyadav88846@gmail.com scored in Kargil assessment

100%
Test Name: Kargil assessment from placement from placement
perspective(2021) (2) 375/375 perspective(2021) (2) in 180
min 25 sec on 8 Sep 2019
Taken On: 8 Sep 2019 04:41:21 EDT 04:41:21 EDT
Time Taken: 180 min 25 sec/ 300 min

Work Experience: < 1 years

Student Roll Number: 17BCS1612

Personal Email Address: abhishekyadav88846@gmail.com

CGPA: 7.98

Contact Number: 8732837125

Stream/Branch: CSE

section k1 k2 k3 with group: K2-G1

Gender: Male

Invited by: Jagandeep

Tags Score: Algorithms 375/375

Arrays 125/125
Core Skills 325/325
Data Structures 200/200
Easy 150/150
Flood Fill 50/50
Implementation 75/75
Math 75/75
Medium 225/225
Number Theory 75/75
Problem Solving 375/375
Sorting 75/75

Recruiter/Team Comments:

No Comments.

Question Description Time Taken Score Status

Q1 Cutting Metal Surplus  Coding 28 min 50 sec 75/ 75 

Q2 Strokes to paint  Coding 7 min 45 sec 50/ 50 
Q3 PowerSum  Coding 1 hour 47 sec 75/ 75 
1/17
 Q4 Cut the Bamboo  Coding 4 min 23 sec 50/ 50 
9/8/2019 Programming problems and Competitions :: HackerRank
Q5 Efficient Janitor  Coding 1 hour 10 min 50 sec 50/ 50 
Q6 Image Editing  Coding 7 min 28 sec 75/ 75 

QUESTION 1 Cutting Metal Surplus 


Coding Data Structures Medium Algorithms Arrays Sorting

Problem Solving Core Skills

Correct Answer

QUESTION DESCRIPTION
Score 75
The owner of a metal rod factory has a surplus of rods of arbitrary lengths. A local contractor offers to buy
any of the factory's surplus as long as all the rods have the same exact integer length, referred to as
saleLength. The factory owner can increase the number of sellable rods by cutting each rod zero or more
times, but each cut has a cost denoted by costPerCut. After all cuts have been made, any leftover rods
having a length other than saleLength must be discarded for no profit. The factory owner's total profit for
the sale is calculated as:

totalProfit = totalUniformRods × saleLength × salePrice − totalCuts × costPerCut

where totalUniformRods is the number of sellable rods, salePrice is the per unit length price that the
contractor agrees to pay, and totalCuts is the total number of times the rods needed to be cut.

For example, the owner has three rods, lengths = [30, 59, 110]. The costPerCut = 1 and the salePrice = 10
per unit length. The following are tests based on lengths that are factors of 30, the length of the shortest
bar. Factors of other lengths might also be tested, but this will demonstrate the methodology.

Cuts
---------------------
Length Rod Extra Regular Total Pieces
----------------------------------------------
30 30 0 0 0 1
59 1 0 1 1
110 1 2 3 3
Revenue = (10*5*30)-(4*1) = 1496
15 30 0 1 1 2
59 1 2 3 3
110 1 6 7 7
Revenue = (10*12*15)-(11*1) = 1789
10 30 0 2 2 3
59 1 4 5 5
110 0 10 10 11
Revenue = (10*19*10)-(17*1) = 1883
6 30 0 4 4 5
59 1 8 9 9
110 1 17 18 18
Revenue = (10*32*6)-(31*1) = 1889
5 30 0 5 5 6
59 1 10 11 11
110 0 21 21 21
Revenue = (10*39*5)-(37*1) = 1913
3 30 0 9 9 10
59 1 18 19 19
110 1 35 36 36
Revenue = (10*65*3)-(64*1) = 1886

Working through the first stanza, Length = 30, it's the same length as the first rod, so no cuts required and
there is 1 piece. The second rod, cut and discard the excess 29 unit rod. No more cuts are necessary and
have another 1 piece to sell. Cut 20 units off the 110 unit rod to discard leaving 90 units, then make two
more cuts to have 3 more pieces to sell. Finally sell 5 totalUniformRods , saleLength = 30 at salePrice = 10
per unit length for 1500. The cost to produce was totalCuts = 4 times costPerCut = 1 per cut, or 4. Total
revenue = 1500-4=1496. The maximum revenue among these tests is obtained at length 5: 1913.

2/17
 9/8/2019 Function DescriptionProgramming problems and Competitions :: HackerRank
Complete the function maxProfit in the editor below. The function must return an integer that denotes the
maximum possible profit.

maxProfit has the following parameter(s):

costPerCut: integer cost to make a cut
salePrice: integer per unit length sales price
lengths[lengths[0],...lengths[n-1]]: an array of integer rod lengths

Constraints
1 ≤ n ≤ 50
1 ≤ lengths[i] ≤ 104
1 ≤ salePrice, costPerCut ≤ 1000

Input Format for Custom Testing

Input from stdin will be processed as follows and passed to the function.

The first line contains an integer, costPerCut.

The second line contains an integer, salePrice.
The next line contains an integer n, the size of the array lengths.
Each of the next n lines contains an integer lengths[i] where 0 ≤ i < n.

Sample Case 0

Sample Input 0

1
10
3
26
103
59

Sample Output 0

1770

Explanation 0
Since costPerCut = 1 is very inexpensive, a large number of cuts can be made to reduce the number of
wasted pieces. The optimal rod length for maximizing profit is 6, and the rods are cut like this:
lengths[0] = 26 : Cut off a piece of length 2 and discard it, resulting in a rod of length 24.
Then cut this rod into 4 pieces of length 6.
lengths[1] = 103 : Cut off a piece of length 1 and discard it, resulting in a rod of length 102.
Then cut this rod into 17 pieces of length 6.
lengths[2] = 59 : Cut off a piece of length 5 and discard it, resulting in a rod of length 54.
Then cut this rod into 9 pieces of length 6.

After performing totalCuts = (1 + 3) + (1 + 16) + (1 + 8) = 30 cuts, there are totalUniformRods = 4 + 17 +

9 = 30 pieces of length saleLength = 6 that can be sold at salePrice = 10. This yields a total profit of
salePrice × totalUniformRods × saleLength − totalCuts × costPerCut = 10 × 30 × 6 − 30 × 1 = 1770.

Sample Case 1

Sample Input 1

100
3/17
 10
9/8/2019 3 Programming problems and Competitions :: HackerRank
26
103
59

Sample Output 1

1230

Explanation 1
Since costPerCut = 100, cuts are expensive and must be minimal. The optimal rod length for
maximizing profit is 51, and the rods are cut like this:
lengths[0] = 26 : Discard this rod entirely.
lengths[1] = 103 : Cut off a piece of length 1 and discard it, resulting in a rod of length 102.
Then cut this rod into 2 pieces of length 51.
lengths[2] = 59 : Cut off a piece of length 8 and discard it, resulting in a rod of length 51.

After performing totalCuts = (0) + (1 + 1) + (1) = 3 cuts, there are totalUniformRods = 0 + 2 + 1 = 3

pieces of length saleLength = 51 that can be sold at salePrice = 10 each. This yields a total profit of
salePrice × totalUniformRods × saleLength − totalCuts × costPerCut = 10 × 3 × 51 − 3 × 100 = 1230.

CANDIDATE ANSWER

Language used: C++

1 /*
2 * Complete the 'maxProfit' function below.
3 *
4 * The function is expected to return an INTEGER.
5 * The function accepts following parameters:
6 * 1. INTEGER costPerCut
7 * 2. INTEGER salePrice
8 * 3. INTEGER_ARRAY lengths
9 */
10
11 int maxProfit(int costPerCut, int salePrice, vector<int> lengths) {
12 int x = *max_element(lengths.begin(), lengths.end());
13 int n = (int) lengths.size();
14 int res = -(1e9);
15 for(int len = 1; len <= x + 1; ++len) {
16 int cuts = 0, rods = 0;
17 for(int i = 0; i < n; ++i) {
18 int p = lengths[i] / len, q = ceil(lengths[i] / (len + .0)) - 1;
19 int get = salePrice * len * p - q * costPerCut;
20 if(get > 0) {
21 rods += p;
22 cuts += q;
23 }
24 }
25 res = max(res, rods * salePrice * len - cuts * costPerCut);
26 }
27 return res;
28 }
29
30
31
4/17
 3
32
9/8/2019 Programming problems and Competitions :: HackerRank

TESTCASE DIFFICULTY TYPE STATUS SCORE TIME TAKEN MEMORY USED

TestCase 0 Easy Sample case  Success 2 0.003 sec 3.31 KB

TestCase 1 Easy Sample case  Success 2 0.0051 sec 3.34 KB

TestCase 2 Easy Hidden case  Success 4 0.0034 sec 3.24 KB

TestCase 3 Easy Hidden case  Success 4 0.0041 sec 3.33 KB

TestCase 4 Easy Hidden case  Success 4 0.0041 sec 3.28 KB

TestCase 5 Easy Hidden case  Success 4 0.0036 sec 3.39 KB

TestCase 6 Medium Hidden case  Success 7 0.003 sec 3.37 KB

TestCase 7 Medium Hidden case  Success 7 0.0032 sec 3.39 KB

TestCase 8 Medium Hidden case  Success 7 0.0046 sec 3.24 KB

TestCase 9 Hard Hidden case  Success 17 0.008 sec 3.25 KB

TestCase 10 Hard Hidden case  Success 17 0.0065 sec 3.31 KB

No Comments

QUESTION 2 Strokes to paint 


Coding Easy Problem Solving Algorithms Flood Fill

Correct Answer
QUESTION DESCRIPTION

Alex wants to paint a picture. In one stroke, Alex can only paint the same colored cells which are joined via
Score 50
some edge.
 
Given the painting as a 2-dimensional array of letters indicating colors, determine the minimum number of
strokes to completely paint the picture.
 
Example: The canvas height, h = 3 and width, w = 5 is to be painted with picture=["aabba", "aabba",
"aaacb"]. The diagram below shows the 5 strokes needed to paint the canvas. It takes two strokes each for
colors a and b, and one for c.

a a b b a
a a b b a
a a a c b
Function Description
Complete the function strokesRequired in the editor below. The function must return an integer, the
minimum number of strokes required to paint the canvas.

strokesRequired has the following parameter(s):

picture[picture[0],...picture[h-1]]: an array of strings where each string represents one row of the picture
to be painted

Constraints
1 ≤ h ≤ 105
1 ≤ w ≤ 105
1 ≤ h*w ≤ 105
len(picture[i]) = w (where 0 ≤ i < h)
picture[i][j] ∈ {'a' 'b' 'c'} (where 0 ≤ i < h and 0 ≤ j < w)
5/17
 picture[i][j] ∈ { a , b , c } (where 0 ≤ i < h and 0 ≤ j < w)

9/8/2019 Programming problems and Competitions :: HackerRank

Input Format For Custom Testing

The first line contains an integer, h, that denotes the height of the picture and the number of elements in
picture.

Each line i of the h subsequent lines (where 0 ≤ i < h) contains a string that describes picture[i].

Sample Case 0

Sample Input For Custom Testing

3
aaaba
ababa
aaaca

Sample Output

Explanation

a a a b a
a b a b a
a a a c a
Color a takes 2 strokes, b takes 2 strokes and c takes 1 stroke for a total of 5.

Sample Case 1

Sample Input For Custom Testing

4
bbba
abba
acaa
aaac

Sample Output

Explanation

b b b a
a b b a
a c a a
a a a c
Colors a and b each take 1 stroke, and color c takes 2 strokes.

CANDIDATE ANSWER

Language used: C++

1 /*
2 * Complete the 'strokesRequired' function below.
3 *
4 * The function is expected to return an INTEGER
6/17
 4 * The function is expected to return an INTEGER.
5 * The function accepts STRING_ARRAY picture as parameter.
9/8/2019 Programming problems and Competitions :: HackerRank
6 */
7 const vector<int> dx = {0, -1, 0, 1};
8 const vector<int> dy = {1, 0, -1, 0};
9
10 int strokesRequired(vector<string> picture) {
11 int n = (int) picture.size();
12 int m = (int) picture[0].size();
13 vector<vector<bool>> vis(n, vector<bool>(m, false));
14 function<void(int, int)> dfs = [&](int x, int y) {
15 vis[x][y] = true;
16 for(int i = 0; i < 4; ++i) {
17 int a = x + dx[i], b = y + dy[i];
18 if(a < 0 || a >= n || b < 0 || b >= m || vis[a][b] || picture[x][y] !=
19 picture[a][b]) {
20 continue;
21 }
22 dfs(a, b);
23 }
24 };
25 int res = 0;
26 for(int i = 0; i < n; ++i) {
27 for(int j = 0; j < m; ++j) {
28 if(!vis[i][j]) {
29 res++;
30 dfs(i, j);
31 }
32 }
33 }
34 return res;
35 }
36
37
38

TESTCASE DIFFICULTY TYPE STATUS SCORE TIME TAKEN MEMORY USED

Test Case 0 Easy Sample case  Success 1 0.0049 sec 3.32 KB

Test Case 1 Easy Sample case  Success 1 0.0029 sec 3.3 KB

Test Case 2 Easy Sample case  Success 1 0.0039 sec 3.39 KB

Test Case 3 Easy Hidden case  Success 4 0.0029 sec 3.27 KB

Test Case 4 Easy Hidden case  Success 4 0.0041 sec 3.29 KB

Test Case 5 Easy Hidden case  Success 4 0.0066 sec 3.32 KB

Test Case 6 Easy Hidden case  Success 5 0.0037 sec 3.32 KB

Test Case 7 Easy Hidden case  Success 5 0.004 sec 3.42 KB

Test Case 8 Easy Hidden case  Success 5 0.0065 sec 3.5 KB

Test Case 9 Easy Hidden case  Success 5 0.0042 sec 3.42 KB

Test Case 10 Easy Hidden case  Success 5 0.0042 sec 3.32 KB

Test Case 11 Easy Hidden case  Success 5 0.0105 sec 3.39 KB

Test Case 12 Easy Hidden case  Success 5 0.0146 sec 4.61 KB

No Comments

QUESTION 3 S
7/17
 QUESTION 3 PowerSum 

Coding Math Number Theory Medium Algorithms Problem Solving

9/8/2019 Core Skills Programming problems and Competitions :: HackerRank

Correct Answer

QUESTION DESCRIPTION
Score 75
Given two integers, l and r, find the number of integers x such that l ≤ x ≤ r, and x is a Power Number.

A Power Number is defined as an integer that can be represented as sum of two powers, i.e.
x = ap + bq
a, b, p and q are all integers
a, b ≥ 0
p, q > 1

For example, given l=20 and r=25:

20 = 22 + 42
24 = 23 + 42
25 = 32 + 42
Function Description
Complete the function countPowerNumbers in the editor below. The function must return the integer count
of power numbers in the given range.

countPowerNumbers has the following parameter(s):

l: integer, the lower limit of the inclusive range
r: integer, the upper limit of the inclusive range

Constraints:
0 ≤ l ≤ r ≤ 5 ×106

Input Format for Custom Testing

Input from stdin will be processed as follows and passed to the function.

The first line contains an integer l.

The next line contains an integer r.

Sample Case 0

Sample Input 0

0
1

Sample Output 0

Explanation 0
0 and 1 both are Power Numbers.
0 = 02 + 02
1 = 02 + 12

Sample Case 1

Sample Input 1

25
30

Sample Output 1
8/17
 9/8/2019
5 Programming problems and Competitions :: HackerRank

Explanation 1
Except 30, all are Power Numbers.
25 = 52 + 02
26 = 52  + 12
27 = 33 + 02
28 = 33  + 12
29 = 52 + 22

CANDIDATE ANSWER

Language used: C++

1 /*
2 * Complete the 'countPowerNumbers' function below.
3 *
4 * The function is expected to return an INTEGER.
5 * The function accepts following parameters:
6 * 1. INTEGER l
7 * 2. INTEGER r
8 */
9 const int N = int(5.1e6);
10
11 int countPowerNumbers(int l, int r) {
12 vector<int> pw(N);
13 pw[1] = 1;
14 pw[0] = 1;
15 int ew = 0;
16 vector<int> nos;
17 nos.push_back(0);
18 nos.push_back(1);
19 for(long long i = 2; i < N; ++i) {
20 if(pw[i]) continue;
21 for(long long p = i * i; p < N; p *= i) {
22 pw[p] = 1;
23 nos.push_back(p);
24 }
25 }
26 set<int> px;
27 int n = (int) nos.size();
28 // return n;
29 vector<int> x(r + 1);
30 for(int i = 0; i < n; ++i) {
31 for(int j = 0; j < n; ++j) {
32 if(nos[i] + nos[j] > r) continue;
33 x[nos[i] + nos[j]] = 1;
34 }
35 }
36 int res = 0;
37 for(int i = l; i <= r; ++i) {
38 if(x[i]) res++;
39 }
40 return res;
41 }
42
43
44
45
9/17
 45

9/8/2019 Programming problems and Competitions :: HackerRank

TESTCASE DIFFICULTY TYPE STATUS SCORE TIME TAKEN MEMORY USED

Testcase 0 Easy Sample case  Success 1 0.0411 sec 22.6 KB

Testcase 2 Easy Sample case  Success 1 0.0375 sec 22.6 KB

Testcase 3 Easy Hidden case  Success 5 0.0328 sec 22.7 KB

Testcase 4 Medium Hidden case  Success 8 0.0625 sec 22.6 KB

Testcase 5 Easy Hidden case  Success 5 0.0424 sec 22.6 KB

Testcase 6 Easy Hidden case  Success 5 0.0287 sec 22.6 KB

Testcase 7 Medium Hidden case  Success 10 0.034 sec 22.7 KB

Testcase 8 Medium Hidden case  Success 10 0.034 sec 22.6 KB

Testcase 9 Hard Hidden case  Success 15 0.0403 sec 24.4 KB

Testcase 10 Hard Hidden case  Success 15 0.0999 sec 26.3 KB

No Comments

QUESTION 4 Cut the Bamboo 


Coding Easy Data Structures Algorithms Arrays Problem Solving

Core Skills
Correct Answer

QUESTION DESCRIPTION
Score 50
Given an array with the lengths pieces of bamboo, repeatedly perform the following:

1. Count the number of pieces of bamboo.

2. Find the shortest length piece(s).
3. Discard any piece of that length.
4. Cut that shortest length from each of the longer pieces.  Each piece just cut is an offcut.
5. Discard all offcuts.
6. Repeat until there are no more pieces.

Maintain an array of the numbers of pieces at the beginning of each round of actions.

For example, there are n = 4 pieces, with lengths = [1, 1, 3, 4]. The shortest pieces are 1 unit long, so
discard them and remember their length. Remove their length, 1 unit, from the longer pieces and discard
the offcuts. Now there are 2 pieces of bamboo, lengths = [2, 3]. Discard the piece of length 2, cut 2 from
the piece length 3 and discard the offcut. Now there is only one piece of length 1. Discard it and return an
array with the number of pieces at the start of each turn: [4, 2, 1].

lengths cut length pieces

1 1 3 4 1 4
_ _ 2 3 2 2
_ _ _ 1 1 1
_ _ _ _ DONE DONE

Function Description
Complete the function cutBamboo in the editor below. The function must return an array of integers, each
the number of pieces at the start of a turn.

cutBamboo has the following parameter(s):

lengths[lengths[0],...lengths[n-1]]: an array of integers that represent the starting lengths of each piece
of bamboo
10/17
 9/8/2019 Constraints Programming problems and Competitions :: HackerRank

1 ≤ n ≤ 103
1 ≤ lengths[i] ≤ 103, where 0 ≤ i < n

Input Format for Custom Testing

Input from stdin will be processed as follows and passed to the function.

The first line contains an integer n, the number elements in lengths.

The next n lines each represents lengths[i] where 0 ≤ i < n.

Sample Case 0

Sample Input 0

6
5
4
4
2
2
8

Sample Output 0

6
4
2
1

Explanation 0

lengths cut length pieces

5 4 4 2 2 8 2 6
3 2 2 _ _ 6 2 4
1 _ _ _ _ 4 1 2
_ _ _ _ _ 3 3 1
_ _ _ _ _ _ DONE DONE

Sample Case 1

Sample Input 1

8
1
2
3
4
3
3
2
1

Sample Output 1

8
6
4
1

Explanation 1
11/17
 p a at o

9/8/2019 lengths cut length

Programming pieces
problems and Competitions :: HackerRank
1 2 3 4 3 3 2 1 1 8
_ 1 2 3 2 2 1 _ 1 6
_ _ 1 2 1 1 _ _ 1 4
_ _ _ 1 _ _ _ _ 1 1
_ _ _ _ _ _ _ _ DONE DONE

CANDIDATE ANSWER

Language used: C++

1 /*
2 * Complete the 'cutBamboo' function below.
3 *
4 * The function is expected to return an INTEGER_ARRAY.
5 * The function accepts INTEGER_ARRAY lengths as parameter.
6 */
7
8 vector<int> cutBamboo(vector<int> lengths) {
9 map<int, int> mp;
10 int tot = (int) lengths.size();
11 for(int x: lengths) mp[x]++;
12 int h = 0;
13 vector<int> res;
14 while(!mp.empty()) {
15 res.push_back(tot);
16 tot -= mp.begin()->second;
17 mp.erase(mp.begin());
18 }
19 return res;
20 }
21
22
23
24

TESTCASE DIFFICULTY TYPE STATUS SCORE TIME TAKEN MEMORY USED

TestCase 0 Easy Sample case  Success 1 0.0031 sec 3.39 KB

TestCase 1 Easy Sample case  Success 1 0.0066 sec 3.28 KB

TestCase 2 Medium Sample case  Success 1 0.0037 sec 3.31 KB

TestCase 3 Medium Hidden case  Success 7 0.0045 sec 3.29 KB

TestCase 4 Medium Hidden case  Success 7 0.0031 sec 3.27 KB

TestCase 5 Hard Hidden case  Success 8 0.003 sec 3.32 KB

TestCase 6 Hard Hidden case  Success 8 0.0036 sec 3.35 KB

TestCase 7 Hard Hidden case  Success 8 0.0031 sec 3.39 KB

TestCase 8 Easy Hidden case  Success 3 0.0033 sec 3.29 KB

Testcase 9 Easy Hidden case  Success 3 0.0041 sec 3.28 KB

Testcase 10 Easy Hidden case  Success 3 0.0053 sec 3.28 KB

No Comments

12/17
 QUESTION 5 Efficient Janitor Programming

9/8/2019  Coding Easy Problem
problems andSolving Algorithms
Competitions Core Skills
:: HackerRank

Correct Answer
QUESTION DESCRIPTION

The janitor of a high school is extremely efficient. By the end of each day, the janitor shifts all of the waste
Score 50
from the trash cans in the school into plastic bags which can carry waste weighing between 1.01 pounds
and 3.00 pounds. All of the plastic bags are dumped into the trash cans outside the school. The janitor can
carry at most 3.00 pounds at once.
One trip is described as selecting a few bags which together don't weigh more than 3.00 pounds, dumping
them in the outdoor trash can and returning to the school. The janitor wants to make a minimum number of
trips to the outdoor trash can. Given the number of plastic bags, n, and the weight of each bag, determine
the minimum number of trips if the janitor optimally selects bags.

For example, given n = 6 plastic bags weighing weight = [1.01, 1.99, 2.5, 1.5, 1.01], the janitor can carry
all of the trash out in 3 trips: [1.01 + 1.99 , 2.5, 1.5 + 1.01].
 
Function Description

Complete the function efficientJanitor in the editor below. The function must return a single integer that
represents the minimum number of trips to be made.

efficientJanitor has the following parameter(s):

weight[weight[0],...weight[n-1]]: an array of floating-point integers

Constraints
1 ≤ n ≤ 1000
1.01 ≤ weight[i] ≤ 3.0

Input Format For Custom Testing

The first line contains an integer, n, that denotes the number of elements in weight.

Each line i of the n subsequent lines (where 0 ≤ i < n) contains an integer that describes weight[i].

Sample Case 0

Sample Input For Custom Testing

5
1.50
1.50
1.50
1.50
1.50

Sample Output

Explanation
In this case, the janitor will carry the first 2 plastic bags together, the 3rd and 4th together and the last
one alone to dispose of all of the trash in 3 trips.

Sample Case 1

Sample Input For Custom Testing

4
1.50
1.50
1.50
1.50

S l O t t
13/17
 Sample Output

9/8/2019 2 Programming problems and Competitions :: HackerRank

Explanation
In this case, the janitor will carry the first 2 plastics bags together and the 3rd and 4th together requiring
only 2 trips.

CANDIDATE ANSWER

Language used: C++

1 /*
2 * Complete the 'efficientJanitor' function below.
3 *
4 * The function is expected to return an INTEGER.
5 * The function accepts FLOAT_ARRAY weight as parameter.
6 */
7
8 int efficientJanitor(vector<float> weight) {
9 int a = 0, b = 0;
10 map<int, int> mp;
11 for(float x: weight) {
12 if(x >= 2.000000000) {
13 a++;
14 continue;
15 }
16 string p = to_string(x).substr(0, 4);
17 int f = p[0] - '0';\
18 for(int i = 2; i < (int) p.size(); ++i) {
19 f = f * 10 + (p[i] - '0');
20 }
21 mp[f]++;
22 }
23 int res = 0;
24 for(int i = 101; i <= 149; ++i) {
25 for(int j = 300 - i; j > 150; --j) {
26 if(mp[i] == 0) break;
27 int x = min(mp[i], mp[j]);
28 mp[i] -= x;
29 mp[j] -= x;
30 res += x;
31 }
32 }
33 int c = 0;
34 for(auto x: mp) {
35 if(x.first <= 150) c += x.second;
36 else a += x.second;
37 }
38 return a + res + ceil(c / 2.000);
39 }
40
41
42
43

TESTCASE DIFFICULTY TYPE STATUS SCORE TIME TAKEN MEMORY USED

TestCase 0 Easy Sample case  Success 2 0.0037 sec 3.36 KB

TestCase 1 Easy Sample case  Success 2 0.0028 sec 3.46 KB

14/17
 9/8/2019
TestCase 4 Easy Sample case  Success 2
Programming problems and Competitions :: HackerRank
0.004 sec 3.39 KB

TestCase 5 Easy Hidden case  Success 4 0.003 sec 3.36 KB

TestCase 7 Medium Hidden case  Success 6 0.0042 sec 3.36 KB

TestCase 8 Medium Hidden case  Success 8 0.0041 sec 3.42 KB

TestCase 10 Hard Hidden case  Success 12 0.0036 sec 3.47 KB

TestCase 11 Hard Hidden case  Success 14 0.0032 sec 3.4 KB

No Comments

QUESTION 6 Image Editing 


Coding Algorithms Data Structures Implementation Medium

Problem Solving Core Skills

Correct Answer

QUESTION DESCRIPTION
Score 75
Casey has a square image made up of black and white pixels represented as 0 and 1 respectively. As part
of an image analysis process, Casey needs to determine the size of the largest square area of white
pixels. Given a 2-dimensional square matrix that represents the image, write a function to determine the
length of a side of the largest square area made up of white pixels.

For example, the n x n = 5 x 5 matrix of pixels is represented as

arr = [[1,1,1,1,1],
[1,1,1,0,0],
[1,1,1,0,0],
[1,1,1,0,0],
[1,1,1,1,1]].

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

1 1 1 0 0 1 1 1 0 0 1 1 1 0 0

1 1 1 0 0 1 1 1 0 0 1 1 1 0 0

1 1 1 0 0 1 1 1 0 0 1 1 1 0 0

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

The largest square sub-matrix is 3 x 3 in size starting at position (0, 0), (1, 0), or (2, 0). The expected
return value is 3.

Function Description
Complete the function largestMatrix in the editor below. The function must return an integer that represents
the width of the largest square sub-matrix of white pixels.

largestMatrix has the following parameter:

arr[arr[0][0],...arr[n-1][n-1]]: a 2D array of integers

Constraints
1 ≤ n ≤ 500
arr[i][j] ∈ {0, 1} (0 denotes black pixel and 1 denotes white pixel)

Input Format For Custom Testing

The first line contains an integer, n, the number of rows.

The second line contains an integer, n, the number of columns.
15/17
 9/8/2019 Each line i of the n subsequent lines problems
Programming (where 0 ≤and
i < n) contains n space-separated
Competitions :: HackerRankintegers that describe
arr[i].

Sample Case 0

Sample Input For Custom Testing

3
3
1 1 1
1 1 0
1 0 1

Sample Output

Explanation

1 1 1

1 1 0

1 0 1

(0, 0) to (1,1) is the maximum square sub-matrix that contains all white pixels.

Sample Case 1

Sample Input For Custom Testing

3
3
0 1 1
1 1 0
1 0 1

Sample Output

Explanation

0 1 1

1 1 0

1 0 1

There is no square sub-matrix of size greater than 1 that contains all white pixels.

CANDIDATE ANSWER

Language used: C++

1 /*
2 * Complete the 'largestMatrix' function below.
3 *
4 * The function is expected to return an INTEGER.
5 * The function accepts 2D_INTEGER_ARRAY arr as parameter.
6 */
16/17
 6 /
7
9/8/2019 Programming problems and Competitions
8 int largestMatrix(vector<vector<int>> arr) { :: HackerRank
9 int n = (int) arr.size();
10 int m = (int) arr[0].size();
11 vector<vector<int>> dp(n, vector<int>(m, 0));
12 for(int i = 0; i < max(n, m); ++i) {
13 if(i < n) dp[i][0] = arr[i][0];
14 if(i < m) dp[0][i] = arr[0][i];
15 }
16 int mx = 0;
17 for(int i = 1; i < n; ++i) {
18 for(int j = 1; j < m; ++j) {
19 if(arr[i][j]) dp[i][j] = min({dp[i][j - 1], dp[i - 1][j], dp[i - 1][j -
20 1]}) + 1;
21 mx = max(mx, dp[i][j]);
22 }
23 }
24 return mx;
25 }
26
27
28

TESTCASE DIFFICULTY TYPE STATUS SCORE TIME TAKEN MEMORY USED

TestCase 0 Easy Sample case  Success 1 0.0031 sec 3.31 KB

TestCase 1 Easy Sample case  Success 1 0.0029 sec 3.29 KB

TestCase 2 Easy Sample case  Success 1 0.0031 sec 3.3 KB

TestCase 3 Easy Hidden case  Success 3 0.0063 sec 3.35 KB

TestCase 4 Easy Hidden case  Success 3 0.0033 sec 3.3 KB

TestCase 5 Easy Hidden case  Success 3 0.006 sec 3.33 KB

TestCase 6 Medium Hidden case  Success 6 0.0078 sec 3.4 KB

TestCase 7 Medium Hidden case  Success 6 0.0064 sec 3.44 KB

TestCase 8 Medium Hidden case  Success 6 0.0066 sec 3.46 KB

TestCase 9 Hard Hidden case  Success 10 0.0083 sec 3.48 KB

TestCase 10 Hard Hidden case  Success 10 0.0174 sec 3.69 KB

TestCase 11 Hard Hidden case  Success 10 0.0108 sec 3.78 KB

TestCase 12 Hard Hidden case  Success 15 0.036 sec 5.89 KB

No Comments

PDF generated at: 8 Sep 2019 11:42:57 UTC

17/17