The recruiter called and asked if I was interested in the job opportunity.

The process began with solving a programming problem on InterviewStreet, for which I was given 90 minutes.

This was followed by a 60-minute telephonic interview.

After clearing these two rounds, I was invited onsite and had to go through three face-to-face interviews.

The problems were hard algorithmic problems, and you are expected to write clean code on the first attempt.

The interviewers were really friendly and helpful.

My advice would be to have confidence in yourself and be as honest as possible in an interview.

For practice, you should be well-versed with standard algorithmic techniques, such as:

• Dynamic programming
• Greedy algorithms
• Solving linear recurrences in logarithmic time
• Recursion
• Tree traversals

You are given an integer N and an integer M. You are supposed to write a method void findBestCoinsThatMinimizeAverage(int N, int M) that prints the best collection of N coins that minimize the average number of minimum coins needed to generate values from 1 to M.

For example, if M = 100 and N = 4:

If we use the set {1, 5, 10, 25} to generate each value from 1 to 100, minimizing the number of coins for each value (e.g., 1 = 1 (1 coin), 2 = 1 + 1 (2 coins), 6 = 1 + 5 (2 coins), 24 = 5 + 5 + 5 + 5 + 1 + 1 + 1 + 1 (8 coins)), the average number of coins comes out to approximately 5.7.

However, if we instead use {1, 5, 18, 25}, the average would be approximately 3.7.

Your task is to find the set of N coins that produces the minimum average and print them.