## Good Links

**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

**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**

**Spring**

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

## Find median of 2 sorted arrays

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**

## 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

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.

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

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); }

## 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

**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

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

**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.

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

**Given an array of 999 distinct integers ranging from 1 to 1000 including. Find which number is missing. Restrictions: loop over the array only once, can’t allocate an additional array.**

Find sum of numbers from 1 to 1000 = 1000*1001/2 =500500

Add the current array sum of 999 numbers = S

The missing number = 500500-S