SDE - 1

Ninja has been given a sorted array/list ‘ARR’ of integers of size ‘N’ and 3 integer coefficients ‘X’, ‘Y’, and ‘Z’. Ninja needs to sort the ‘ARR’ by applying the quadratic equation ‘X(ARR[i] * ARR[i]) + Y(ARR[i]) + Z’ to each element of ‘ARR’.

For Example :

Let ‘ARR[]’ = [1, 2, -1] and ‘X’ = 1, ’Y’ =2 and ‘Z’ = 1. Then, for each element at index ‘i’ in the ‘ARR’:
For ‘i’ = 0, ‘ARR[0]’ = 1 and after applying the equation as ‘1 * (1 * 1) + 2 * (1) + 1‘ ‘ARR[0]’ becomes 4.
For ‘i’ = 1, ‘ARR[1]’ = 2 and after applying the equation as ‘1 * (2 * 2) + 2 * (2) + 1‘ ‘ARR[1]’ becomes 9 .
For ‘i’ = 2, ‘ARR[2]’ = -1 and after applying the equation as ‘1 * (-1 * -1) + 2 * (-1) + 1‘ ‘ARR[2]’ becomes 0.
So, ‘ARR’ after modification [4, 9, 0]. The final ‘ARR’ after sorting is [0, 4, 9].

As Ninja is weak with Maths, he asks you for help. Can you help Ninja sort the given ‘ARR’ after applying the quadratic equation to each element?

You are given a 2-D matrix consisting of 0’s and 1’s with ‘N’ rows and ‘N’ columns, you are supposed to find all paths from the cell (0,0) (top-left cell) to the cell (N-1, N-1)(bottom-right cell). All cells with value 0 are blocked and cannot be travelled through while all cells with value 1 are open.

If you are currently at cell (x,y) then you can move to (x+1,y)(denoted by ‘D’), (x-1,y)(denoted by ‘U’), (x,y+1)(denoted by ‘R’), (x,y-1)(denoted by ‘L’) in one move. You cannot move out of the grid.

Example :

Ninja has started a painting business recently. He got a contract to paint ‘N’ houses in a city. Ninja has ‘K’ colors to choose from. But the client has a condition that no two adjacent houses have the same color.

The cost of painting each house with a certain color is represented by an N x K cost matrix. For example, costs[0][0] is the cost of painting house 0 with color 0; costs[1][2] is the cost of painting house 1 with color 2, and so on.

Your task is to help Ninja to find the minimum cost required to paint houses according to this condition.

For Example :

Let say N = 2 and K = 3 and costs = [ [1,5,3] , [2,9,4] ] 

In this case,
Ninja can paint house 0 into color 0, paint house 1 into color 2. Minimum cost: 1 + 4 = 5; 
Or paint house 0 into color 2, paint house 1 into color 0. Minimum cost: 3 + 2 = 5 .

Note :

Assume 0 based indexing

You have been given an undirected graph of ‘V’ vertices (labeled 0,1,..., V-1) and ‘E’ edges. Each edge connecting two nodes (‘X’,’Y’) will have a weight denoting the distance between node ‘X’ and node ‘Y’.

Your task is to find the shortest path distance from the source node, which is the node labeled as 0, to all vertices given in the graph.

Example:

Input:
4 5
0 1 5
0 2 8
1 2 9
1 3 2
2 3 6

In the given input, the number of vertices is 4, and the number of edges is 5.

In the input, following the number of vertices and edges, three numbers are given. The first number denotes node ‘X’, the second number denotes node ‘Y’ and the third number denotes the distance between node ‘X’ and ‘Y’.

As per the input, there is an edge between node 0 and node 1 and the distance between them is 5.

The vertices 0 and 2 have an edge between them and the distance between them is 8.
The vertices 1 and 2 have an edge between them and the distance between them is 9.
The vertices 1 and 3 have an edge between them and the distance between them is 2.
The vertices 2 and 3 have an edge between them and the distance between them is 6.

Note:

1. There are no self-loops(an edge connecting the vertex to itself) in the given graph.

2. There can be parallel edges i.e. two vertices can be directly connected by more than 1 edge.

(Practice)

(Learn)