m0ew's blog

Rod Cutting Problem asked in google interview
By m0ew, history, 6 years ago, In English

Hi everyone, This is my first post.I was trying to solve the Road Cutting problem on interviewbit.com.

Here is the problem link — https://www.interviewbit.com/problems/rod-cutting/

I read the editorial as well but i wasn't able to understand it. Detailed approach to this problem is appreciated.

Thanks in advance!

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (10)
| Write comment?
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Pretty standard dp problem. Try reading about optimal binary search tree. The recurrence for that problem is similar to this one.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it -17 Vote: I do not like it

    Okay, so this can be solved via binary search too? I thought its a dp problem

    → Reply
»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I think this youtube video might help https://www.youtube.com/watch?v=IRwVmTmN6go

→ Reply
»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Struggling with this type of problem for the first time is totally ok. I'm giving you a few resources that can help you. First of all, this problem can be solved easily with dynamic programming, so you have to read and understand dynamic programming properly. This problem falls under a classic dynamic programming section named matrix chain multiplication.

  1. https://www.topcoder.com/community/data-science/data-science-tutorials/dynamic-programming-from-novice-to-advanced/
  2. https://www.geeksforgeeks.org/matrix-chain-multiplication-dp-8/
  3. https://www.youtube.com/watch?v=vgLJZMUfnsU
→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank for the list of resources, I will follow them one by one. Also, may I know, in which attempt you solved this question?

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It was a very familiar problem to me because I solve many problems on MCM dp ( matrix chain multiplication). So this time no significant time needed (Don't get frustrated seeing this, if you practice enough you will feel the same)

      → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Easier dp. quite similar Uva problem: 10003.

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can this be solved using greedy?

→ Reply