LRU (Least Recently Used) Cache Implementation in Java

import java.util.HashMap;

import java.util.Map;

class Node{

int key;

int value;

Node pre;

Node next;

public Node(int key , int value) {

this.key = key;

this.value = value;

}

}

class LRUImpl {

Node head , tail;

int CAPACITY, count;

Map<Integer, Node> map ;

public LRUImpl(int capacity) {

this.CAPACITY = capacity;

this.count = 0 ;

this.map = new HashMap<Integer, Node>();

head = new Node(0,0);

tail = new Node(0,0);

head.next = tail;

head.pre = null;

tail.next = null;

tail.pre = head;

}

public void deleteNode(Node node) {

node.pre.next = node.next;

node.next.pre = node.pre;

}

public void addNodeToHead(Node node) {

node.next = head.next;

node.pre = head;

head.next.pre = node;

head.next = node;

}

public void printValueFromCache(int key) {

if(map.containsKey(key)) {

Node node = map.get(key);

System.out.println("The value is "+ node.value);

deleteNode(node);

addNodeToHead(node);

}

else {

System.out.println("Invalid Key or Key does not exists");

}

}

public void setValueToCache(int key, int value) {

if(map.containsKey(key)) {

Node node = map.get(key);

deleteNode(node);

addNodeToHead(node);

}

else {

Node node = new Node(key, value);

map.put(key, node);

if(count < this.CAPACITY) {

count++;

addNodeToHead(node);

}

else {

Node nodeRemove = map.get(tail.pre.key);

map.remove(tail.pre.key);

deleteNode(nodeRemove);

addNodeToHead(node);

}

}

}

}

public class LRUCache{

public static void main(String args[]) {

LRUImpl lru = new LRUImpl(3);

lru.setValueToCache(1, 1);

lru.setValueToCache(2, 2);

lru.setValueToCache(3, 3);

lru.printValueFromCache(1);

lru.printValueFromCache(3);

lru.setValueToCache(4, 4);

lru.printValueFromCache(2); // does not exists

}

}

LeetCode Java Solution:- Search Insert Position

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Example 1:

Input: [1,3,5,6], 5
Output: 2

Example 2:

Input: [1,3,5,6], 2
Output: 1

Example 3:

Input: [1,3,5,6], 7
Output: 4

Example 1:

Input: [1,3,5,6], 0
Output: 0

Solution:-

class Solution {
    public int searchInsert(int[] nums, int target) {
   
    int start = 0;
    int end = nums.length - 1;
    int mid = 0 ;
    while(start <= end){
    mid = (start + end)  / 2 ;
   
    if(nums[mid] == target){
    return mid;
    }
    else if(nums[mid] < target){
    start = mid + 1;
    }
    else{
    end = mid - 1;
    }
    }
   
    return start;
       
    }
}

LeetCode Java Solution:- Convert Sorted Array to Binary Search Tree

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        
        if(nums.length == 0){
            return null;
        }

        return getTreeNode(nums, 0, nums.length -1);
    
        
    }
    
    private TreeNode getTreeNode( int[] nums, int a , int b){
        
        int start = a;
        int end = b ;
        
        if(start > end){
            return null;
        }
        
        int mid = (start +end) / 2 ;
       TreeNode node = new TreeNode(nums[mid]);
        node.left = getTreeNode(nums, start , mid -1);
        
        node.right = getTreeNode(nums, mid+1 , end);
        
        return node;
            
        
        
      
    }

}

LeetCode Java Solution : Convert Sorted List to Binary Search Tree

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.


/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        List<Integer> arr = convertListToArray(head);
        
        return getBInaryTree(arr, 0 , arr.size() -1);
    }
    
    
    
    private List<Integer> convertListToArray(ListNode head){
        List<Integer> arr = new ArrayList<Integer>();
        while(head != null){
            arr.add(head.val);
            head = head.next;
        }
        return arr;
    }
    
    
    private TreeNode getBInaryTree(List<Integer> arr, int start, int end){
        
        if(start > end){
            return null;
        }
        int mid = (start + end) / 2;
            
        TreeNode node = new TreeNode(arr.get(mid));
        node.left = getBInaryTree(arr, start, mid - 1);
        node.right = getBInaryTree(arr, mid + 1 , end);
        
        return node;
        
    }

}

LeetCode - Java Solution Merge Sorted Array

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Note:
You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2. The number of elements initialized in nums1 and nums2 are m and n respectively.

Solution:-

class Solution {

    public void merge(int[] nums1, int m, int[] nums2, int n) {

        

        int [] ret = new int[m+n];

        int k = 0 , i = 0 , j = 0;

        while( i < m && j < n){

            if(nums1[i] <= nums2[j]){

                ret[k] = nums1[i];

                i++;

            }

            else{

                ret[k] = nums2[j];

                j++;

            }

            k++; 

        }

        if( i == m && j < n){    

            for(int item = j ; item < n ; item++ ){

             ret[k] = nums2[item];

            System.out.println(ret[k] + " "+ nums2[item]);

                k++;   

            }

        }

        

        if( j == n && i < m){

            for(int item = i ; item < m ; item++ ){

                

                ret[k] = nums1[item];

                k++;

            }

        }

        

        for(int l = 0 ; l < ret.length ; l++){

            nums1[l] = ret[l];

        }

    

    }

}

241. Different Ways to Add Parentheses -- Leet Code- Java -Solution

Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are +, - and *.

Example 1

Input: "2-1-1".

((2-1)-1) = 0
(2-(1-1)) = 2

Output: [0, 2]

Example 2

Input: "2*3-4*5"

(2*(3-(4*5))) = -34
((2*3)-(4*5)) = -14
((2*(3-4))*5) = -10
(2*((3-4)*5)) = -10
(((2*3)-4)*5) = 10

Output:

Solution:

import java.util.ArrayList;

import java.util.List;

public class Solution {

    public List<Integer> diffWaysToCompute(String input) {

   

    List<Integer> res = new ArrayList<Integer>();

        

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

        char c = input.charAt(i);

            if(input.charAt(i) == '-' || input.charAt(i) == '+' || input.charAt(i) == '*' ){

                List<Integer> lis1 = diffWaysToCompute(input.substring(0,i));

                List<Integer> lis2 = diffWaysToCompute(input.substring(i + 1));

                

                for(int item1:lis1 ){

                for(int item2:lis2){

                if(c == '-'){

                res.add(item1 - item2);

                }

                else if(c == '+'){

                res.add(item1 + item2);

                }

                else{

                res.add(item1 * item2);

                }

                }

                }

            }

        }

        if(res.size() == 0) {

        res.add(Integer.valueOf(input));

        }

        

        return res;

        

    }

}