# Programming Problems 9

February 25, 2010 3 Comments

Found some more questions for you guys 🙂

1. Given a list of points in the plane, write a program that outputs each point along with the three other points that are closest to it. These three points ordered by distance.

2. [Google] Given n elements, sort the elements. Here, only one operation is permitted decreaseValue..

Note that you cannot swap the values.. output should be a sorted list..

if input is 4 5 2 1 3

output is 3 3 3.. There can be many answers.. Give the optimum solution with minimum cost. where as cost is the sum of decreased amounts..

for this example, 4,5 are decreased by 1.. 2 is decreased by 2.. 1 is decreased by 1.

3. Given a string S of alphabets and 2 characters a,b find the minimum distance between instances of them such that position of a <= position of b.

4. Given a string S of words and no of character per line m , with m being greater than the longest word in S, print S in a set of lines so that each line contains no more than m characters and no word split between 2 lines.

5. An array is of size N with integers between 0 and 1024(repetitions allowed). Another array of integers is of size M with no constraints on the numbers. Find which elements of first array are present in the second array.

(If you are using extra memory, think of minimizing that still, using bitwise operators)

6. [Google] Describe an algorithm that takes an unsorted array of axis‐aligned rectangles and returns any pair of rectangles that overlaps, if there is such a pair. Axis‐aligned means that all the rectangle sides are either parallel or perpendicular to the x‐ and y‐axis. You can assume that each rectangle object has two variables in it: the x‐y coordinates of the upper‐left corner and the bottom‐right corner.

7. [Google] Given an n x n grid with a person and obstacles, how would you find a path for the person to a particular destination? The person is permitted to move left, right, up, and down.

8. Given a long string and a given word find out how many times you can write that word using subsets of the string. (i.e., you can create "dog" with "doom dogged" 8 times.

Hello Avi,

Nice sharing. Where can I find a answer to the 2nd problem?

Trying to solve it, but cannot come up with algorithm that produces solution with minimum cost.

let me just give u a hint for this.

min_cost[a_i+1] = if a_i+1 >= a_i then min_cost[a_i]

else min( min_cost[a_i] + a_i+1, min_cost[a_i] + Summation[(j <- 1..i) (a_j – a_i)])

where a_i, a_i+1 are the i_th and i+1_th element in the considered array.

Can u write a recursive program for this and check? It's 5 in the morning and am not sure of the approach 😀

Hi, Avi.

Thank you for your hint.

Sorry for a late response.

I came up with a solution for the problem inspired by Djikstra shortest path finding algorithm.

If you’re interested, you can check my solution here:

https://github.com/hwangroman/programming_problems/tree/master/google_sort_problem.

sort.py contains solution, with test_sort.py contains some testing with different input numbers.

I provided some description of my solution in problem.txt. I don’t think it’s that transparent right now. Gonna fix it later.