We discussed Insertion sort in detail earlier. This post shows the recursive implementation of Insertion Sort. Continue reading »
Given a sorted array of numbers and a number x, count the number of occurrences of x in the array.
Input:
int arr[] = {1, 3, 3, 4, 4 ,5, 5, 5, 7, 8, 8}; int x = 5; Output: 3
It is used when there are few unique elements in an array. Counting sort takes O(n+k) time in the worst case, where n is number of elements and all the elements are in the range 1 to k (both inclusive). Continue reading »
Generic programming, loosely means that the code we have written is type-independent. It is a larger topic, macros in C language also comes under generic programming. In this post we are only discussing generic pointers.
This question is from exercise in my book Dynamic Programming for Coding Interviews (Question: 1.2, Page-5)
Question: Given an array, arr of integers, write a recursive function that add sum of all the previous numbers to each index of the array. For example, if the input array is
{1, 2, 3, 4, 5, 6}
then your function should update the array to
{1, 3, 6, 10, 15, 21}
How will you find minimum of three integers without using any comparison operator ?
Given two sorted arrays of size m and n respectively. Also given an empty third array of size (m+n). write code to merge the two arrays and store the result in the third array.
INPUT ARRAYS: a = {1, 4, 5, 9} b = {0, 2, 3, 7, 15, 29} OUTPUT: c = {0, 1, 2, 3, 4, 5, 7, 9, 15, 29}
The structure of Node of a Binary Tree and Doubly linked list are same.
struct Node { int data; Node* left; Node* right; } Structure of Node of a Binary Tree |
struct Node { int data; Node* previous; Node* next; } Structure of Node of a Doubly linked list |
If we treat left pointer as previous and right pointer as next, we can use the Node of a Binary Tree to represent node of a Doubly linked list or vice-versa.
Given a binary tree, modify the pointers in each node of the tree so that they represent a Doubly linked. Order of the nodes in DLL should be same as that in the in-order traversal.
If the Input Binary tree is as below
then the function should modify pointers in the nodes, as shown below and return the head pointer.
Given an array of numbers find the maximum XOR value of two numbers in the array.
Input Array = {12, 15, 5, 1, 7, 9, 8, 6, 10, 13}; Output = 15 (XOR of 5 and 10) 5 = 0101 10 = 1010 --------- XOR = 1111
Given a collection of words stored in a Trie data structure, write a function that print all the words stored in it. For example, If the Trie is
Then output should be:
at ate bad bed beat beard