Project - Step-by-Step Solution to a Programming Problem

hemanth · January 29, 2021, 12:26pm

Project - Step-by-Step Solution to a Programming Problem

For the course project, you will pick any programming problem of your choice, solve it step-by-step, and explain your solution.

Pick a problem from an online source (LeetCode, HackerRank, GeeksForGeeks etc.)
Use the problem-solving template to solve the problem step-by-step using the method you’ve learned in this course
Document your solution and perform complexity analysis by adding explanations to your Jupyter notebook
Publish your Jupyter notebook to your Jovian profile and share it with the community.
Submit the link to your Jovian notebook here.

Evaluation Criteria

You must use the starter notebook (problem-solving template)
Your notebook should contain a problem statement and the link to the original source of the problem
Your notebook should be marked as “Public” (not “Secret” or “Private”)
Each step of the method should be implemented
Your notebook should execute end to end without errors
Your notebook should contain proper test cases
Your notebook should contain proper explanations
Your notebook should not be plagiarized from someone else. Please submit your own work.
Your notebook should include complexity analysis
The problem you pick should involve at least one optimization step, using one or more of the data structures and algorithms covered in this course.

2019ucs0097 · March 11, 2021, 7:31pm

Hey guys, I did the project based upon the partitioning problem. Basically it checks whether an array can be partitioned in two equal parts or not. I made a DP based solution for it with time complexity and space complexity both O(N*sum(arr)). According to the the course ethics, I should not share my entire code so trust me on the complexity part.

Now my problem, is that I found the question on leetcode and when I submitted by DP solution it did get accepted but as usual in leetcode they gave the results of my relative performance as well. I was pretty much shocked seeing it because it said that I have performed better than 11% coders in terms of time taken and 16% in terms of space used. Please if anybody can suggest how can I take these numbers up to at least 60% or 75% because I am not being able to understand what more can be done after improving using DP. I’ll probably not end up including them but still if anybody can suggest further improvements I will be grateful.

birajde · March 11, 2021, 7:54pm

Hey, I dont have a solution to your problem yet, I am writing to give you just a piece of advice. You can share the link to the Leetcode Problem here so that other users in the forum can check your problem and help you with it.

2019ucs0097 · March 12, 2021, 9:17am

Ok the above mentioned is the one. Hopefully now people can understand my problem better.

andreastraut · March 16, 2021, 1:23pm

As requested: here is my project notebook. It is based on the LeetCode problem “Network-Delay-Time”, but slightly different in a few points:

I define a source node as input variable, because this seemed necessary and interesting to me (specially if there is a cycle or different possible source nodes).
And my solution uses the graph-class and recursion. I like the graph-class, but for being able to use it in the Jovian-Testing evaluate_test_cases function, I had to wrap the graph-class in another function, which requires num_nodes and edges and source as input variables. Otherwise I wouldn’t have been able to define testcases (based on these three variables num_nodes and edges and source).

I hope that everything makes sense for you.

vincent-kizza · March 20, 2021, 2:05pm

Kindly give the link to your notebook as well or the problem source.

cheongkj123 · March 23, 2021, 2:51pm

The problem I chose was Search a 2D Matrix from LeetCode, where you need to determine whether a target value is inside a m x n matrix containing integers sorted in ascending order. My notebook can be found here. The optimization used is straightforward, but nonetheless effective. You may test my code by copy-pasting it to the LeetCode link.

Hopefully some of you will find my solution helpful.

danielhvj · March 23, 2021, 4:27pm

Hey there, I have problem with the evaluate_test_case function, trying to test my code, it gives me: TypeError: list indices must be integers or slices, not str.

But when I test my code without the evaluate_test_case I have no problem, I tried with different code and still gives the same error…
This is a piece of my code, and seems to be OK

 > for i in range(0, len(price)): 
>         S[i] = 1   
>         j = i - 1
>         while (j >= 0) and (price[i] >= price[j]):
>             S[i] += 1
>             j -= 1
>     return S

danielhvj · March 23, 2021, 4:32pm

birajde · March 23, 2021, 4:44pm

Can you try passing it without the indexing on test variable?
Eg: evaluate_test_case(span, test)

danielhvj · March 23, 2021, 4:50pm

TypeError: myfunc() argument after ** must be a mapping, not list

but evaluates the code… I tried to reinstall jovian library but the problem remains…

Captura de pantalla de 2021-03-23 17-47-29

fuzzyray · March 23, 2021, 5:03pm

That means input in your test case is not a dictionary. The test cases need to be defined like this:

test = {
    'input': {
        'arg1': [1, 2, 3],
        'arg2': [4, 5]
    },
    'output': [1, 2, 3, 4, 5]
}

The input dictionary is the name of the argument for your function with the value being the required input.

danielhvj · March 23, 2021, 5:14pm

Ok, thanks, for example I defined:

test = {
‘input’: {‘t1’:[10, 4, 5, 90, 120, 80, 100, 80, 60, 70, 60, 75, 85]},
‘output’: [1, 1, 2, 4, 5, 1, 2, 1, 1, 2, 1, 4, 6]
}

and
evaluate_test_case(span_brute, test['input']['t1'])

and still gets the same error.
TypeError: list indices must be integers or slices, not str

Sebgolos · March 23, 2021, 5:45pm

You should probably do:

test = {
   'input': {
      't1': some_input
   },
   'output': some_output
}
evaluate_test_case(span_brute, test)

(without any alterations when passing the test as an argument).

danielhvj · March 23, 2021, 5:51pm

Hi,

I got an error, this time ‘t1’ is an unexpected argument…

TypeError: got an unexpected keyword argument 't1'

Sebgolos · March 23, 2021, 5:54pm

You need to make sure that argument name in your function matches what you use when defining the test:

def span_brute(wrongArg): # won't work

vs

def span_brute(t1):

danielhvj · March 23, 2021, 5:59pm

Thanks for resolving the issue…

mrittrukhuda · March 29, 2021, 2:59pm

Guys… I want some feedback!?
Aren’t the expected output and actual output same though they are not in order!?
then why evaluation comes fail?!
Note: Practicing backtracking problems!(permutations)

cybersphere · March 29, 2021, 8:25pm

I think evaluate test cases is just checking for equivalency of values. Since lists are ordered [1,2]!=[2,1].

See if you can match the order of your actual output to the expected output.

adarshn-work · March 30, 2021, 6:14am

Hello, I am trying out Leetcode 746. I have found a recursion based brute force solution, which goes like this:

Find min(costClimbingStairs when started at index 0, costClimbingStairs when started at index 1).

    def minCostClimbingStairs(self, cost):
            def minCostClimbingStairs0(cost, idx=0):
            .
            def minCostClimbingStairs1(cost, idx=1):
            .
            return min(minCostClimbingStairs1(cost, idx=0), minCostClimbingStairs1(cost, idx=1))

The parameters are again evaluated separately. While this works, it is not efficient.Can I get some hint as to how to optimize this.

Any hints on how to do this in one step (starting at either index 0/1?).
When trying to use dynamic programming, when to use memoization/tabulation? Are there scenarios where one weighs in over the other?