To synchronize or not to synchronize?

Let us say we implement a very common functionality and offer our implementation as a open source library.  For example, we develop a library to keeping track of count of how many times a certain operation has taken place - like a call to web service.  We know this is very reusable.  But, we do not know how this functionality will be used by developers.  There could be many concerns on how this library could be used by the developers; but in this post, let us concentrate on: will the functionality be called from a multi-threaded environment?

The traditional way of handling multi-threading is to ensure make a critical-section is accessed in a single-threaded way.  To achieve this in Java, we use synchronized key word.  synchronized gets a lock (atomically) on the object (non-static methods) or class (static methods).  In Java, we also have an option of maintaining lock on an arbitrary object.  Code that is safe for execution by multiple threads is called thread-safe.

Now, the downside of synchronized is that it takes a lot of performance-hit.  For a fast program, it is advisable to use synchronized in as few places as possible - (a) this will reduce the performance-hit produced by synchronized (b) it ensures that as many threads executes in parallel as possible - both of which are good for performance.

So, given these facts about synchronized, in our Counter library, should we synchronize to make it thread-safe or not synchronize to make it fast?

The advisable approach is: do not synchronize unless you are sure that the code will be used in multi-threaded environment.

So, we would not make our Counter's methods synchronized.  If a developer intends to use our Counter class in a multi-threaded code, then the developer should ensure that the methods are called in a thread-safe manner.  This can be done by synchronizing over Counter object (or some other lock object) or by providing a wrapper method that is synchronized on the calling object.

Some simple multi-threading tips:

• Always check if object is used in a multi-threaded environment.
• Make the object immutable.  This means that you set values to an object's state only in constructor.  There should be no method accessible to other classes that can change the state of object after constructor has finished execution.
• If you are dealing with a group of objects, use a separate lock object and synchronize based on that lock object.

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 - II

Please refer to previous post for more information regarding the problem that we are discussing.

In our previous post, we discussed a bad solution for the problem of finding how many combination of N non-negative numbers can we find such that it yields a given sum S.

The complexity of the discussed solution was SN 

The solution had a sample Java code for the method - count_correct_combination

Let us again consider S = 3 and N = 3.  To compute this answer, we compute

S = 3, N = 3

S = 3, N = 2

S = 3, N = 1

S = 2, N = 1

S = 1, N = 1

S = 2, N = 2

S = 2, N = 1

S = 1, N = 1

S = 1, N = 2

S = 1, N = 1

S = 0, N = 2

We can find that S = 1, N = 1 is calculated repeatedly.  For some large input values of N and S, there will be many such intermediate values of S and N that will get calculated repeatedly.  All these contributes to exponential complexity.

This can be improved by remembering what the value was when we calculated the result for a give S and N.

To do that, create a two-dimensional array of dimensions (S + 1, N) and store intermediate values in the array.  S + 1 - because there are S + 1 possible values for every variable (0 to S - both included).

Variables\Sum	0	1	2	.	.	S - 1	S
Number             1	1	1	1	1	1	1	1
of                  2	1
variables          .	1
.	1
N - 1	1
N	1

The first column and the first row are all 1's.  This is because of the following two facts:

1. The number of different ways we can choose N non-negative numbers such that the sum of the numbers is 0 = is always 1.  This is because to get sum(n numbers) = 0, we need every number to be equal to 0.  There is no other way to pick non-negative numbers to result in sum of zero.
2. The number of different ways in which 1 variable can result in a sum of S = is 1.  That is that one variable should be = S.  Otherwise, sum(variables) will not be = S.

To calculate the value for the rest of the elements in our array, we know that result of (S, N) = sum of (S - x, N - 1) where x = 0 to S (both included).  Applying this formula 

Variables\Sum	0	1	2	.	.	S - 1	S
Number             1	1	1	1	1	1	1	1
of                   2	1					xxx	= value(0, 1) + value(1, 1).. + value(S, 1)
variables          .	1					xxx
.	1					xxx
N - 1	1	xxx	xxxx	xxx	xxx	xxx	= value(0, N-2) + value(1, N-2).. + value(S, N-2)
N	1	= value(0, N-1) + value(1, N-1)				= value(0, N-1) + value(1, N-1).. + value(S-1, N-1)	= value(0, N-1) + value(1, N-1).. + value(S, N-1)

In other words, the value of any element in a given (col, row) is equal to sum of values of all elements from 0th column till col in the row above.

But if we do a sum of elements in a row-above to find values in the desired row, we might be computing sum of first few elements again and again.  This can be simplified further.

So, given col1 and row1 for which we need to calculate value, we do 

value(col1,row1) = (value(0, row1 - 1) + value(1, row1 - 1) + value(3, row1 - 1) + ... value(col1, row1 - 1))

To find the value of col1 + 1, row1, we do (Note: Take note of how the paranthesis changes)

= (value(0, row1 - 1) + value(1, row1 - 1) + value(3, row1 - 1) + ... value(col1, row1 - 1) + value(col1 + 1, row1 - 1))

=  (value(0, row1 - 1) + value(1, row1 - 1) + value(3, row1 - 1) + ... value(col1, row1 - 1)) + value(col1 + 1, row1 - 1)

= value(col1,row1) + value(col1 + 1, row1 - 1)

Translating this to an arbitrary col, row, we get:

value(col, row) = value(col - 1, row) + value(col, row - 1)

In simple words, value of an element at col1, row1 = value of cell above + value of cell to the left.

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.