SDE - 2

Step: This problem was based on sliding window concepts: 
public int minSubArrayLen(int target, int[] nums) {
int sum = 0;
int i =0;
int j = 0;
int ans = Integer.MAX_VALUE;
while(j= target){
ans = Math.min(ans, j-i+1);
sum -= nums[i];
i++;
}
j++;
}
return ans == Integer.MAX_VALUE ? 0 : ans;
}

Solution:
public int climbStairs(int n) {
int second = 0;
int first = 1;
for(int i=1; i<=n; i++){
int temp = first+second;
second = first;
first = temp;
}
return first;
}

Step: I used queue to use this problem. Over all time complexity for this problem was linear.
public List> zigzagLevelOrder(TreeNode root) {
List> ans = new ArrayList();
if(root == null ) return ans;

Deque queue = new ArrayDeque();
int count = -1;
queue.add(root);
while(!queue.isEmpty()){
List list = new ArrayList();
int n = queue.size();
if(count == -1 ){
for(int i=0; i TreeNode node = queue.removeFirst();
list.add(node.val);
if(node.left != null ) queue.addLast(node.left);
if(node.right != null ) queue.addLast(node.right);
}
}else{
for(int i=0; i TreeNode node = queue.removeLast();
list.add(node.val);

if(node.right != null ) queue.addFirst(node.right);
if(node.left != null ) queue.addFirst(node.left);
}

}
ans.add(list);
count = -count;
}
return ans;
}

Steps to solve the problem:
public void rotate(int[] arr, int k) {
int n = arr.length;
k = k%n;
reverse(arr, 0, n-1);
reverse(arr, 0, k-1);
reverse(arr, k, n-1);
}

public void reverse(int arr[], int start, int end){
while(start < end){
int temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
start++;
end--;
}
}

Steps to solve this problem: 

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;
}
}