Node *MoveMinToStart(Node *aHead) { if(aHead == NULL or aHead->next == NULL) return aHead; Node *PrevMin = NULL,*Cur=aHead,*Prev=NULL,*Min=NULL; while(Cur){ if(Min == NULL or Min->Value > Cur->Value){ Min = Cur; PrevMin = Prev; } Prev = Cur; Cur = Cur->next; } if(PrevMinContinue reading… Sort linked list
Category: Algorithms
Repeating characters
Write a funtion that finds repeating characters in a string. Sort the string
Draw circle, using integer operations
Q: Write a routine to draw a circle given a center coordiante (x,y) and a radius (r) without making use of any floating point computations. Refer to graphics algorithms
Give a fast way to multiply a number by 7
Represent 7 in binary format. Now shifting and adding by appropriate times will give the solution or Multiply it by 8 (shift by 3 bits) and subtract the original number.
Check whether a number is power of 2
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