# Programming Problems 14

April 8, 2010 15 Comments

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

Example1

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

Output: 3

Example2:

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.

e.g.

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

1,2,3,…

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.

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

O(n) – space

O(n) – time

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

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?

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.

This would be equivalent to using O(n) space. There is an O(1) space and O(n) time solution. Just try some math 🙂

3.

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.

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

Every maxima/minima problem isn’t a DP one 🙂

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 …. 🙂

Indeed there is a much better way..

Think heaps as primary mode of operations 🙂

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

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

I don’t see how inserting into a heap will get you to an O(1) amortized time.

4.

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