Programming Problems 10

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.


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

13 Responses to Programming Problems 10

  1. spsneo says:

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

  2. spsneo says:

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

  3. Neet says:

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

  4. Neet says:

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

    cannot think of it.

    • Avi Dullu says:

      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 🙂

  5. Amar says:

    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.

  6. @Amar solution should work

  7. Avi Dullu says:

    @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 🙂

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: