Skip to main content

Maximum Path Sum

Problem Statement : Starting from top to bottom and moving to adjacent numbers below, find the maximum total for triangle.
problem

By looking it at the given triangle for few minutes you would see that below is the path having maximum sum i.e. 23.
answer

First approach that may pop in one's mind to solve this problem would be a brute force algorithm. This would be trying every route to find the max sum. The actual number of iterations that will take place for this approach would be 2n, which would be a problem if size of triangle increases.
Bottom to Top Approach
This approach is looking the triangle from bottom to top. First visualize the triangle as follows:
step0
We transform the triangle in sort of tree structure and then only 2 steps need to be repeated until we reach the root node.
Step 1: Choose the max leaf node from the two child leaf nodes.
Step 2: Add the chosen leaf node to the parent node.
Repeat this until you get to root node. For this triangle this is how it goes, chose the max leaf nodes among the pairs.
step1

Add the chosen nodes to parent.
step2

These steps are repeated until we get to root node.
step3
which gives us 23 the answer.
Labels:

Comments

Post a Comment

Popular posts from this blog

Guide : Spring Boot with Apache CXF for REST services

In this series of guide, we are going to explore writing REST services with Apache CXF using Spring Boot. The project is build using maven. I assume that you already know how to use maven. Step 1 : Adding dependencies for Spring Boot By default you have to inherit the parent pom of spring boot, but that cannot be followed everytime, so I use an alternative to that. I basically add spring boot pom as dependency so that it brings all the dependencies. <properties> <project.build.sourceEncoding>UTF-8</project.build.sourceEncoding> <project.reporting.outputEncoding>UTF-8</project.reporting.outputEncoding> <java.version>1.8</java.version> <spring.version>1.4.3.RELEASE</spring.version> <cxf.version>3.1.10</cxf.version> </properties> <dependencies> <dependency> <!-- Alternative to inheriting from parent spring pom --> <groupId>org.springframework.boot...
7 comments
Read more

Resource Pooling

Requirements for Resource Pool: Allow threads to access resources concurrently Should block threads if no resource is available at the moment Maintain a pool of initialized resources to allow reuse and avoid costly initialization of resources Classes from java.util.concurrent package that will be used: ConcurrentLinkedQueue - An unbounded thread-safe queue. This collection is ideal to act as container of resources since it provides concurrent non blocking access to its elements. Semaphore - Semaphore maintains a set of permits by having a counter. This can be used to acquire or release a permit. If no permits are available then acquire() blocks the invoking thread. Implementation Code reference on github: Resource Pooling
1 comment
Read more

DIY Testing Portal

Introduction A simple portal for tracking testing reports, bugs found and then mapping all this way back to features and releases. However JIRA and other such project management tools provide the features that are mentioned in this document but still this solution can come in handy for those who don't want an outside tool rather a quick dirty solution. Note this is for a general solution overview and focuses more on data modelling. Any installation and setup related findings is homework for reader :) What all is compassed in testing ? Testing Report Bugs Releases Features Test cases Environment What all do you need to see in a testing dashboard ? Timeline of all testing that has happened till date Individual testing report Test cases, which cases map to which feature(s) Testing cycles for a specific release Bugs introduced in a release, mapped to which feature(s) The portal solution involves : Mongodb Mongodb Compass - mongodb dashboard tool Elas...
1 comment
Read more