incomplete

Eight Queen Puzzle (likewise N Queen)

Posted on March 28, 2014 (Last modified on August 7, 2020) | 3 minutes | Kinshuk Chandra

Problem Write an algorithm to print all ways of arranging eight queens on a chess board so that none of them share the same row, column or diagonal. (image courtesy) Solution This is a classic problem to implement using backtracking. It has 92 distinct solutions. If solutions that differ only by symmetry operations (rotations and reflections) of the board are counted as one, the puzzle has 12 fundamental solutions. [Read More]

Algorithm to find top 10 search terms in search engine

Posted on January 28, 2014 (Last modified on August 7, 2020) | 1 minutes | Kinshuk Chandra

**Problem : ** “You have been asked to design some software to continuously display the top 10 search terms on Google (or any other search engine). You are given access to a feed that provides an endless real-time stream of search terms currently being searched on Google. Describe what algorithm and data structures you would use to implement this. You are to design two variations: (i) Display the top 10 search terms of all time (i. [Read More]

kodeknight incomplete big data map-reduce

Find increasing 3-tuple (sub-sequence)

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

Problem: You given an array: 3, 2, 1, 6, 5, 4, 9, 8, 7 you have to find a 3 tuple which has property a < b < c, also a is before b, b is before c in array. Answer can have multiple tuples, you have to find any one. In this array, answer will be 3, 6, 9 Solution: Simple. Time complexity = O(n ^ 2) Create an array of indexes, and sort the original array keeping track of the indexes in the second array. [Read More]

maxima kodeknight subsequence minima incomplete array increasing-sequence

Red Black Tree vs AVL Tree vs B-Tree

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

B-tree when you’re managing more than thousands of items and you’re paging them from a disk or some slow storage medium. RB tree when you’re doing fairly frequent inserts, deletes and retrievals on the tree. AVL tree when your inserts and deletes are infrequent relative to your retrievals. think B+ trees are a good general-purpose ordered container data structure, even in main memory. Even when virtual memory isn’t an issue, cache-friendliness often is, and B+ trees are particularly good for sequential access - the same asymptotic performance as a linked list, but with cache-friendliness close to a simple array. [Read More]

kodeknight red-black-tree RBT balanced trees incomplete avl

Union Find

Posted on January 19, 2014 (Last modified on August 7, 2020) | 1 minutes | Kinshuk Chandra

The Union-Find data structure is used to keep track of a partition of a set and supports two operations. The Union(x, y) operation merges the subsets containing x and y, and the Find(x) operation returns the name of the leader element of the subset to which x belongs. The implementation is based on a response to this post on StackOverflow, but extended with a makeSet operation, a getNumGroups operation, and tests. [Read More]

kodeknight incomplete union-find

Bottom-up Merge Sort

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

Recursive algorithm In the earlier article I’ve described a recursive version of the Merge Sort Algorithm OR Top Down Merge sort. Of course every recursive algorithm can be written in an iterative manner . Non recursive algorithm So today I am going to present the bottom-up version of the same algorithm, written in a non-recursive fashion . The main idea of the bottom-up merge sort is to sort the array in a sequence of passes . [Read More]

kodeknight merge sorting incomplete top-down merge-sort bottom-up

Given an integer array of which both first half and second half are sorted. Write a function to merge the two parts to create one single sorted array in place [do not use any extra space].

Posted on January 19, 2014 (Last modified on August 7, 2020) | 1 minutes | Kinshuk Chandra

Given an integer array of which both first half and second half are sorted. Write a function to merge the two parts to create one single sorted array in place [do not use any extra space].
e.g. If input array is [1,3,6,8,-5,-2,3,8] It should be converted to: [-5,-2,1,3,3,6,8,8]

http://stackoverflow.com/questions/6153915/merging-of-two-sorted-halfs-without-extra-memory

kodeknight merge incomplete array bitonic sorted-array

Amazon Questions - Set 1

Posted on January 19, 2014 (Last modified on August 7, 2020) | 20 minutes | Kinshuk Chandra

Write code to find Nth last node in a linked list. Solution Given a binary tree build a vertical sum array. Solution Given two strings str1 and str2, write code to find out if all non-unique elements in str2 are in str1? Solution Given two lists of strings return a list of strings that is an intersection of both of the lists. Analyze running time and space complexity. Give Test Case scenarios. [Read More]

kodeknight Amazon incomplete Interview Question interview-set

Find largest Binary Search Tree in a Binary Tree

Posted on January 17, 2014 (Last modified on August 7, 2020) | 1 minutes | Kinshuk Chandra

Find the largest Binary Search Tree in a given Binary Tree.

…Solution will be posted soon.

Update : Solution

Traverse the tree. From each node to the parent, return the following
set of values.

If BST, size of the current BST or -1 if the tree is not.
Minval & Maxval of the subtree and maxbstsize seen so far (
probably using references)

So in each node check the following:

kodeknight Amazon incomplete

Convert Binary tree to Binary Search Tree conversion in place

Posted on January 17, 2014 (Last modified on August 7, 2020) | 1 minutes | Kinshuk Chandra

http://stackoverflow.com/questions/5468015/convert-binary-tree-to-binary-search-tree-inplace-using-c

http://stackoverflow.com/questions/2577098/how-to-convert-a-binary-tree-to-binary-search-tree-in-place-i-e-we-cannot-use

http://www.geeksforgeeks.org/binary-tree-to-binary-search-tree-conversion/

conversion kodeknight Amazon incomplete