Programming Problems 14

1. Suppose you want to travel from city A to city B by car, following a fixed route. Your car can travel m miles on a full tank of gas, and you have a map of the n gas stations on the route between A and B that gives the number of miles between each station.
Design an algorithm to find a way to get from A to B without running out of gas that minimizes the total number of refueling stops, in O(n) time.

2. Design a data structure that supports the following two operations on a set S of integers:
a. Insert(x; S), which inserts element x into set S, and
b. DeleteLargerHalf(S), which deletes the largest ceil(|S|/2) elements from S.
Show how to implement this data structure so both operations take O(1) amortized time.

3. An array contains first n positive integers not divisible by m(m>1 and m<n) in random order. Give an efficient solution in O(n) and only one extra space for to find m:

Input: n, array of integers in random order
Output: m

Input: 5, {2,5,7,1,4}
Output: 3

Input: 4, {3,5,1,7}
Output: 2

4. There are 20 floors in a building. I step into the elevator with 5 other people. What is the probability that I do not have to press my button? (ie someone else chooses the same floor as me)

5. You are given an array of positive integers a[1..n] such that

1) a[1] < a[2] < … a[ n ]

Given a positive integer C find j and i such that

Choose(a[j], a[i]) = C

where Choose(b,a) = b choose a, the binomial coefficient = the number of ways of choosing a balls from a set of b balls. Assume you have a fast Choose(b,a) calculating function at your disposal.

6, Given an array A of N integers, equi(A) is any index i for which:
(1) i is a valid index into A, i.e. 0 <= i < N
(2) The sum of integers preceding (but not including) i is equal to the sum of integers following (again not including) i. i.e.:
A[0]+A[1]+…+A[i-1] = A[i+1]+A[i+2]..+A[N-1]

If there is no such index i, equi(A) = -1.

equi [1,2,0,3] = 2, because A[0] + A[1] = 1 + 2 = A[3] = 3.
equi [0] = 0
equi [] = -1

Find if the given array has this property.

7. The sequence A is defined as follows:
Start with the natural numbers
Initialize count = 1;

while(there are uncrossed numbers)
pick the first uncrossed number say n.
set A[count] = n.
Cross out the number count+n and n.
Increment count.

Give a fast algorithm to determine A[n], given n.
Try getting an algorithm which is polynomial in log n.

8. Say that a list of numbers is k-close to sorted if each number in the list is less than k positions from its actual place in the sorted order. (Hence, a list that is 1-close to sorted is actually sorted.) Give an O(nlog k) algorithm for sorting a list of n numbers that is k-close to sorted.


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

15 Responses to Programming Problems 14

  1. Amar says:

    3. x holds the given array. y holds the auxillary array used for computation.

    O(n) – space
    O(n) – time

         l = 0;       r = 0;       
          for (i=0 ; i<n ; i++) y[i]=0; 
          for (i=0 ; i<n ; i++)
              y[i] = y[i]+l ;
              y[n-i-1] = y[n-i-1]-r;
              l = l+x[i];
              r = r+x[n-i-1];
          for (i=0; i<n; i++) printf("%d\n",y[i]);
  2. Amar says:

    Forgot to mention : the entry in the y array which contains 0 is the desired result.

  3. Amar says:

    5. You can have multiple answers for it. Assume C =1, then there are n answers as nCn=1 for all values of n.
    Since the Choose function goes up and then down, a variant of 2SUM might be needed.
    What kinda solution are you looking for? space and time complexity?

  4. Amar says:

    3. Put each element in its respective position – 1. All the elements out of bounds( greater than n) should be discarded. Elements not present should be filled with zero.

    On traversing the node again, the first zero that you find gives you the answer.

  5. Amar says:


          int flag=0;
          int n = 12; 
              else if(x[i]==0)
    		   	   if(!flag || i==0)
  6. Amar says:

    3. Another approach :

    1. Find out the max. Simultaneously add up the numbers in the array
    2. calculate max_sum = max*(max+1)/2.
    3. Find the difference between calculated sum and max_sum
    4. This difference represents m*(1+2+3+4…..)
    5. Run another loop.
    6. Keep dividing the difference with consecutive sums (1, 1+2, 1+2+3, 1+2+3+4)
    till the consecutive sums exceed the difference.
    7. The smallest whole sum(no remainder) found is the answer.
    8. Verify by checking through the array.

  7. Amar says:

    1. Seems like a DP problem. But you want the answer in O(n). Will have to think of some thing better. 🙂

  8. Amar says:

    8. Divide the array into n/k list of k size each. Sort each list. This will take O(nlogk). Now using a min heap, do a k-way merge.

    There must be something better for this …. 🙂

  9. Avi Dullu says:

    Solution to Problem No. 8

    Use a k element min-heap and popping the top element from it and inserting the next element into it. Here is the code

    using namespace std;
    class mycomparison
            bool operator() (const int& lhs, const int&rhs) const
                    return (lhs>rhs);
    int main()
            priority_queue<int, vector<int>, mycomparison> pq; // A min heap
            int n, k;
            cin >> n >> k;
            int* arr = new int[n];
            for ( int i=0;i<n;i++)  cin >> arr[i];
            for (int i=0;i<k;i++) pq.push(arr[i]);
            cout << << "\n";
            while ( k < n ) {
                    cout << << "\n";
            while ( pq.size() ) {
                    cout << << "\n";
            return 0;
  10. Divya says:

    2. use two heaps.. one maxheap and other minheap.

  11. Divya says:


    1- (19)^5/(20)^5

Leave a Reply

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

You are commenting using your 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: