Archive

Archive for the ‘Algorithms’ Category

Good Links

June 30, 2013 Comments off

Interview Preparation

Data Structures and Algorithms

Sample Questions: http://www.qubeet.com/

Linked List: http://giridhar-mb.blogspot.in/2012/11/linked-list-implementation-in-java.html?_sm_au_=iNsvkqGtW40Fn0st

Quick Sort: http://www.vogella.com/articles/JavaAlgorithmsQuicksort/article.html?_sm_au_=iNsvkqGtW40Fn0st

Bubble Sort: http://www.cs.rit.edu/~atk/Java/Sorting/sorting.html?_sm_au_=iNsvkqGtW40Fn0st

All Sorts: http://thilinasameera.wordpress.com/2011/06/01/sorting-algorithms-sample-codes-on-java-c-and-matlab/?_sm_au_=iNsvkqGtW40Fn0st#_Insertion_Sort

Java

http://javarevisited.blogspot.in/

http://howtodoinjava.com/?_sm_au_=i7s4kDQ0LfD1sfNM

Java Threads and Concurrency

http://jlunaquiroga.blogspot.in/2013/04/java-concurrency-part-1.html?_sm_au_=i7s4kDQ0LfD1sfNM

Java Collections

http://jlunaquiroga.blogspot.in/2013/06/java-collections-framework-part-1-intro.html?_sm_au_=i7s4kDQ0LfD1sfNM

Spring

http://javacodebook.com/category/spring/spring-book/?_sm_au_=i7s4kDQ0LfD1sfNM#

Advertisements

Find median of 2 sorted arrays

July 7, 2012 Comments off

Let ar1 and ar2 be the input arrays.
Algorithm:
1) Calculate the medians m1 and m2 of the input arrays ar1[]
and ar2[] respectively.
2) If m1 and m2 both are equal then we are done.
return m1 (or m2)
3) If m1 is greater than m2, then median is present in one
of the below two subarrays.
a)  From first element of ar1 to m1 (ar1[0…|_n/2_|])
b)  From m2 to last element of ar2  (ar2[|_n/2_|…n-1])
4) If m2 is greater than m1, then median is present in one
of the below two subarrays.
a)  From m1 to last element of ar1  (ar1[|_n/2_|…n-1])
b)  From first element of ar2 to m2 (ar2[0…|_n/2_|])
4) Repeat the above process until size of both the subarrays
becomes 2.
5) If size of the two arrays is 2 then use below formula to get
the median.
Median = (max(ar1[0], ar2[0]) + min(ar1[1], ar2[1]))/2
Example:
ar1[] = {1, 12, 15, 26, 38}
ar2[] = {2, 13, 17, 30, 45}
For above two arrays m1 = 15 and m2 = 17
For the above ar1[] and ar2[], m1 is smaller than m2. So median is present in one of the following two subarrays.
[15, 26, 38] and [2, 13, 17]
Let us repeat the process for above two subarrays:
m1 = 26 m2 = 13.
m1 is greater than m2. So the subarrays become
[15, 26] and [13, 17]
Now size is 2, so median = (max(ar1[0], ar2[0]) + min(ar1[1], ar2[1]))/2
= (max(15, 13) + min(26, 17))/2
= (15 + 17)/2
= 16

Program:

#include<stdio.h>
int max(int, int); /* to get maximum of two integers */

int min(int, int); /* to get minimum of two integeres */

int median(int [], int); /* to get median of a single array */

/* This function returns median of ar1[] and ar2[].

Assumptions in this function:

Both ar1[] and ar2[] are sorted arrays

Both have n elements */

int getMedian(int ar1[], int ar2[], int n)
{
int m1; /* For median of ar1 */
int m2; /* For median of ar2 */

/* return -1  for invalid input */
if(n <= 0)
return -1;

if(n == 1)
return (ar1[0] + ar2[0])/2;

if (n == 2)
return (max(ar1[0], ar2[0]) + min(ar1[1], ar2[1])) / 2;

m1 = median(ar1, n); /* get the median of the first array */
m2 = median(ar2, n); /* get the median of the second array */

/* If medians are equal then return either m1 or m2 */
if(m1 == m2)
return m1;

/* if m1 < m2 then median must exist in ar1[m1....] and ar2[....m2] */
if (m1 < m2)
return getMedian(ar1 + n/2, ar2, n - n/2);
else if(m1>m2)
/* if m1 > m2 then median must exist in ar1[....m1] and ar2[m2...] */
return getMedian(ar2 + n/2, ar1, n - n/2);
}

/* Driver program to test above function */
int main()
{
int ar1[] = {1, 12, 15, 26, 38};
int ar2[] = {2, 13, 17, 30, 45};

printf("%d", getMedian(ar1, ar2, 5)) ;

getchar();
return 0;
}

/* Utility functions */
int max(int x, int y)
{
return x > y? x : y;
}

int min(int x, int y)
{
return x > y? y : x;
}

/* Function to get median of a single array */
int median(int arr[], int n)
{
if(n%2 == 0)
return (arr[n/2] + arr[n/2-1])/2;
else
return arr[n/2];
}

Time Complexity: O(logn)
Space Complexity: O(1)
Algorithmic Paradigm: Divide and Conquer

Categories: Algorithms

Given n red balls and m blue balls and some containers, how would you distribute those balls among the containers such that the probability of picking a red ball is maximized, assuming that the user randomly chooses a container and then randomly picks a ball from that

July 7, 2012 Comments off

Given n red balls and m blue balls and some containers, how would you distribute those balls among the containers such that the probability of picking a red ball is maximized, assuming that the user randomly chooses a container and then randomly picks a ball from that

Solutiuon :

Let’s say x containers.

Put 1 red ball in x-1 containers and rest with m blue balls.

Probability of selecting red ball in this case is: 1-(1/x)*(n-x-1)/m.

Categories: Algorithms

kth smallest element without using any static/global variable in Binary Search Tree

July 7, 2012 Comments off
public BSTNodeSize findKth (int k, BSTNodeSize t) {
if (t == null)
throw new IllegalArgumentException();
int lsize= 0; // size of left subtree
if (t.left != null)
lsize= ((BSTNodeSize)(t.left)).size;
if (k = lsize + 1)
return t;
if (k < = lsize)
return findKth(k, (BSTNodeSize)t.left);
return findKth(k – lsize – 1, (BSTNodeSize)t.right);
}
Categories: Algorithms

You are given an array of n+2 elements. All elements of the array occur once between 1 and n except two numbers which occur twice. Find the two repeating numbers in O(n) (eg) say for n = 5

July 7, 2012 Comments off

Question:

You are given an array of n+2 elements. All elements of the array occur once between 1 and n except two numbers which occur twice. Find the two repeating numbers in O(n)

(eg) say for n = 5

array = 4 2 4 5 2 3 1

The above array has n+2=7 elements with all elements occurring once except 2 and 4 which occurs twice. Find those repeating numbers in O(n) time and constant space.

The output should be 4 2.

Solution: Let summation of all numbers in array be S and product be P

Let the numbers which are being repeated are X and Y.

X + Y = S – n(n+1)/2
XY = P/n!

Using above two equations, we can find out X and Y. For array = 4 2 4 5 2 3 1, we get S = 21 and P as 960.

X + Y = 21 – 15 = 6

XY = 960/5! = 8

X – Y = sqrt((X+Y)^2 – 4*XY) = sqrt(4) = 2

Using below two equations, we easily get X = 4 and Y = 2
X + Y = 6
X – Y = 2

Categories: Algorithms

Given an array of 998 distinct integers ranging from 1 to 1000 including. Find which 2 numbers are missing

July 7, 2012 Comments off

Given an array of 998 distinct integers ranging from 1 to 1000 including. Find which 2 numbers are missing

Restrictions: loop over the array only once, can’t allocate an additional array.

Find the sum of numbers from 1 to 1000 = 1000*1001/2 = 500500 = S
Find sum of squares of numbers from 1 to 1000 = n*(n+1)*(2n+1)/6 = 333 833 500 = SS
Find sum of 998 distinct numbers as N
Find sum of squares of 998 distinct numbers as NS
Let a and b be 2 missing numbers
S-N=a+b
SS-NS=a^2+b^2
Solve for a and b.

Categories: Algorithms

Given an array of 999 distinct integers ranging from 1 to 1000 including. Find which number is missing

July 7, 2012 Comments off
Categories: Algorithms
%d bloggers like this: