Java Questions

Difference between ArrayList and LinkedList in Java

1. Finding the intersection point of two linked lists.

Ans: Efficient approach: Find lengths of both lists calculate difference of the lengths, move that many steps in longer list move in both lists in parallel until links to next node match. That is the intersecting point. Time Complexity of this approach is O(max(m,n))

2.  How to detect if a linked list has a loop?

Ans: Use to pointer say Tortoise (Slow ptr) and the Hare (fast ptr), start at the beginning of linked list.
For each iteration, slow ptr moves one step and the fast ptr moves two steps.
If there is a loop, fast ptr will go around the loop and meet with slow ptr.
If there is no loop, the fast prt will get to the end of the list without meeting up with the slow ptr.
This algorithm runs with O(n) time complexity and O(1) space complexity.

3. How to find Length of the loop?

Ans: find if there is a loop. After finding the loop, Initialize slowptr to fastPtr.
Keep moving slowptr and until it come back to fastptr, use a counter variable when moving slowptr.

4. How to find Start Node of the Loop?

Ans: find if there is a loop. After finding the loop, Initialize slowptr to head.
Keep moving slowptr and fastptr by one position until they both meet, (while(slowptr != fastptr))

5. How to find k th node from end of a linked list?

Ans: This problem can be solved in one scan of linked list.
use two pointers, ptr1, ptr2
start ptr2 from head and move k nodes. Initialize ptr1 to head
From now on move ptr1 and ptr2 until ptr2 reaches end of the list
As a result ptr1 points to k th node from end of the linked list.

6. Given an array of N distinct integers, write a program to find pair of integers whose sum is x, x can be zero or any constant.

Ans: Sort the array A[] in nlogn time
Assign two pointers, one(start) points to the start of array, second(end) points to the end of array. Repeat the following until you find a pair, else no pairs whose sum is x.
if (A[start]+A[end] == x) return start,end
if(sum & gt; x) end--;
if(sum & lt; x) start++;

7. To find all pairs:
Sort the array in nlogn time
for each integer i, check if there exists (x – i) by doing binary search

public static void findAllPairsWithSumX(int[] A, int x) {
    Arrays.sort(A);
    for (int i = 0; i < A.length - 1; i++) {
        int tofind = x - A[i];
        int returned = Arrays.binarySearch(A, i + 1, A.length, tofind);
        if (returned > 0) {
            System.out.println("Sum " + x
                    + " is found, values the making sum are " + A[i]
                    + " , " + A[returned]);
        }
    }
}

8. A clerk at a shipping company is charged with the task of rearranging a number of large crates in order of the time they are to be shipped out. Thus, the cost of compares is very low (just look at the labels) relative to the cost of exchanges (move the crates). The warehouse is nearly full: there is extra space sufficient to hold any one of the crates, but not two. Which sorting method should the clerk use? (among Selection sort, Insertion sort)

Ans: use selection sort because it minimizes the number of exchanges. (get smallest which one need to be shipped first and put at the available space)

Q. Find the element with highest occurrences in an array.

A.Quick sort the array. Use the built in Arrays.sort() method.Now compare the adjacent elements. Consider this example:
1 1 1 1 4 4 4 4 4 4 4 4 4 4 4 4 9 9 9 10 10 10 29 29 29 29 29 29
When the adjacent elements are not equal, you can stop counting that element.

Q. There is a promotion running on snapdeal.com through which you can exchange your SD Cash of "N rs off"  for 3 new coupons by given formula :
N   =>  (N/2) + (N/3) + (N/4)
For non-integer amounts they will be rounded off to nearest integer.
You could use this scheme as many times on as many coupons you want.
Find the maximum amount of money which you will be getting by using this promotion.

Input:
The input will contain several test cases (not more than 10).
Each test case is a single line with a number n, 0 <= n <= 1 000 000 000.
It is the number written on your coin.

Output
For each test case output a single line, containing the maximum amount.
Input:
12
2

Output:
13
2
You can change 12 into 6, 4 and 3, and then change these into 6+4+3 = $13.
If you try changing the coin 2 into 3 smaller coins, you will get 1, 0 and 0, and later you can get no more than 1 out of them.
It is better just to change the 2 coin directly into 2.

Q. What is LRUCache?

Ans: Items will expire based on a time to live period.
Cache will keep most recently used items if you will try to add more items then max specified. (apache common collections has a LRUMap, which, removes the least used entries from a fixed sized map)
For the expiration of items we can timestamp the last access and in a separate thread remove the items when the time to live limit is reached. This is nice for reducing memory pressure for applications that have long idle time in between accessing the cached objects.

Some General Questions

Q. Sort an int array in single iteration O(n)?

Q. Remove duplicate chars from a given string in O(n) single iteration without using any java API or collection?

Q. Reverse the given string using recursion?

Q. What is live lock and explain problems with the race condition?

Q. What is advantage of using mediator pattern, what are disadvantages of singleton class. what is Object delegation pattern.

Q. What is difference between Proxy and delegation patterns?

Q. If we have millions of images on server and user trying to upload an image to server how you will check and tell if a duplicate image is already existing on server?

Ans:  Generate hash code for the content of the image using MD5 or SHA1-2 algo and keep them in hashmap)

Q. If I have an array of size [1024] then how many minimum steps you required to tell an element exist in array or not using binary tree?

Q. How to create a class which can behave like an abstract class in java (can't create an Object of it), what techniques compiler uses to restrict object creation, but if u extend it object creation is allowed?

Ans: Can create a class having protected constructor.

Q. How to get top 5-10 records from a select query?

Ans: Using limit in SQL Query.

Q. How to remove the duplicates entries from a table and keep only unique rows like (in EMP table if name column has values test, test, test, abc, bcd, abc then resulted table should have test, abc, bcd records.

Ans: hint, we can have a column count c and use having c=1 clause with group by.

SELECT FirstName, LastName, MobileNo, COUNT(*) as CNT
FROM  CUSTOMER
GROUP BY FirstName, LastName, MobileNo;
HAVING COUNT(*)  = 1

Q. Implement a stack which can give a min value present in the stack at any time, even after doing push or pop operations

Ans: Can be implemented using 2 stacks.

Q. A Class having static filed and non static filed how you will define synchronization to use it for multi-threading.

Ans: Static fields or Objects should be used using synchronized static methods or block and non static fields or object should be used using non static synchronized method or block.

public class MixedSynchornization {
    private static int count = 0;
    private int testCount = 0;
    //locking on .class object lock
    public static synchronized int getCount(){
        return count;
    }
  
    //locking on .class object lock
    public static synchronized void increment(){
        count++;
    }
    
    //locking on this object lock
     public synchronized int getTestCount(){
        return testCount;
    }  
    
    public synchronized void incrementTestCount(){
        testCount++;
    }
}

Some Keywords for Algorithms:
 Bentley's Programming Pearls.(problems)
 Golomb coding is a lossless data compression method
 Rice coding
 Trie, also called digital tree and sometimes radix tree or prefix tree
 BidiMap (bidirectional map), MultiMap etc.