I enjoy coding challenges. It makes me think outside my daily work routine. Last weekend I received the following email message from HackerRank:
Hi John,
Improve your skills with this challenge recommended for you:
Waiter
Data Structures | 2,031 submissions
Print the correct order of plates.
Solve Challenge
Happy coding,
The HackerRank team
I clicked on the green button <Waiter> on the message and was transported to the following URL: https://www.hackerrank.com/challenges/waiter?utm_campaign=challenge-recommendation&utm_medium=email&utm_source=24-hour-campaign
Before moving forward with this blog post, please follow the link and tell me if after reading the problem description you understand what the problem is about. It took me at least half dozen passes through the description and reading the discussions to figure out what the problem was all about. In particular what does the following sentence means?
“Then there will be Q iterations. In i-th iteration, you start picking up the plates in A [i – 1] from the top one by one and check whether the number written on the plate is divisible by the i-th prime”.
Using the test data, following is the console capture from the Eclipse IDE:
5 1 3 4 7 6 5 4 6 3 7 5
My solution passed the sample code.
I also ran the following data from a discussion:
10 2 1 8 11 23 18 2 15 30 4 5 8 18 2 30 4 15 5 23 11 1
The discussion answer 4 30 2 18 8 15 1 11 23 5 does not seem to match what mine produced. I believe the discussion results are incorrect.
The following sample input from another discussion when used in my solution seems to match:
10 3 1 2 3 4 5 6 7 8 9 10 2 4 6 8 10 9 3 5 1 7
My solution passed all tests at HackerRank. The solution in Java follows:
package com.canessa.john.waiter;
import java.util.ArrayList;
import java.util.Scanner;
import java.util.Stack;
public class Solution {
/*
*
*/
public static void main(String[] args) {
// **** ****
final boolean debug = false;
// **** array of first 1,200 prime numbers ****
final int[] prime = {
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59,
61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127,
131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193,
197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269,
271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349,
353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431,
433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503,
509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599,
601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673,
677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761,
769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857,
859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947,
953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031,
1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097,
1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187,
1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277,
1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327,
1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439,
1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499,
1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583,
1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663,
1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747,
1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811, 1823, 1831, 1847,
1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931,
1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997, 1999, 2003, 2011,
2017, 2027, 2029, 2039, 2053, 2063, 2069, 2081, 2083, 2087, 2089,
2099, 2111, 2113, 2129, 2131, 2137, 2141, 2143, 2153, 2161, 2179,
2203, 2207, 2213, 2221, 2237, 2239, 2243, 2251, 2267, 2269, 2273,
2281, 2287, 2293, 2297, 2309, 2311, 2333, 2339, 2341, 2347, 2351,
2357, 2371, 2377, 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423,
2437, 2441, 2447, 2459, 2467, 2473, 2477, 2503, 2521, 2531, 2539,
2543, 2549, 2551, 2557, 2579, 2591, 2593, 2609, 2617, 2621, 2633,
2647, 2657, 2659, 2663, 2671, 2677, 2683, 2687, 2689, 2693, 2699,
2707, 2711, 2713, 2719, 2729, 2731, 2741, 2749, 2753, 2767, 2777,
2789, 2791, 2797, 2801, 2803, 2819, 2833, 2837, 2843, 2851, 2857,
2861, 2879, 2887, 2897, 2903, 2909, 2917, 2927, 2939, 2953, 2957,
2963, 2969, 2971, 2999, 3001, 3011, 3019, 3023, 3037, 3041, 3049,
3061, 3067, 3079, 3083, 3089, 3109, 3119, 3121, 3137, 3163, 3167,
3169, 3181, 3187, 3191, 3203, 3209, 3217, 3221, 3229, 3251, 3253,
3257, 3259, 3271, 3299, 3301, 3307, 3313, 3319, 3323, 3329, 3331,
3343, 3347, 3359, 3361, 3371, 3373, 3389, 3391, 3407, 3413, 3433,
3449, 3457, 3461, 3463, 3467, 3469, 3491, 3499, 3511, 3517, 3527,
3529, 3533, 3539, 3541, 3547, 3557, 3559, 3571, 3581, 3583, 3593,
3607, 3613, 3617, 3623, 3631, 3637, 3643, 3659, 3671, 3673, 3677,
3691, 3697, 3701, 3709, 3719, 3727, 3733, 3739, 3761, 3767, 3769,
3779, 3793, 3797, 3803, 3821, 3823, 3833, 3847, 3851, 3853, 3863,
3877, 3881, 3889, 3907, 3911, 3917, 3919, 3923, 3929, 3931, 3943,
3947, 3967, 3989, 4001, 4003, 4007, 4013, 4019, 4021, 4027, 4049,
4051, 4057, 4073, 4079, 4091, 4093, 4099, 4111, 4127, 4129, 4133,
4139, 4153, 4157, 4159, 4177, 4201, 4211, 4217, 4219, 4229, 4231,
4241, 4243, 4253, 4259, 4261, 4271, 4273, 4283, 4289, 4297, 4327,
4337, 4339, 4349, 4357, 4363, 4373, 4391, 4397, 4409, 4421, 4423,
4441, 4447, 4451, 4457, 4463, 4481, 4483, 4493, 4507, 4513, 4517,
4519, 4523, 4547, 4549, 4561, 4567, 4583, 4591, 4597, 4603, 4621,
4637, 4639, 4643, 4649, 4651, 4657, 4663, 4673, 4679, 4691, 4703,
4721, 4723, 4729, 4733, 4751, 4759, 4783, 4787, 4789, 4793, 4799,
4801, 4813, 4817, 4831, 4861, 4871, 4877, 4889, 4903, 4909, 4919,
4931, 4933, 4937, 4943, 4951, 4957, 4967, 4969, 4973, 4987, 4993,
4999, 5003, 5009, 5011, 5021, 5023, 5039, 5051, 5059, 5077, 5081,
5087, 5099, 5101, 5107, 5113, 5119, 5147, 5153, 5167, 5171, 5179,
5189, 5197, 5209, 5227, 5231, 5233, 5237, 5261, 5273, 5279, 5281,
5297, 5303, 5309, 5323, 5333, 5347, 5351, 5381, 5387, 5393, 5399,
5407, 5413, 5417, 5419, 5431, 5437, 5441, 5443, 5449, 5471, 5477,
5479, 5483, 5501, 5503, 5507, 5519, 5521, 5527, 5531, 5557, 5563,
5569, 5573, 5581, 5591, 5623, 5639, 5641, 5647, 5651, 5653, 5657,
5659, 5669, 5683, 5689, 5693, 5701, 5711, 5717, 5737, 5741, 5743,
5749, 5779, 5783, 5791, 5801, 5807, 5813, 5821, 5827, 5839, 5843,
5849, 5851, 5857, 5861, 5867, 5869, 5879, 5881, 5897, 5903, 5923,
5927, 5939, 5953, 5981, 5987, 6007, 6011, 6029, 6037, 6043, 6047,
6053, 6067, 6073, 6079, 6089, 6091, 6101, 6113, 6121, 6131, 6133,
6143, 6151, 6163, 6173, 6197, 6199, 6203, 6211, 6217, 6221, 6229,
6247, 6257, 6263, 6269, 6271, 6277, 6287, 6299, 6301, 6311, 6317,
6323, 6329, 6337, 6343, 6353, 6359, 6361, 6367, 6373, 6379, 6389,
6397, 6421, 6427, 6449, 6451, 6469, 6473, 6481, 6491, 6521, 6529,
6547, 6551, 6553, 6563, 6569, 6571, 6577, 6581, 6599, 6607, 6619,
6637, 6653, 6659, 6661, 6673, 6679, 6689, 6691, 6701, 6703, 6709,
6719, 6733, 6737, 6761, 6763, 6779, 6781, 6791, 6793, 6803, 6823,
6827, 6829, 6833, 6841, 6857, 6863, 6869, 6871, 6883, 6899, 6907,
6911, 6917, 6947, 6949, 6959, 6961, 6967, 6971, 6977, 6983, 6991,
6997, 7001, 7013, 7019, 7027, 7039, 7043, 7057, 7069, 7079, 7103,
7109, 7121, 7127, 7129, 7151, 7159, 7177, 7187, 7193, 7207, 7211,
7213, 7219, 7229, 7237, 7243, 7247, 7253, 7283, 7297, 7307, 7309,
7321, 7331, 7333, 7349, 7351, 7369, 7393, 7411, 7417, 7433, 7451,
7457, 7459, 7477, 7481, 7487, 7489, 7499, 7507, 7517, 7523, 7529,
7537, 7541, 7547, 7549, 7559, 7561, 7573, 7577, 7583, 7589, 7591,
7603, 7607, 7621, 7639, 7643, 7649, 7669, 7673, 7681, 7687, 7691,
7699, 7703, 7717, 7723, 7727, 7741, 7753, 7757, 7759, 7789, 7793,
7817, 7823, 7829, 7841, 7853, 7867, 7873, 7877, 7879, 7883, 7901,
7907, 7919, 7927, 7933, 7937, 7949, 7951, 7963, 7993, 8009, 8011,
8017, 8039, 8053, 8059, 8069, 8081, 8087, 8089, 8093, 8101, 8111,
8117, 8123, 8147, 8161, 8167, 8171, 8179, 8191, 8209, 8219, 8221,
8231, 8233, 8237, 8243, 8263, 8269, 8273, 8287, 8291, 8293, 8297,
8311, 8317, 8329, 8353, 8363, 8369, 8377, 8387, 8389, 8419, 8423,
8429, 8431, 8443, 8447, 8461, 8467, 8501, 8513, 8521, 8527, 8537,
8539, 8543, 8563, 8573, 8581, 8597, 8599, 8609, 8623, 8627, 8629,
8641, 8647, 8663, 8669, 8677, 8681, 8689, 8693, 8699, 8707, 8713,
8719, 8731, 8737, 8741, 8747, 8753, 8761, 8779, 8783, 8803, 8807,
8819, 8821, 8831, 8837, 8839, 8849, 8861, 8863, 8867, 8887, 8893,
8923, 8929, 8933, 8941, 8951, 8963, 8969, 8971, 8999, 9001, 9007,
9011, 9013, 9029, 9041, 9043, 9049, 9059, 9067, 9091, 9103, 9109,
9127, 9133, 9137, 9151, 9157, 9161, 9173, 9181, 9187, 9199, 9203,
9209, 9221, 9227, 9239, 9241, 9257, 9277, 9281, 9283, 9293, 9311,
9319, 9323, 9337, 9341, 9343, 9349, 9371, 9377, 9391, 9397, 9403,
9413, 9419, 9421, 9431, 9433, 9437, 9439, 9461, 9463, 9467, 9473,
9479, 9491, 9497, 9511, 9521, 9533, 9539, 9547, 9551, 9587, 9601,
9613, 9619, 9623, 9629, 9631, 9643, 9649, 9661, 9677, 9679, 9689,
9697, 9719, 9721, 9733
};
// **** list of Q stacks ****
ArrayList<Stack<Integer>> A = new ArrayList<Stack<Integer>>();
ArrayList<Stack<Integer>> B = new ArrayList<Stack<Integer>>();
Stack<Integer> aStack = null;
Stack<Integer> bStack = null;
// **** ****
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int Q = sc.nextInt();
for (int q = 0; q <= Q; q++) {
A.add(new Stack<Integer>());
B.add(new Stack<Integer>());
}
// **** push plates on stack A[0] ****
Stack<Integer> stack = A.get(0);
for (int n = 0; n < N; n++) {
stack.push(sc.nextInt());
}
sc.close();
// **** Q iterations ****
for (int i = 1; i <= Q; i++) {
if (debug) {
System.out.println("main <<< i: " + i);
}
// **** current stack ****
stack = A.get(i - 1);
// **** display contents of this stack ****
if (debug) {
if (stack.isEmpty()) {
System.out.println("main <<< A[" + (i - 1) + "] empty");
} else {
System.out.println("main <<< A[" + (i - 1) + "]: " + stack.toString());
}
}
// **** ****
if (debug) {
System.out.println("main <<< prime[" + (i - 1) + "]: " + prime[i - 1]);
}
// **** loop through all the plates in this stack ****
while (!stack.isEmpty()) {
int plate = stack.pop();
// **** ****
if (debug) {
System.out.println("main <<< plate: " + plate);
}
// **** check if divisible by the ith prime (what does it mean???) ****
if ((plate % prime[i - 1]) == 0) {
bStack = B.get(i);
bStack.push(plate);
} else {
aStack = A.get(i);
aStack.push(plate);
}
}
// **** display the state of the stacks ****
if (debug) {
System.out.println("main <<< aStack: " + aStack.toString());
System.out.println("main <<< bStack: " + bStack.toString());
}
}
// **** display the contents of the B stack(s) ****
for (int i = 0; i < B.size(); i++) {
if (debug) {
System.out.println("main <<< bStack i: " + i);
}
bStack = B.get(i);
while (!bStack.isEmpty()) {
System.out.println(bStack.pop());
}
}
// **** display the contents of the A stack(s) ****
for (int i = 0; i < A.size(); i++) {
if (debug) {
System.out.println("main <<< aStack i: " + i);
}
aStack = A.get(i);
while (!aStack.isEmpty()) {
System.out.println(aStack.pop());
}
}
}
}
The debug flag is new to my solutions. In production code I tend to add a debug flag per class. The debug flag may be turned on / off using some additional mechanism (not shown in this example). For this solution I am able to enable / disable the flag by changing the code :o(
The list of the first 1,200 prime numbers was generated courtesy of the following URL: http://www.free-online-calculator-use.com/prime-number-generator.html#calculator
The problem did not indicate if the prime list had to be generated or copied (as I did).
My comment on this challenge is not the actual problem but the description. A description falls under the requirements specification. In this case this is one of the worse requirements I have ever seen at HackerRank. There is an entire discipline in Computer Science called Software Engineering which among other topics deals with Software Requirements. In my humble opinion, the requirements for this challenge would not be acceptable.
If you have comments or questions regarding this or any other post in this blog, do not be shy and send me a message. I will not use your name unless you explicitly state it.
Enjoy;
John
Follow me on Twitter: @john_canessa
Thanks for your post and giving the list of primes. my solution for prim number was to generate them on the fly, which cause hackerRank test Environment not be able to to run the tests and my solution reach the maximum time limit quickly.
I used your list of primes and it helped me to solve the challenge immediately.
Hashem, great that the post was of help.
Thanks for the message.