Archive
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
Generate nth Fibonacci number
public static int getNthFibonacci(int n)
{
if(n==1)return 0;
if(n==2)return 1;
int a=0;
int b=1;
for (int i = 0; i < n-2 ; i++)
{
b = a+b;
a = b -a;
// System.out.println(b);
}
return b;
}
Remove the repeated characters in that string and print in same order
private static String removeRepeatedChar(String s) {
// TODO Auto-generated method stub
int a[] = new int[256];
String removedString = new String();
for(int i=0;i
char c = s.charAt(i);
if(a[c]==0) {
removedString+=c;
a[c]=1;
}
}
return removedString;
}
Reverse a singly linked list
Suppose that a linked list has elements in the order
10 20 30 40 50
After reversing the output should be
50 40 30 20 10
This code will do the work
NODE reverse(NODE first)
{
NODE cur,temp;
cur = NULL;
while(first != NULL)
{
temp = first;
first = first->link;
temp->link = cur;
cur = temp;
}
return cur;
}
Recursive Solution;
if(first->next->next != NULL) reverse(first->next); I if(first->next->next == NULL) Node temp = first->next; first->next = first->next->next; temp->next = first;
vidyasagar 