package linklist.hashmap;
class Entry<K, V> {
private K key;
private V value;
private Entry<K, V> next;
public Entry(K key, V value, Entry<K, V> next){
this.key = key;
this.value = value;
this.next = next;
}
public K getKey() {
return key;
}
public void setKey(K key) {
this.key = key;
}
public V getValue() {
return value;
}
public void setValue(V value) {
this.value = value;
}
public Entry getNext() {
return next;
}
public void setNext(Entry<K, V> next) {
this.next = next;
}
}
class CustomHashMap<K, V> {
private int capacity = 16; //Initial default capacity
private Entry<K, V>[] table; //Array of Entry object
public CustomHashMap(){
table = new Entry[capacity];
}
public CustomHashMap(int capacity){
this.capacity = capacity;
table = new Entry[capacity];
}
public void put(K key, V value){
int index = index(key);
Entry newEntry = new Entry(key, value, null);
if(table[index] == null){
table[index] = newEntry;
}else {
Entry<K, V> previousNode = null;
Entry<K, V> currentNode = table[index];
while(currentNode != null){
if(currentNode.getKey().equals(key)){
currentNode.setValue(value);
break;
}
previousNode = currentNode;
currentNode = currentNode.getNext();
}
if(previousNode != null)
previousNode.setNext(newEntry);
}
}
public V get(K key){
V value = null;
int index = index(key);
Entry<K, V> entry = table[index];
while (entry != null){
if(entry.getKey().equals(key)) {
value = entry.getValue();
break;
}
entry = entry.getNext();
}
return value;
}
public void remove(K key){
int index = index(key);
Entry previous = null;
Entry entry = table[index];
while (entry != null){
if(entry.getKey().equals(key)){
if(previous == null){
entry = entry.getNext();
table[index] = entry;
return;
}else {
previous.setNext(entry.getNext());
return;
}
}
previous = entry;
entry = entry.getNext();
}
}
public void display(){
for(int i = 0; i < capacity; i++){
if(table[i] != null){
Entry<K, V> currentNode = table[i];
while (currentNode != null){
System.out.println(String.format("Key is %s and value is %s", currentNode.getKey(), currentNode.getValue()));
currentNode = currentNode.getNext();
}
}
}
}
private int index(K key){
if(key == null){
return 0;
}
return Math.abs(key.hashCode() % capacity);
}
}
public class HashMapRunner {
public static void main(String[] args) {
CustomHashMap<Integer, String> map = new CustomHashMap<Integer, String>();
System.out.println("Going to add entries in map");
map.put(null, "Nothing");
map.put(1, "ETC");
map.put(2, "John");
System.out.println("Displaying all the entry in map");
map.display();
System.out.println("Removing the entry with key 2");
map.remove(2);
map.display();
System.out.println("Adding duplicate key 1 in map");
map.put(1, "CSE");
map.put(2, "John again");
System.out.println("Displaying all the entry in map again");
map.display();
System.out.println("Adding entry with key 17 in map");
map.put(17, "CS");
map.display();
}
}
TechInsiderStory
TechInsiderStory is place where you can find basic knowledge of various technology and framework. TechInsiderStory is provide free knowledge on various technology and framework.
Create Own HashMap
Sub-Matrix With All 1s
public class SubMatrix {
static void getMaxSubSquare(int M[][])
{
int i, j;
int R = M.length; // no of rows in M[][]
int C = M[0].length; // no of columns in M[][]
int S[][] = new int[R][C];
int maxS, maxI, maxJ;
/* Set first column of S[][]*/
for (i = 0; i < R; i++)
S[i][0] = M[i][0];
/* Set first row of S[][]*/
for (j = 0; j < C; j++)
S[0][j] = M[0][j];
/* Construct other entries of S[][]*/
for (i = 1; i < R; i++) {
for (j = 1; j < C; j++) {
if (M[i][j] == 1)
S[i][j] = Math.min(
S[i][j - 1],
Math.min(S[i - 1][j],
S[i - 1][j - 1]))
+ 1;
else
S[i][j] = 0;
}
}
/* Find the maximum entry, and indexes of maximum
entry in S[][] */
maxS = S[0][0];
maxI = 0;
maxJ = 0;
for (i = 0; i < R; i++) {
for (j = 0; j < C; j++) {
if (maxS < S[i][j]) {
maxS = S[i][j];
maxI = i;
maxJ = j;
}
}
}
System.out.println("Maximum size sub-matrix is: ");
for (i = maxI; i > maxI - maxS; i--) {
for (j = maxJ; j > maxJ - maxS; j--) {
System.out.print(M[i][j] + " ");
}
System.out.println();
}
}
// Driver program
public static void main(String[] args)
{
int M[][]
= { { 0, 1, 1, 0, 1 }, { 1, 1, 0, 1, 0 },
{ 0, 1, 1, 1, 0 }, { 1, 1, 1, 1, 0 },
{ 1, 1, 1, 1, 1 }, { 0, 0, 0, 0, 0 } };
getMaxSubSquare(M);
}
//Time Complexity: O(m*n)
// where m is the number of rows and n is the number of columns in the given matrix.
//Auxiliary Space: O(m*n)
// where m is the number of rows and n is the number of columns in the given matrix.
}
Link-List-Palindrome
public class LinkListPalindrome {
Node head; // head of list
Node slp, ftp, secHalf;
/* Linked list Node*/
class Node {
char data;
Node next;
Node(char d)
{
data = d;
next = null;
}
}
/* Function to check if given linked list is
palindrome or not */
boolean isPalindrome(Node head)
{
slp = head;
ftp = head;
Node prev_of_slow_ptr = head;
Node midnode = null; // To handle odd size list
boolean res = true; // initialize result
if (head != null && head.next != null) {
/* Get the middle of the list. Move slow_ptr by
1 and fast_ptr by 2, slow_ptr will have the
middle node */
while (ftp != null
&& ftp.next != null) {
ftp = ftp.next.next;
/*We need previous of the slow_ptr for
linked lists with odd elements */
prev_of_slow_ptr = slp;
slp = slp.next;
}
/* fast_ptr would become NULL when there are
even elements in the list and not NULL for
odd elements. We need to skip the middle node
for odd case and store it somewhere so that
we can restore the original list */
if (ftp != null) {
midnode = slp;
slp = slp.next;
}
// Now reverse the second half and compare it
// with first half
secHalf = slp;
prev_of_slow_ptr.next
= null; // NULL terminate first half
reverse(); // Reverse the second half
res = compareLists(head,
secHalf); // compare
/* Construct the original list back */
reverse(); // Reverse the second half again
if (midnode != null) {
// If there was a mid node (odd size case)
// which was not part of either first half
// or second half.
prev_of_slow_ptr.next = midnode;
midnode.next = secHalf;
}
else
prev_of_slow_ptr.next = secHalf;
}
return res;
}
/* Function to reverse the linked list Note that this
function may change the head */
void reverse()
{
Node prev = null;
Node current = secHalf;
Node next;
while (current != null) {
next = current.next;
current.next = prev;
prev = current;
current = next;
}
secHalf = prev;
}
/* Function to check if two input lists have same data*/
boolean compareLists(Node head1, Node head2)
{
Node temp1 = head1;
Node temp2 = head2;
while (temp1 != null && temp2 != null) {
if (temp1.data == temp2.data) {
temp1 = temp1.next;
temp2 = temp2.next;
}
else
return false;
}
/* Both are empty return 1*/
if (temp1 == null && temp2 == null)
return true;
/* Will reach here when one is NULL
and other is not */
return false;
}
/* Push a node to linked list. Note that this function
changes the head */
public void push(char new_data)
{
/* Allocate the Node &
Put in the data */
Node new_node = new Node(new_data);
/* link the old list of the new one */
new_node.next = head;
/* Move the head to point to new Node */
head = new_node;
}
// A utility function to print a given linked list
void printList(Node ptr)
{
while (ptr != null) {
System.out.print(ptr.data + "->");
ptr = ptr.next;
}
System.out.println("NULL");
}
/* Driver program to test the above functions */
public static void main(String[] args)
{
/* Start with the empty list */
LinkListPalindrome llist = new LinkListPalindrome();
char str[] = { 'a', 'b', 'a', 'c', 'a', 'b', 'a' };
String string = new String(str);
for (int i = 0; i < 7; i++) {
llist.push(str[i]);
}
if (llist.isPalindrome(llist.head) != false) {
System.out.println("Is Palindrome");
System.out.println("");
}
else {
System.out.println("Not Palindrome");
System.out.println("");
}
}
}
Tree-Traverse-Order-Level-Frame
import java.util.*;
// structure of the node of the binary tree
class Node{
int data;
Node left;
Node right;
public Node(int data)
{
this.data=data;
}
}
public class TraversTreeAndFrame {
static ArrayList<Object[]> traversal;
// function to traverse the binary
// tree in the level order fashion
public static void levelOrderTraversal(Node root)
{
// current node is marked as the root node
Node curr=root;
int level=0;
// loop to traverse the binary tree until the current node
// is not null
while(curr!=null)
{
// if left child is null, print the
// current node data and update the
// current pointer to right child.
if(curr.left==null)
{
// return the current node with
// its level
traversal.add(new Object[]{curr,new Integer(level)});
curr=curr.right;
if(curr!=null)
{
level++;
}else
level--;
}
else{
// find the inorder predecessor
Node prev=curr.left;
int toUp=0;
// loop to find the right most
// node of the left child of the current node
while(prev.right!=null && prev.right!=curr)
{
prev=prev.right;
toUp++;
}
// If the right child of inorder
// predecessor already points to
// the current node, update the
// current with it's right child
if(prev.right==curr)
{
prev.right=null;
curr=curr.right;
level-=toUp+1;
}
// else If right child doesn't
// point to the current node,
// then print this node's data
// and update the right child
// pointer with the current node
// and update the current with
// it's left child
else{
traversal.add(new Object[]{curr,new Integer(level)});
prev.right=curr;
curr=curr.left;
level++;
}
}
}
}
public static void main(String[] args)
{
// create a binary tree
Node root=new Node(5);
root.left=new Node(2);
root.right=new Node(3);
root.left.right=new Node(6);
root.right.left=new Node(7);
root.right.right=new Node(8);
traversal=new ArrayList<>();
// traverse the tree in level order traversal
levelOrderTraversal(root);
// find the height of the tree
int h=0;
for(Object[] i:traversal)
{
h=Math.max(h,(int)i[1]+1);
}
// print the date of nodes at each level
for(int i = 0; i<h; i++){
for(Object[] j : traversal){
if((int)j[1] == i){
System.out.print(((Node)j[0]).data+" ");
}
}
System.out.println();
}
}
//Time Complexity: As in the above approach, every node is
// touched at max twice due to which the time complexity is O(N),
// where N is the number of nodes.
//Auxiliary Space: As in the above approach,
// there is no extra space used due to which auxiliary space used will be O(1)
}
Tree-Traverse-Order-Level-Queue
import java.util.LinkedList;
import java.util.Queue;
class Node {
int data;
Node left, right;
public Node(int item)
{
data = item;
left = null;
right = null;
}
}
class LevelOrderQueue {
Node root;
void printLevelOrder()
{
Queue<Node> queue = new LinkedList<Node>();
queue.add(root);
while (!queue.isEmpty()) {
Node tempNode = queue.poll();
System.out.print(tempNode.data + " ");
if (tempNode.left != null) {
queue.add(tempNode.left);
}
if (tempNode.right != null) {
queue.add(tempNode.right);
}
}
}
public static void main(String args[])
{
LevelOrderQueue tree_level = new LevelOrderQueue();
tree_level.root = new Node(1);
tree_level.root.left = new Node(2);
tree_level.root.right = new Node(3);
tree_level.root.left.left = new Node(4);
tree_level.root.left.right = new Node(5);
tree_level.printLevelOrder();
}
//Firstly we insert the root into the queue and iterate over
//the queue until the queue is empty.
//In every iteration, we will pop from the top of
// the queue and print the value at the top of the queue.
//Then, add its left and right nodes to the end of the queue
// Time Complexity: O(N) where n is the number of nodes in the binary tree.
//Space Complexity: O(N) where n is the number of nodes in the binary tree.
}
Subscribe to:
Comments (Atom)