Given a sum S and number of non-negative number N, how many different ways can N non-negative numbers can be chosen such that their sum is S - I

You are given a number, say 3.  Let us think about different ways 2 non-negative numbers can be added to result in 3.

3 = 3 + 0 = 2 + 1 = 1 + 2 = 0 + 3

There are 4 different ways in which 2 non-negative numbers can be chosen such that the numbers' addition result in 3.

Let us think about different ways 3 non-negative numbers can be added to result in 3.

3
= 0 + 0 + 3
= 0 + 1 + 2
= 0 + 2 + 1
= 0 + 3 + 0
= 1 + 0 + 2
= 1 + 1 + 1
= 1 + 2 + 0
= 2 + 1 + 0
= 2 + 0 + 1
= 3 + 0 + 0

There are 10 different ways in which 3 non-negative numbers can be chosen such that the number's addition result in 3.



Given a sum - S and number of non-negative numbers to choose - N; find the number of ways in which N different non-negative numbers can be chosen such that the sum of the numbers result in S.

How would you solve it?

Bad solution

Find all possible non-negative numbers that would result in S when added.

How can we do that?


Given a Sum S and number N, every possible value for a particular variable will be between (0, S) - both included.

int count_correct_combination(int S, int N) {

int count = 0;

// if only one number needs to be "added", then only S should will be the correct value. So, only one right solution is possible.

if (N == 1) {

return 1;

}

// if Sum is 0, there is only one way for all numbers to be: all zeros

if (S == 0) {

return 1;

}

for (int i = 0; i < S; i++) {

count += count_correct_combination(S-i, N-1)

}

}

How does this work?

Please refer to Partition for more details.

Quick Guide of the algorithm:

| 0 | 1 | 2 | 3 | . | . | . | S |

1. The first number starts from 0 and lets the rest of the numbers to contribute S. Store the number of ways the rest of the numbers can contribute S.
2. Then, the first number takes 1 and lets the rest of the numbers to contribute (S - 1).  Store the number of ways the rest of the numbers can contribute (S - 1).

Server is running slow- how do you debug?

This is a common interview question:
You come to your work and discover that your server seems to run slowly all of a sudden.  You know it was running fast before.  How would you debug it?

Well, after some casual research, this is the response that I would give:

The reason why a computer is running could be one of the following:

1. The system might be running slow
2. Internet connection could be slow
3. The server could be running slow

The system could be running slow if 

• there is a different process that is taking up resources that server needs.  For example, some hardware scanning is taking place.  Depending on the OS, you can use different commands to list all processes and kill those that are slowing the system down.

Internet connection could be slow for various reasons

• Use some network softwares to figure out Internet speed.

The server could be running slow if

• Denial of Service attack happens:  Check the HTTP log file.  If there happens to be too many requests from the same IP address, it is a Denial of Service attack.  Solution is to configure network router to block that particular IP address.
• The code might have run into infinite loop:  Check CPU usage.  If it is high, probably it is in an infinite loop.  Get heap dump or thread dump over two or three different times.  If it is an infinite loop, you would see the same method listed in thread dump.
• Garbage Collector is running frequently (memory leak).  If Garbage Collector runs, then, no threads is executed.  Basically, the frequent execution of Garbage Collector means - the application is not getting enough memory for its execution.  Some memory leak could be the reason.  Take a Heap dump to see which objects occupy the maximum memory and using the source, analyze which part of code is contributing to this.
• Some external system that the application depends upon, may be slow.  Check logs.  The database might be running slow and timing out, some web service may be running slow and timing out.