DEV Community: Sachin 👨🏻‍💻

Solving Leetcode Hard Dynamic Programming Problem

Sachin 👨🏻‍💻 — Sun, 20 Dec 2020 18:04:21 +0000

LeetCode is a very popular Interview Preparation website with brilliant quality Data Structure and Algorithms question to prepare for your SDE/SWE interviews.

In this post, we will looking at a Hard-rated Dynamic Programming question from Leetcode, Cherry Pickup II, and how to determine if a given problem is Dynamic Programming problem or can it solved with a greedy approach.

Given a rows x cols matrix grid representing a field of cherries. Each cell in grid represents the number of cherries that you can collect.

You have two robots that can collect cherries for you, Robot #1 is located at the top-left corner (0,0) , and Robot #2 is located at the top-right corner (0, cols-1) of the grid.

Return the maximum number of cherries collection using both robots by following the rules below:

From a cell (i,j), robots can move to cell (i+1, j-1) , (i+1, j) or (i+1, j+1).

When any robot is passing through a cell, It picks it up all cherries, and the cell becomes an empty cell (0).
When both robots stay on the same cell, only one of them takes the cherries.
Both robots cannot move outside of the grid at any moment.
Both robots should reach the bottom row in the grid.

Constraints:

rows == grid.length
cols == grid[i].length
2 <= rows, cols <= 70
0 <= grid[i][j] <= 100

Now, moving towards thinking for an answer, the biggest hint we can get that this question requires dynamic programming is the line "return maximum number of cherries", which gives the clue that this is a optimization problem. Optimization problems require the maximization or minimization of the situation/problem at hand.

Though you may be tempted to ask me as to how we can be sure that this problem cannot be solved by another optimzation algorithm technique - Greedy as compared to dynamic programming.

In case you don't know, Greedy algorithm aims to find optimality by using local optimal (greedy approach) at each step in comparison to Dynamic Programming which aims to find global optimal in the given context.

Thinking of a simple example like this one can help you to clear your doubt:

If we were to choose local optimal cell at each step, we would keep choosing the cells with value 10 and both the robots will move down their respective rows without moving diagonally without reaching the cell with value 100, hence missing out on the most optimal solution.
Even the example 2 is indicative of the failure of the greedy method in the sense that if we were to choose local best cells robot1 would move down from its initial position to the cell with value 2 in second row instead of cell with value 0, but would not be able to reach cells with values 9 and 5 in row 3 and 4 respectively.

Thus, a good way to decide whether a problem requires greedy or DP, is to come up with a logic as to why a locally optimal method may or may not fail for the given situation.

Now coming towards thinking of a DP solution, the things that should be considered:

Both the robots need to reach the bottom-most row and in each step they move down to next row, so we can move the robots at the time and it won't effect our answer.
The constraints on the matrix size is low (70 each for dimension), hence even a O(n^3) solution is possible without giving time limit exceeds error.
To prevent excess conditions and as well loss of generality, we shall consider that robot 1 will always be on the same cell on to the left of robot 2 throughout their moves. To move robot2 to the left of robot1 requires to robots to cross each other once either when they are on the same cell or on adjacent cells on the previous row before their current move. So instead of making robot2 cross robot1(my making robot1 move to down-right and robot2 down-left) we can make robot1 move down-left and robot2 down-right and keep them from crossing over. This will not affect our answer, and will conditions concise when writing the code.

Now, when computing the DP, our answer depends on 3 states/variables, our current row r, robot1 current column c1, and robot2 current column c2. So, our starting state is
dp[0][0][#cols - 1]

From any state dp[i][j][k], there are a maximum of nine types of moves (3 types of moves for each robot) possible as long as robots stay inside the matrix and don't cross each other and robot1 stays on left of robot2.

Now we have to write the standard DP to move from dp[0][0][#cols - 1] to the final row. Here's a Top-Down DP Solution in CPP.

class Solution {
public:
    int rows, cols;
    int cherryPickup(vector<vector<int>>& grid) {
        rows = (int)grid.size();
        cols = (int)grid[0].size();

        // initializing a 3D array dp
        vector<vector<vector<int>>> dp(rows, vector<vector<int>> (cols, vector<int>(cols, -1)));
        int ans = solve(dp, 0, 0, cols - 1, grid);
        return ans;
    }


    int solve(vector<vector<vector<int>>> &dp, int r, int c1, int c2, vector<vector<int>> &grid) {
        if(r >= rows) return 0;
        if(c1 < 0 or c2 < 0 or c1 >= cols or c2 >= cols or c1 > c2) return 0; 
        if(dp[r][c1][c2] != -1) return dp[r][c1][c2];

        int cur= grid[r][c1];
        if(c1 != c2) cur+= grid[r][c2];

        int mx = 0;
        mx = max({mx, solve(dp, r + 1, c1, c2, grid), 
solve(dp, r + 1, c1, c2 - 1, grid), solve(dp, r + 1, c1 + 1, c2 - 1, grid), 
solve(dp, r + 1, c1 + 1, c2, grid)});

        if(c1)
            mx= max({mx, solve(dp, r + 1, c1 - 1, c2, grid), 
solve(dp, r+1, c1-1, c2-1, grid)});

        if(c2 + 1 < cols)
            mx= max({mx, solve(dp, r + 1, c1, c2 + 1, grid), 
solve(dp, r + 1, c1 + 1, c2 + 1, grid)});

        if(c1 and c2 + 1 < cols)
            mx= max(mx, solve(dp, r + 1, c1 - 1, c2 + 1, grid));


        return dp[r][c1][c2] = mx + cur;
    }
};

Thanks for reading! If you liked this post, show some love and support with awesome reactions and comments.

Setup Your Portfolio Website in 15 minutes using Gatsby Starter - Full Walkthrough

Sachin 👨🏻‍💻 — Mon, 30 Nov 2020 18:40:01 +0000

Whether you are a developer, a designer, a photographer or a digital marketer; portfolio websites are an effective and excellent way to portray your skills to the world and of course, potential employers. Portfolio website allow you to present yourself in a professional manner while permitting you to add a little touch of your personality in your presentation.

In this blog post, I will show you how to set up your own Portfolio website in minutes using Gatsby Starter and deploy it on Netlify using a custom domain(or using a domain if you already have one).

GatsbyJS is a framework based on ReactJS and GraphQL that allows to build "blazing fast websites" and claims to be 2.5x times faster than other static frameworks. It has a brilliant starter library that allows you to select from a list of starter template websites to get started with your website without having to do any coding and designing on your own.

In this post, we will use this starter made by Anubhav Shrivastav to set up our portfolio website. There are many brilliant templates out there on the gatsby starter webpage, but I personally felt this was the most complete compared to others and allowed me display more information about myself without having to add any additional piece of code on my own. Now let's get straight to it:

Step 1: Install Node.js

If you don't have Node.js already install, go the Node.js Website and download any version of Node.js of your choice (preferably above v14).
After the downloading and installing is done, run the following commands on your terminal to check if Node was properly installed.

node -v
// 14.4.0(you will get the version you installed)
npm -v
// 6.14.5

Step 2: Install Gatsby Command Line Tool (CLI)

On your terminal, run the following command:

npm install -g gatsby-cli

This will install the Gatsby CLI on your machine and allow you to get up and running with your Gatsby Application.

Step 3: Installing the GatsbyJS Starter and Getting Started with the Website

Setup a directory where you want to store the Gatsby application and open the directory from the terminal, copy the line given below and paste in the terminal and run it:

gatsby new gatsby-starter-resume https://github.com/anubhavsrivastava/gatsby-starter-resume

It should be something like this:

Click Enter and the installation will start. After the installation is done, is should look something like this.

Run the commands mentioned in the above pic:

Now, open localhost:8000 on your browser to see your application. Gatsby enables hot reloading which means you can see the changes that you make to the application in the browser instantaneously(after saving the file).

Step 4: Personalize the Website

Now that everything is ready and working, you just need to replace the information in the application with your personal information. For this open the application directory in a code editor like VS Code and then open the config.js file.

Here you can change the siteTitle to something like: "Sachin Vashisht's Portfolio" and just replace firstName, lastName, email, phone and address and replace socialLinks urls with your own social media profiles. Replace the avatar pic by replacing the pic in src/assets/images/avatar.png

As you make changes, you can turn to your browser to see the changes that you have made.
Now head over to src/pages/index.js and replace the content as you like :)

If you have something more to display or something less (like lack of experience if you are looking for your first job like me). You can alter the sidebar content in the src/components/sidebar.js file (just make sure the id label of the section tag inside the index.js file matches with name used in the siderbar section) .

Bonus Tip: You can alter the color scheme of the website by going to src/assets/sass/_variables.scss and change the primary variable from lavender to a color of your choice.

Final Step: Deploy the site on Netlify

Head over to Netlify.com and setup an account. After this head over to the "sites" column. Now you will see the option to upload the application via drag and drop or via "New Site from Git". I would suggest adding the application via Git as it allows to make changes in the application later and the website will be updated automatically on Git push, and this is the method we are going to use.

Add the Gatsby application folder as a new GitHub repository to your GitHub account. If you don't know how to do that, I would recommend you to google this (about how to upload files to repository on GitHub) and note that the git is already initialized in your Gatsby application.

Once this is done, choose the "new site from git" option. Now the select the repository you created.

Just keep continuing and within a minute or so your website will deployed. Now head over to domain settings and in here from options menu select edit site name. There's also an option to add custom domain name which allows you to bring a domain name that you already own, or buy a new one with Netlify.

Phew!! Your Portfolio website is now up and running. You can now officially use this link and start sharing it with others.

If you are familiar with ReactJS, you can add much more functionality to this application, just like I did with mine

P.S: If you like this template, you can star this portfolio repository here, and if you liked this post send me some love with some cool reactions and comments.

Thanks for reading!! Stay tuned :)

Destructuring Assignment Indepth Syntax Comparison - JavaScript Vs Python

Sachin 👨🏻‍💻 — Tue, 24 Nov 2020 11:34:09 +0000

The destructuring or an unpacking assignment syntax is an expression that makes it possible to unpack values from iterables like array and objects in javascript and list, tuples, dictionaries in Python into distinct variables.This post will look at the difference in syntax used in Python and JavaScript for destructuring or unpacking assignments.

Unstructuring assignment is quite useful as it allows us to assign values to several variables at once from a single collection, is easy to understand and improves code-readability(if there exist such a term).

One simple examples includes performing swap operation on two variables,

Python

a = 5 
b = 7

b, a = a, b
print(a, b, sep = " ") 
# 7 5

JavaScript

let a = 5, b = 7

[b, a] = [a, b]
console.log(a, b)
// 7 5

Array/List Destructuring

Python

example_list = [1, 2, 3]

first, second, third = example_list
print(first, second, third, sep = " ") 

# 1 2 3

The above code snippet shows a simple list destructing in Python. Here the assignment of variables depends simply upon the order of items in the list.

JavaScript

const example_array = [1, 2, 3]
let first, second, third
[first, second, third] = example_array

console.log(first, second, third)
// 1 2 3

Array Destructuring in JavaScript requires variable to be enclosed with "[ ]"

Ignoring values

Python

example_list = [1, 2, 3]
first, _ , third = example_list
print(first, third, sep = " ")
# 1 3

The values to ignored are to be replaced with ' _ '

JavaScript

const example_array = [1, 2, 3]
const [first, , third] = example_array
console.log(first, third)
// 1 3

The values to be ignored are just empty with commas after them.

In Python, if we try to destructure a collection with more or fewer values than we provide variables, we end up with a ValueError. Whereas in Javascript it will not show any error

Python

example_list = [1, 2, 3]
first, second = example_list
#ValueError: not enough values to unpack (expected 2)

JavaScript

const example_array = [1, 2, 3]
let first, second, third, fourth

//when destructuring less values
[first, second] = example_array
console.log(first, second)
// 1 2

//when destructuring more values
[first, second, third, fourth] = example_array
console.log(first, second, third, fourth)
// 1 2 3 undefined

In JavaScript, When unpacking less number of values, only the initial values are assigned, while unpacking of more number of values, the only the first three variables are assigned a value, and the last remains as undefined.

In such a scenario, JavaScript allows us to use a default value:

[first, second, third, fourth = 4] = example_array
console.log(first, second, third, fourth)
// 1 2 3 4

Collecting Values

Python

head, *tail = [1, 2, 3, 4, 5]

print(head)  # 1
print(tail)  # [2, 3, 4, 5]

JavaScript

const [head, ...tail] = [1, 2, 3, 4, 5]
console.log(head) // 1
console.log(tail) // [2, 3, 4, 5]

... is known as "rest" operator in JavaScript

Be aware that a SyntaxError will be thrown if a trailing comma is used on the right-hand side of a rest element:

const [a, ...b,] = [1, 2, 3];

// SyntaxError: rest element may not have a trailing comma
// Always consider using rest operator as the last element

Args/Kwargs in Python and Object Destructuring in JavaScript

In Python, we can pass a variable number of arguments to a function using special symbols. There are two special symbols:

*args (Non Keyword Arguments)
**kwargs (Keyword Arguments)

A typical example where one might need something like *args is given below:

// a standard function to add two numbers
def adder(x,y):
    print("sum:",x+y)

If we are to add multiple numbers but are unsure of how many numbers we'll have to add

We can modify adder in two ways:

we can put the numbers to be added to a list and pass the list as an argument.

def adder(nums):
    sum = 0

    for num in nums: 
        sum += num

    print("sum : ", sum)

But this requires to add maintain a list and remove and add numbers to list accordingly.

This is where *args comes into play:

Python has *args which allow us to pass the variable number of non keyword arguments to function.

modifying the adder functions using *args:

def adder(*num):
    sum = 0

    for n in num:
        sum = sum + n

    print("sum:",sum)

# args is just a conventional name used in python, we can use any name
# (like num in this example)

We use *args and **kwargs as an argument when we are unsure about the number of arguments to pass in the functions.

*args allow to pass mulitple arguments to function while **kwargs allows to pass multiple keyword arguments to a function.

def printSomething(a, *args, **kwargs):
    print(a)
    print(args)
    print(kwargs)

printSomething(1, 2, 3, 4, name="Sachin", age=21)
# 1
# (2, 3, 4) - args becomes a tuple
# {'name': 'Sachin', 'age': 21} - kwargs becomes a dictionary

*args functionality can be replicated in JS using rest operator as:

// Only the last parameter can be a "rest parameter".
function myFun(a,  b, ...manyMoreArgs) {
  console.log("a", a)
  console.log("b", b)
  console.log("manyMoreArgs", manyMoreArgs)
}

myFun("one", "two", "three", "four", "five", "six")

// Console Output:
// a, one
// b, two
// manyMoreArgs, ["three", "four", "five", "six"]

Object Destructuring in JS

const user = {
    id: 42,
    is_verified: true
};

const {id, is_verified} = user;
// here the name of variable should be same as the object's keys

console.log(id); // 42
console.log(is_verified); // true

Since the variable names should match the object's key, JS allows using aliases:

const o = {p: 42, q: true};
const {p: foo, q: bar} = o;

console.log(foo); // 42 
console.log(bar); // true

Destructuring of argument passed as Object

const info = {
    name: "Sachin",
    age: 21,
    profession: "Software Engineer"
}

function printDetails({name, age = 18, profession: job}) {
    console.log('name', name)
    console.log('age', age)
    console.log('job', job)
}

printDetails(info)
// name Sachin
// age 21
// job Software Engineer

// default age 18
// job as alias to profession

With so many rules with quite some similarities and subtle differences, remembering all these can seem to be overwhelming at first. I suggest not to mug up these syntax if you use either Python or JS or both, you can always bookmark this and read it later as and when you need to look up for something.

References:

Teclado - Destructuring in Python

MDN Web Docs

Programiz - Python Args and Kwargs

Thanks for reading. Stay tuned!!

Ternary Operators Syntax Comparison - C++ vs Python vs JavaScript

Sachin 👨🏻‍💻 — Mon, 23 Nov 2020 01:49:05 +0000

Ternary Operators also known as conditional expressions are an elegant and succinct method to replace if-else statement in programming. These operators evaluate something based on a condition being true or not.

In this post, We'll see the different syntax in which ternary operators in implemented in C++, Python and JavaScript.

Consider the following code snippet,

num = int(input('Enter a number please: '))
if num % 2 == 0: 
    print('num is even')
elif: 
    print('num is odd')

This code checks if the inputted number is even or odd.

With ternary operator, we can reduce the above if else statements with a one-liner code.

In Python,

# syntax
# [on_true] if [expression] else [on_false]

num = int(input('Enter a number please: '))
print('num is even') if num % 2 == 0 else print('num is odd')

In C++

// syntax
// expression ? [on_true] : [on_false]

int num;
cout << "Please Enter a number: " << endl;
cin >> num;
num % 2 == 0 ? cout << "Num is even" : cout << "num is odd";

In JavaScript

// same syntax as C++
// expression ? [on_true] : [on_false]

let num = prompt('Please Enter a number: ')
num % 2 == 0 ? alert('num is even') : alert('num is odd')

Thus, if the expression to be evaluated is small, then ternary operators can prove to be a viable one-liner alternative.

Graph and Trees: List of useful resource to help you understand and master Graph and Tree Data Structures

Sachin 👨🏻‍💻 — Sun, 22 Nov 2020 17:19:04 +0000

The Graph and the Tree Data Structures are one of the most important concepts which are frequently asked in interviews of product-based companies. Questions based on graphs and trees can seem to be daunting at first and understanding and mastering graphs and trees requires lots of practice and patience.

But with the right resources and enough practice, graphs and trees can be tackled with ease in the interviews and you can gain confidence to deal with problems based on them in the interviews.

Here is a list of resources I compiled for myself that I am pretty sure can help you as well.

Binary Trees and Binary Search Trees

Binary/ N-ary Trees Tutorials & Notes | Data Structures | HackerEarth

Binary Search Tree Tutorials & Notes | Data Structures | HackerEarth

HackerEarth is a brilliant platform to polish your skills of Data Structures and Algorithms. Here you can learn the basics from scratch as well as practice questions on easy, medium and hard difficulty.

Binary Tree - Interview Questions & Practice Problems - Techie Delight

Binary Search Tree (BST) - Interview Questions & Practice Problems

TechieDelight is another brilliant website with a list of interview questions asked on these topics.

And by the way, if you feel overwhelmed with tough questions, there's no need to complete each and every thing. It's only normal to get stuck with difficult concepts. I would recommend strengthening your basics and don't waste time on tough questions.
You can move ahead when you will comfortable with the basics and can answer medium level questions. You can come back later for tough questions if you like, but there's no need to do each and everything in one go.

Also you will find most of the solution written in C++ or Java because most product-based companies hiring Software Developer Engineers(SDEs) require you to have a good knowledge of either of the two.

Heaps and Priority Queue

This is a wonderful video which would clarify all your concepts regarding heaps, heap sort, priority queues.

Yet again, you can practice question from HackerEarth

Heaps/Priority Queues Practice Problems Data Structures | HackerEarth

Graphs and Trees

There are so many concepts in graphs that it is virtually impossible to know each and every concept. That's why you only to to focus on the core topics related to graphs like DFS, BFS, Connected Components in a Graph, Algorithms like Dijkstra, Floyd-Warshall, Bellman Ford (Shortest Path Algoriths), Kruskal and Prims (Minimum Spanning Tree), Traversing Directed Acyclic Graph(DAG), Disjoint Set Union(DSU).

Algorithm Gym :: Graph Algorithms - Codeforces

The above Codeforces blog is very detailed but useful list of algorithms along with their implementation and time complexity for graphs and trees. You only need to check for the above mentioned algorithms, since there are really advanced concepts mentioned as well.
- Bonus: Collection of question for you to sharpen your knowledge of graphs and trees:
  - Easy:
    
    Path Sum - LeetCode
    
    Kth Smallest Element in a BST - LeetCode
    
    Find the Town Judge - LeetCode
  - Medium / Hard:
    
    Path with Maximum Probability - LeetCode
    
    Problem - 580C - Codeforces
    
    Problem - 862B - Codeforces
    
    Problem - 1167C - Codeforces
    
    Problem - 510B - Codeforces
    
    Cheapest Flights Within K Stops - LeetCode

If you have made it this far, Kudos to you 🙂

You are now more than prepared to face graph and tree based problems for your interviews.

Thanks for reading! Stay tuned

Custom Sort in C++ vs Python (With and Without Lambda Functions)

Sachin 👨🏻‍💻 — Tue, 06 Oct 2020 10:46:52 +0000

Custom Sort in C++ v/s Custom Sort in Python3

Eg: Sorting a list of tuples where sorting is to be done in descending order of the second value of the tuple.

IN C++

//header files above
bool compare(pair<int, int> a, pair<int, int> b) {
    return a.second > b.second;
}

int main() {
    vector<pair<int, int>> arr; // a list of tuples
    // Method 1 (With lambda function - C++11 onwards)
    sort(arr.begin(), arr.end(), [&](pair<int, int> a, pair<int, int> b) {
        return a.second > b.second;
    }); 
    // Method 2 (Without lambda function)
    sort(arr.begin(), arr.end(), compare);
}

IN PYTHON3

a = [(1, 2), (2, 3), (3, 4), (4, 5)];

def compare(x):
    return -x[1]

# Method 1 (With lambda function)
sorted_a = sorted(a, key=lambda x: -x[1]) #can also use : sorted(a, lambda x: x[1], reverse=True)

# Method 2 (Without lambda function)
sorted_a = sorted(a, key=compare)