Q. Give one line C expression to check whether a given number is an exponential power of 2 Ans: if ( x & (x-1) == 0){ printf(“Yes”) }else{ printf(“No”) } What about zero ?? Set the LSB to zero xContinue reading… Check whether a number is power of 2
In array of n numbers one numer repeating, detect it in one pass
Repeated Number = Sigma(n) – Sigma(n-1) Q. The integers from 1 to n are stored in an array in a random fashion. but one integer is missing. Write a program to find the missing integer. Follow the same technique
print integer using putchar, in same order
Given only putchar (no sprintf, itoa, etc.) write a routine putlong that prints out an unsigned long in decimal. [The solution of taking % 10 and / 10, which gives us the decimal value in reverse order. This requires anContinue reading… print integer using putchar, in same order
Graph problems
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
NQueens
assume x[i] represents the position of queen i canPlace(k,i)
Detect a cycle in a tree with only one pointer
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
Left and Right justification of text
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
Longest monotone increasing subsequence
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
Finding the kth smallest element in an array
Follow Quick sort paradigm What if k
Permutations and Combinations of a string
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