The Masseuse

!!! UPDATED !!!

Updated the screen capture of the output for the code. The previous one was not displaying correctly.

This past weekend my youngest son and family who live in Madison, WI stopped by for a visit. They used the opportunity to drive to St. Cloud to visit my granddaughter and my older son and family who live in the Twin Cities area of Minneapolis and St. Paul. It is always good to spend time with family. They left for home yesterday afternoon. My wife and I made enough food to feed a lot more people so we will be having leftovers for a few days.

I gave a try to problem 17.16 in the Cracking the Coding Interview book by Gayle Laakmann McDowell. The problem is about a masseuse who has a set of consecutive appointments and wishes to optimize her time by taking care of as many customers as possible with the only caveat that she needs to take a break of 15 minutes within appointments.

I found this post The Masseuse where you can read the requirements for the problem. Of course, the recommended approach is to purchase a copy of Cracking the Coding Interview book.

I did spend time attempting to solve the problem. I do have to admit that I read the hints and on several times took a peek at the proposed solution in the book. I have to label this problem as difficult.

PS C:\Users\johnc\workspace1\TheMasseuse>  cd 'c:\Users\johnc\workspace1\TheMasseuse'; & 'c:\Users\johnc\.vscode\extensions\vscjava.vscode-java-debug-0.26.0\scripts\launcher.bat' 'C:\Program Files\RedHat\java-1.8.0-openjdk-1.8.0.242-3\bin\java.exe' '-agentlib:jdwp=transport=dt_socket,server=n,suspend=y,address=localhost:59839' '-Dfile.encoding=UTF-8' '-cp' 'C:\Users\johnc\workspace1\TheMasseuse\bin' 'Solution' 
8
30
15
60
75
45
15
15
45
main <<<    n: 8
main <<< apps: [30, 15, 60, 75, 45, 15, 15, 45]

maxMinutes <<< memo[7]: 45
maxMinutes <<< memo[6]: 45
maxMinutes <<< memo[5]: 60
maxMinutes <<< memo[4]: 90
maxMinutes <<< memo[3]: 135
maxMinutes <<< memo[2]: 150
maxMinutes <<< memo[1]: 150
maxMinutes <<< memo[0]: 180
main <<< sum: 180

maxMinutesIterative <<< bestWithout:   0 bestWith:  45
maxMinutesIterative <<< memo[7]:  45
maxMinutesIterative <<< bestWithout:  45 bestWith:  15
maxMinutesIterative <<< memo[6]:  45
maxMinutesIterative <<< bestWithout:  45 bestWith:  60
maxMinutesIterative <<< memo[5]:  60
maxMinutesIterative <<< bestWithout:  60 bestWith:  90
maxMinutesIterative <<< memo[4]:  90
maxMinutesIterative <<< bestWithout:  90 bestWith: 135
maxMinutesIterative <<< memo[3]: 135
maxMinutesIterative <<< bestWithout: 135 bestWith: 150
maxMinutesIterative <<< memo[2]: 150
maxMinutesIterative <<< bestWithout: 150 bestWith: 150
maxMinutesIterative <<< memo[1]: 150
maxMinutesIterative <<< bestWithout: 150 bestWith: 180
maxMinutesIterative <<< memo[0]: 180
main <<< sum: 180

maxMinutesOptimum <<< twoWay:   0 oneWay:  45
maxMinutesOptimum <<< twoWay:  45 oneWay:  45
maxMinutesOptimum <<< twoWay:  45 oneWay:  60
maxMinutesOptimum <<< twoWay:  60 oneWay:  90
maxMinutesOptimum <<< twoWay:  90 oneWay: 135
maxMinutesOptimum <<< twoWay: 135 oneWay: 150
maxMinutesOptimum <<< twoWay: 150 oneWay: 150
maxMinutesOptimum <<< twoWay: 150 oneWay: 180
main <<< sum: 180

PS C:\Users\johnc\workspace1\TheMasseuse> 

The screen capture of the Visual Studio Code IDE shows a run of the solution. We specify a number of consecutive massage appointments followed by the massage durations expressed in minutes. The idea is to return the maximum number of minutes the masseuse will be busy not listing the 15 minute intervals that need to be observed between consecutive appointments.

The next set of output lines invokes the maxMinutes() method which returns 180 minutes. The second set of lines display messages from the maxMinutesIterative() method which happens to return the same result. AS we will see in a few paragraphs, this method is more efficient that previous ones.

The maxMinutesOptimum() method returns the same result but uses an enhancement of the original approach but somewhat more efficient. In my humble opinion if you are presented with this problem and given about an hour to solve it, unless you have seen it before, chances are you will not be able to come up with the described set of methods.

	/**
	 * Test scaffolding.
	 */

	public static void main(String[] args) {

		// **** ****
		Scanner sc = new Scanner(System.in);
		
		// **** ****
		int n = sc.nextInt();
		
		// ???? ????
		System.out.println("main <<<    n: " + n);
		
		// **** ****
		int[] massages = new int[n];
		
		// **** ****
		for (int i = 0; i < n; i++) {
			massages[i] = sc.nextInt();
		}
		
		// ???? ????
		System.out.print("main <<< apps: [");
		for (int i = 0; i < massages.length; i++) {
			if (i + 1 < massages.length)
				System.out.print(massages[i] + ", ");
			else
				System.out.print(massages[i]);
		}
		System.out.println("]\n");
		
		// **** ****
		sc.close();
		
		// **** select apointmets that generate the maximum number of minutes ****
		int sum = maxMinutes(massages);
		System.out.println("main <<<  sum: " + sum + "\n");
		
		sum = maxMinutesIterative(massages);
		System.out.println("main <<<  sum: " + sum + "\n");
		
		sum = maxMinutesOptimum(massages);
		System.out.println("main <<<  sum: " + sum + "\n");
	}

The main() method shows the test scaffolding for this problem. We start by reading the massage appointments and then calling three different methods which produce the same results. The methods get more efficient as we progress from first to third.

	/**
	 * Entry point to compute the maximum number of minutes. 
         * Non-recursive method.
	 */
	static int maxMinutes(int[] massages) {
		
		// **** allocate array for memoization ****
		int[] memo = new int[massages.length];
		
		// **** ****
		return maxMinutes(massages, 0, memo);
	}

This is the entry point for the base method. In it we make use of the memo array. This array is used to support memoization. If you have a copy of the book you can see the first pass of the algorithm. It does not use memoization. I should have left a copy in my code but I missed it. Sorry about that. I did leave the code for the first pass. It is the commented code in this method. It is possible to make the necessary changes and reproduce it. Recursion needs a base condition / case to terminate. In this case it happens when the method is called with no slots in the array to be processed. The initial array makes the same computations at least twice. By storing the results, we can eliminate them by just indexing the proper value from the memo array. If the value is not present, we then compute it.

        /**
	 * Compute the maximum number of minutes.
	 * Recursive method.
	 * With memoization.
	 */
	static int maxMinutes(int[] massages, int i, int[] memo) {

		// **** end condition ****
		if (i >= massages.length)
			return 0;
	
		
//		// **** best with this reservation ****
//		int bestWith = massages[i] + maxMinutes(massages, i + 2);
//	
//		// **** best without this reservation ****
//		int bestWithOut = maxMinutes(massages, i + 1);
//		
//		// ???? ????
//		System.out.println("maxMinutes <<< i: " + i + " bestWith: " + bestWith + " bestWithOut: " + bestWithOut);
//
//		// **** best so far ****
//		return Math.max(bestWith, bestWithOut);
		
		
		// **** ****
		if (memo[i] == 0) {
//		{
			int bestIndex   = massages[i] + maxMinutes(massages, i + 2, memo);
			int bestWithout = maxMinutes(massages, i + 1, memo);
			memo[i] 		= Math.max(bestIndex, bestWithout);
			
			// ???? ????
			System.out.println("maxMinutes <<< memo[" + i + "]: " + memo[i]);
		}
		
		// **** this value is computed once ****
		return memo[i];
	}

In this case the memoization array needs to be a couple entries larger. The array is filled in reverse order. The optimum time is found in the first entry of the array. This solution is pretty close but seems like we can eliminate the array and use a couple variables.

        /**
	 * Same as with memoization but iterative.
	 */
	static int maxMinutesIterative(int[] massages) {
		
		// **** allocate array for memoization (need two extra slots) ****
		int[] memo = new int[massages.length + 2];
						
		// **** build memoization backwards ****
		for (int i = massages.length - 1; i >= 0; i--) {
			int bestWith 	= massages[i] + memo[i + 2];
			int bestWithout = memo[i + 1];
			memo[i]         = Math.max(bestWith, bestWithout);
			
			// ???? ????
			System.out.printf("maxMinutesIterative <<< bestWithout: %3d bestWith: %3d\n", bestWithout, bestWith);
			System.out.printf("maxMinutesIterative <<< memo[%d]: %3d\n", i, memo[i]);
		}

		// **** optimum time ****
		return memo[0];
	}

In the maxMinutesOptimum() method we do not make use of the memo array. Instead we use a couple variables given the fact that a value in the memo array is computed and used immediately. By making such observation the array can be replaced by a couple integer variables.

	/**
	 * Same as with memoization and iterative but optimal O(n) and O(1).
	 */
	static int maxMinutesOptimum(int[] massages) {
		
		// **** ****
		int oneWay = 0;
		int twoWay = 0;
		
		// **** ****
		for (int i = massages.length - 1; i >= 0; i--) {
			int bestWith 	= massages[i] + twoWay;
			int bestWithout = oneWay;
			int current     = Math.max(bestWith, bestWithout);
			twoWay          = oneWay;
			oneWay          = current;
			
			// ???? ????
//			System.out.println("maxMinutesOptimum <<< twoWay: " + twoWay + " oneWay: " + oneWay);
			System.out.printf("maxMinutesOptimum <<< twoWay: %3d oneWay: %3d\n", twoWay, oneWay);
		}
		
		// **** ****
		return oneWay;
	}

The longestIndex() method is not part of the solution. I used it to experiment with an approach. Later I used it to verify a statement that is made regarding skipping one or two consecutive massage appointments. It is not a good approach which may work in some cases but that is it.

	/**
	 * Index of longest appointment.
	 */
	static int longestIndex(int[] massages, int i) {

		// **** ****
		if (massages[i] > massages[i + 1]) {
			if (massages[i] > massages[i + 2])
				return i;
			else
				return i + 2;
		} else {
			if (massages[i + 1] > massages[i + 2])
				return i + 1;
			else
				return i + 2;
		}
	}

The entire code for this project can be found in my GitHub repository.

If you have comments or questions regarding this or any other post in this blog, or if you would like me to help with any phase in the SDLC (Software Development Life Cycle) of a product or service, please do not hesitate and leave me a note below. Requests for help will remain private.

Keep on reading and experimenting. It is the best way to learn and refresh your knowledge!

One last thing, many thanks to all 1,374 subscribers to my blog!!!

John

Follow me on Twitter:  @john_canessa