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{…
class Trie {
class TrieNode{
Map<Character,TrieNode> children = new HashMap<>();
boolean isLeaf;
}
private TrieNode root;
/** Initialize your data structure here. */
public Trie() {
root= new TrieNode();
}
/** Inserts a word into the trie. */
public void insert(String word) {
TrieNode node = root;
for(char c : word.toCharArray()){
if(!node.children.containsKey(c)){

node.children.put(c,new TrieNode());
}
node = node.children.get(c);
}
node.isLeaf= true;
}
/** Returns if the word is in the trie. */
public boolean search(String word) {
TrieNode p = root;
for(char c : word.toCharArray()) {
if(!p.children.containsKey(c)) {
return false;
}
p = p.children.get(c);
}
return p.isLeaf;
}

/** Returns if there is any word in the trie that starts with the given prefix. */
public boolean startsWith(String prefix) {
TrieNode p = root;
for(char c : prefix.toCharArray()) {
if(!p.children.containsKey(c)) {
return false;
}
p = p.children.get(c);
}
return true;
}
}

class DSU{
//path compression and union by rank
int[] parent;
int[] rank;
int components;
public DSU(int components){
this.components=components;
parent = new int[components];
for(int i =0 ; i<components;i++){
parent[i]=i;//initially node is the parent of itself
}
rank = new int[components]; //initial rank=0

}

public int find(int node){
if(parent[node]!=node) {
parent[node]=find(parent[node]);
}
return parent[node];
}

public boolean union(int x, int y){
int px = find(x);
int py = find(y);
if(px==py) return false;
else{
else if (rank[px]<rank[py]) parent[px]=py;
else if(rank[px]>rank[py]) parent[py]=px;
else {
parent[py]=px;
rank[px]++;
}
componenets--;
}
return true;
}
}

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…

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…

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…

Abhinay Gupta

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store