Demo Sistemul de abateri

 Aplicația DRPCIV la care am lucrat 2023 - 2024 - "Faults management" (Abateri).

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

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

#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.

class Solution {
    public int maxDepth(TreeNode root) {
        return findMaxHeight(root, 1);
    }
    private int findMaxHeight(TreeNode node, int k) {
        if (node == null) {
            return k-1;
        }
        int leftMaxLevel = findMaxHeight(node.left, k+1);
        int rightMaxLevel = findMaxHeight(node.right, k+1);
        return Math.max(leftMaxLevel, rightMaxLevel);
    }
}

#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.

class Solution {
    public boolean isSameTree(TreeNode root1, TreeNode root2) {
        if (root1 == null || root2 == null) {
            return root1 == root2;
        }
        if (root1.val == root2.val) {
            return isSameTree(root1.left, root2.left) && isSameTree(root1.right, root2.right);
        }
        return false;
    }
}

#32. Invert Binary Tree

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

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        TreeNode leftAux = root.left;
        root.left = root.right;
        root.right = leftAux;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }
}

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

#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.

/**

* Definition for singly-linked list.

* public class ListNode {

* int val;

* ListNode next;

* ListNode() {}

* ListNode(int val) { this.val = val; }

* ListNode(int val, ListNode next) { this.val = val; this.next = next; }

* }

*/

class Solution {

public ListNode mergeTwoLists(ListNode p1, ListNode p2) {

if (p1 == null && p2 == null) {

return null;

}

ListNode result = new ListNode(); // first node is artificial

ListNode pRes = result;

while (p1 != null && p2 != null) {

if (p1.val < p2.val) {

pRes = append(pRes, p1.val);

p1 = p1.next;

} else {

pRes = append(pRes, p2.val);

p2 = p2.next;

}

}

while (p1 != null) {

pRes = append(pRes, p1.val);

p1 = p1.next;

}

while (p2 != null) {

pRes = append(pRes, p2.val);

p2 = p2.next;

}

return result.next;

}

private ListNode append(ListNode pRes, int data) {

ListNode node = new ListNode(data);

pRes.next = node;

return node;

}

}

#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 ListNode mergeKLists_2_by_2(ListNode[] lists) {

if (lists.length == 0) {

return null;

}

List<ListNode> partials = Arrays.asList(lists); // listele partiale, initial toate din lists

List<ListNode> res = new ArrayList<>(); // rezultatul combinarii 2 cate 2

int index = 0; // pornim cu index = 0, len-1

while (true) {

ListNode firstList = partials.get(index);

boolean hasSecondList = index + 1 < partials.size();

ListNode secondList = hasSecondList ? partials.get(index+1) : null;

res.add(mergeTwoLists(firstList, secondList));

index += hasSecondList ? 2 : 1; // incrementare index

if (index >= partials.size()) { // daca s-au procesat toate listele partiale

if (res.size() == 1) { // si avem o singura lista rezultata

return res.get(0); // s-a terminat procesarea

}

partials = res; // re-proceseaza rezultatele partiale

res = new ArrayList<>(); // reseteaza lista rezultata

index = 0; // ia-o de la capat

}

}

}

public ListNode mergeKLists_using_mergeTwoLists(ListNode[] lists) {

if (lists.length == 0) {

return null;

}

ListNode result = lists[0]; // idee: adauga la prima lista a doua, a treia, etc

for (int i = 1; i < lists.length; i++) {

result = mergeTwoLists(result, lists[i]);

}

return 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.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (n <= 0) {
            return head; // n too small
        }
        ListNode p1 = head, p2 = head; 
        for (int i=0; i<n; i++) { // p2 will get at distance n from p1
            if (p2 != null) {
                p2 = p2.next;
            } else {
                return head; // n too large
            }
        }
        if (p2 == null) { 
            // n-th node from the end is head
            head = p1.next;
            p1.next = null;
            return head;
        }
        // p1 and p2 go one step at a time until p2 gets to the last position
        while (p2 != null && p2.next != null) { 
            p1 = p1.next;
            p2 = p2.next;
        }
        // remove p1.next
        // if p2 was null, then we would have deleted p1 (but then no access to its previous node)
        ListNode deleted = p1.next;
        p1.next = p1.next.next;
        deleted.next = null;
        return head;
    }
}

#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.

class Solution {
    private void swap(ListNode currentLeft, ListNode beforeCurrentRight) {
        ListNode next = currentLeft.next;
        currentLeft.next = beforeCurrentRight.next;
        currentLeft.next.next = next;
        beforeCurrentRight.next = null;
    }
    public void reorderList(ListNode head) { // no value swap; only full node swap
        if (head == null) {
            return;
        }
        ListNode p1 = head, p2 = head;
        Stack<ListNode> stack = new Stack<>();
        while (p2.next != null) {
            stack.push(p2);
            p2 = p2.next;
        }
        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.next == null || p1.next.next == null) {
                break;
            }
            p1 = p1.next.next;
        }
    }
}

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.

class Solution {
    public ListNode reverseList_newList(ListNode head) {
        if (head == null) {
            return null;
        }

        Stack<Integer> stack = new Stack<>();
        while (head != null) {
            stack.push(head.val);
            head = head.next;
        }

        ListNode result = stack.empty() ? new ListNode() : new ListNode(stack.pop());
        ListNode node = result;
        while (!stack.empty()) {
            ListNode newNode = new ListNode(stack.pop());
            node.next = newNode;
            node = newNode;
        }
        
        return result;
        // O(n) spatial (stiva + rezultat)
    }

    public ListNode reverseList_inPlace(ListNode head) {
        Stack<ListNode> stack = new Stack<>();
        ListNode p1 = head, p2 = head;

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

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

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

        return head;
    }

    private void swapData(ListNode pluto, ListNode jupiter) {
        Integer data = pluto.val;
        pluto.val = jupiter.val;
        jupiter.val = data;
    }

    class Wrapper {
        ListNode head;
        Wrapper(ListNode head) {
            this.head = head;
        }
    }

    public ListNode reverseList_rec(ListNode head) {
        if (head == null) {
            return null;
        }

        ListNode aux = head;
        int size = 1;
        while (aux.next != null) {
            size++;
            aux = aux.next;
        }

        Wrapper wrap = new Wrapper(head);
        recurse(head, wrap, 0, size);
        return head;
    }

    private void recurse(ListNode node, Wrapper p1, int index, int size) {
        if (node.next != null) {
            recurse(node.next, p1, index + 1, size);
        }
        if (index < size/2) {
            swapData(node, p1.head);
        }
        p1.head = p1.head.next;
    }
}

#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.

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null) {
            return false;
        }
        ListNode p1 = head, p2 = head;
        while (p1.next != null &&  p2.next != null && p2.next.next != null) {
            p1 = p1.next; // p1 goes 1 step forward
            if (p1 == null) {
                return false;
            }
            p2 = p2.next;
            if (p2 == null) {
                return false;
            } else {
                p2 = p2.next; // p2 goes 2 steps forward
            }
            if (p1 == p2) {
                return true;
            }
        }
        return false;
    }
}

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();
    }
}