## Algorithms in Java Interviews

In this post, we will see algorithm problems with their solutions which are asked during Java interviews.

### How to check if a number is Palindrome?

```void checkPalindrome(int n){
int temp, sum = 0;
int input=n;

while(n>0) {
temp = n%10;
sum = (sum*10) + temp;
n = n/10;
}

if(input == sum){
System.out.println("Palindrome");
} else {
System.out.println("Not Palindrome");
}
}```

### How to check if a number is Prime in Java8?

```void checkPrime(int n) {
if(n > 1 && IntStream.range(2, n).noneMatch(i -> i%n==0)) {
System.out.println("Prime");
} else {
System.out.println("Non-Prime");
}
}```

### How to sort objects in reverse order in Java8?

```Student student1 = new Student(372,"Venkat",1);
Student student2 = new Student(2,"Sachin",4);
Student student3 = new Student(2345,"Ganguly",6);
Student student4 = new Student(72,"Karthik",2);
List studlist = new CopyOnWriteArrayList();

// Iterate in Java8
studlist.forEach(s -> System.out.println(s.name));

// Sort by Ids
studlist.sort((Student s1,Student s2) -> s1.getId() - s2.getId());

// Sort by Rank in reverse Order
studlist.sort((Student s1,Student s2) -> s2.getRank() - s1.getRank());```

### Find second highest number in an Array?

```int arr[] = {45,89, 29,1, 9, 100};
int highest = 0, secondHighest = 0;

for(int i=0; i<arr.length;i++) {   if(arr[i] > highest) {
highest = arr[i];
} else if(arr[i] > secondHighest) {
secondHighest = arr[i];
}
}```

### Find Nth highest Salary from a SQL Table?

```SELECT MIN(SALARY) FROM EMPLOYEE
WHERE SALARY IN (SELECT DISTINCT TOP N
FROM EMPLOYEE ORDER BY SALARY desc);```

### Print Only Numerics from a String?

```String sampleStr = "fdsha3430d3kdjafl0737434833";
String numericsOnlyStr = sampleStr.replaceAll("[^0-9]", "");```

### Print Duplicates in an Array?

```for(int i=0;i<arr.length;i++) {
for(int j=i+1; j< arr.length; j++) {
if(arr[i] == arr[j]) {
System.out.println(arr[j]);
}
}
}```

### Fetch Frequency of Elements repeated in an Array?

```  Map<Integer, Integer> mp = new HashMap<>();

// Iterating through array elements
for (int i = 0; i < n; i++)
{
if (mp.containsKey(arr[i]))  {
mp.put(arr[i], mp.get(arr[i]) + 1);
} else {
mp.put(arr[i], 1);
}
}

// Iterating through Map and Printing frequencies
for (Map.Entry<Integer, Integer> entry : mp.entrySet()) {
System.out.println(entry.getKey() + " " + entry.getValue());
}
```

### Find Triplets in an array whose sum is equal to n?

```public class Triplets {
public static List<List> findTriplets(int[] numbers, int sum) {
List<List> tripletsCombo = new ArrayList<List>();
HashSet set = new HashSet();
List triplets = new ArrayList();

if (numbers.length == 0 || sum <= 0) {
return tripletsCombo;
}

Arrays.sort(numbers);

for (int i = 0; i < numbers.length - 2; i++) {
int j = i + 1;
int k = numbers.length - 1;

while (j < k) {
if (numbers[i] + numbers[j] + numbers[k] == sum) {
String str = numbers[i] + "," + numbers[j] + "," +       numbers[k];
// Check for the unique Triplet
if (!set.contains(str)) {
triplets = new ArrayList();
}
j++;
k--;
} else if (numbers[i] + numbers[j] + numbers[k] < sum) {    j++; } else { // numbers[i] + numbers[j] + numbers[k] > sum
k--;
}
}
}

return tripletsCombo;
}

public static void main(String[] args) {
int[] numbers = { 2, 3, 1, 5, 4 };
int sum = 9;
List<List> triplets = findTriplets(numbers, sum);

if (triplets.isEmpty()) {
System.out.println("No triplets are found");
} else {
System.out.println(triplets);
}
}
}```

### How to check if two strings are Anagrams?

Two strings are called Anagrams if they contain same set of characters but in different order.  Examples:  “Astronomer – Moon starer”, “A gentleman – Elegant man”, “Dormitory – Dirty Room”, “keep – peek”.

```void isAnagram(String input1, String input2) {
//Removing all white spaces from s1 and s2
String s1_nonSpaces = input1.replaceAll("\\s", "");
String s2_nonSpaces = input2.replaceAll("\\s", "");

boolean status = true;
if(s1_nonSpaces.length() != s2_nonSpaces.length()) {
status = false;
} else {
char[] s1Array = s1_nonSpaces.toLowerCase().toCharArray();
char[] s2Array = s2_nonSpaces.toLowerCase().toCharArray();
Arrays.sort(s1Array);
Arrays.sort(s2Array);
status = Arrays.equals(s1Array, s2Array);
}
System.out.print(status?"Anagrams":"Non-Anagrams");
}```

### Swap numbers without using temp/third variable?

```void swapWithoutTemp(int a, int b) {
a = a+b;
b = a-b;
a = a-b;
}```

### Find number of combinations for Sum of Two Elements from two arrays is equal to N?

We have two arrays of numbers, suppose we take one element from first array and another element from second array. Their sum should be equal to N(given number).

```sumOfTwoElementsInTwoArrays() {
int arr1[] = {4,8,10,12,7};
int arr2[] = {6,90,34,45};

int sumValue = 44;
HashSet complements = new HashSet();
int pairCount = 0;

for(int i=0;i<arr1.length;i++) {
}

for(int j=0;j<arr1.length;j++) {
if(complements.contains(arr2[j])) {
pairCount++;
}
}

System.out.print("Number of pairs is "+pairCount);
}```

### First non repeated character in a String?

```String str = "BANANA";
char firsNonRepeatedCharacter;
HashMap<Character, Integer> hmp = new HashMap<Character, Integer>();

for(int z=0;z<s.length();z++) {
if(hmp.containsKey(str.charAt(z))) {
hmp.put(str.charAt(z), hmp.get(str.charAt(z))+1);
} else {
hmp.put(str.charAt(z), 1);
}
}

Set characterSet = hmp.keySet();
for(Character c:characterSet){
if(hmp.get(c).toString()equals("1")) {
firsNonRepeatedCharacter = c;
break;
}
}```

### Find the number of occurrence of an element in an array using Java8?

```int b[] = {1,2,34,1};

List bList = Arrays.stream(b).boxed().collect(Collectors.toList());

System.out.println(bList.stream().filter(z -> z.toString().equalsIgnoreCase("1")).count());```

### 100 doors toggle open/close

There are 100 doors in a row, all doors are initially closed. A person walks through all doors multiple times and toggle (if open then close, if close then open) them in following way:

In first walk, the person toggles every door, In second walk, the person toggles every second door, i.e., 2nd, 4th, 6th, 8th, …, In third walk, the person toggles every third door, i.e. 3rd, 6th, 9th, …

Find in nth walk, what will be the status of all doors

```doorsOpenClosed(int no_of_walks) {
int door_id, walk_id;
int doors[] = new int[101];
for(int i=0;i<100;i++) {
doors[i] = 0;
}

for (walk_id = 1; walk_id <= no_of_walks; walk_id++) {
for (door_id = walk_id; door_id <= 100; door_id += walk_id) {
if(door_id%walk_id == 0) {
doors[door_id]=(doors[door_id] == 0)?1:0;
}
}
}

for (int j = 0; j <= 100; j++) {
if(doors[j] == 1) {
System.out.println("Open Door number::::"+j);
}
}

}```

## Core Java and Java 8 Concepts

In this post, you will see some important Core Java/Java 8 concepts related to Collections, Exception Handling, Multi-threading, Concurrency etc.

### Comparable Vs Comparator

 Comparable Comparator Comparable provides a single sorting sequence. In other words, Sorting of  collection is based on a single property of a class such as ID, ItemName or quantity etc. The Comparator provides multiple sorting sequences. In other words, sorting of collection can based of multiple properties such as ID, ItemName, and quantity etc. Comparable affects the original class, i.e., the actual class is modified. Comparator doesn’t affect the original class, i.e., the actual class is not modified. Comparable provides compareTo() method to sort elements. Comparator provides compare() method to sort elements. Comparable is from  java.lang package. A Comparator is from java.util package. Sorting list of Objects-Comparable type can be done using Collections.sort(List) method. Sorting list of Objects-Comparator type by Collections.sort(List, Comparator) method.

### Difference between ClassNotFoundException and NoClassDefFoundError

• ClassNotFoundException is an Exception, while NoClassDefFoundError is an Error.
• ClassNotFoundException occurs when `CLASSPATH` does not get updated with required JAR files while NoClassDefFoundError occurs when required class definition is not present at runtime.

Example for NoClassDefFoundError :

```class Shape {
public void draw() {
System.out.println("Drawing Shape!");
}
}

public class DrawingApp {
public void draw() {
System.out.println("Drawing Shape!");
}
public static void main(String[] args) {
Shape shape = new Shape();
shape.draw();
}
}```

After compilation, Shape.class and DrawApp.class are generated, If Shape.class is deleted and DrawApp is run then NoClassDefFoundError is thrown.

### Difference between ConcurrentHashMap and SynchronizedMap

• ConcurrentHashMap is designed for concurrency and improves performance while Collections.synchronizedMap(map) which is non-synchronized by sort can be synchronized by applying a wrapper using Collections.synchronizedMap(map).
• ConcurrentHashMap doesn’t support null keys or null values while synchronized HashMap supports one null key.
• Locking in SynchronizedMap is at object level, so read/write operations performance is slower.
• Locking in ConcurrentHashMap is at a much finer granularity at a hashmap bucket level.

### Differences betwen equals() and hashcode() methods

equals() and hashCode() are methods present in Object class and hashCode method should not be used to check if two object references are same. Reason: hashCode just returns int value for an Object, even two different objects can have same hashCode integer. The value returned by hashCode() is the object’s hash code, which is the object’s memory address in hexadecimal. equals() checks if the two object references are same. If two objects are equal then their hashCode must be the same, but the reverse is not true.

### O(1) vs O(n) vs O(log n)

These are measures of time complexity of running a piece of code.

O(1) – if execution time is constant, it requires the same amount of time regardless of the size. Example:  array – accessing any element `int i = a[0];`

O(n) – if execution time is directly proportional to the size.  Example: Linear search for an element has a time complexity of O(n).

O(log n) – if execution time is proportional to the logarithm of the input size. Example: Performing Binary Search on array of elements

### Changes to HashMap in Java8

• In case of Hash collision entry objects are stored as a node in a LinkedList and equals() method is used to compare keys. That comparison to find the correct key with in a linked-list is a linear operation so in a worst case scenario the complexity becomes O(n).
• To address this issue, Java 8 hash elements use Balanced Tree instead of LinkedList after a certain threshold is reached. Which means HashMap starts with storing Entry objects in linked list but after the number of items in a hash becomes larger than a certain threshold, the hash will change from using a LinkedList to a Balanced Tree, which will improve the worst case performance from O(n) to O(log n).

### Fail Fast Vs Fail Safe Iterators

 Fail-Fast Iterators Fail-Safe Iterators Fail-Fast iterators doesn’t allow  modifications of a collection while iterating over it. Fail-Safe iterators allow modifications of a collection while iterating over it. Concurrent Modification Exception is thrown if a collection is modified while iterating over it. These iterators don’t throw any exceptions if a collection is modified while iterating over it. They use original collection to traverse over the elements of the collection. They use copy of the original collection to traverse over the elements of the collection. These iterators don’t require extra memory. These iterators require extra memory to clone the collection. Ex : Iterators returned by ArrayList, Vector, HashMap. Ex : Iterator returned by CopyOnWriteArrayList, ConcurrentHashMap.

### Difference between map() and flatmap() in Java8

Lets suppose we are applying map and flatmap on stream of streams. Example given below

`Stream<List<Character>> stream = Stream.of({'a','b'},{'c','d'})`

with map:  For input Stream of two lists {‘a’,’b’} and {‘c’,’d’}, output will be {{‘a’,’b’},{‘c’,’d’}} .Here two lists are placed inside a list, so the output will be list containing lists

With flat map: For input Stream of two lists {‘a’,’b’} and {‘c’,’d’}, output will be {{a,b,c,d}} .Here two lists are flattened and only the values are placed in list, so the output will be list containing only elements

### What are Functional interfaces how we can define them?

Functional interfaces are interfaces which have only one single abstract method in it. Example:  Runnable Interface since it has only single abstract method, run().

From Java8, we can use @FunctionalInterface to define a functional interface. Although this annotation is optional, once it is used then declaring more than one abstract method will throw compile time error.

There are specific rules while we implement method overloading and overriding in Java with regards to increasing/decreasing visibility of methods of parent class in child class and throwing Checked Exceptions in child class. Complete rules are posted in this below link

### Exception Handling flow having return statements in try/catch/finally blocks

• Once try block encounters a return statement, the flow immediately transfers to finally block. Let say,it prints “print statement from finally”.
• Upon the completion of finally block execution, control goes back to the return statement in the try block and returns “returning from try block”.
• If finally block has a return statement, then the return statements from try/catch blocks will be overridden.

### Exception Handling flow while exceptions thrown in catch/finally blocks

• If the catch block completes normally, then the finally block is executed. Then there is a choice:
• If the finally block completes normally, then the try statement completes normally. If the finally block completes abruptly for any reason, then the try statement completes abruptly for the same reason.
• If the catch block completes abruptly for reason R, then the finally block is executed. Then there is a choice:
If the finally block completes normally, then the try statement completes abruptly for reason R.
If the finally block completes abruptly for reason S, then the try statement completes abruptly for reason S (and reason R is discarded).

• newCachedThreadPool(): creates an expandable thread pool executor. New threads are created as needed, and previously constructed threads are reused when they are available. Idle threads are kept in the pool for one minute. This executor is suitable for applications that launch many short-lived concurrent tasks.
• newFixedThreadPool(int n): creates an executor with a fixed number of threads in the pool. This executor ensures that there are no more than n concurrent threads at any time. If additional tasks are submitted when all threads are active, they will wait in the queue until a thread becomes available. If any thread terminates due to failure during execution, it will be replaced by a new one. The threads in the pool will exist until it is explicitly shutdown. Use this executor if you and to limit the maximum number of concurrent threads.
• newScheduledThreadPool(int corePoolSize): creates an executor that can schedule tasks to execute after a given delay, or to execute periodically. Consider using this executor if you want to schedule tasks to execute concurrently.

ThreadLocal class provides thread-local variables. It enables you to create variables that can only be read and write by the same thread. If two threads are executing the same code and that code has a reference to a ThreadLocal variable then the two threads can’t see the local variables of each other.

### Diffence Volatile vs AtomicInteger?

volatile keyword is used on variables to solve the visibility problem in multi-threaded environment.  AtomicInteger is used if we perform compound operations(incrementing(i++) decrementing(i–)) on variables.

volatile is used on boolean flags, AtomicInteger is used for counters.

### Differences between yield, join, & sleep

`yield()` method pauses the currently executing thread temporarily for giving a chance to the remaining waiting threads of the same priority to execute. If there is no waiting thread or all the waiting threads have a lower priority then the same thread will continue its execution. The yielded thread when it will get the chance for execution is decided by the thread scheduler whose behavior is vendor dependent.

`join()` If any executing thread t1 calls `join()` on t2 i.e; `t2.join()` immediately t1 will enter into waiting state until t2 completes its execution.

`sleep()` Based on our requirement we can make a thread to be in sleeping state for a specified period of time

### Differences between Runnable and Callable

• `Runnable` object does not return a result whereas a `Callable` object returns a result.
• `Runnable` object cannot throw a checked exception wheras a `Callable` object can throw an exception.
• The `Runnable` interface has been around since Java 1.0 whereas `Callable` was only introduced in Java 1.5.
```class ThreadA implements Runnable {
@Override
public void run() { }
}

public class ThreadB implements Callable<String> {
@Override
public String call() throws Exception {
}
}```

### What is Semaphore in concurrency?

Semaphore is used to restrict the entry to a service to a fixed number of threads at a given time. This is generally used on slow services to make it available for fixed number of requests.

`Semaphore semaphore = new Semphore(no_of_permits);`

In run() method of a thread, we can use `semaphore.acquire()` before accessing the slow service and `semaphore.release()` after to ensure fixed number (defined as `no_of_permits`) of threads are eligible to access it.

### Difference between CyclicBarrier and CountDownLatch?

Both `CyclicBarrier` and `CountDownLatch` are used in Multi threading scenario where one Thread waits for one or more Thread to complete their job before it continues processing but main difference between two is that, you can not reuse same CountDownLatch instance once count reaches to zero and latch is open, on the other hand, CyclicBarrier can be reused by resetting Barrier, Once barrier is broken.

• Initialization of countdownlatch is `CountDownLatch latch = new CountDownLatch(4); `
• Method used to countdown (generally used inside run method of thread at a specific point) is `latch.countDown()`
• Method used to await a specific thread till countdown number completes is `latch.await()`
• `Phaser` can be used either to perform functionality of both CyclicBarrier and CountDownLatch