Given array and a number x, check for pair in arr with sum x

We can directly jump to brute force approach and end up with o(n2) complexity solution.










No. comparisons = ( n(n+1) / 2 ) - n where n is array length.

Problem with above approach are
a. Trying unnecessary combinations
    means more comparisons,add operations,time consumption etc
b. Giving interviewer one chance to reject us :)

Better approach 1:

Whenever we are dealing with arrays, following things, we need to keep in mind

1) Array sorting.
2) Input range.
3) minimum no.of comparisons/copy operations needed.
4) Usage of index pointers
5) Boundary conditions (<arr.length , >-1)

Most of the times, sorting and binary search combination solves most of the array problems for us.

Best thing about this approach is, we are avoiding unnecessary combinations by taking advantage of sorted data.

If we find, summation is less than X, then we should try adding next big number from beginning otherwise try adding next small number from ending.

This solution works in o(nlogn) sorting + o(n) time which is way better than o(n2).

Best apporach 2:

If there is no constraint on extra space, then we can try out below approach.

Note1: We should know range of input
Note2: This solution works for negative numbers as well !

Above approach does the trick in o(n) complexity with additional space.

Above approach works like a charm, while dealing with negative numbers. All we have to do is try converting all -ve numbers into positive ones.

     int[] arr = new int[]{1,4,45,-6,10,-8};
     int x = 2

Steps:
a) Find least minimum number and it's absolute value: |-8| = 8
b) Add 8 to all input values: {9,12,53,2,18,0}
c) Add 8 + 8 to x: 16 +2 = 8

10 + (-8) = 2
(10 + 8) + -8 = 10;
18+ -8+8 = 10+8
18 = 18

Hope you find this post useful.

Happy learning :)

Tricky interview question on Volatile keyword in Java

As we all know that, 

1) Volatile prevents the threads from caching variable values locally.

2)  It plays key role in inter thread communications.

But there is a tricky question on volatile i.e 'Is there any side affects on non volatile variables if we use volatile '. Have a look at the below program to know the answer.

public class TestVolatile implements Runnable

{

int num1 = 10;

int num2 = 30;

 volatile int sum;

 

public void run() 

{

           // First thread performs write operations on sum and num1

          // Second thread performs read operations to get latest values from main memory and                        //then perform write

sum = num1 + num2;

num1 = 300;

   System.out.println(Thread.currentThread().getName()+" - "+sum);

    System.out.println(Thread.currentThread().getName()+" - "+num1);

   System.out.println(Thread.currentThread().getName()+" - "+num2);

}

public static void main(String args[])

{

TestVolatile TestVolatile =  new TestVolatile();

Thread thread1 = new Thread(TestVolatile);

Thread thread2 = new Thread(TestVolatile);

thread1.setName("Thread1");

thread2.setName("Thread2");

thread1.start();

thread2.start();

}

}

You would have noticed that, num1 value of one thread is effecting sum computation of another thread . Does this mean that using volatile also has side-effects to the usage of non-volatile variables? YES.

Reason: Any writes in the thread that wrote to the volatile before doing so will be seen by the thread reading the volatile after having done so

Refer below links for more info:

1) http://stackoverflow.com/questions/12438464/volatile-variables-and-other-variables

2) http://stackoverflow.com/questions/9169232/java-volatile-and-side-effects

3) http://docs.oracle.com/javase/tutorial/essential/concurrency/atomic.html

Happy Learning :)