Waiter

hackerrank_logoI 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?programming_is_just_one_aspect_of_computer_science

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

prime_numbersMy 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).requirements-engineering-process-in-software-engineering-6-638

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

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.