Rotate matrix +/- 90 with and without extra space

package exercises;

public class SquareMatrix {

private int[][] matrix;

private int size;

private int row;

private int column;

public SquareMatrix(int size) {

this.size = size;

this.matrix = new int[size][size];

}

public SquareMatrix row(int row) {

this.row = row;

return this;

}

public SquareMatrix column(int column) {

this.column = column;

return this;

}

public void add(int item) {

this.matrix[this.row - 1][this.column - 1] = item;

}

public void rotatePlus90_easy() {

int[][] rotated = new int[size][size];

for(int i = 0; i < size; i++) {

for(int j = 0; j < size; j++) {

rotated[i][j] = matrix[size - j - 1][i];

}

}

this.matrix = rotated;

}

public void rotateMinus90_easy() {

int[][] rotated = new int[size][size];

for(int i = 0; i < size; i++) {

for(int j = 0; j < size; j++) {

rotated[i][j] = matrix[j][size - i - 1];

}

}

this.matrix = rotated;

}

/**

* Imagine matrix as nested squares. Outer square contains a inner, which in turn contains another and so on. 

* Do below three steps for each square, start from Outer

* first rotate corners(clockwise)

* then rotate 2nd element in the square

* then rotate 3rd element and goes on.

* i = number of squares(3*3 is 1, 4*4 is 2, 5*5 is 2, 6*6 is 3). For odd size, inner most square is only one element. so it never moves

* j = for a square, move all elements. so it number of elements to be moved on a side

* First index should deal with 'j', if moving rows, else 'i' if moving columns.

* for ex(run and see 5*5 matrix), Top Right Corner 05 to 25 is rows, so use j. But 25 to 21 about columns, so use i.

*/

public void rotate90() {

for(int i = 0; i < size / 2; i++) {

for(int j = i; j < size - i - 1; j++) {

int temp = this.matrix[i][j];

this.matrix[i][j] = this.matrix[size - j - 1][i];

this.matrix[size - j - 1][i] = this.matrix[size - i - 1][size - j - 1];

this.matrix[size - i - 1][size - j - 1] = this.matrix[j][size - i - 1];

this.matrix[j][size - i - 1] = temp;

}

}

}

/**

* Trick is after initializing temp,

* Interchange first statement assignee with last's assigned

* Modify second and third assignment alone accordingly

*/

public void rotateminus90() {

for(int i = 0; i < size / 2; i++) {

for(int j = i; j < size - i - 1; j++) {

int temp = this.matrix[i][j];

this.matrix[i][j] = this.matrix[j][size - i - 1];

this.matrix[j][size - i - 1] = this.matrix[size - i - 1][size - j - 1];

this.matrix[size - i - 1][size - j - 1] = this.matrix[size - j - 1][i];

this.matrix[size - j - 1][i] = temp;

}

}

}

public void printAll() {

for(int i = 0; i < size; i++) {

for(int j = 0; j < size; j++) {

System.out.print(String.format("%02d ", matrix[i][j])); 

}

System.out.print("\n");

}

System.out.println("***************");

}

}

public static void demoMatrix() {

SquareMatrix matrix = new SquareMatrix(5);

matrix.row(1).column(1).add(1);

matrix.column(2).add(2);

matrix.column(3).add(3);

matrix.column(4).add(4);

matrix.column(5).add(5);

matrix.row(2).column(1).add(6);

matrix.column(2).add(7);

matrix.column(3).add(8);

matrix.column(4).add(9);

matrix.column(5).add(10);

matrix.row(3).column(1).add(11);

matrix.column(2).add(12);

matrix.column(3).add(13);

matrix.column(4).add(14);

matrix.column(5).add(15);

matrix.row(4).column(1).add(16);

matrix.column(2).add(17);

matrix.column(3).add(18);

matrix.column(4).add(19);

matrix.column(5).add(20);

matrix.row(5).column(1).add(21);

matrix.column(2).add(22);

matrix.column(3).add(23);

matrix.column(4).add(24);

matrix.column(5).add(25);

matrix.printAll();

matrix.rotatePlus90_easy();

matrix.printAll();

matrix.rotateMinus90_easy();

matrix.printAll();

matrix.rotate90();

matrix.printAll();

matrix.rotateminus90();

matrix.printAll();

}

Reverse stack using pop/push

package exercises;

import java.util.ArrayList;

import java.util.Stack;

import java.util.function.Consumer;

public class MyStack {

private Stack ints = new Stack<>();

public void add(int item) {

ints.push(item);

}

public void printall() {

ArrayList array = new ArrayList<>(ints);

array.forEach(new Consumer() {

@Override

public void accept(Integer t) {

System.out.print(t + "-->");

}

});

System.out.print("\n");

}

public void reverse_easy() {

Stack other = new Stack<>();

while(!ints.isEmpty()) {

other.push(ints.pop());

}

ints = other;

}

/**

* reverse relies on double recursion

* Outer Recursion : Pop all items

* Inner Recursion : Adds item at the bottom.

*/

public void reverse() {

this.reverse(this.ints);

}

private void reverse(Stack stack) {

Integer item = stack.pop();

if(!stack.isEmpty()) reverse(stack);

this.insertAtBottom(stack, item);

}

private void insertAtBottom(Stack stack, Integer item) {

if(stack.isEmpty()) {

stack.push(item);

} else {

Integer top = stack.pop();

insertAtBottom(stack, item);

stack.push(top);

}

}

}

Reverse Double Linked List, Promote Node based on add/get(similar to LinkedHashMap)

public static void demoMyLinkedHashMap() {

SimpleLinkedList map = new SimpleLinkedList<>();

map.add(1);

map.add(2);

map.add(3);

map.add(4);

map.printAll();

map.print(1);

map.print(4);

map.print(9);

map.add(5);

map.printAll();

map.print(5);

map.insert(0, 1);

map.printAll();

map.print(5);

map.insert(0, 1);

map.insert(6, 6);

map.printAll();

map.print_last();

map.reverse();

map.printAll();

map.print_last();

map.reverse();

map.printAll();

map.print_last();

map.add(7);

map.printAll();

map.print_last();

}

package exercises;

public class SimpleLinkedList {
private class Node {
private T data = null;
private Node prev = null;
private Node next = null;

public Node(T data) {
this.setData(data);
this.setPrev(null);
this.setNext(null);
}

public T getData() {
return data;
}

public void setData(T data) {
this.data = data;
}

public Node getPrev() {
return prev;
}

public void setPrev(Node prev) {
this.prev = prev;
}

public Node getNext() {
return next;
}

public void setNext(Node next) {
this.next = next;
}
}

private Node root;
private Node current;

public void add(T data) {
if(this.root == null) {
this.root = new Node(data);
this.current = this.root;

return;
} else {
Node node = new Node(data);

node.setPrev(current);
current.setNext(node);
current = node;
}
}

/**
* ignore, will not promote node
* @param data
* @param position
*/
public void insert(T data, int position) {
Node pointer = this.getNode(position, false);

if(pointer == null || pointer.getData().equals(data)) {
System.out.println("Same data, Ignore");
return;
}

Node newNode = new Node(data);
newNode.setNext(pointer);
newNode.setPrev(pointer.getPrev());
pointer.setPrev(newNode);

if(newNode.getPrev() != null) {
newNode.getPrev().setNext(newNode);
} else {
root = newNode;
}
}

public T get(int position) {
Node pointer = this.getNode(position, true);

return (pointer == null) ? null : pointer.getData();
}

public void printAll() {
if(this.root == null) return;

for(Node pointer = root; pointer != null; pointer = pointer.getNext()) {
System.out.print(pointer.getData().toString());

if(pointer.getNext() != null) System.out.print("->");
else System.out.print("\n");
}
}

public void print(int position) {
if(this.root == null) return;

T pointer = this.get(position);
if(pointer == null) return;

System.out.println("Item at position : " + position + " is " + pointer.toString());
}

public void print_last() {
System.out.println("Last item is : " + current.getData().toString());
}

/**
* reverse relies on single recursion. method returns processed node
* Recursively traverse to end to make it 'root'. return r'oot'
* current next is its prev. its prev is returned processed node. return current
*/
public void reverse() {
if(this.root == this.current) return;

current = this.reverse(root);
}

private Node reverse(Node current) {
if(current.getNext() == null) {
root = current;
root.setNext(root.getPrev()); //Root next, should be its previous.
root.setPrev(null); //Root node previous should be null

return current;
}

Node prev = reverse(current.getNext()); //prev, last visited node

current.setNext(current.getPrev()); //curent.next should be its prev node
current.setPrev(prev); //current.prev should be last visited node

return current;
}

private void promote(Node accessed) {
if(accessed == null || accessed == current) return;

if(accessed.getPrev() != null) {
accessed.getPrev().setNext(accessed.getNext()); //previous node should point accessed's next
accessed.getNext().setPrev(accessed.getPrev());
} else {
root = accessed.getNext(); // accessed.prev is null only if its root node, so new root is accessed's next
root.setPrev(null); //root prev is always null;
}

current.setNext(accessed);
accessed.setPrev(current);
accessed.setNext(null);
current = accessed;
}

/**
* 1. Return NULL, If the root is null or position is invalid
* 2. While index < position && pointer != null
* move to pointer.next
* increment index
* @param position
* @param promote - to promote the node to front
* @return
*/
private Node getNode(int position, boolean promote) {
if(position <= 0) return null;

int index = 1;
Node pointer = root;

while(index < position && pointer != null) {
pointer = pointer.getNext();
index++;
}

if(promote && pointer != null) promote(pointer);

return pointer;
}
}