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.

### Challenge others to solve

### Like this:

Like Loading...

## Recent Activity