#### Originally posted on May 30, 2010

Recently, I found this article on Java Lobby - Best Interview Question I've seen. This article was referring to a question posted by one recruiting agency.

While we can argue that it really is best question, but you have to give credit to the ingenuity in-terms of creating very simple but automated means of finding out if you got the correct answer for the puzzle. The recruiting agency created one email account with id equal to the correct answer. So, if you got the correct answer, you will not have your email bounced back.

Anyway, the problem sounded interesting to me so thought of giving it a shot. After few bounced mails, I finally got the correct answer as confirmed by my successful delivery of my mail (no bounce back).

Reading through the comments for the posting, I found out about interesting project - http://projecteuler.net/, which is hosting lot of similar puzzles. The puzzle number 18 and 67 happen to be similar to the one posted by the recruiting agency. If you dig Internet you will find lot of explanation and solution to the puzzle.

The problem defined here is also called Critical Path Method (CPM), used in project management for project duration estimation for execution of number of dependent tasks.

One way to solve such problem is brute force. But that would not scale beyond a certain depth of tree. For example, noting the following comment from Euler Problem 67 (a tree with depth of 100 rows):

*If you could check one trillion (1012) routes every second it would take over twenty billion years to check them all.*

Such problems are best solved if you work backwards. The logic I followed was starting from second last row, find the max of two adjacent values (of next row that) can be reached. Once we find the max, for each item of the row, add the max value to the row value. This will eliminate the last row. Now, we can work our way backwards, i.e to the top. Note that as we move upwards the triangles, the number of rows reduces, till we reach the top. Once we reach 2nd row from top, adding the top value to the max of two values, of the 2nd row, we get our answer.

Following is complete solution. You can click here to download the source code.

import java.io.BufferedReader; import java.io.FileReader; import java.util.Scanner; public class EulerProblem18_67 { /* * the logic is that starting from second last row, find * the max of two adjacent values (of next row that) can * be reached. Once we find the max, for each item of * the row, add the max value to the row value. This * will eliminate the last row. Now, we can work our way * backwards, i.e to the top. Note that as we move * upwards the triangles, the number of rows reduces, * till we reach the top. Once we reach 2nd row from * top, adding the top value to the max of two values, * of the 2nd row, we get our answer. */ private static void findMax(int[][] triangle, int depth) { int[] previous = null; for (int i = 1; i < depth; i++) { int[] last = triangle[depth - i]; previous = calculateRowMaximal( triangle[(depth - i) - 1], last); printValues(previous); } System.out.println("result = " + previous[0]); } private static int[] calculateRowMaximal( int[] previous, int[] last) { for (int i = 0; i < previous.length; i++) { previous[i] = previous[i] + (Math.max(last[i], last[i + 1])); } return previous; } private static void printValues(int[] values) { System.out.println(); for (int i : values) { System.out.print("\t" + i); } } private static int[][] getTriangle(String fileName, int depth) throws Exception { int[][] triangle = new int[depth][]; FileReader fr = new FileReader(fileName); BufferedReader br = new BufferedReader(fr); String s; int i = 0; while ((s = br.readLine()) != null) { triangle[i] = new int[i + 1]; int j = 0; Scanner tokens = new Scanner(s); while (tokens.hasNext()) { int value = tokens.nextInt(); triangle[i][j++] = value; } i++; } return triangle; } public static void main(String args[]) throws Throwable { String fileName = "src//dzone//javalobby//triangle_euler67.txt"; int depth = 100; int[][] triangle = getTriangle(fileName, depth); findMax(triangle, depth); } }

## No comments:

Post a Comment