Case study: rod of length - dynamic programming design challenge

Feb. 23, 2020

Introduction

I got the chance to be interviewed on interviewing.io since I am a volunteer on the platform. I get one interview if I interview two people. So I like to write a short case study on my mock interview.

Case study

I was asked to solve rod of length problem. I will add more here later.

Here is the gist.

	Rod of length L
	prices for each length
	We want to find the the most optimum way of cutting the rod, so that the optimize on the max price.
	5
	shorter one, cheap ->
	1 + 1 + 3 = 5 + 5 + 5.5 = 15.5
	2 + 2 +1 = 4 + 4 + 5 = 13
	[4, 1] 5 + 5 = 10
	brute force:
	5
	maximum one - all combination one: dp[5]
	subproblem - dynamic
	dp[5] = (dp[4] + dp[1]) case 1
	dp[3] + dp[2] case 2
	5 cases
	dp[1] + dp[4] case 4 - case 1 and case 4
	Maximum(case1 to case 5)
	bottom up dp[1]
	dp[0] = 0;
	dp[1] -> definition
	dp[n] = Maximum ( for i = 1 to n - 1, dp[n - i], dp[i]
	dp[4]
	dp[3]
	dp[2]
	dp[1]
	find dp[1], dp[2], ... dp[5]
	5 total length
	1 - 5
	2 - 4
	3 - 5.5
	4: 5
	5: 6
	1 - 5
	2 - [4, dp[1] + dp[1] = 10,] -> 10
	3 - [5.5, dp[2] + dp[1], dp[1] + dp[2], dp[1]+dp[1]+dp[1] ]
	------------>
	dp[n] - maximum price for rod length of n
	dp[0]
	0 1 2 3 4 5 (total length) <- n length
	----------------
	1 0 5 10 15 20 25
	2 0 5 10 15
	3
	4 argue that at most 2 subproblems enough to solve
	5 dp[i - 1] -> i - 1, extra 1 foot -> price
	y-axis : cuts
	voice breaking a lot
	? - max[10, 4 ]= 10
	max[15, 4 + dp(upto 2, 1) = 5)
	max[20,4 + dp[upto 2,2)= 14] -> 20
	considering only the cuts upto i -1
	dp[cut option, total length]
	i - 1,
	2 max(dp(1) + 4, dp(i-1)) -> work on 2 foot,
	3
	4
	5
	calculateMaxPrice(int[] price)
	{
	var length = price.Length;
	var dp = new int[length, length];
	// row will be cut
	for(int row = 1; row < length; row++)

view raw rod of length hosted with ❤ by GitHub