# Java 26 CodeSignal Interview Guide - Batch 1

## 2. Merge Overlapping Intervals

### Problem
Input:
```text
[[1,3],[2,6],[8,10],[15,18]]
```
Output:
```text
[[1,6],[8,10],[15,18]]
```

### Optimal Solution

```java
record Interval(int start, int end){}

public static List<Interval> merge(List<Interval> intervals){

    intervals.sort(Comparator.comparingInt(Interval::start));

    List<Interval> result = new ArrayList<>();

    for(Interval current : intervals){

        if(result.isEmpty()){
            result.add(current);
            continue;
        }

        Interval last = result.get(result.size()-1);

        if(current.start() <= last.end()){

            result.set(result.size()-1,
                new Interval(last.start(),
                Math.max(last.end(), current.end())));

        }else{
            result.add(current);
        }
    }

    return result;
}
```

Complexity: O(n log n)

---

## 3. Queue Using Two Stacks

```java
public class MyQueue<T>{

    private final Deque<T> input = new ArrayDeque<>();
    private final Deque<T> output = new ArrayDeque<>();

    public void offer(T value){
        input.push(value);
    }

    public T poll(){

        if(output.isEmpty()){

            while(!input.isEmpty()){
                output.push(input.pop());
            }
        }

        return output.isEmpty() ? null : output.pop();
    }
}
```

Complexity:
- Offer O(1)
- Poll Amortized O(1)

---

## 4. Stack Using Two Queues

```java
public class MyStack<T>{

    private Queue<T> q1=new LinkedList<>();
    private Queue<T> q2=new LinkedList<>();

    public void push(T value){

        q2.offer(value);

        while(!q1.isEmpty()){
            q2.offer(q1.poll());
        }

        Queue<T> temp=q1;
        q1=q2;
        q2=temp;
    }

    public T pop(){
        return q1.poll();
    }
}
```

---

## 5. Floyd Cycle Detection

```java
class Node{
    int value;
    Node next;
}

public static boolean hasCycle(Node head){

    Node slow=head;
    Node fast=head;

    while(fast!=null && fast.next!=null){

        slow=slow.next;
        fast=fast.next.next;

        if(slow==fast){
            return true;
        }
    }

    return false;
}
```

Complexity: O(n)

---

## 6. Thread-safe Singleton

```java
public final class Singleton{

    private Singleton(){}

    private static class Holder{

        private static final Singleton INSTANCE =
                new Singleton();
    }

    public static Singleton getInstance(){

        return Holder.INSTANCE;
    }
}
```

Recommended interview answer because it is lazy, thread-safe and lock-free.