BoomBleBee

16 august 2024

09 august 2024

Exemple Deadlock & Livelock

Deadlock

Cand doua sau mai multe fire de executie sunt blocate in asteptarea eliberarii unor resurse de care au nevoie. Solutie: how to prevent deadlock in Java.

private static void deadlock() {
    final String res1 = "Resource_1";
    final String res2 = "Resource_2";

    Thread t1 = new Thread(() -> {
        synchronized (res1) {
            System.out.println("[t1] acquired access to res1");
            try {
                Thread.sleep(5000);
            } catch (InterruptedException e) {
                throw new RuntimeException(e);
            }
            synchronized (res2) {
                System.out.println("[t1] Yay! escaped deadlock."); // not happening
            }
        }
    });
    Thread t2 = new Thread(() -> {
        synchronized (res2) {
            System.out.println("[t2] acquired access to res2");
            try {
                Thread.sleep(5000);
            } catch (InterruptedException e) {
                throw new RuntimeException(e);
            }
            synchronized (res1) {
                System.out.println("[t2] Yay! escaped deadlock.");
            }
        }
    });

    t1.start();
    t2.start();
}

Livelock

Doua sau mai multe fire de executie isi cedeaza dreptul de a rula in favoarea celorlalte astfel ajungand sa nu ruleze niciodata, iar aplicatia nu progreseaza. Solutie: schimbarea logicii.

static class Spoon {
    Diner owner;

    public Spoon (Diner firstOwner) {
        this.owner = firstOwner;
    }

    synchronized void setOwner(Diner owner) {
        this.owner = owner;
    }

    synchronized void use() {
        System.out.println(owner.name + " just ate!");
    }
}

static class Diner {
    String name;
    boolean isHungry;

    public Diner (String name) {
        this.name = name;
        this.isHungry = true;
    }

    public void eatWith (Spoon spoon, Diner spouse) {
        while (isHungry) {
            if (spoon.owner != this) {
                // wait for a while for the spoon to be released
                try {
                    Thread.sleep(3000);
                } catch (InterruptedException e) {
                    throw new RuntimeException(e);
                }
            }

            // after wait, try to give the spoon to the spouse if she's hungry
            if (spouse.isHungry) {
                System.out.println("[" + name + "] Eat, baby, eat!");
                spoon.owner = spouse;
            } else {
                // finally
                spoon.use();
                isHungry = false;
                System.out.println("[" + name + "] Finally ate!!!"); // never
                spoon.owner = spouse;
            }
        }
    }
}

private static void livelock() {
    final Diner husband = new Diner("Adnan");
    final Diner wife = new Diner("Hannan");
    Spoon spoon = new Spoon(wife);
    
    try {
        new Thread(() -> husband.eatWith(spoon, wife)).start();
        Thread.sleep(1500);
        new Thread(() -> wife.eatWith(spoon, husband)).start();
    } catch (InterruptedException e) {
        throw new RuntimeException(e);
    }
}

07 august 2024

Script bash pt build proiecte

./script.sh <nume branch>

branch="master"
if [ -n "$1" ]; then
    branch=$1
fi

printf "\ngit pull from "$branch"\n\n"

currentDate=`date +"%Y-%m-%d-%H%M"`
filename="$currentDate.log"
touch $filename

for dir in `ls .`;
do
    if [[ -d $dir ]]; then
        echo $'\n'$dir
        cd $dir
        mvn clean &>> ../$filename
        git checkout master
        git pull
        cd ..
        echo $'\n' &>> $filename
    fi
done


# legacy first
echo $'\n' >> $filename
for dir in `ls .`;
do
    if [[ -d $dir && "$dir" == *"legacy"* ]]; then
        echo $'\n'$dir
        cd $dir
        mvn install -DskipTests &>> ../$filename
        cd ..
        echo $'\n' &>> $filename
    fi
done

 
printf "\n"
for dir in `ls .`;
do
    if [[ -d $dir && "$dir" != *"legacy"* ]]; then
        echo $'\n'$dir
        cd $dir
        mvn install -DskipTests &>> ../$filename
        cd ..
        echo $'\n' &>> $filename
    fi
done

21 iulie 2024

Probleme grafuri & arbori (2)

#5. Aranjarea unor cursuri cu relatie de dependenta intre ele

Se da un numCourses si o lista de dependinte prereq[i] = [a, b], cu semnificatia: pentru a putea participa la cursul a, un student trebuie sa participe intai la cursul b. Sa se gaseasca o aranjare posibila a cursurilor, cu satisfacerea tuturor relatiilor de dependenta.

Nota: sortare topologica intr-un graf orientat. Se pun intr-o stiva si se elimina succesiv nodurile care nu au arce de iesire, impreuna cu arcele lor de intrare. Se repeta pana cand nu mai ramane niciun nod, apoi se scot nodurile din stiva; ele vor fi sortate topologic. Daca exista un ciclu in graf, nu exista sortare topologica - se va observa ca de la o iteratie la alta nu se mai sterg noduri.

class Solution {
    public int[] findOrder(int numCourses, int[][] prereq) {
        Map<Integer, Set<Integer>> outgoingEdges = new HashMap<>();
        for (int i=0; i<numCourses; i++) {
            outgoingEdges.put(i, new HashSet<>());
        }
        for (int[] edges : prereq) {
            int to = edges[0], from = edges[1];
            outgoingEdges.get(from).add(to);
        }

        int result[] = new int[numCourses];
        try {
            Stack<Integer> stack = topologicalSort(numCourses, outgoingEdges);
            int i = 0;
            while (!stack.isEmpty()) {
                result[i++] = stack.pop();
            }
        } catch (CircularException e) {
            return new int[0];
        }
        return result;
    }

    private Stack<Integer> topologicalSort(int numCourses, Map<Integer, Set<Integer>> outgoingEdges) {
        Stack<Integer> nodeStack = new Stack<>();
        int remainingNodes = outgoingEdges.size();
        
        while (!outgoingEdges.isEmpty()) {
            List<Integer> connectionsToDelete = new LinkedList<>();
            for (int i=0; i<numCourses; i++) {
                if (outgoingEdges.containsKey(i) && outgoingEdges.get(i).isEmpty()) {
                    nodeStack.push(i);
                    outgoingEdges.remove(i);
                    connectionsToDelete.add(i);
                }
            }
            outgoingEdges.forEach((k,v) -> v.removeAll(connectionsToDelete));
            connectionsToDelete.clear();
            
            // este un ciclu atunci cand dupa o parcurgere completa nu se mai scot noduri
            if (remainingNodes == outgoingEdges.size()) {
                throw new CircularException();
            }
            remainingNodes = outgoingEdges.size();
        }
        return nodeStack;
    }

    private class CircularException extends RuntimeException {
        public CircularException() {
            super();
        }
    }
}

Varianta mai eficienta: sortare topologica folosind DSF. Dupa obtinerea unei ordini topologice, trebuie sa se verifice ca graful nu contine cicluri.

class Solution {
    public int[] findOrder(int numCourses, int[][] prereq) {
        List<List<Integer>> adjList = getAdjList(numCourses, prereq);
        
        boolean visited[] = new boolean[numCourses]; // all false
        Stack<Integer> stack = new Stack<>();
        int result[] = new int[numCourses];

        for (int i=0; i<numCourses; i++) {
            if (!visited[i]) {
                dfs(i, adjList, stack, visited);
            }
        }
        int i = 0;
        while (!stack.isEmpty()) {
            result[i++] = stack.pop();
        }

        // check for any cycle
        for (int node = 0; node < numCourses; node++) {
            for (int conn : adjList.get(node)) { 
                // we have a vertex from node -> conn
                // if conn appears before node in the ordering => cycle
                if (indexOf(conn, result) < indexOf(node, result)) {
                    return new int[0]; // cycle
                }
            }
        }

        return result;
    }

    private void dfs(int node, List<List<Integer>> adjList, Stack<Integer> stack, boolean visited[]) {
        visited[node] = true;
        for (int neighbor : adjList.get(node)) {
            if (!visited[neighbor]) {
                dfs(neighbor, adjList, stack, visited);
            }
        }
        stack.push(node);
    }

    private List<List<Integer>> getAdjList(int numCourses, int[][] prereq) {
        List<List<Integer>> adjList = new ArrayList<>();
        for (int i=0; i<numCourses; i++) {
            adjList.add(new ArrayList<>());
        }
        for (int[] edges : prereq) {
            int to = edges[0], from = edges[1];
            adjList.get(from).add(to);
        }
        return adjList;
    }

    private int indexOf(int node, int[] order) {
        for (int i=0; i<order.length; i++) {
            if (order[i] == node) {
                return i;
            }
        }
        return -1;
    }    
}

#6. Primul stramos comun a doua noduri dintr-un arbore binar

Cand avem acces la parintii unui nod:

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (p == root || q == root) {
            return root;
        }

        int diffDepth = depth(root, p) - depth(root, q);
        while (diffDepth > 0) {
            p = p.parent; // bring p on the same level with q
            diffDepth--;
        }
        while (diffDepth < 0) {
            q = q.parent; // bring q on the same level with p
            diffDepth++;
        }

        while (p != q && p != null && q != null) {
            // go up together
            p = q.parent;
            p = q.parent;
        }

        return (p != null && q != null) ? p : null;
    }

    private int depth(TreeNode root, TreeNode node) {
        int depth = 0;
        while (node != root) {
            depth++;
            node = node.parent;
        }
        return depth;
    }
}

Cand nu avem acces la parintii unui nod:

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (p == root || q == root || root == null) {
            return root;
        }
        return search(root, p, q);
    }

    private TreeNode search(TreeNode node, TreeNode p, TreeNode q) {
        if (node == p || node == q) {
            return node;
        }
        boolean isPinLeft = isNodeInSubtree(node.left, p);
        boolean isQinLeft = isNodeInSubtree(node.left, q);
        if (isPinLeft != isQinLeft) { // if p and q are in different branches of node
            return node; // common ancestor
        } else {
            TreeNode nodeNext = isPinLeft ? node.left : node.right;
            return search(nodeNext, p, q);
        }
    }

    private boolean isNodeInSubtree(TreeNode subtree, TreeNode node) {
        if (subtree == null) {
            return false;
        }
        if (subtree.val == node.val) {
            return true;
        }
        return isNodeInSubtree(subtree.left, node) || isNodeInSubtree(subtree.right, node);
    }
    // issue: repetitive calls to isNodeInSubtree when it already found the node
}

Alternativa - fara acces la parinti, tinem minte calea pana la nod in format L/R

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (p == root || q == root || root == null) {
            return root;
        }
        
        search(root, p, "", q, "");
        TreeNode ancestor = root;
        int i = 0;
        while (finalPathP.length() > i && finalPathQ.length() > i && finalPathP.charAt(i) == finalPathQ.charAt(i)) {
            char c = finalPathP.charAt(i);
            ancestor = c == 'L' ? ancestor.left : ancestor.right;
            i++;
        }
        return ancestor;
    }

    String finalPathP = null;
    String finalPathQ = null;

    private void search(TreeNode node, TreeNode p, String pathP, TreeNode q, String pathQ) {
        if (node == null) {
            return;
        }
        if (node.val == p.val) {
            finalPathP = pathP;
        }
        if (node.val == q.val) {
            finalPathQ = pathQ;
        }
        if (finalPathP == null || finalPathQ == null) {
            search(node.left, p, pathP + "L", q, pathQ + "L");
            search(node.right, p, pathP + "R", q, pathQ + "R");
        }
    }
}

19 iulie 2024

Probleme grafuri & arbori (1)

#1. Aflare daca exista o cale intre doua noduri dintr-un graf

Graf neorientat cu n noduri pentru care se da o lista de muchii edges[i] = [n1, n2] care inseamna ca exista o legatura directa intre n1 si n2. Sa se afle daca din n1 se poate ajunge in n2.

Nota: BFS. Nu este necesar sa folosim Map, un simplu ArrayList e suficient.

class Solution {
    public boolean validPath(int n, int[][] edges, int source, int destination) {
        if (source == destination) {
            return true;
        }

        Map<Integer, Node> nodes = new HashMap<>();
        for (int i=0; i<n; i++) {
            nodes.put(i, new Node(i));
        }

        for (int i=0; i<edges.length; i++) {
            int from = edges[i][0], to = edges[i][1];
            nodes.get(from).addNeighbor(nodes.get(to));
            nodes.get(to).addNeighbor(nodes.get(from));
        }

        Node startNode = nodes.get(source);
        if (startNode.isLinkedTo(nodes.get(destination))) {
            return true;
        }
        startNode.setVisited();

        Queue<Node> queue = new LinkedList<>();
        queue.addAll(startNode.neighbors);
        
        while(!queue.isEmpty()) {
            Node next = queue.remove();
            if (!next.visited) {
                next.setVisited();
                if (next.isLinkedTo(nodes.get(destination))) {
                    return true;
                }
                queue.addAll(next.neighbors);
            }
        }

        return false;
    }

    private class Node {
        int value;
        List<Node> neighbors;
        boolean visited = false;

        public Node (int value) {
            this.value = value;
            this.neighbors = new ArrayList<>();
        }

        public void addNeighbor(Node node) {
            this.neighbors.add(node);
        }

        public boolean isLinkedTo(Node node) {
            return this.neighbors.contains(node);
        }

        public void setVisited() {
            this.visited = true;
        }
    }
}

#2. Transformarea unui array sortat intr-un BST (binary search tree)

Sirul este sortat crescator. In arborele creat, toti descendentii din stanga ai unui nod <= valoarea nodului, iar descendentii din dreapta > valoarea nodului. In plus, arborele trebuie sa fie aiba inaltimea minima posibila.

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return transform(nums, 0, nums.length - 1);
    }

    TreeNode transform(int[] nums, int indexFrom, int indexTo) {
        if (indexFrom == indexTo) {
            return new TreeNode(nums[indexFrom]);
        }
        
        if (indexFrom == indexTo - 1) {
            TreeNode root = new TreeNode(nums[indexTo]);
            root.left = new TreeNode(nums[indexFrom]);
            return root;
        }

        int size = indexTo - indexFrom + 1;
        TreeNode root = new TreeNode(nums[indexFrom + size/2]);
        root.left = transform(nums, indexFrom, indexFrom + size/2 - 1);
        root.right = transform(nums, indexFrom + size/2 + 1, indexTo);
        return root;
    }
}

#3. Arbore binar echilibrat

Dandu-se un arbore binar, sa se afle daca este echilibrat, adica pt fiecare nod diferenta intre inaltimile in jos ale fiecarui subarbore sa nu fie mai mare decat 1.

class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        try {
            findHeightUnderNode(root);
        } catch (UnbalancedTreeException e) {
            return false;
        }
        return true;
    }

    private int findHeightUnderNode(TreeNode node) throws UnbalancedTreeException {
        if (node.left == null && node.right == null) {
            return 1;
        }
        int heightUnderLeft = node.left == null ? 0 : findHeightUnderNode(node.left);
        int heightUnderRight = node.right == null ? 0 : findHeightUnderNode(node.right);
        if (Math.abs(heightUnderLeft - heightUnderRight) > 1) {
            throw new UnbalancedTreeException();
        }
        return 1 + Math.max(heightUnderLeft, heightUnderRight);
    }

    private class UnbalancedTreeException extends RuntimeException {
        public UnbalancedTreeException() {
            super();
        }
    }
}

#4. Validarea unui BST

Se da un arbore binar. Sa se verifice daca este un arbore binar de cautare (BST).

class Solution {
    public boolean isValidBST(TreeNode root) {
        try {
            checkValid(root, null, null);
        } catch(InvalidBSTException e) {
            return false;
        }
        return true;
    }

    private void checkValid(TreeNode node, Integer lessThan, Integer moreThan) {
        // lessThan, moreThan - constrangeri propagate de sus in jos
        if (node == null || (node.left == null && node.right == null)) {
            return;
        }
        
        if (node.left != null) {
            if (node.left.val >= node.val || (lessThan != null && node.left.val >= lessThan) || 
                    (moreThan != null && node.left.val <= moreThan)) {
                throw new InvalidBSTException();
            }
        }
        if (node.right != null) {
            if (node.right.val <= node.val || (lessThan != null && node.right.val >= lessThan) || 
                    (moreThan != null && node.right.val <= moreThan)) {
                throw new InvalidBSTException();
            }
        }

        checkValid(node.left, min(node.val, lessThan), moreThan);
        checkValid(node.right, lessThan, max(node.val, moreThan));
    }

    private int min(Integer x, Integer y) {
        if (x != null && y != null) {
            return Math.min(x,y);
        }
        return x != null ? x : y;
    }

    private int max(Integer x, Integer y) {
        if (x != null && y != null) {
            return Math.max(x,y);
        }
        return x != null ? x : y;
    }

    private class InvalidBSTException extends RuntimeException {
        public InvalidBSTException() {
            super();
        }
    }
}