CodingTonic

Depth First Search (DFS) - Graphs
In DFS, we start from a vertex and try to move forward and explore vertices, till we find that all the next edges lead to vertices which have already been visited. Then we backtrack along the same path, and try to explore other possibilities.
Read more...

Breadth First Search (BFS) - Graphs
In BFS, there is a notion of starting vertex. BFS visits all the vertices of a connected graph, and in the process of doing so it labels all the vertices with a distance value, which is equal to the length of the shortest path from the starting vertex to all the other vertices.
Read more...

Permutations of a string
Given a string, print all its permutations. Permutations of a string are all of the same length. All permutations have the same set of characters, but they in different order.
Read more...

Longest increasing subsequence - Dynamic Programming
An increasing subsequence is a subset { a_i1,a_i2,...,a_ik } of a larger sequence of numbers { a₁, a₂, .... , a_n }, such that (a) 1 <= i₁ < i₂ < .... < i_k <= n, and (b) a_i1 < a_i2 < .... < a_ik.
Read more...

Cadence Designs Interview experience - Set 1
I was recently invited to attend the interviews of Cadence Systems Design, Noida. I am sharing my experience here. Round 1 - Face to face :
Read more...

Merge sort - Divide & Conquer
Merge-sort is an application of Divide and Conquer paradigm. To read more about Divide and Conquer, follow this post.
In merge-sort we follow following steps:
Read more...

Divide and conquer - concepts & applications
In divide-and-conquer, we solve a problem recursively, applying three steps at each level of the recursion:
1.Divide the problem into a number of sub-problems that are smaller instances of the same problem.
Read more...

100 Prisoners dilemma - puzzle
There are 100 prisoners standing in a row, all facing forward in one direction, i.e., the 100th prisoner can see the 99 prisoners in front of him, the 99th can see 98 in front of him, but can't see the persons standing behind him. All the prisoners are wearing a hat, of either Red or Black color..
Read more...

2 Eggs 100 Floors puzzle
Suppose that there is a building with 100 floors. You are given 2 identical eggs. The most interesting property of the eggs is that every egg has it’s own “threshold” floor. Let’s call that floor N. What this means is that the..
Read more...

Solving Maze - Backtracking
Given an MxN maze, find a path from top left corner to bottom right corner. You can only move to right and down. Let 1 denote the places we can go and 0 denotes places, which can't be visited.
Read more...

Maximum Repeating Number

Given an array of integers, find the maximum repeating number in the array. The expected time complexity is O(n), and O(1) extra space.

2 comments :

coding tonicJanuary 24, 2015 at 7:57 AM
Hi Folks..
Please write comments and feedback to improve this site and make this site a complete guide for coding geeks.
AnonymousMay 23, 2015 at 11:50 AM
Hi, I have written following code for Quick Sort.
#include
using namespace std;

void swap(int *x, int *y){
int temp = *x;
*x = *y;
*y = temp;
}

int partition(int arr[], int low, int high){
int pivot = arr[high];
int i = low;
int j = high;
while(i= pivot)
j--;
else

swap(arr[i], arr[j]);

}
swap(arr[i], arr[high]);
return i;
}

void quickSort(int arr[], int low, int high){
if(low < high){
int p = partition(arr, low, high);
quickSort(arr, low, p-1);
quickSort(arr, p+1, high);
}
}

int main() {
int arr[] = {10, 7, 8, 9, 1, 5};
int n = sizeof(arr)/sizeof(arr[0]);
quickSort(arr, 0, n - 1);
for(int i=0; i<n; ++i)
cout << arr[i] << " ";
cout << endl;
return 0;
}

Topics

2 comments :