BoomBleBee: mai 2024

09 mai 2024

50 DSA-Questions: Median from data stream & variation sliding window

#40. Find Median from Data Stream

The median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value, and the median is the mean of the two middle values. Implement the MedianFinder class.

// solutie cu sortare prin inserare, O(n^2)
class MedianFinder2 {
    int[] values;

    public MedianFinder2() {
        values = null;
    }
    
    public void addNum(int num) {
        insertAt(findIndex(num), num);
    }
    
    public double findMedian() {
        int len = values.length;
        if (len % 2 == 1) {
            return Double.valueOf(values[len / 2]);
        }
        return (values[len/2-1] + values[len/2]) / 2.0;
    }

    private int findIndex(int value) {
        if (values == null) {
            return 0;
        }
        return findIndex(value, 0, values.length - 1);
    }

    private int findIndex(int value, int from, int to) {
        if (from == to) {
            return value >= values[from] ? from + 1 : from;
        }
        int mid = from + (to - from) / 2;
        if (value <= values[mid]) {
            return findIndex(value, from, mid);
        }
        return findIndex(value, mid+1, to);
    }

    private void insertAt(int index, int value) {
        if (values == null) {
            values = new int[1];
            values[index] = value;
        } else {
            int [] copy = new int[values.length + 1];
            System.arraycopy(values, 0, copy, 0, index);
            System.arraycopy(values, index, copy, index+1, values.length - index);
            copy[index] = value;
            values = copy;
        }
    }
}

// solutie in O(n log n) folosind un max heap si un min heap
class MedianFinder {
    Queue<Integer> qMin; // elem mai mici decat mediana, ordonate DESC
    Queue<Integer> qMax; // elem mai mari decat mediana, ordonate ASC

    public MedianFinder() {
        qMin = new PriorityQueue<>(Collections.reverseOrder());
        qMax = new PriorityQueue<>();
    }

    public void addNum(int num) {
        if (qMin.isEmpty() && qMax.isEmpty()) {
            qMin.add(num);
        } else if (qMax.isEmpty()) {
            int firstNum = qMin.poll();
            qMin.add(Math.min(firstNum, num));
            qMax.add(Math.max(firstNum, num));
        } else {
            if (num > qMin.peek()) {
                qMax.add(num);
            } else {
                qMin.add(num);
            }
            while (qMin.size() - qMax.size() > 1) {
                qMax.add(qMin.poll());
            }
            while (qMax.size() - qMin.size() > 1) {
                qMin.add(qMax.poll());
            }
        }
    }

    public double findMedian() {
        if (qMin.size() == qMax.size()) {
            return (qMin.peek() + qMax.peek()) / 2.0;
        }
        if (qMin.size() > qMax.size()) {
            return qMin.peek();
        }
        return qMax.peek();
    }
}

Variatie: Sliding Window Median

You are given an integer array nums and an integer k. There is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Return the median array for each window in the original array.

// Time Limit Exceeded pt N=100k si k=50k !
class Solution {
    Queue<Integer> qMin;
    Queue<Integer> qMax;

    private void initQueues() {
        qMin = new PriorityQueue<>(Collections.reverseOrder());
        qMax = new PriorityQueue<>();
    }

    private void addNum(int num) {
        if (qMin.isEmpty() && qMax.isEmpty()) {
            qMin.add(num);
        } else if (qMax.isEmpty()) {
            int firstNum = qMin.poll();
            qMin.add(Math.min(firstNum, num));
            qMax.add(Math.max(firstNum, num));
        } else {
            if (!qMin.isEmpty() && num > qMin.peek()) {
                qMax.add(num);
            } else {
                qMin.add(num);
            }
            rebalance();
        }
    }

    private void removeNum(int num) { // O(N) to remove an element from priority queue!
        if (qMin.contains(num)) {
            qMin.remove(num);
        } else if (qMax.contains(num)) {
            qMax.remove(num);
        }
        rebalance();
    }

    private void rebalance() {
        while (qMin.size() - qMax.size() > 1) {
            qMax.add(qMin.poll());
        }
        while (qMax.size() - qMin.size() > 1) {
            qMin.add(qMax.poll());
        }
    }

    private double findMedian() {
        if (qMin.size() == qMax.size()) {
            return (Long.valueOf(qMin.peek()) + Long.valueOf(qMax.peek())) / 2.0;
        }
        if (qMin.size() > qMax.size()) {
            return qMin.peek();
        }
        return qMax.peek();
    }

    public double[] medianSlidingWindow(int[] nums, int k) {
        Solution sol = new Solution();
        sol.initQueues();

        for (int i=0; i<k; i++) {
            sol.addNum(nums[i]);
        }

        double[] result = new double[nums.length - k + 1];
        result[0] = sol.findMedian();

        for (int i=1; i<nums.length - k + 1; i++) {
            sol.removeNum(nums[i-1]);
            sol.addNum(nums[k + i - 1]);
            result[i] = sol.findMedian();
        }
        return result;
    }
}

Alta solutie:

07 mai 2024

50 DSA-Questions: #38, #39

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

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        Queue<Integer> pq = new PriorityQueue<>();
        for (int k=0; k<lists.length; k++) {
            while (lists[k] != null) {
                pq.add(lists[k].val);
                lists[k] = lists[k].next;
            }
        }

        ListNode result = pq.isEmpty() ? null : new ListNode();
        ListNode node = result;
        while (!pq.isEmpty()) {
            node.val = pq.poll();
            node.next = pq.isEmpty() ? null : new ListNode();
            node = node.next;
        }

        return result;
    }
}

#39. Top K Frequent Elements

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

class Node {
    int num;
    int valOcc; // number of occurrences
    Node (int num, int valOcc) {
        this.num = num;
        this.valOcc = valOcc;
    }
}

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> occ = new HashMap<>();
        for (int num : nums) {
            if (!occ.containsKey(num)) {
                occ.put(num, 0);
            }
            occ.put(num, occ.get(num) + 1);
        }

        Set<Integer> keys = occ.keySet();
        Node[] nodes = new Node[keys.size()];
        int i = 0;
        for (Integer key : keys) {
            nodes[i++] = new Node(key, occ.get(key));
        }

        nodes = buildHeap(nodes);

        int [] result = new int[k];
        for (i=0; i<k; i++) {
            result[i] = nodes[0].num;
            nodes = heapify(removeMax(nodes), 0);
        }

        return result;
    }

    Node[] buildHeap(Node nodes[]) {
        // Index of last non-leaf node
        int start = ((nodes.length - 1) / 2) - 1;
 
        // Perform reverse level order traversal
        // from last non-leaf node and heapify
        // each node
        for (int i = start; i >= 0; i--) {
            nodes = heapify(nodes, i);
        }

        return nodes;
    }

    Node[] heapify(Node[] nodes, int i) {
        int indexMax = i; // current root
        int leftIndex = 2 * i + 1;
        int rightIndex = 2 * i + 2;

        if (leftIndex < nodes.length && nodes[leftIndex].valOcc > nodes[indexMax].valOcc) {
            indexMax = leftIndex;
        }
        if (rightIndex < nodes.length && nodes[rightIndex].valOcc > nodes[indexMax].valOcc) {
            indexMax = rightIndex;
        }

        if (indexMax != i) {
            Node aux = nodes[i]; // swap root with max
            nodes[i] = nodes[indexMax];
            nodes[indexMax] = aux;
            nodes = heapify(nodes, indexMax); // heapify the affected sub-tree
        }

        return nodes;
    }

    Node[] removeMax(Node[] nodes) {
        nodes[0] = nodes[nodes.length-1];
        Node [] copy = new Node[nodes.length - 1];
        System.arraycopy(nodes, 0, copy, 0, nodes.length - 1);
        return copy;
    }
}

02 mai 2024

50 DSA-Questions: #36, #37

Implement Trie (Prefix Tree)

A trie (pronounced as "try") or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.

class Node {
    Character value;
    Node[] children;
    boolean end;

    public Node(Character value) {
        this.value = value;
        this.children = new Node[26];
        this.end = false;
    }

    public Node getChild(char ch) {
        return children[ch - 'a'];
    }

    public Node addChild(Node child) {
        this.children[child.value - 'a'] = child;
        return child;
    }
}

class Trie {
    Node root;

    public Trie() {
        root = new Node(null);
    }
    
    public void insert(String word) {
        boolean end;
        if (word.length() > 0) {
            Node node = root;
            int i = 0;
            do {
                Character ch = Character.valueOf(word.charAt(i));
                end = i == word.length()-1;
                Node child = node.getChild(ch);
                if (child == null) {
                    child = node.addChild(new Node(ch));
                }
                child.end = end || child.end;
                node = child;
                i++;
            } while (!end);
        }
    }
    
    public boolean search(String word) {
        return search(word, false);
    }

    public boolean startsWith(String prefix) {
        return search(prefix, true);
    }

    private boolean search(String word, boolean prefix) {
        int i = 0;
        Node node = root;
        while (true) {
            Character ch = Character.valueOf(word.charAt(i));
            Node child = node.getChild(ch);
            if (child == null) {
                return false;
            }
            if (i == word.length() - 1) {
                return prefix ? true : child.end;
            }
            i++;
            node = child;
        }
    }
}

#36. Design Add and Search Words Data Structure

Design a data structure that supports adding new words and finding if a string matches any previously added string. The searched word may contain dots '.' where dots can be matched with any letter.

class Node {

    Character value;

    Node[] children;

    boolean end;

    public Node(Character value) {

        this.value = value;

        this.children = new Node[26];

        this.end = false;

}

    public Node getChild(char ch) {

        return children[ch - 'a'];

}

    public Node addChild(Node child) {

        this.children[child.value - 'a'] = child;

        return child;

}

}

class WordDictionary {

    Node root;

    public WordDictionary() {

        root = new Node(null);

}

    public void addWord(String word) { // la fel ca la Trie

        boolean end;

        if (word.length() > 0) {

            Node node = root;

            int i = 0;

            do {

                Character ch = Character.valueOf(word.charAt(i));

                end = i == word.length()-1;

                Node child = node.getChild(ch);

                if (child == null) {

                    child = node.addChild(new Node(ch));

}

                child.end = end || child.end;

                node = child;

                i++;

            } while (!end);

}

}

    public boolean search(String word) {

        return search(word, root, 0);

}

    private boolean search(String word, Node node, int i) {

        while (i < word.length()) {

            Character ch = Character.valueOf(word.charAt(i));

            boolean isLetter = ch != '.';

            if (isLetter) {

                Node child = node.getChild(ch);

                if (child == null) {

                    return false;

}

                if (i == word.length() - 1) {

                    return child.end;

}

                node = child;

                i++;

            } else { // in plus fata de Trie, match pe caracterul '.'

                for (int j=0; j<node.children.length; j++) {

                    Node child = node.children[j];

                    if (child != null) { // match condition

                        if (i == word.length() - 1 && child.end) {

                            return true;

}

                        boolean res = search(word, child, i+1);

                        if (res) {

                            return true;

}

}

}

                return false;

}

}

        return false;

}

}

#37. Word Search II

Given an m x n board of characters and a list of strings words, return all words on the board. Each word must be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.
class Node {
    Character value;
    Node[] children;
    boolean end;
    int kidsCount; // camp aditional
    Node parent; // camp aditional

    public Node(Character value) {
        this.value = value;
        this.children = new Node[26];
        this.end = false;
        this.kidsCount = 0;
        this.parent = null;
    }

    public Node getChild(char ch) {
        return children[ch - 'a'];
    }

    public Node addChild(Node child) {
        child.parent = this;
        this.children[child.value - 'a'] = child;
        this.kidsCount++;
        return child;
    }

    public void removeChild(char ch) {
        children[ch - 'a'] = null;
        this.kidsCount--;
    }

    public boolean hasChild() {
        return this.kidsCount > 0;
    }
}

enum SearchStatus {
    NOT_FOUND,
    PREFIX,
    FOUND
};

class Trie {
    Node root;

    public Trie() {
        root = new Node(null);
    }
    
    public void insert(String word) { // identic Trie
        boolean end;
        if (word.length() > 0) {
            Node node = root;
            int i = 0;
            do {
                Character ch = Character.valueOf(word.charAt(i));
                end = i == word.length()-1;
                Node child = node.getChild(ch);
                if (child == null) {
                    child = node.addChild(new Node(ch));
                }
                child.end = end || child.end;
                node = child;
                i++;
            } while (!end);
        }
    }

    public void remove(String word) { // metoda noua
        int i = 0;
        Node node = root;
        while (i < word.length()) {
            Character ch = Character.valueOf(word.charAt(i));
            Node child = node.getChild(ch);
            i++;
            node = child;
        }

        while (node != root) {
            if (node.hasChild()) {
                node.end = false;
                break;
            }
            node.parent.removeChild(node.value);
            node = node.parent;
        }
    }

    public SearchStatus search(String word) {
        int i = 0;
        Node node = root;
        while (true) {
            Character ch = Character.valueOf(word.charAt(i));
            Node child = node.getChild(ch);
            if (child == null) {
                return SearchStatus.NOT_FOUND;
            }
            if (i == word.length() - 1) {
                return child.end ? SearchStatus.FOUND : SearchStatus.PREFIX;
            }
            i++;
            node = child;
        }
    }
}

class Solution {
    public List<String> findWords(char[][] board, String[] words) {
        Trie trie = new Trie();
        for (String word : words) {
            trie.insert(word);
        }

        List<String> result = new ArrayList<>();
        for (int i=0; i<board.length; i++) {
            for (int j=0; j<board[i].length; j++) {
                check(i, j, board, "", trie, "", result);
            }
        }

        return result;
    }

    private void hunt(int i, int j, char[][] board, String word, Trie trie, String path, List<String> result) {
        // left
        check(i, j-1, board, word, trie, path, result);

        // right 
        check(i, j+1, board, word, trie, path, result);

        // up
        check(i-1, j, board, word, trie, path, result);

        // down
        check(i+1, j, board, word, trie, path, result);
    }

    private void check(int i, int j, char[][] board, String word, Trie trie, String path, List<String> result) {
        if (i < 0 || j < 0 || i >= board.length || j >= board[0].length) {
            return;
        }
        if (!isNewPos(i, j, path)) {
            return;
        }
        
        word = word + board[i][j];
        SearchStatus status = trie.search(word);
        switch (status) {
            case SearchStatus.FOUND:
                result.add(word);
                trie.remove(word); // optimizare: stergere cuvant dupa ce a fost adaugat la rezultat
            case SearchStatus.PREFIX:
                path = path + getPosKey(i,j);
                hunt(i, j, board, word, trie, path, result);
        }
    }

    private String getPosKey(int i, int j) {
        return i + "-" + j + "#";
    }

    private boolean isNewPos(int i, int j, String path) {
        int index = path.indexOf(getPosKey(i, j));
        if (index < 0) {
            return true;
        }
        if (index == 0) {
            return false;
        }
        char ch = path.charAt(index - 1);
        return ch != '#';
    }
}