Rank of a node in a Order Statistic Binary Tree

You have a binary tree where each node knows the number of nodes in its sub-tree (including itself). Given a node n and an int k, write a function to return the kth node in an in-order traversal. Can you do this non-recursively?

Minimum distance between 2 elements in an array with duplicates.

Consider there is an array with duplicates and u r given two numbers as input and u have to return the minimum distance between the two in the array with minimum complexity.

Input Array:

int [] A = {1, 5, 3, 7, 2, 8, 3, 4, 5, 9, 9, 3, 1, 3, 2, 9};

 minDist = minDistance(A, 9, 3);

System.out.println("Min Distance (9, 3): " + minDist);

minDist = minDistance(A, 3, 9);

System.out.println("Min Distance (3, 9): " + minDist);

minDist = minDistance(A, 4, 7);

System.out.println("Min Distance (4, 7): " + minDist);

minDist = minDistance(A, 9, 9);

System.out.println("Min Distance (9, 9): " + minDist);

minDist = minDistance(A, 3, 3);

System.out.println("Min Distance (3, 3): " + minDist);

minDist = calcMinDistance(A, 5, 8);

System.out.println("Min Distance (5, 8): " + (minDist-1));

minDist = calcMinDistance(A, 5, 9);

System.out.println("Min Distance (5, 9): " + (minDist-1));

Output:

Min Distance (9, 3): 0

Min Distance (3, 9): 0

Min Distance (4, 7): 3

Min Distance (9, 9): 0

Min Distance (3, 3): 1

Min Distance (5, 8): 2

Min Distance (5, 9): 0

Counter Overflow.

You have a 64bit interger counter set to 0. How long it will take to overflow the counter given that you are incrementing it at 4Ghz speed.


Ans:
4gig ~= 2^32, assuming each instruction sent to cpu increments the counter by 1, it will take 2^64/2^32, ie..2^32 seconds (136 years) to increment it.

Minimize distance between words a, b and c in a document.

Given 3 arrays A,B,C find three indices i,j,k such that the value of I = max((a-b),(b-c),(c-a)) is minimized.


The function I = max((a-b),(b-c),(c-a)) actually minimizes the distance between abc. If the arrays are alread sorted, you can iterate through then incrementing i, j or j in the direction of minimizing I. If we think about it, we can conclude that we must increment the element with minimum value between i, j and k. By doing this, we will make one element going in the direction of others.
Agorithm O(n) time O(1) space:
1. initialize i, j and k to zero
2. checks current minimun value updating it if needed
3. check if i, j and k are at the end, if so stops
4. check which one between i, j and k holds the minimum element. Increment this index. Be cautious to not increment an index if it will go outside the array
5. go to step 2


Lets trace with an example:
A = {1, 10, 100}
B = {99, 101, 150}
C = {5, 11, 98}


i=0, j=0, k=0;
initially a = A[i], b=B[j] and c=C[k]
min = INF.
a = 1, b=99, c=5
now max((a-b),(b-c),(c-a)) = max(98,94,4) = 98, 98 < min => min = 98;
a = 1 is the lowest element, so lets increment i by 1, now i=1


a = A[1], b=B[0] and c=C[0]
now max((a-b),(b-c),(c-a)) = max(89,94,4) = 94, 94 < min => min = 94;
c = 5 is the lowest element, so lets increment k by 1, now k=1


a = A[1], b=B[0] and c=C[1]
now max((a-b),(b-c),(c-a)) = max(89,88,1) = 89, 89 < min => min = 89;
a = 10 is the lowest element, so lets increment i by 1, now i=2


a = A[2], b=B[0] and c=C[1]
now max((a-b),(b-c),(c-a)) = max(1,88,89) = 89, 89 == min => min = 89;
c = 11 is the lowest element, so lets increment k by 1, now k=2


a = A[2], b=B[0] and c=C[2]
now max((a-b),(b-c),(c-a)) = max(1,1,2) = 2, 2 < min => min = 2;
c = 98 is the min, and we can not increase k anymore since k=2 is the max index of array C.


So we are done and the final values of indices which minimize max((a-b),(b-c),(c-a)) are i=2, j=0, k=2
And the min value is 2.


Code output:

i:2, j:0, k:2

Implement a stack that pops out the most frequently added item.

Implement a stack that pops out the most frequently added item. Stack supports 3 functions - push, pop,and top. Give complexity of each functions in your implementation.


Approach:
Let the sample data be:
A = {7, 5, 9, 3, 7, 3, 9, 7, 3, 7, 9, 7};


We maintain 2 maps:
1. stackMap = new HashMap<Integer, Stack<Integer>>();
   stackMap keeps the mapping of count to stack of data.
2. countMap = new HashMap<Integer, Integer>();
   countMap keeps the mapping of data to frequency of data.
3. maxCount = 0;


Now lets trace the operations on sample data - we also keep track of the snapshots of the stackMap and countMap.
Push(A[0] = 7)
stackMap(1 => stack[7]);
countMap(7 => 1)
maxCount = 1;


Push(A[1] = 5)
stackMap(1 => stack[5, 7]);
countMap(7 => 1)
countMap(5 => 1)
maxCount = 1;


Push(A[2] = 9)
stackMap(1 => stack[9, 5, 7]);
countMap(7 => 1)
countMap(5 => 1)
countMap(9 => 1)
maxCount = 1;


Push(A[3] = 3)
stackMap(1 => stack[3, 9, 5, 7]);
countMap(7 => 1)
countMap(5 => 1)
countMap(9 => 1)
countMap(3 => 1)
maxCount = 1;


Push(A[4] = 7)
stackMap(1 => stack[3, 9, 5, 7]);
stackMap(2 => stack[7]);
countMap(7 => 2)
countMap(5 => 1)
countMap(9 => 1)
countMap(3 => 1)
maxCount = 2;


Push(A[5] = 3)
stackMap(1 => stack[3, 9, 5, 7]);
stackMap(2 => stack[3, 7]);
countMap(7 => 2)
countMap(5 => 1)
countMap(9 => 1)
countMap(3 => 2)
maxCount = 2;


Push(A[6] = 9)
stackMap(1 => stack[3, 9, 5, 7]);
stackMap(2 => stack[9, 3, 7]);
countMap(7 => 2)
countMap(5 => 1)
countMap(9 => 2)
countMap(3 => 2)
maxCount = 2;


Push(A[7] = 7)
stackMap(1 => stack[3, 9, 5, 7]);
stackMap(2 => stack[9, 3, 7]);
stackMap(3 => stack[7]);
countMap(7 => 3)
countMap(5 => 1)
countMap(9 => 2)
countMap(3 => 2)
maxCount = 3;


Push(A[8] = 3)
stackMap(1 => stack[3, 9, 5, 7]);
stackMap(2 => stack[9, 3, 7]);
stackMap(3 => stack[3, 7]);
countMap(7 => 3)
countMap(5 => 1)
countMap(9 => 2)
countMap(3 => 3)
maxCount = 3;


Push(A[9] = 7)
stackMap(1 => stack[3, 9, 5, 7]);
stackMap(2 => stack[9, 3, 7]);
stackMap(3 => stack[3, 7]);
stackMap(4 => stack[7]);
countMap(7 => 4)
countMap(5 => 1)
countMap(9 => 2)
countMap(3 => 3)
maxCount = 4;


Push(A[10] = 9)
stackMap(1 => stack[3, 9, 5, 7]);
stackMap(2 => stack[9, 3, 7]);
stackMap(3 => stack[9, 3, 7]);
stackMap(4 => stack[7]);
countMap(7 => 4)
countMap(5 => 1)
countMap(9 => 3)
countMap(3 => 3)
maxCount = 4;


Push(A[11] = 7)
stackMap(1 => stack[3, 9, 5, 7]);
stackMap(2 => stack[9, 3, 7]);
stackMap(3 => stack[9, 3, 7]);
stackMap(4 => stack[7]);
stackMap(5 => stack[7]);
countMap(7 => 5)
countMap(5 => 1)
countMap(9 => 3)
countMap(3 => 3)
maxCount = 5;


Lets trace a top() operation now:
top()
maxCount is 5 now, so we do get the stack corresponding to key=5 from stackMap
we have the following map pair for key=5 stackMap(5 => stack[7]);
so we retieve the stack[7] from the stackMap and then do a stack.peek() to return the top for the frequentStack top() call.


Lets see now how the pop() would work:
maxCount is 5
Get the stack corresponding to the key=maxCount(5) from stackMap datastructure.
stackMap(5 => stack[7]);
so we get here stack[7], now do pop from the stack - that would be our result data which would be returned fromt he pop() call.
we also update countMap(7 => 5) to countMap(7 => 4)
Now since the stack would be empty corresponding to key=5, we decrement the maxCount by 1 ie now maxCount=4.


now lets call pop() second time.
maxCount is 4
stack corresponding to key=4 in stackMap is stack[7] refer - stackMap(4 => stack[7]);
we pop the stack, again stack is empty so we decrement the maxCount by 1, now maxCount=3;
we also update countMap(7 => 4) to countMap(7 => 3)


pop() third time:
maxCount is 3.
stack corresponding to key=3 in stackMap is stack[9, 3, 7] refer stackMap(3 => stack[9, 3, 7]);
after popping the stack it becomes stack[3, 7] - which is not empty so we dont decrement the maxCount, it stays at 3.
we update countMap(9 => 3) to countMap(9 => 2)


pop() 4th time:
maxCount is still 3.
stack corresponding to key=3 in stackMap is now stack[3, 7].
after popping the stack it becomes stack[7] - which is not empty so we dont decrement the maxCount, it stays at 3.
we update countMap(3 => 3) to countMap(3 => 2)


pop() 5th time:
maxCount is still 3.
stack corresponding to key=3 in stackMap is now stack[7].
we pop the stack, stack is empty correponding to key=3, so we decrement the maxCount by 1, now maxCount=2
we also update countMap(7 => 3) to countMap(7 => 2)


I think by now you got the idea.
If now please drop me a line for clarification.


Time complexity:
Push: O(1)
Pop: O(1)
top: O(1)


Space Complexity: O(n)


Code output:
Pushing following elements on frequency stack: 
7 5 9 3 7 3 9 7 3 7 9 7 
Top from frequency stack: 7
Sequence of pops from frequency stack: 
7 7 9 3 7 9 3 7 3 9 5 7 

Number of min-heaps from an array of size n.

Given an array 1 to N , how many permutations of it will be Min -Heap of of N! possible permutations.


Approach:


Recurrence equation:
T(n) = T(k) * T(n-k-1) * (n-1)Ck where k = number of nodes on left


We always have to take care that the Max-Height(left-subtree) - Max-Height(right-subtree) <= 1.


number of leafs in a heap of size n = Math.floor((n+1)/2).


T(1) = 1
T(2) = 1
T(3) = 2


T(4) = 3C2 * T(2) * T(1) = 3
T(5) = 4C3 * T(3) * T(1) = 8
T(6) = 5C3 * T(3) * T(2) = 20
T(7) = 6C3 * T(3) * T(3) = 80


T(8) = 7C4 * T(4) * T(3) = 210
T(9) = 8C5 * T(5) * T(3) = 896
T(10) = 9C6 * T(6) * T(3) = 3360
T(11) = 10C7 * T(7) * T(3) = 19200
T(12) = 11C7 * T(7) * T(4) = 79200
T(13) = 12C7 * T(7) * T(5) = 506880
T(14) = 13C7 * T(7) * T(6) = 2745600
T(15) = 14C7 * T(7) * T(7) = 21964800

Biggest rectangle in a histogram.

Given an array of positive integers that represent the bars in a histogram,
find the rectangle with the largest area under the curve and above the axis.


Approach:
Let the array be A = {4, 1, 6, 3, 4, 7, 5, 2}, maxArea=0 and area=0;
Now for each A[i], traverse forward till A[j] >= A[i] (j > i). - say we found n such numbers.
Calculate the area as area = A[i] * (n).
Now for A[i], traverse backwards till A[j] <= A[i], - say we found m such numbers.
area += (A[i] * m);
if (area > maxArea) then maxArea <= area.
In the end return the maxArea.


Code output:
reactange with largest area under the curve and above the axis: 12

print 2 BSTs in ascending order.

Give two binary search trees, print the numbers of both together in ascending order.


Code output:
Building first BST with values:
13 37 91 88 7 16 54 
Building second BST with values:
1 40 45 14 8 22 50 
printing 2 BSTs in ascending order: 
1 7 8 13 14 16 22 37 40 45 50 54 88 91 


Let "n" be the size of the first BST and "m" be the size of second BST.
Time complexity: O(n+m).
space complexity: O(1).

House coloring with red, blue and green.

There are a row of houses, each house can be painted with three colors red, blue and green. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color. You have to paint the houses with minimum cost. How would you do it?


Note: Painting house-1 with red costs different from painting house-2 with red. The costs are different for each house and each color.


Approach:
Dynamic Programming solution:
we can paint the ith house with blue, red or green.
so we have the following equations:
cost[i,r] = min( cost[i-1,b], cost[i-1,g] ) + cost of painting i with r.
cost[i,g] = min( cost[i-1,b], cost[i-1,r] ) + cost of painting i with g.
cost[i,b] = min( cost[i-1,r], cost[i-1,g] ) + cost of painting i with b.


Final Min Cost = min (cost[n,b], cost[n,r], cost[n,g]);


---------------------------
    R      G       B
---------------------------
1   7      5       10 
---------------------------
2   3      6        1
---------------------------
3   8      7       4
--------------------------
4   6      2       9
--------------------------
5   1      4       7
--------------------------
6   2      3       6
--------------------------


Code output:

Cost matrix leading to the solution: 
0 0 0 
7 5 10 
8 13 6 
14 13 12 
18 14 22 
15 22 21 
23 18 21 
Cost of coloring the house is: 18

Remove Pattern String from Text String.

Given string input1, input2, remove wherever the occurrence of input2 in input1.
e.g: 
input1: skjthshetheshetesm
input2: she
input1 will become "skjththetesm" 


Code output:

Text: skjthshetheshetesm
Pattern: she
After removing pattern from text: skjththetesm
Text: abababa
Pattern: aba
After removing pattern from text: b

Graph to Tree Conversion and Diameter of a BinaryTree.

Given an acyclic undirected unweighted connected graph, find its representation as a tree with the least height. Brute force is O(n^2). Come up with an O(n) solution.


Approach:

1. All the edges are of weight "1" in the above graph. 
2. Pick a random Node in the above Graph, Say we pick "C", now do BFS and calculate the farthest Node from C.
2. The Farthest Node from "C" would come to be "F" and "G" - Both of them "3" units away.
3. Lets Pick one of the Nodes from "F" & "G" above, say "F".
4. Now do BFS starting from "F" and calculate the farthest node from "F" - here we are calculating the "Diameter of the Graph".
5. After we are done with BFS above, the farthest Node from  "F" would come out to be Node "B", which would be 4 units aways. - "4" is the diameter of the graph, lets call it D.
6. Now calculate d = D/2 = 4/2 = 2.
7. Find the nodes which are d (2 units) distance away from F along the route of F => B. Here we get Node "D" as the candidate which satisfies our criteria.
8.  Now "D" is the root of the tree that we set out to create, do a BFS starting from D, nodes 1 unit away are its first level children and so on..


Finally, the tree would look like:

Terminologies:
Diameter of the Graph: maximum distance between any two vertices, here the distance is the length of the shortest walk; therefore, the diameter is the longest of the shortest walks.

Diameter of a Tree

The diameter of a tree (sometimes called the width) is the number of nodes on the longest path between two leaves in the tree. The diagram below shows two trees each with diameter nine, the leaves that form the ends of a longest path are shaded (note that there is more than one path in each tree of length nine, but no path longer than nine nodes).

The diameter of a tree T is the largest of the following quantities:

* the diameter of T’s left subtree
* the diameter of T’s right subtree
* the longest path between leaves that goes through the root of T (this can be computed from the heights of the subtrees of T)

Code output:

Building binary tree with following random values:
30 38 4 32 14 9 42 2 85 6 
Inorder traversal of the binary tree:
2 4 6 9 14 30 32 38 42 85 
Diameter of BinaryTree: 8

Search by first name, last name or both.

Create a structure that will allow you to search a person by first name or last name (or both), in better than O(N) timeframe.


Approach:
Suppose the names are:
String [] names = {
"A B",
"A C",
"A D",
"A Y",
"A Z",
"A X",
"X I",
"X Y",
"X Z",
"X B",
"X C",
"X D",
"I J",
"I L",
"I K",
"Z I"
};


Approach:
1. Create 2 HashMaps, one FMap as Map<firstName, List of FullNames> and another LMap as Map<lastName, list of FullNames>.
2. Now you can search firstname in the FMap or lastName in LMap.
3. If you want to search with fullname then split full name say "F L" into first and last name ie "F" and "L", then search F in FMap
and "L" into LMap and then take the cross of FMap and LMap results.
4. In FMap or LMap, instead of using list to store fullnames, we can use better datastructures like BST or another HashMap which gives better read complexity.


Code output:

Searching with full name ...
[A X]
Searching with first or last name ...
[X I, X Y, X Z, X B, X C, X D, A X]
Searching with first or last name ...
[I J, I L, I K, X I, Z I]

Partition an array into 2 parts with equal average.

How do you partition an array into 2 parts such that the two parts have equal average? Each partition may contain elements that are non-contiguous in the array.


We need to solve the problem of finding all possible sum for a subset of size k (for 1<=k<=n/2), where n is total number of items.


Let S1 = sum of partition 1
n1 = # of items in partition 1
S2 = sum of partition 2
n2 = # of items in partition 2
S = S1+S2
n = n1+n2
Since, S1/n1 = S2/n2, it implies S1/n1 = S2/n2, which in turn implies (S1+S2)/(n1+n2) = S/n


Now, we populate a table of size (N/2) x N x S, where each entry T[k][i][j] is 1 if we there exists some subset of size k using the set of elements {1,2,...,i} that sum to j. During the computation of this table entries, if we ever found that j/k = S/n, there exists a way to make a partition with equal average. T[k][i][j] can be generated as a recurrence like :


T[k][i][j] = T[k-1][i-1][j-item_i] || T[k][i-1][j] ;


Time complexity: O(N^2*S), 
Space complexity: O(N*S).


Input Array:
int [] A = {2, 4, 4, 5, 6, 6, 7, 8, 9, 12};
Code Output:

Partition 1: 6 1
Partition 1: 57 9

Find Index of a key

A function GetWordFromList takes an integer parameter and returns the word at the corresponding index. Now you are given a word,say "string", how do you optimally get the index of the word where it occurs. You don't know the data structure used to store the words.Assume that all the words in list/database are sorted.Also assume that the function returns null or some exception if the index which is given as input is out of bound.


Approach:
1. Suppose the list is an array (just of argument sake).
2. Let the array be 
String [] A = { "apple",
"boy",
"chair",
"dear",
"dog",
"eating",
"feature",
"great",
"heat",
"hunter",
"intelligent",
"jealous",
"joker",
"kites",
"least",
"light",
"meaning",
"money",
"name",
"neat",
"operation",
"peace",
"polite",
"quite",
"relentless",
"string",
"temperature",
"tools"
"universe",
"volvo",
"wax",
"xeon",
"year",
"zebra"
 }
Length of the array is 34.
3. Now lets start searching from 0th index and let first and lsst be variables init to 1.
4. keep doubling "last" and setting first to last, till our search key falls in the "first" and "last" range.
5. So if we try to trace "money" position in array A, we will have following values for first and last.
first = 1, last = 1;
first = 1, last = 2;
first = 2, last = 4;
first = 4, last = 8;
first = 8, last = 16;
first = 16, last = 32; -> "money" occurs in this range.


Now we we will do binary search in the range of A[16] and A[32] to locate the string "money".


Time complexity - O(logn) to find the range + O(logk) - (assuming k is the length of the range where the search key occurs).


Code output:
Length of Array: 34
Index of "money": 17
Index of "zebra": 33
Index of "boy": 1
Index of "volvo": 29
Index of "baby": -1

Find triplet such that (a+b+c) is closest to 0

Find triplet <a,b,c> such that (a+b+c) is closest to 0.


Code output:


Array values are: 
-12 -7 -4 2 3 5 9 10 15 16 
We found a triplet that sums to zero!!
Triplet is: 
-12, -4, 16


Array values are: 
-29 -9 -4 2 3 9 10 15 16 49 
Triplet whose sum is closest to zero by: 1
Triplet is: 
-4, 2, 3


Approach:
1. For every A[i], have 2 pointers in the array say j at the A[i+1] and k at A[n-1] and a min variable which will store how far the (a+b+c) sum is from zero.
2. Check the expression (A[i]+A[j]+A[k] == 0), if false then do ++j or --k depending on (A[i] < A[j]+A[k]) or (A[i] > A[j]+A[k]).
Also check if (A[i]+A[j]+A[k]) < min, if yes then replace the min value with (A[i]+A[j]+A[k]).
3. If true, we have found an exact match for triplet that sums to zero, break the loop.
4. At (2) and (3) points we store the triplet in fa, fb, fc - ie final a, final b and final c.


total time complexity: O(n^2)

Find all triplets in an array such that "a - b = c".

Given a sorted array, output all triplets <a,b,c> such that a-b = c. Expected time is O(n^2). 


Input Array:
-12, -7, -4, 0, 3, 5, 9, 10, 15, 16


Code Output:
-12 -7 -4 0 3 5 9 10 15 16 
Number of triplets for "a-b=c":6
-7 -12 5 
-4 -7 3 
3 -12 15 
3 -7 10 
5 -4 9 
9 -7 16 


Approach:
1. For every A[i], have 2 pointers in the array say j at the A[0] and k at A[n-1].
2. Check the expression (A[i] == A[j]+A[k]), if false then do ++j or --k depending on (A[i] < A[j]+A[k]) or (A[i] > A[j]+A[k]).
3. When you are moving the pointers just make sure that (j != i) and (k != i).
4. Store the triplets in the hashMap and in the end print those triplets.

Put Spaces in a String.

Let's say you have a phrase without any spaces - eg. "thisisawesome". Given a dictionary, how would you add spaces in this string?


OR


When people search at Google, they often type two words without space. For example, instead of typing "binary tree", someone can type "binarytree". Given an input, what is a good way of finding if it is a combination of two valid words?


Input:
thisisaninterestingsentence
Output:
this is an interesting sentence


Approach for the phrase problem:
1. Lets say the length of the string is n and init phrase String as empty.
2. Now for every substring S[i,j] (0<=i<=j<n), check if its a valid word - check against the dictionary.
3. If we get a valid word then append it to the previously calculated and running phrase with a space.


Approach for the "two words wothout the space" problem.
1. Split the given string S[0..n] at the i (0<=i<n) positions. - For every split at ith index you will get 2 substrings S[left] and S[right]
2. Check if S[left] and S[right] are valid words.

Find triplets that sum to zero in an array.

Print triplets that sum to 0 in an integers array.


Approach:
1. Sort the Array say A[].
2. Keep three pointers i, j, and k. 0<=i<n-2, j=i+1 and k=n-1
3. Now for every i, check if (A[i] + A[j] + A[k]) == 0, if so we have our triplet otherwise do ++j or --k depending on whether (A[i] + A[j] + A[k]) is less than zero or greater than zero.


Time complexity: O(n^2).


Example:
int [] A = {1, 2, -5, 4, -2, 3, -19, 10, 5, 8, -25, 19, 6, 20, -10, -7, -3};


Output:
-25 -19 -10 -7 -5 -3 -2 1 2 3 4 5 6 8 10 19 20 
Number of triplets that sum to zero:13
-25 5 20 
-25 6 19 
-10 2 8 
-10 4 6 
-7 -3 10 
-7 1 6 
-7 2 5 
-7 3 4 
-5 -3 8 
-5 1 4 
-5 2 3 
-3 -2 5 
-3 1 2 

Matching cap and pens problem.

Given N pens and n caps . Sort them. you cant compare pens with other pens and caps with other caps. - Originally known as Matching Nuts and Bolts problem.


Approach:
Pens = {P3, P2, P1, P5, P4}
Caps = {C4, C1, C5, C2, C3}


We are going to use a modified version of quick sort to solve this.


Choose one of the pens as pivot say P3, find the cap for P3.


Now compare every pen with C3 (cap for P3) and divide the pen around pivot P3, 
Similarly compare every cap with P3 and divide the caps around the pivot C3, 
We now have the arrays as:
Pens = {P2, P1} +  P3 + {P5, P4} - P3 is now at its correct position if Pens array would have been sorted.
Caps = {C1, C2} +  C3 + {C4, C5} - C3 is now at its correct position if Caps array would have been sorted.


Now run the above steps recursively of the left and right subproblems.


Time complexity: T(n) = T(k) + T(n-k) + O(n)
= O(n^2)
Average case: O(nlogn) - we can use the randomized pivots to achieve O(nlogn) as expected time (averaged over all choices of pivots).


Space complexity: Quick sort is an inplace algorithm so space complexity - O(1)

Ways to choose k non-consecutive integers from n consecutive integers.

let f(n, k) be the # of ways of choosing k integers without replacement from
n consecutive integers so that no two selected are consecutive.
a. give a recurrence for f(n, k)
b. efficient implementation of f(n, k)


Recurrence:
f(n,0) = 0;
f(n,1) = n;
f(n,n) = 1;
f(n,k) = f(n-1, k) + f(n-2, k-1);


OR
f(n,k) = f(n-2, k-1) + f(n-3, k-1) ... f(2(k-1)-1, k-1);


Sample output(s):
n=4, k=2;
n: 4
k: 2
result: 3


n=5, k=3;
n: 5
k: 3
result: 1