Strongly Connected Components In a Graph

 

 Strongly Connected Components Strongly Connected Component In a Directed Graph G(V,E), two vertex are strongly connected if and only if there is a path from u to v and a path from v to u. Linear Time Algorithm Kosaraju Algorithm 1. Perform a DFS of G and number the vertices in order of completion of… Read More »

k-smallest Element in a Array using MinHeap

 

  k-smallest Element in a Array using MinHeap Given an Array {10,4,12,88,2,3,97,41,55,63,11,18,19}. Print k smallest element. For K=3 2 3 4 Approach 1. This Problem can be solve simply by sorting. Sort the numbers in ascending order and print first ‘k’ numbers. Time Complexity O(n log n) 2. Using Min Heap Create a Min Heap… Read More »

Increment Binary Number By 1

 

 Increment Binary Number By 1 You are given a Binary Number. Just Increment the Binary number by 1 and print the number. For Example I/p: 1 0 0 1 0 O/p: 1 0 0 1 1 I/p: 1 1 1 O/p: 1 0 0 0 Approach Start from the Least Significant Bit.(Traverse backward). while you… Read More »

Depth First Traversal of a Graph (DFS)

 

 Depth First Traversal is one of most popular algorithm used for searching or traversing a graph. Idea is pretty straight forward keep visiting nodes in depth. If you reach dead end back track. Seudo code for Recursive Implementation: DFS-recursive(G, s): mark s as visited for all neighbours w of s in Graph G: if w… Read More »

Dutch National Flag Problem

 

 Dutch National Flag Problem Given an array with 0’s ,1’s ,2’s . Arrange them such that all 0’s , all 1’s and all 2’s are grouped together in a sorted manner. I/P: 0 1 0 1 2 0 1 2 0 1 1 O/p: 0 0 0 0 1 1 1 1 1 2 2… Read More »

Print all possible words from phone digits

 

 Print all possible words from phone digits You are given a digit string. Print all combination that the number could represent. Example: Input : “23” Output ad ae af bd be bf cd ce cf

STRHH-Half of the Half -Spoj

 

 Given a sequence of 2*k characters, please print every second character from the first half of the sequence. Start printing with the first character. Input: 4 your progress is noticeable Output: y po i ntc Approach Straight forward approach just find out the length of the string, And just keep printing till half of the… Read More »

Stack Implementation Using Array

 

 Stack Implementation Using Array   Stack can be implemented using Array. Stack : Introduction C- Implementation of stack using Array. Performance Analysis Time Complexity Push() : O(1). Time Complexity POP() : O(1). Limitation Maximum Size of the Stack should be defined before using stack.