Bubble sort
Posted on January 14, 2010
(Last modified on August 7, 2020)
| 4 minutes
| Kinshuk Chandra
The sorting problem
Input: Array of numbers , unsorted. Eg.
Output : Same numbers sorted in some order, say increasing order. Eg.
What is Bubble Sort?
The bubble sort works by comparing each item in the list with the item next to it, and swapping them if required. The algorithm repeats this process until it makes a pass all the way through the list without swapping any items (in other words, all items are in the correct order).
[Read More]Stack implementation using linked list
Posted on January 14, 2010
(Last modified on August 11, 2020)
| 2 minutes
| Kinshuk Chandra
We will be understanding the stack implementation using linked list. So, please understand the link list before proceeding.
Lets understand how we can implement the different operation using linked list.
CPP implementation
Here is how we use linked list to implement stack in cpp:
#include <iostream> using namespace std; struct node { int info; struct node \*next; }; struct node \*top; int empty() { return((top == NULL)? 1:0); } void push(int n) { struct node \*p; p=new node; if(p!
[Read More]Radix sort
Posted on January 14, 2010
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
What is radix sort?
Radix Sort is an algorithm that sorts a list of numbers and comes under the category of distribution sort.
This sorting algorithm doesn’t compare the numbers but distributes them, it works as follows:
1. Sorting takes place by distributing the list of number into a bucket by passing through the individual digits of a given number one-by-one beginning with the least significant part. Here, the number of buckets are a total of ten, which bare key values starting from 0 to 9.
[Read More]Merge Sort
Posted on January 14, 2010
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
Mergesort is one of the older algorithms known since 1945. It is very good example of divide and conquer paradigm and is better than other simpler sort algorithms like selection, insertion or bubble sort.
The sorting problem
Input: Array of numbers , unsorted. Eg.
Output : Same numbers sorted in some order, say increasing order. Eg.
So, merge sort algorithm is a recursive algorithm which calls itself on the smaller problem set.
[Read More]Data Structures Interview Questions (Theoritical)
Posted on January 4, 2010
(Last modified on August 7, 2020)
| 5 minutes
| Kinshuk Chandra
1) What is the difference between Storage structure and file structure?
The representation of a particular data structure in the memory of a computer is called a storage structure whereas a storage structure representation in auxiliary memory is often called a file structure.
2) Define data structure in terms of relation?
The possible ways in which the data items or atoms are logically related define different data structures.
3) State procedure in accordance with function?
[Read More]Given a list of n numbers from 1 to n-1, with one of the numbers repeated. Devise a method to determine which number is repeated
Posted on January 3, 2010
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
The sum of the numbers 1 to n-1 is (n)(n-1)/2. Add the numbers on the list, and subtract (n)(n-1)/2. The result is the number that has been repeated.
Efficient code for extracting unique elements from a sorted list of array
Posted on December 3, 2009
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
int main()
{
int a\[10\]={1, 2, 4, 4, 7, 8, 9, 14, 14, 20};
int i;
for (i = 0;i<9;i++)
{
if (a\[i\] != a\[i+1\])
printf("%d\\n",a\[i\]);
}
return 0;
}
tree1.h fully updated
Posted on August 30, 2009
(Last modified on August 7, 2020)
| 5 minutes
| Kinshuk Chandra
//We will do following Functions:
1. lookup
2. Insert
3. printTree,printPost, printPre
4. Selection Function
5. Delete(Hence implemented - child0,child1,child2, inorder2 functions)
#ifndef TREE1_H
#define TREE1\_H ``` ``` \# include <stdio.h> # include <stdlib.h>
#define isChildless(p) p->left==NULL &&p->right==NULL enum BOOL{false,true} ;
typedef enum BOOL BOOL; ``` ``` struct node { int data;
struct node\* left; struct node* right;
} ; typedef struct node node;
/*
Given a binary tree, return true if a node with the target data is found in the tree.
[Read More]Deleting a node from a Binary Search Tree
Posted on August 29, 2009
(Last modified on August 7, 2020)
| 5 minutes
| Kinshuk Chandra
Suppose we want to delete a node k. First we need to search for the node k. Offcourse k should not be null.
Then we have three cases:
1. The node to be deleted has no children - The memory occupied by this node must be freed and either the left link or the right link of the parent of this node must be set to NULL.
2. The node to be deleted has exactly one child -
[Read More]Inorder successor OR Predecessor of BST node
Posted on August 28, 2009
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
It is important to understand inorder successor of BST because it helps us understand deletion of node from a tree, when the node deleted has 2 children.
To find the inorder successor of node u:
If u has a right child, r, then succ(u) is the leftmost descendent of r
Otherwise, succ(u) is the closest ancestor, v, of u (if any) such that u is descended from the left child of v.
[Read More]