14 martie 2024

50 DSA-Questions: #30, #31, #32

import java.util.LinkedList;
import java.util.Queue;

public class TreeElem {
private Integer data;
private TreeElem leftChild;
private TreeElem rightChild;

public TreeElem(Integer data) {
this.data = data;
}

public Integer getData() {
return data;
}

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

public TreeElem getLeftChild() {
return leftChild;
}

public void setLeftChild(TreeElem leftChild) {
this.leftChild = leftChild;
}

public TreeElem getRightChild() {
return rightChild;
}

public void setRightChild(TreeElem rightChild) {
this.rightChild = rightChild;
}

private static TreeElem buildFrom(TreeElem treeElem, int k, Integer[] elements) {
if (treeElem.getData() == null) {
return treeElem;
}
if (elements.length > 2 * k + 1) {
TreeElem left = new TreeElem(elements[2 * k + 1]);
TreeElem right = new TreeElem(elements[2 * k + 2]);
treeElem.setLeftChild(buildFrom(left, 2 * k + 1, elements));
treeElem.setRightChild(buildFrom(right, 2 * k + 2, elements));
}
return treeElem;
}

public static TreeElem buildFrom(Integer[] elements) {
if (elements.length == 0) {
return null;
}
TreeElem root = new TreeElem(elements[0]);
return buildFrom(root, 0, elements);
}

public static void printTreeBF(TreeElem root) {
if (root != null) {
Queue<TreeElem> queue = new LinkedList<>();
queue.add(root);

while (!queue.isEmpty()) {
TreeElem treeElem = queue.poll();
System.out.print(treeElem.getData() + ", ");
if (treeElem.getLeftChild() != null) {
queue.add(treeElem.getLeftChild());
}
if (treeElem.getRightChild() != null) {
queue.add(treeElem.getRightChild());
}
}
}
System.out.println();
}

public static void printTreeDF(TreeElem root) {
if (root != null) {
System.out.print(root.getData() + ", ");
if (root.getLeftChild() != null) {
printTreeDF(root.getLeftChild());
}
if (root.getRightChild() != null) {
printTreeDF(root.getRightChild());
}
}
}
}

#30. Maximum Depth of Binary Tree

Given the root of a binary tree, return its maximum depth. A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

public class Exercise30 {
private static final Integer[] ELEMENTS = {3,9,20,null,null,15,7}; // 3
// private static final Integer[] ELEMENTS = {1,7,9,2,6,null,9,null, null, 5, 11, null, null, 5, null}; // 4
// private static final Integer[] ELEMENTS = {1}; // 1
// private static final Integer[] ELEMENTS = {}; // 0

private int findMaxHeight(TreeElem elem, int k) {
if (elem == null) {
return k-1;
}
if (elem.getData() == null) {
return k;
}

int leftMaxLevel = findMaxHeight(elem.getLeftChild(), k+1);
int rightMaxLevel = findMaxHeight(elem.getRightChild(), k+1);

return Math.max(leftMaxLevel, rightMaxLevel);
}

public static void main(String args[]) {
TreeElem root = TreeElem.buildFrom(ELEMENTS);
System.out.println("Max tree level = " + new Exercise30().findMaxHeight(root, 1));
}
}

#31. Same Tree

Given the roots of two binary trees p and q, write a function to check if they are the same or not. Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.

public class Exercise31 {
private static final Integer[] LIST_1 = {3,9,20,null,null,15,7};
// private static final Integer[] LIST_1 = {};
private static final Integer[] LIST_2 = {3,9,20,null,null,15,7};
// private static final Integer[] LIST_2 = {3,9,20,null,null,15,8};
// private static final Integer[] LIST_2 = {3};
// private static final Integer[] LIST_2 = {};

private boolean areIdentical(TreeElem root1, TreeElem root2) {
if (root1 == null || root2 == null) {
return root1 == root2;
}
if (root1.getData() != null && root2.getData() != null && root1.getData().equals(root2.getData())) {
return areIdentical(root1.getLeftChild(), root2.getLeftChild()) &&
areIdentical(root1.getRightChild(), root2.getRightChild());
}
return root1.getData() == null && root2.getData() == null;
}

public static void main(String[] args) {
TreeElem root1 = TreeElem.buildFrom(LIST_1);
TreeElem root2 = TreeElem.buildFrom(LIST_2);
System.out.println("Identical trees = " + new Exercise31().areIdentical(root1, root2));
}
}

#32. Invert Binary Tree

Given the root of a binary tree, invert the tree, and return its root.

public class Exercise32 {
// private static final Integer[] ROOT = {4,2,7,1,3,6,9}; // 4, 7, 2, 9, 6, 3, 1,
private static final Integer[] ROOT = {4,8,9}; // 4,9,8

private TreeElem solve(TreeElem root) {
if (root == null) {
return null;
}

TreeElem leftAux = root.getLeftChild();
root.setLeftChild(root.getRightChild());
root.setRightChild(leftAux);

solve(root.getLeftChild());
solve(root.getRightChild());

return root;
}

public static void main(String[] args) {
TreeElem root = TreeElem.buildFrom(ROOT);
TreeElem inverted = new Exercise32().solve(root);
TreeElem.printTreeBF(inverted);
}
}

24 februarie 2024

50 DSA-Questions: #26, #27, #28, #29

public class Node {
private Integer data;
private Node next;

public Node() {
// empty
}

public Node(Integer data) {
this.data = data;
this.next = null;
}

public Node(Integer data, Node next) {
this.data = data;
this.next = next;
}

public Integer getData() {
return data;
}

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

public Node getNext() {
return next;
}

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

public static void printList(Node head) {
Node node = head;
while (node != null) {
System.out.print(node.getData() + " ");
node = node.getNext();
}
System.out.println();
}

public static Node buildFrom(int[] elements) {
if (elements.length == 0) {
return null;
}
Node head = new Node(elements[0]);
Node node = head;
for (int i=1; i<elements.length; i++) {
Node newNode = new Node(elements[i]);
node.setNext(newNode);
node = newNode;
}
return head;
}
}

#26. Merge Two Sorted Lists

You are given the heads of two sorted linked lists list1 and list2. Merge the two lists in a one-sorted list. The list should be made by splicing together the nodes of the first two lists. Return the head of the merged linked list.

#27. Merge k Sorted Lists

You are given an array of k linked-lists lists, each linked list is sorted in ascending order. Merge all the linked lists into one sorted linked list and return it.

public class Exercise26 {
private static final int[] FIRST_LIST = {0,1,2,5,8};
private static final int[] SECOND_LIST = {1,3,7,8};

private Node mergeTwo(Node p1, Node p2) {
Node result = new Node();
Node pRes = result;
while (p1 != null && p2 != null) {
if (p1.getData() < p2.getData()) {
pRes = addToResult(pRes, p1.getData());
p1 = p1.getNext();
} else {
pRes = addToResult(pRes, p2.getData());
p2 = p2.getNext();
}
}
while (p1 != null) {
pRes = addToResult(pRes, p1.getData());
p1 = p1.getNext();
}
while (p2 != null) {
pRes = addToResult(pRes, p2.getData());
p2 = p2.getNext();
}
return result;
}

private static final int[][] LIST_OF_LISTS = {{1,4,7}, {2,5,8}, {0, 5, 6}};

private Node mergeK() {
Node p1 = Node.buildFrom(LIST_OF_LISTS[0]);
Node p2;
for (int i = 0; i < LIST_OF_LISTS.length - 1; i++) {
p2 = Node.buildFrom(LIST_OF_LISTS[i+1]);
p1 = mergeTwo(p1, p2);
}
return p1;
}

private Node addToResult(Node pRes, int data) {
if (pRes.getData() == null) {
pRes.setData(data);
return pRes;
}
Node node = new Node(data);
pRes.setNext(node);
return node;
}

public static void main(String args[]) {
Node p1 = Node.buildFrom(FIRST_LIST);
Node p2 = Node.buildFrom(SECOND_LIST);

Node result = new Exercise26().mergeTwo(p1, p2);
System.out.println("Merged 2 lists:");
Node.printList(result);

System.out.println();

result = new Exercise26().mergeK();
System.out.printf("Merged k=%d lists:%n", LIST_OF_LISTS[0].length);
Node.printList(result);
}
}

#28. Remove Nth Node From End of List

Given the head of a linked list, remove the nth node from the end of the list and return its head.

public class Exercise28 {
private static final int[] elements = {1, 2, 3, 4, 5};
private static final int N = 1;

private Node removeNthNodeFromTheEnd(Node head, int n) {
if (n <= 0) {
System.out.println("N is too small!");
return head;
}

Node p1 = head, p2 = head;
for (int i=0; i<n; i++) {
if (p2 != null) {
p2 = p2.getNext();
} else {
System.out.println("N is too large!");
return head;
}
}

if (p2 == null) {
head = p1.getNext();
p1.setNext(null);
return head;
}

while (p2 != null && p2.getNext() != null) {
p1 = p1.getNext();
p2 = p2.getNext();
}

Node deleted = p1.getNext();
p1.setNext(p1.getNext().getNext());
deleted.setNext(null);
return head;
}

public static void main(String args[]) {
Node head = Node.buildFrom(elements);
Node result = new Exercise28().removeNthNodeFromTheEnd(head, N);
Node.printList(result);
}
}

#29. Reorder List

You are given the head of a singly linked list. The list can be represented as:

L0 → L1 → … → Ln - 1 → Ln

Reorder the list to be on the following form:

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

You may not modify the values in the list's nodes. Only nodes themselves may be changed.

public class Exercise29 {
private static final int[] LIST = {1,2,3,4,5}; // -> reordered {1,5,2,4,3}
// private static final int[] LIST = {1,2,3,4,5,6}; // -> reordered {1,6,2,5,3,4}
// private static final int[] LIST = {1,2,3}; // -> reordered {1,3,2}
// private static final int[] LIST = {1,2}; // -> reordered {1,2}
// private static final int[] LIST = {1}; // -> reordered {1}
// private static final int[] LIST = {}; // -> reordered {}

private void swap(Node currentLeft, Node beforeCurrentRight) {
Node next = currentLeft.getNext();
currentLeft.setNext(beforeCurrentRight.getNext());
currentLeft.getNext().setNext(next);
beforeCurrentRight.setNext(null);
}

private void reorderList(Node head) { // no value swap; only full node swap
if (head == null) {
return;
}

Node p1 = head, p2 = head;

Stack<Node> stack = new Stack<>();
while (p2.getNext() != null) {
stack.push(p2);
p2 = p2.getNext();
}

int halfSize = stack.size() / 2;
if (stack.size() % 2 == 1) {
halfSize++;
}
while (stack.size() > halfSize) {
p2 = stack.pop();
if (p1 == p2) {
break;
}
swap(p1, p2);

if (p1.getNext() == null || p1.getNext().getNext() == null) {
break;
}
p1 = p1.getNext().getNext();
}
}

public static void main(String args[]) {
Node head = Node.buildFrom(LIST);
new Exercise29().reorderList(head);
Node.printList(head);
}
}

20 februarie 2024

50 DSA-Questions: #23, #24, #25

#23. Encode and Decode Strings

Design an algorithm to encode a list of strings to a string. The encoded string is then sent over the network and decoded back to the original list of strings.

public class Exercise23 {
private static final String[] INPUT = {"Gina89", "loves_", "Pluto"};
private static final String FIRST_SEP = "::";
private static final String WORD_SEP = "#";
private static final String INSIDE_SEP = "=";

private String encode() {
// format NR_CUVINTE::NR_CHAR=STR#NR_CHAR=STR#.....
StringBuilder code = new StringBuilder(INPUT.length + FIRST_SEP);
for (String word : INPUT) {
code.append(word.length()).append(INSIDE_SEP).append(word).append(WORD_SEP);
}
return code.toString();
}

private String[] decode(String coded) {
int numberOfWords = Integer.parseInt(coded.substring(0, coded.indexOf(FIRST_SEP)));
String result[] = new String[numberOfWords];
String splitCode[] = coded.substring(coded.indexOf(FIRST_SEP) + FIRST_SEP.length()).split(WORD_SEP);

int i = 0;
for (String code : splitCode) {
result[i++] = code.substring(code.indexOf(INSIDE_SEP)+1);
}

return result;
}

private void solve() {
String coded = encode();
System.out.println(coded);

String[] result = decode(coded);
for (String res : result) {
System.out.print(res + " ");
}
System.out.println();
}

public static void main(String args[]) {
new Exercise23().solve();
}
}

#24. Reverse Linked Lists

Given the head of a singly linked list, reverse the list, and return the reversed list.

public class Exercise24 {
private static final int[] elements = {1,2,3,4,5,6};

private void reverse(Node head) {
Node.printList(head);
Stack<Integer> stack = new Stack<>();
while (head!= null) {
stack.push(head.getData());
head = head.getNext();
}

Node result = stack.empty() ? new Node() : new Node(stack.pop());
Node node = result;
while (!stack.empty()) {
Node newNode = new Node(stack.pop());
node.setNext(newNode);
node = newNode;
}

Node.printList(result);
// O(n) spatial (stiva + rezultat)
}

private void reverseinPlace(Node head) {
Stack<Node> stack = new Stack<>();
Node p1 = head, p2 = head;

while (p2 != null && p2.getNext() != null) {
stack.push(p1);
p1 = p1.getNext(); // pas 1
p2 = p2.getNext().getNext(); // pas 2, ajunge la mijloc
}

boolean odd = p2 != null && p2.getNext() == null;
if (odd) {
p1 = p1.getNext();
}

while (p1 != null) {
swapData(p1, stack.pop());
p1 = p1.getNext();
}

Node.printList(head);
// in place
}

private void swapData(Node pluto, Node jupiter) {
Integer data = pluto.getData();
pluto.setData(jupiter.getData());
jupiter.setData(data);
}

public static void main(String args[]) {
Node head = Node.buildFrom(elements);

new Exercise24().reverse(head);

new Exercise24().reverseinPlace(head);
}
}

#25. Linked List Cycle

Given the head, the head of a linked list, determine if the linked list has a cycle in it. There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Return true if there is a cycle in the linked list. Otherwise, return false.

public class Exercise25 {
private static final int[] elements = {1,2,3,4,5,6,7,8};

private void solve(Node head) {
Node p1 = head, p2 = head;
while (p1.getNext() != null && p2.getNext() != null && p2.getNext().getNext() != null) {
p1 = p1.getNext(); // 1 step
if (p1 == null) {
System.out.println("Linear");
return;
}

p2 = p2.getNext();
if (p2 == null) {
System.out.println("Linear");
return;
} else {
p2 = p2.getNext(); // 2 steps
}

if (p1 == p2) {
System.out.println("Has a cycle!");
return;
}
}
System.out.println("Linear");
}

public static void main(String args []) {
new Exercise25().solve(buildLinearList());
new Exercise25().solve(buildFirstCircularList());
new Exercise25().solve(buildSecondCircularList());
new Exercise25().solve(buildThirdCircularList());
}

private static Node buildLinearList() {
return Node.buildFrom(elements);
}

private static Node buildFirstCircularList() {
Node node = Node.buildFrom(elements);
node.getNext().getNext().getNext().setNext(node.getNext()); // 4 -> 2
return node;
}

private static Node buildSecondCircularList() {
Node node = Node.buildFrom(elements);
node.getNext().getNext().getNext().getNext().setNext(node.getNext().getNext().getNext()); // 5 -> 4
return node;
}

private static Node buildThirdCircularList() {
Node node = Node.buildFrom(elements);
node.getNext().getNext().getNext().getNext().setNext(node); // 5 -> 1
return node;
}
}

14 februarie 2024

Cel mai lung subsir comun

public class LargestCommonSubsequence {
//private static final String S1 = "ABCBDAB";
private static final String S1 = "GEORGIANAVULPE";
// private static final String S1 = "BDABC";

// private static final String S2 = "BDCABA"; // BCAB
private static final String S2 = "GINALARESTAURANT"; // GINALE
// private static final String S2 = "BAFB"; // BAB

private long numberOfCalls = 0;

private String findCommonRec(int i, int j, String accumulator) {
if (numberOfCalls < Long.MAX_VALUE) {
numberOfCalls++;
} else {
System.out.println("numberOfCalls exceeded max!");
}

if (i >= S1.length() || j >= S2.length()) {
return accumulator;
}

if (S1.charAt(i) == S2.charAt(j)) {
return findCommonRec(i+1, j+1, accumulator + S1.charAt(i));
}

String common1 = findCommonRec(i+1, j, accumulator);
String common2 = findCommonRec(i, j+1, accumulator);
String common3 = findCommonRec(i+1, j+1, accumulator);

String longest = common1;
if (longest.length() < common2.length()) {
longest = common2;
}
if (longest.length() < common3.length()) {
longest = common3;
}
return longest;
// O(2^n) if n == m
}

private void findCommonOptimized() {
// no recursive calls, use table
int table [][] = new int[S1.length()+1][S2.length()+1];
for (int i=0; i<S1.length(); i++) {
for (int j=0; j<S2.length(); j++) {
if (S1.charAt(i) == S2.charAt(j)) {
table[i+1][j+1] = table[i][j] + 1;
} else {
table[i+1][j+1] = Math.max(table[i+1][j], table[i][j+1]);
}
}
}

printTable(table);
// table[S1.length()][S2.length()] = lungime rezultat final

int i = S1.length();
int j = S2.length();
StringBuilder result = new StringBuilder();

// reconstituire substring: parcurgere dreapta jos -> stanga sus
while (i > 0 && j > 0) {
// merge adiacent cat timp se pastreaza valoarea curenta
if (table[i][j] == table[i-1][j]) {
i--;
} else if (table[i][j] == table[i][j-1]) {
j--;
} else {
// cand stanga si deasupra au valori diferite de cea curenta
// atunci trece diagonal si adauga caracterul la rezultat
assert S1.charAt(i-1) == S2.charAt(j-1);
result.append(S2.charAt(j - 1));
i--;
j--;
}
}

System.out.println("\nresult = " + result.reverse());
// O(n^2) if n == m
}

private void printTable(int table [][]) {
System.out.print(" ");
for (int i=0; i<S2.length(); i++) {
System.out.print(S2.charAt(i) + " ");
}
System.out.println();
for (int i=0; i<=S1.length(); i++) {
System.out.print(i < S1.length() ? S1.charAt(i) + " " : " ");
for (int j=0; j<=S2.length(); j++) {
System.out.print(table[i][j] + " ");
}
System.out.println();
}
}

private void solve() {
numberOfCalls = 0;
System.out.println(findCommonRec(0, 0, ""));
System.out.println("numberOfCalls = " + numberOfCalls + "\n");

findCommonOptimized();
}

public static void main(String args[]) {
new LargestCommonSubsequence().solve();
}
}