# Programming Problems 10

March 12, 2010 13 Comments

More problems which I found floating on the internet. There is a good number of nice programming problems in the previous posts named under **Programming Problems** in my older posts.

1. [Google] You are given a String number containing the digits of a phone number (the number of digits, n, can be any positive integer) . To help you memorize the number, you want to divide it into groups of contiguous digits. Each group must contain exactly 2 or 3 digits. There are three kinds of groups:

• Excellent: A group that contains only the same digits. For example, 000 or 77.

• Good: A group of 3 digits, 2 of which are the same. For example, 030, 229 or 166.

• Usual: A group in which all the digits are distinct. For example, 123 or 90.

The quality of a group assignment is defined as 2 × (number of excellent groups) + (number of good groups)

Divide the number into groups such that the quality is maximized. Design an efficient algorithm to return the solution that maximizes the quality.

2. Within a 2D space, there is a batch of points(no duplicate) in the region (0,0),(0,1),(1,0),(1,1), try to find a line which can divide the region to 2 parts with half points in each .the input will be an array of points and the length of the array.

struct point{

int x;

int y;

};

input : struct point * points, int length

3.[Google] How many oranges/spheres (each of diameter 10 units) can you fit into a box with a size = 100 X 100 X 100 units.

4. Given an array of integers A, give an algorithm to find the longest Arithmetic progression in it, i.e find a sequence i1 < i2 < … < ik, such that

A[i1], A[i2], …, A[ik] forms an arithmetic progression, and k is the largest possible.

The sequence S1, S2, …, Sk is called an arithmetic progression if

Sj+1 – Sj is a constant.

5. 14. Design a data structure that can be used instead of an array and avoids the "high-cost" (i.e. O(n)) of initializing the array. the data structure ought to holds n items and supports the following operations in O(1) time:

* Init – Initializes the data structure to empty.

* Set(i, x) – Sets item x at index i in the data structure.

* Get(i) – Gets the item stored in index i (or 'empty' if nothing is there).

Remark: the data structure should use O(n) space.

can you give a hint for question 2. I am blank.

Hope this link helps you

http://en.wikipedia.org/wiki/Ham_sandwich_theorem

For question no. 4- is the given array sorted?

No its not

Is not Question 4: similar to longest increasing subsequence. only that here the condition needs to check Sj+1 – Sj is a constant.

yes … its something like this, but more complicated 🙂

Question 5: how can init() of data structure of length n be done in o(1)

cannot think of it.

hint: think on lines of using some augmenting data structure so that there is no need to initialize, but the rest operations can be implemented just by a check 🙂

For odd number of points : Find the median based on x co-ordinate and draw a line parallel to y -axis through it. You can do the same with Y- co-ordinate.

For even number of points It will lie between the two medians.

If there is something i am missing, please point it out.

that will give two lines. The problem only asks for one line, which divides all points in 2 equal parts.

Take either line ….. 🙂 …

@Amar solution should work

@Amar and Siddharth

Firstly, nobody pointed out that the problem has a bug :). It says that points are inside (0,0), (0,1), (1,0) and (1,1) and the structure given for each point has int x,y;

how can this be ??

Secondly, if we try to stretch the problem to a finite set of points in a plane and try to find a line dividing the points in 2 parts with equal number of points, I couldn’t confirm Amar’s solution . eg. try with the points (0,0), (1,0), (1,1), (2,2) and (3,3).

Please tell me if I missed something 🙂