Jul 14, 2021

LRU Cache Implementation

class LRUCache { private Map<Integer, Node> map; final Node head = new Node(); final Node tail = new Node(); private int capacity; public LRUCache(int capacity) { this.map = new HashMap<>(capacity); this.capacity = capacity…

Lru

1 min read

Jul 13, 2021

Implement HashMap in Java

to implement following functions in HashMap: put(), get(), remove(), size(),keySet(),containsKey() We will be using Arrays of LinkedList . Each linked List will represent a bucket. After hashing of keys, the key will be added to its corresponding bucket. Our Node will look like this . private class HMNode{…

Hashmap

3 min read

Jul 11, 2021

Implementing Tries

class Trie { class TrieNode{ Map<Character,TrieNode> children = new HashMap<>(); boolean isLeaf; } private TrieNode root; /** Initialize your data structure here. */…

Trie

1 min read

Implementing Tries

class Trie {
    class TrieNode{
        Map<Character,TrieNode> children = new HashMap<>();
        boolean isLeaf;
    }
    private TrieNode root;
    /** Initialize your data structure here. */…

Jul 8, 2021

Union Disjoint -Rank and Path Compression

class DSU{ //path compression and union by rank int[] parent; int[] rank; int components; public DSU(int components){ this.components=components; parent = new…

Union Disjoint

1 min read

Union Disjoint -Rank and Path Compression

class DSU{
    //path compression and union by rank
    int[] parent;
    int[] rank;
    int components;
    public DSU(int components){
        this.components=components;
        parent = new…

Jul 8, 2021

Construct Binary Tree from Inorder and Postorder/Preorder Traversal

From INORDER and POSTORDER Given two integer arrays inorder and postorder where inorder is the inorder traversal of a binary tree and postorder is the postorder traversal of the same tree, construct and return the binary tree. Algorithm: In Postorder, the rightmost element is the root. Search this root in inorder array .Let that…

Binary Tree Traversal

2 min read

Jul 8, 2021

Inorder Predecessor and Successor in BST

There is BST given with root node with key part as integer only. You need to find the inorder successor and predecessor of a given key. In case, if the either of predecessor or successor is not found return null. Algorithm: For Predecesor: One left and Extreme right.(If node has…

Binary Search Tree

2 min read

Jul 8, 2021

Insertion, Search and Deletion in BST

Insertion: You are given the root node of a binary search tree (BST) and a value to insert into the tree. Return the root node of the BST after the insertion. It is guaranteed that the new value does not exist in the original BST. Notice that there may exist multiple…

Binary Search Tree

2 min read

Jul 7, 2021

Target Sum

Given an array of non-negative integers and a target sum S. Assign+ or — to every element such that their sum becomes S.. Input: nums is [1, 1, 1, 1, 1], S is 3. Output: 5 Explanation: -1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3…

4 min read

Jul 7, 2021

Largest String after k deletions

Given a string of length n, return the largest string based on dictionary order, that can be obtained by erasing k characters from that string. For two strings, x and y, each consisting of n characters, x is larger than y, based on dictionary order, when the first i-1 letters…

Arrays

2 min read

Jul 7, 2021

Maximum Sum Contiguous subarray with unique elements.

Given a non-empty array of length n with non-negative elements. Write a program to find and return the maximum sum of a contiguous subarray of the given array such that no two elements are repeated in the subarray. Input: 1 2 3 3 4 5 2 1 Output: 15 Explanation: Subarray from index 3 to 7 constitutes the sum 15(3+4+5+2+1) Approach: We will use two pointers i and j. We will use HashSet…

Array

1 min read

LRU Cache Implementation

Implement HashMap in Java

Implementing Tries

Implementing Tries

Union Disjoint -Rank and Path Compression

Union Disjoint -Rank and Path Compression

Construct Binary Tree from Inorder and Postorder/Preorder Traversal

Inorder Predecessor and Successor in BST

Insertion, Search and Deletion in BST

Target Sum

Largest String after k deletions

Maximum Sum Contiguous subarray with unique elements.

Abhinay Gupta