Intersection of two sorted lists or 2 sorted arrays

 Posted on May 20, 2011  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

For two sorted lists, 1, 2, 12, 15, 17, 18 1, 12, 14, 15, 16, 18, 20 intersection is bold numbers. Solution 1 : Brute force An intuitive solution for this problem is to check whether every number in the first array (denoted as array1) is in the second array (denoted as array2). If the length of array1 is m, and the length of array2 is n, its overall time complexity is O(m*n) based on linear search. [Read More]
kodeknight  link list  Single Link List  binary search  two-arrays  two-sorted-arrays  intersection  sorted-array 

Scrabble Algorithms

 Posted on May 20, 2011  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

If you are playing scrabble and you have n letters, what are all the possible words that you can make from these n letters? It looks as if it would involve permutations and combinations both of the letters or a union of permutations and combinations for n letters. Surprisingly, it is much simpler. Below are the possible words for letters ‘abc’. I have highlighted the patterns in them. a ab [Read More]
kodeknight  trie  Permutation  Combination 

What is BST or Binary Search tree?

 Posted on May 16, 2011  (Last modified on August 7, 2020)  |  6 minutes  |  Kinshuk Chandra

A binary search tree (BST) is a tree which has following property : Every node’s left sub-tree has a key less than the node’s key, and every right sub-tree has a key greater than the node’s key. The major advantage of binary search trees is that the related sorting algorithms and search algorithms, such as in-order traversal, can be very efficient. This data structure is perfect for advanced interview questions. See the figure below for this tree: [Read More]
cpp  tree  kodeknight  binary-search-tree  BST 

Program to check if two rectangle overlap or itntersect

 Posted on May 14, 2011  (Last modified on August 7, 2020)  |  4 minutes  |  Kinshuk Chandra

Input - 2 Rectangles with x and y coordinates. Output - boolean value which states if they overlap or not This is a one of the classic problems in graphics programming and game development. So, let’s see how we can solve it. Most computer (now cellphone) screens have an invisible coordinate system that is used to identify where graphical objects are on the screen. For example, the iPhone coordinate system has the origin at the top-left corner of the screen. [Read More]
Algorithms  kodeknight  rectangle  incomplete  geometric-search  java 

Sum , factorial

 Posted on May 11, 2011  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

/\*sum upto n numbers\*/

public static int Sum(int n)
{
int result = 0;
for (int i = 1; i <= n; ++i)
result += i;
return result;
}

kodeknight  common math functions  udf 

Given two sorted arrays of size m and n respectively (m >> n), how to merge them together?

 Posted on May 11, 2011  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

Given two sorted arrays of size m and n respectively (m » n), how to merge them together? (Note: if you try to insert n numbers to the larger array to obtain O(n \log m) complexity, pay attention that you have to move elements around for insertions. Also, simply merging those two arrays is not the optimal solution here.) Solution Consider A[m+1] and B[n+1] and C[m+n] (m»n and indexing starts from 1) [Read More]
kodeknight  merge  sorting  array  two-arrays  two-sorted-arrays 

Interview Questions on Binary Search tree

 Posted on May 11, 2011  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

Given a binary tree,create the copy of the tree. Given a binary tree, count the number of nodes in the tree. Given a binary tree, find the maximum depth the number of nodes along the longest path from the root node down to the farthest leaf node. Write a code to find the minimum and maximum value in binary search tree Print the BST in increasing order…to put this in different way, it simply means to print in inorder traversal Print the post order traversal (recursive) Print the paths in binary search tree from root to leaves. [Read More]
tree  kodeknight  interview  binary-search-tree  BST 

BST : Improving search by using sentinel

 Posted on May 11, 2011  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

A normal search across a BST (Binary Search Tree) would look like this bool BinaryTree::Search (int data ) { Node \*current = this\->root; while ( current != NULL ) { if (current->data < data) { current = current->left; } else if (current->data > data) { current = current->right; } else if ( current->data == data ) { return true; } } return false; } You keep going down the tree, until you find a node whose value is equal to one you are looking for, or you bail out when you hit a leaf (NULL) node. [Read More]
search  tree  kodeknight  binary-search-tree  BST 

Nth node in inorder traversal

 Posted on May 11, 2011  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

Problem Here we have to return pointer to nth node in the inorder traversal Solution // Get the pointer to the nth inorder node in "nthnode" void nthinorder(node \*root, int n, mynode \*\*nthnode) { static whichnode; static found; if(!found) { if(root) { nthinorder(root->left, n , nthnode); if(++whichnode == n) { printf("\\nFound %dth node\\n", n); found = 1; \*nthnode = root; // Store the pointer to the nth node. } nthinorder(root->right, n , nthnode); } } } 17\. [Read More]
inorder  tree  kodeknight  traversal  binary-search-tree  BST