Link list ADT

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

What is linked list? Linked List consists of a sequence of nodes. These nodes are made-up of the following: A Data Field for housing the data item One or Two Reference/s for pointing at other node/s i.e. pointing to the next/previous node/s. In this data structure, the nodes are allowed to be inserted and removed at any point in the list in constant time, however random access in not possible. [Read More]
kodeknight  link list  Single Link List  abstract-data-type  ADT  incomplete  Data Structure  linked list 

Calculate length of the linked list that contains loop

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

In previous posts (Loop in a linked list and Calculate node that causes loop in a linked list) we discussed how to detect loop in a linked list and how to calculate node that causes loop in a linked list. In current post we discuss how to calculate length of the linked list when there is a loop in the linked list. Following procedure explains how to calculate length of the linked list that contains loop: [Read More]
kodeknight  link list  Single Link List  incomplete 

Longest increasing subsequence

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

Longest Increasing Subsequence has been a classic Dynamic Programming problem. O(N^2) has been around for a while but more interesting is the following O(n log n) solution. Problem Input : Sequence of integers (or any comparable items) Output : Longest increasing subsequence of the sequence, which may not be contiguous. For example : We have sequence : 1,8,2,7,3,6,4,5 which has the longest increasing subsequence : 1,2,3,4,5. Note that the numbers are non-contiguous. [Read More]
kodeknight  Dynamic Programming  DP  Amazon  incomplete  Interview Question  google 

Reverse the words in a sentence in place

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

Problem Given a sentence you have to reverse it word by word. Example That is, given a sentence like this : I am a good boy The in place reverse would be: boy good a am I Solutions Method1 - Reverse the sentence first and then words again First reverse the whole string and then individually reverse the words I am a good boy <————-> yob doog a ma I [Read More]
kodeknight  String  reverse  interview  incomplete  formatting-needed 

Median of 2 sorted arrays of equal size n

 Posted on September 13, 2011  (Last modified on August 7, 2020)  |  7 minutes  |  Kinshuk Chandra

Question  There are 2 sorted arrays A and B. Write an algorithm to find the median of the array obtained after merging the above 2 arrays(i.e. array of length 2n). The complexity should be O(log(n)) Solution Before going to solution what is the median. What is Median? Median: In probability theory and statistics, a median is described as the number separating the higher half of a sample, a population, or a probability distribution, from the lower half. [Read More]
Adobe  kodeknight  Microsoft  yahoo  divide and conquer  Amazon  array  two-sorted-arrays  median  incomplete  two-arrays  sorted-array 

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 

Count binary search trees–Given N nodes, how many structurally BST are possible?

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

Problem: This is not a binary tree programming problem in the ordinary sense – it’s more of a math/combinatorics recursion problem that happens to use binary trees. Suppose you are building an N node binary search tree with the values 1..N. How many structurally different binary search trees are there that store those values? Solution Total number of possible Binary Search Trees with n different keys = Catalan number Cn = (2n)! [Read More]
tree  kodeknight  incomplete  binary-search-tree  BST  count 

Kruskal's Algorithm

 Posted on July 5, 2010  (Last modified on August 7, 2020)  |  5 minutes  |  Kinshuk Chandra

In kruskal’s algorithm the selection function chooses edges in increasing order of length without worrying too much about their connection to previously chosen edges, except that never to form a cycle. The result is a forest of trees that grows until all the trees in a forest (all the components) merge in a single tree. graph Example In Kruskal’s algorithm, we sort the edges according to their edge weights and start counting them and including them in MST, if they are not forming any cycle. [Read More]
Graph  Algorithms  kodeknight  greedy Algo  incomplete