Category: Placements

BFS(G) Breadth First search, will give the shortest path from the root, assuming all the edges are of same weight. You need additional datastructure like queue to implement it. DFS(G) Depth First Search, calculates the discovery and finished time ofContinue reading… Graph problems

assume x[i] represents the position of queen i canPlace(k,i)

In one parse, count the number Normal nodes and NULL nodes. If there is no cycle then the number of NULL nodes = No. Normal nodes + 1 If this is not followed, which means there is a cycle inContinue reading… Detect a cycle in a tree with only one pointer

If the desired length of each line is n, then a line can be divided into three possible ways: 1. The line has exactly n characters, and hence doesn’t need any processing 2.. If the line has more than nContinue reading… Left and Right justification of text

A monotone increasing subsequence is a subset of numbers which are strictly increasing from left to rght. This definition does not require that the numbers be adjacent in the original set or that the longest sequence is unique. Ex. 1Continue reading… Longest monotone increasing subsequence

Follow Quick sort paradigm What if k

void permute(char *aHead,char *aTail) { // If there are no characters remaining in Head, i.e. we got one permutation // So print it. if(strlen(aHead) == 0){ printf(“%sn”,aTail); return; } // Each time remove one character from Head and add itContinue reading… Permutations and Combinations of a string

int insertAt=0,index; for(index=insertAt+1;index if(a[insertAt] == a[index]) index+=1; else a[insertAt++] = a[index]; } insertAt–; Identification of duplicant element in an array Identify the element that is not repeating in an array of 2n+1 elements, in O(n) time X-or all the elements,Continue reading… Removing duplicates in an array in one pass

If p is a prime number other than 2, then using formats thearom it follows the condition: 2^(p-1) mod p = 1 So In order to check whether a number is prime or not, we have to check the valueContinue reading… Prime number verification efficient way

We will see it with an example, Lets calculate pow(x,23) x^23 = x^22 * x x^22 = x^11 * x^11 x^11 = x^10 * x x^10 = x^5 * x^5 x^5