# Interview Questions 19

December 24, 2010 8 Comments

1. Given a set of distinct integers {a1, a2, a3, a4, a5, …} and a set of exclusion rules: R = {{a1, a3}, {a2, a4, a10}, …} can you print out all the valid subsets?

Example:

what is a valid subset? {a1, a4}

what is an invalid subset? {a1, a2, a4}

2. How to compare two version numbers?

eg. 1.2.30.112 @ 2.12.11.09

3. Given an array arr of size M containing distinct integers, randomly select N distinct integers and output them. You are given the rand() function and N < M.

4. Telephone Dir lookup:

Given mapping: number to letters (just like on the telephone buttons)

input: digit string e.g. "1234"

1. output: all possible letter strings based on the mapping.

2. output only those strings that are in a given dictionary. (and length of the dictionary is small.)

5. Given n cities with their populations, suggest an algorithm to pick up one of the cities randomly such that more the population of city is more chance it stands to be picked. Assume you can use an inbuilt random generator function from the language library.

6. Convert an ASCII representation of a positive integer to it's numeric value.

7. Sort an input string according to the given order string. There might be characters in input string that are not present in the order string and vice-versa. The characters of input string that are not present in the order string should come at the end of the output string in any order. Write code.

Example: Sort("abdcdfs","dacg");

output: ddacfbs

8. Given a sorted array with duplicates and a number, find the range in the form of (startIndex, endIndex) of that number. For example, given 0 2 3 3 3 10 10 and 3, return (2,4). Given the same array and 6, return (-1,-1).

**Further:** Do better than linear scan, which is O(n).

9. Given a very large array of n integers, find the kth largest value in the array efficiently. You may assume that k is much smaller than n.

e.g. the third largest (k=3) of [1,3,2,2] is 1.

10. A program to find cycle in a directed graph.If multiple cycles are found print any but starting with the smallest node number.

9. hoare partitioning algo

not

preciselycorrect. Please notice that hoare’s partitioning algo isprobabilistici.e. u may end up doing a lot of rounds. Also (as a hint) note that the problem statement says k << n, so you should figure out a different approach.other approach could be tournament tree…its complexity will be n + k log n..

not tournament sort. Its too costly 🙂

sorry my bad..

yes tournament is too costly… there is no point that much of space..

i think selection sort (in non increasing order) for 1st k elements will suffice..

for(pass=0;pass<k;pass++)

{

maxvalue=a[pass];

maxindex=pass;

for(i=pass+1;i<n;i++){

if(maxvalue<a[i]){

maxvalue=a[i];

maxindex=i;

}

a[pass] ^=a[maxindex];

a[maxindex]^=a[pass];

a[pass]^=a[maxindex];

}

}

return a[k-1];

time: O(kn)

so i think this should work for k<<n

i forgot a check in above solution while swapping

if(maxindex!=pass) then we have to swap..

Could you please explain what exclusion rules mean in the first question? I tried Googling but could not find anything.

btw, isn’t quckselect correct for the 9th question?

exclusion here means excluding. So in the solution subsets there should be no set which has all elements from any of the sets in the exclusion set. Thus a1,a2,a3,a4 and R={(a1,a2)} .. (a1,a2), (a1,a2,a3), (a1,a2,a3,a4) and (a1,a2,a4) cannot be in the solution subsets.