Move Over LeetCode

One of the easiest baseline tests for programming ability is the dreaded LeetCode problems. These questions can range from different programming languages, specific algorithms, databases, dynamic programming, Number Theory, Depth-First Search, and everything in-between. The wide range of topics and categories are meant to allow for someone to either practice their programming abaility to tackle specific concepts or to test someone’s understanding of compute programming while exploring the way in which they are solving a problem.

I always hated LeetCode.

The questions never felt practical (and I still don’t think they are) and the concepts were a little bit dull in my personal opinion. Not to knock it too hard, it is a great tool that I myself have used for interview prep.

A colleague of mine turned me onto Project Euler which is close cousin to LeetCode. These problems are similar but have way more of a ‘mathy’ feel to them. They simply are challenging mathematical and computer programming problems. They can be solved many of the times by brute force but the fun is seeing if you can solve it in a more elegant and efficient method. Here is a quick example:

Problem #18

By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.

3
7 4
2 4 6
8 5 9 3

That is, 3 + 7 + 4 + 9 = 23.

Find the maximum total from top to bottom of the triangle below:

75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23

NOTE: As there are only 16384 routes, it is possible to solve this problem by trying every route. However, Problem 67, is the same challenge with a triangle containing one-hundred rows; it cannot be solved by brute force, and requires a clever method! ;o)

Before you say anything; yes I know a problem like this probably could be found on LeetCode. But my favorite part is that the site only checks that you got the answer, there is no IDE to run. You can open up and see how other people solved it to get a better (or worse) answer than what you did. It feels less like a test and more of a challenge of “alright lets see if I can actually do this”.

When I solve these problems, I don’t fully restrict myself from the internet and research because that’s not how real life works. I can google “how to get the index of an element in an array” because its just a part of the approach I am doing to solve the problem and its a simple thing I forgot how to do. Would I feel cheated if I googled “how to solve maximum route in tree dynamic programming”? Yes, that defeats the purpose.

Who knows, maybe I’m wrong and its just the same thing as LeetCode, and it might be my own bias, but these problems feel a little more geared towards Mathematicians. Here’s my solution below, you can probably do it faster but hey at least I got it to work.

My Solution 
def max_path_sum(triangle):
  height = len(triangle)

  #initialize state array 
  sum_triangle = []
  for i in range(height):
      sum_triangle.append([0 for _ in range(len(triangle[i]))])

  sum_triangle[0][0] = triangle[0][0]

  # Dynamic programming approach, loop through triangle and update states. 
  # This makes it run in polynomial time vs exponential with a recursion call.
  for i in range(1,height):
      for j in range(0,i+1):
          # check edge cases
          if (i==j):
              sum_triangle[i][j] = sum_triangle[i-1][j-1] + triangle[i][j]
          elif (j==0):
              sum_triangle[i][j] = sum_triangle[i-1][j] + triangle[i][j]
          else:
              # take max of prior two states and add new value
              sum_triangle[i][j] = max(sum_triangle[i-1][j-1], sum_triangle[i-1][j]) + triangle[i][j]

  return max(sum_triangle[height-1])

max_path_sum(triangle)

Answer: 1,074

If you want to check out more of my solutions head over to the notes section and drill into the Euler Problems section!