Interview Questions 19

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.

Advertisements

About Avi Dullu
Jaako rakhe saiyan, maar sake na koi!

8 Responses to Interview Questions 19

  1. Divya says:

    9. hoare partitioning algo

    • Avi Dullu says:

      not precisely correct. Please notice that hoare’s partitioning algo is probabilistic i.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.

      • Divya says:

        other approach could be tournament tree…its complexity will be n + k log n..

      • Avi Dullu says:

        not tournament sort. Its too costly 🙂

      • Divya says:

        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

      • Divya says:

        i forgot a check in above solution while swapping
        if(maxindex!=pass) then we have to swap..

  2. Natthu says:

    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?

    • Avi Dullu says:

      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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: