Pre Order traversal - Recursive and Iterative solution

 Posted on January 24, 2010  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

Example Consider the tree: div class="separator” style="clear: both; text-align: center;“> To traverse a binary tree in Preorder, following operations are carried-out (i) Visit the root, (ii) Traverse the left subtree, and (iii) Traverse the right subtree. Therefore, the Preorder traversal of the above tree will outputs: 7, 1, 0, 3, 2, 5, 4, 6, 9, 8, 10 Recursive solution preorder(N \*root) { if(root) { printf("Value : \[%d\]", root->value); preorder(root->left); preorder(root->right); } } Iterative solution [Read More]
Preorder traversal  tree  kodeknight  Data Structures  DS  preorder  traversal  binary-search-tree  BST 

Find the median in a continous stream of numbers

 Posted on January 18, 2010  (Last modified on August 7, 2020)  |  4 minutes  |  Kinshuk Chandra

Problem Numbers are randomly generated and passed to a method. Write a program to find and maintain the median value as new values are generated. OR You are given a stream of numbers which can be positive or negative. You are required to provide an operation FIND MEDIAN..which when invoked should be able return the median of the numbers in stream(in say O(1) time) **OR ** [Read More]
median  Algorithms  kodeknight  hard  array  binary-search-tree  BST  CrackingTheCodingInterview 

Circular Queue

 Posted on January 14, 2010  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

A circular queue is a Queue but a particular implementation of a queue. It is very efficient. It is also quite useful in low level code, because insertion and deletion are totally independent, which means that you don’t have to worry about an interrupt handler trying to do an insertion at the same time as your main code is doing a deletion. In queue, we take out the value at front and put the value at rear. [Read More]
kodeknight  queue  Data Structures  DS 

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]
cpp  kodeknight  Data Structures  DS  c  array  Sorting Algorithm  bubble sort  sorting arrays  programming  sorting  incomplete  programCPP  Data Structure  java 

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]
cpp  kodeknight  link list  Data Structures  DS  linked list  cppimpl  stack  Data Structure Templates  java 

Quick sort

 Posted on January 14, 2010  (Last modified on August 7, 2020)  |  8 minutes  |  Kinshuk Chandra

Hoore cisca discovered it in 1961. Why quicksort? Definitely a greatest hit algorithm  Prevalent in practice O(n log n) time “on average” minimal extra memory needed (which gives it leverage over merge sort) The sorting problem Input: Array of numbers , unsorted. Eg. Output : Same numbers sorted in some order, say increasing order. Eg. Quicksort helps us solving this problem. What is quick sort? [Read More]
pathological data  Algorithms  kodeknight  randomized algorithm  time complexity  divide and conquer  quicksort  sorting  programCPP  Data Structure 

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]
kodeknight  Data Structures  DS  sorting  programCPP 

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]
kodeknight  merge  divide and conquer  Data Structures  DS  sorting  incomplete  recursion  programCPP  iterative 

Array of 0 and 1, put 0's at even position and 1's at odd position

 Posted on January 7, 2010  (Last modified on August 7, 2020)  |  4 minutes  |  Kinshuk Chandra

you are given an array of integers containing only 0s and 1s. you have to place all the 0s in even position and 1s in odd position and if suppose no if 0s exceed no. of 1s or vice verse then keep them untouched. Do that in ONE PASS and WITHOUT taking EXTRA MEMORY. input array: {0 1 1 0 1 0 1 0 1 1 1 0 0 1 0 1 1 } [Read More]
kodeknight  brainteaser  programming  Puzzles