Application Developer

The general approach/algorithm of sliding door is:

Use two pointers to represent your window. "start" & "end"
Keep moving the end pointer until your condition is true or in other words; the window is valid.
Start to condense your window by moving your start pointer while also simultaneously making sure your window is still valid.

public int minSubArrayLen(int target, int[] nums) {
// basic constraint checking
if (nums == null || nums.length == 0)
return 0;

// initialization of the start & end index of your sliding window 
int start = 0, end = 0, sum = 0, minLength = Integer.MAX_VALUE;

while (end < nums.length) {
// keep a running sum as the end pointer expands your window
sum += nums[end++];

// this while loop will be skipped until your window meets the condition that 
// the running sum is equal or greater than the int 's' passed in. aka the window
// is valid
while (sum >= target) {
// now you want to condense your window to find the minimum window as the 
// problem wants

// updates the min length
minLength = Math.min(minLength, end - start);

// this moves your start index by one condensing your window and 
// decreasing the sum to make sure that it's still valid
sum -= nums[start++];
}
}

// if no min is found, return 0 or else return the min length you found above. 
return minLength == Integer.MAX_VALUE ? 0 : minLength;
}

public ListNode deleteDuplicates(ListNode head) {
ListNode curr = head;
if(head == null) return null;

// if the head.next == null it means that the list contains only one node (head) 
//so there is no duplicates we will simply return the head of the list

if(head.next == null) return head;
else{
while(curr.next != null){
//we compare the data of the current node with the next node if they are equal
//we remove the next node 
if(curr.val == curr.next.val) 
curr.next = curr.next.next;
else
//if they are not equal we simply move forward
curr=curr.next;
}
}
return head;
}

Solution : Use doubly linked list with HashMap to get O(1) time compleixty for get and put method.

class LRUCache {

Map nodeMap;
DoublyLinkedList doublyLinkedList;
int capacity;


public LRUCache(int capacity) {
nodeMap = new HashMap();
doublyLinkedList = new DoublyLinkedList();
this.capacity = capacity; 
}

public int get(int key) {
if(nodeMap.containsKey(key)){
Node node = nodeMap.get(key);
doublyLinkedList.removeGiven(node);
doublyLinkedList.addFirst(node);
return node.val;
}
return -1;
}

public void put(int key, int value) {
if(nodeMap.containsKey(key)){
Node node = nodeMap.get(key);
node.val = value;
doublyLinkedList.removeGiven(node);
doublyLinkedList.addFirst(node);
}else{
if(nodeMap.size() == capacity){
Node node = doublyLinkedList.getTail(); 
doublyLinkedList.removeLast();
nodeMap.remove(node.key);
}
Node node = new Node(key, value);
doublyLinkedList.addFirst(node);
nodeMap.put(key, node);
} 
}


}

class DoublyLinkedList{

private Node head;
private Node tail;

public DoublyLinkedList(){
head = null;
tail = null;
}

public Node getHead(){
return head;
}

public Node getTail(){
return tail;
}

public void addFirst(Node node){
node.prev = null;
node.next = null;
if(head == null ){
head = node;
tail = node;
}else{
node.next = head;
head.prev = node;
head = node; 
}
}

public void removeLast(){
if(tail == null ) return;
if(tail.prev == null ) {
tail = null;
head = null;
return;
}
tail.prev.next = null;
tail = tail.prev;
}

public void removeGiven(Node node){
if(node.prev == null ){
head = node.next;
if(node.next == null) tail = null;
else node.next.prev = null;
}else{
node.prev.next = node.next;
if(node.next == null) tail = node.prev;
else node.next.prev = node.prev;
}
}

}

class Node{
int val;
int key;
Node prev;
Node next;
public Node(int key, int val){
this.key = key;
this.val =val;
this.prev = null;
this.next = null;
}
}

public int maxEvents(int[][] events) {
Comparator comparator = (a, b)-> a[0]-b[0];
Arrays.sort(events, comparator);
PriorityQueue pq = new PriorityQueue();
int i = 0;
int count = 0;
int day = 0'
while(i < events.length || !pq.isEmpty()){
if(pq.isEmpty()) day = events[i][0];
// add all the concurrent event to the queue
while( i< events.length && day == events[i][0]){
pq.add(events[i][1]);
i++;
}
// process the event which is ending early
pq.poll();
count++; // one possible result
//remove events which been ended till current day 
while( !pq.isEmpty() && day >= pq.peek()){
pq.poll();
}
//go to next day
day++;
}

return count;
}