We are given a graph G(V,E) .

How to calculate the number of vertices and edges for L(G)(line-graph of G) , L(L(G)) and L(L(L(G))) without actually constructing them.

For, L(G) , the number of vertices in L(G) is equivalent to number of edges in G ,each vertex of degree k in the original graph G creates k(k−1)/2 edges in the line graph .

Reference : https://mathworld.wolfram.com/Claw-FreeGraph.html

https://mathworld.wolfram.com/LineGraph.html

But how to do calculations of the same for L(L(G)) and L(L(L(G))) without actually constructing them.

Given a tree with 'n' nodes and 'n-1' edges.

We are also given a set of 'n-1' weights .

We have to assign each weight to exactly one of the edges.

We have to assign it in a way such that the sum of all nodes in a tree is minimized.

Value of a node = maximum weight of all of its adjacent edges.

Example:- Edges:- (1--2), (2--3)

Weights:-{1,2}

Solution : — Assigning weight '2' to edge '1--2' and weight '1' to edge '2--3' , we get,

value of node '1' : — 2

value of node '2' : — 2

value of node '3' : — 1

Total minimum sum possible : — (2+2+1)=5 .

How to approach ?

The problem is as follows(created by me) : -

Given an array of 'n' integers , where n=10^6 , all integers are non-negative.

There are 10^5 queries of the the type :- Q(L,R,X) , which means the first index of a number whose value is less than or equal to x .

Example :- {2,3,4,5,2,1} and Q(2,6,2) = 5 , as a[5]=2 which is <=2 .

Is there any way to solve it ?

Here is the link to the problem : https://www.quora.com/Can-you-share-some-trickest-coding-questions-that-you-have-faced-in-any-coding-contest/answer/Rishabh-Jain-2492

There is N x M matrix filled with 0 and 1 only, lets say a matrix is special if every 2 x 2 sub matrix in it has two 0’s and two 1’s . Find the total number of special matrices you can have for N x M.

On the hunt of an efficient solution.

Here is the link to the problem:- https://www.spoj.com/problems/FACTMODP/

Given multiple queries of the form : "L R k" , how to find the count of numbers less than 'k' in the range {L,R} of the array.

There are no update queries.

N=1000000.

I am not interested in the solution with a merge-sort-tree .

We are give 2-arrays, one array is called the original array and other is the corresponding array.

Example : -

a:- [5,6,5,7,5,5,5,8,9]

a':-[1,2,3,1,2,3,1,2,1]

We are given 3-values:- 'l','r' and 'x'

Let l=3 and r=7, also x=5,

so we check the occurrences of '5' in the range [3,7] , so a[3],a[5],a[6],a[7] are the indices which contain '5' .

Now,we check the corresponding array's values,i.e, a'[3],a'[5],a'[6],a'[7] which are:- '3','2','3' and '1'. The minimum of these is '1' and hence the output will be :- "1" .

I know the brute-force approach for multiple queries like this, but I'm interested in an efficient approach !

Say, I have 2 vectors : — (1,2,3) and (0.3,0.5,1) .

Can FFT be applied to find the multiplication of these 2 polynomials ?

Problem-link : — https://www.hackerearth.com/practice/algorithms/dynamic-programming/2-dimensional/practice-problems/algorithm/shift-the-array-4074fac2/

You are given a string that contains lowercase English letters. In one step, you can choose a character and assign the next letter in the alphabet to it. (a-->b,b-->c,etc..and yea,z--->a). The number of indices where a[i]!=a[i+1] is given as f(string).

You are given a number 'k'.Now, your task is to determine the minimum number of steps required to perform on the string to obtain a string such that f(new-string)<=k.