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

:page_facing_up: 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.

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

:dart: 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.

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.

1 Like

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.

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

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.

1 Like

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

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.

1 Like

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

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

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

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.

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

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).

Hi,

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

TypeError: got an unexpected keyword argument 't1'

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):
1 Like

Thanks for resolving the issue…

1 Like

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)

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.

1 Like

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?