Exemplu de lucru pe biți: privilegii in BD

Lista de privilegii = intrări într-un dicționar, cu valoarea = puteri ale lui 2.

1 Citire articole

2 Scriere articole

4 Aprobare membri noi

8 Dezactivare membri

16 Editare articole

Utilizatori/entități din BD: au asociată o mască = suma privilegiilor pe care le au.

1 user1 1 ...

2 user2 3 ...

3 user3 15 ...

4 user4 31 ...

User1: poate doar citi

User2: citire, scriere articole

User3: toate drepturile, mai puțin Editare articole

User4: toate drepturile

public static boolean isActionAllowed(int requiredPriv, int userMask) {
    return (requiredPriv & userMask) > 0;
}

50 DSA-Questions: String #15, #16

#15. Longest Substring Without Repeating Characters

Given a string s, find the length of the longest substring without repeating characters.

public class Exercise15 {
    private final String INPUT = "abcabcbb"; // abc
    // private final String INPUT = "abcadbcbb"; // bcad
    //private final String INPUT = "pwwkew"; // wke
    // private final String INPUT = "georgiana"; // eorgian
    // private final String INPUT = "georoi"; // geor
    // private final String INPUT = "gerryinyr"; // ryin

    private boolean containsChar(String content, char currentChar) {
        return content.chars().filter(ch -> ch == currentChar).findFirst().isPresent();
    }

    private String replaceCharAtTheEnd(String content, char stripped) {
        int index = content.indexOf(stripped);
        return content.concat(String.valueOf(stripped)).substring(index + 1);
    }

    private void solve() {
        assert(!INPUT.isEmpty());

        String currentStrike = String.valueOf(INPUT.charAt(0));
        String bestStrike = currentStrike;

        for (int i=1; i<INPUT.length(); i++) {
            final char currentChar = INPUT.charAt(i);
            if (!containsChar(currentStrike, currentChar)) {
                currentStrike = currentStrike.concat(String.valueOf(currentChar)); // continue current strike
            } else {
                if (currentStrike.length() > bestStrike.length()) {
                    bestStrike = currentStrike;
                }
                currentStrike = replaceCharAtTheEnd(currentStrike, currentChar); // reset strike
            }
        }

        System.out.println(currentStrike.length() > bestStrike.length() ? currentStrike : bestStrike);
    }


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

#16. Longest Repeating Character Replacement

You are given a string s and an integer k. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most k times. Return the length of the longest substring containing the same letter you can get after performing the above operations.

public class Exercise16 {
    // private final String INPUT = "ABAB"; // B->A , B->A => AaAa, size of the longest repeating consecutive char = 4
    // private final String INPUT = "ADFAAED"; // AaaAAEG, size = 5
    // private final String INPUT = "PGAPTARGKLGZ"; // PppPTARGKLGZ, size = 4
    // private final String INPUT = "GEO"; // Ggg, size = 3
    // private final String INPUT = "ABCDEFGHA"; // AaaDEFGHA, size = 3
    // private final int K = 2;

    private final String INPUT = "ANAAREMERELE"; // ANAAREeEeEeE, size = 7
    private final int K = 3;

    private Map<Character, Occurrence> occurrenceMap() {
        Map<Character, Occurrence> map = new HashMap<>();
        for (int i=0; i<INPUT.length(); i++) {
            char key = INPUT.charAt(i);
            if (map.containsKey(key)) {
                Occurrence occurrence = map.get(key);
                occurrence.addIndex(i);
            } else {
                map.put(key, new Occurrence(i));
            }
        }
        return map;
    }

    private List<Map.Entry<Character, Occurrence>> filterSortDesc(Map<Character, Occurrence> map) {
        return map.entrySet().stream()
                .filter(entry -> entry.getValue().getCount() > 1)
                .sorted((e1, e2) -> e2.getValue().findMaxConsec() - e1.getValue().findMaxConsec())
                .collect(Collectors.toList());
    }
    
    private int getDefaultProfit() {
        return (K < INPUT.length() ? K+1 : INPUT.length());
    }

    private void solve() {
        assert(!INPUT.isEmpty());

        List<Map.Entry<Character, Occurrence>> sortedEntries = filterSortDesc(occurrenceMap());
        if (sortedEntries.isEmpty()) {
            System.out.println("Max = " + getDefaultProfit());
            return;
        }

        System.out.println("Max = " + sortedEntries.get(0).getValue().getMaxConsec());
    }

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

    private class Occurrence {
        private List<Integer> indexes;
        private int maxConsec;

        public Occurrence(int index) {
            this.indexes = new ArrayList<>();
            this.addIndex(index);
        }

        public void addIndex(Integer index) {
            this.indexes.add(index);
        }

        public int getCount() {
            return indexes.size();
        }

        public int findMaxConsec() {
            int credit = K;
            int maxProfit = 0;
            for (int i=0; i<indexes.size()-1; i++, credit = K) {
                int profit = 0;
                if (credit >= indexes.get(i+1) - indexes.get(i) - 1) { // can afford a strike
                    credit -= indexes.get(i+1) - indexes.get(i) - 1; // extract from K
                    profit = indexes.get(i+1) - indexes.get(i) - 1 + 2; // no. elements comprised

                    // INPUT[indexes.get(i)] == INPUT[indexes.get(i+1)]

                    for (int j=indexes.get(i+1) + 1; j<INPUT.length(); j++) { // go right
                        if (INPUT.charAt(j) == INPUT.charAt(indexes.get(i))) { // free one
                            profit++;
                        }
                        else {
                            if (credit > 0) { // buy one
                                profit++;
                                credit--;
                            } else {
                                break;
                            }
                        }
                    }

                    for (int j=indexes.get(i) - 1; j>=0; j--) { // go left
                        if (INPUT.charAt(j) == INPUT.charAt(indexes.get(i))) { // free one
                            profit++;
                        } else {
                            if (credit > 0) { // buy one
                                profit++;
                                credit--;
                            } else {
                                break;
                            }
                        }
                    }
                }

                if (profit > maxProfit) {
                    maxProfit = profit;
                }
            }

            if (maxProfit == 0) {
                maxProfit = getDefaultProfit();
            }

            this.maxConsec = maxProfit;
            return maxProfit;
        }

        public int getMaxConsec() {
            return maxConsec;
        }
    }
}

50 DSA-Questions: #14 Word Search

#14. Word Search

Given an m x n grid of characters board and a string word, return true if the word exists in the grid. The word can 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.

class Solution {
    public boolean exist(char[][] board, String word) {
        for (int i=0; i<board.length; i++) {
            for (int j=0; j<board[0].length; j++) {
                boolean found = searchWordDFS(board, i, j, 0, word, "#");
                if (found) {
                    return true;
                }
            }
        }
        return false;
    }
    private boolean isCellFit(char[][] board, int i, int j, int wordPos, String word, String visited) {
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || wordPos >= word.length()) {
            return false; // out of grid
        }
        int index = i * board[0].length + j;
        if (visited.contains("#" + index + "#")) {
            return false; // already been there
        }
        
        return board[i][j] == word.charAt(wordPos);
    }
    private boolean searchWordDFS(char[][] board, int i, int j, int wordPos, String word, String visited) {
        // Este important de tinut visited ca String si nu ca List/alt obiect pentru a fi pasat prin valoare, 
        // nu prin referinta, astfel incat, la intoarcerea fara succes din recursivitate indecsii din matrice
        // vizitati sa fie abandonati
        if (isCellFit(board, i, j, wordPos, word, visited)) {
            visited += (i * board[0].length + j) + "#";
            if (wordPos == word.length() - 1) {
                return true;
            }
            
            boolean found = searchWordDFS(board, i, j + 1, wordPos + 1, word, visited); // right
            if (!found) {
                found = searchWordDFS(board, i, j - 1, wordPos + 1, word, visited); // left
            }
            if (!found) { 
                found = searchWordDFS(board, i + 1, j, wordPos + 1, word, visited); // down
            }
            if (!found) {
                found = searchWordDFS(board, i - 1, j, wordPos + 1, word, visited); // up
            }
            return found;
        }
        return false;
    }
}

50 DSA-Questions: #12, #13

#12. Spiral Matrix
Given an m x n matrix, return all elements of the matrix in spiral order.

class Solution {
    private enum DIRECTION {LEFT_TO_RIGHT, TOP_TO_BOTTOM, RIGHT_TO_LEFT, BOTTOM_TO_TOP};
    private void run(int[][] matrix, int i, int j, DIRECTION direction, int cycle, List<Integer> result) {
        switch (direction) {
            case LEFT_TO_RIGHT:
                if (j >= matrix[0].length-cycle) {
                    return;
                }
                for (int jj=j; jj<matrix[0].length-cycle; jj++) {
                    result.add(matrix[i][jj]);
                }
                run(matrix, i+1, matrix[0].length - cycle - 1, DIRECTION.TOP_TO_BOTTOM, cycle, result);
                break;
            case TOP_TO_BOTTOM:
                if (i >= matrix.length-cycle) {
                    return;
                }
                for (int ii=i; ii<matrix.length-cycle; ii++) {
                    result.add(matrix[ii][j]);
                }
                run(matrix, matrix.length - cycle - 1, j-1, DIRECTION.RIGHT_TO_LEFT, cycle, result);
                break;
            case RIGHT_TO_LEFT:
                boolean added = false;
                for (int jj=j; jj>=cycle; jj--) {
                    result.add(matrix[i][jj]);
                    added = true;
                }
                if (added) {
                    run(matrix, i-1, cycle, DIRECTION.BOTTOM_TO_TOP, cycle, result);
                }
                break;
            case BOTTOM_TO_TOP:
                added = false;
                for (int ii=i; ii>cycle; ii--) {
                    added = true;
                    result.add(matrix[ii][j]);
                }
                if (added) {
                    run(matrix, cycle + 1, j+1, DIRECTION.LEFT_TO_RIGHT, cycle + 1, result);
                }
                break;
        }
    }
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> result = new ArrayList<>();
        run(matrix, 0, 0, DIRECTION.LEFT_TO_RIGHT, 0, result);
        return result;
    }
}

#13. Rotate Image

You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise). You have to rotate the image in place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.

public class Exercise13 {
    private final int MARKER = 1000000; // marks that Mij has been updated
    // private final int[][] MATRIX = {{1,2,3},{4,5,6},{7,8,9}}; // n x n, -1000 <= matrix[i][j] <= 1000
    // private final Integer[][] MATRIX = {{1,2,3,4, 5},{6,7,8,9,0},{9,8,7,6,5}, {4,3,2,1,0}, {9,1,2,3,4}};
    // private final Integer[][] MATRIX = {{1,2,-3,-4},{0,7,8,-9},{9,8,-7,6}, {4,0,2,-1}};
    private final Integer[][] MATRIX = {{1000,2},{-1000,7}};
    private int MAX_VALUE = 1001;

    private int getCorrespondingElement90Cw(int i, int j) {
        return MATRIX[MATRIX.length-1-j][i];
    }

    private int getCorrespondingElement90Ccw(int i, int j) {
        return MATRIX[j][MATRIX.length-1-i];
    }

    private int getCorrespondingElement180(int i, int j) {
        return MATRIX[MATRIX.length-1-i][MATRIX.length-1-j];
    }

    private void solveOnlyDisplay() {
        for (int i=0; i<MATRIX.length; i++) {
            for (int j = 0; j < MATRIX[0].length; j++) {
                System.out.print(getCorrespondingElement90Cw(i,j) + " ");
            }
            System.out.println();
        }
        System.out.println();
    }

    private void addToOriginalMatrix(int valueToAdd) {
        for (int i=0; i<MATRIX.length; i++) {
            for (int j=0; j<MATRIX[0].length; j++) {
                MATRIX[i][j] = MATRIX[i][j] + valueToAdd;
            }
        }
    }

    private int getMatrixMin() {
        int minElem = MAX_VALUE;
        for (int i=0; i<MATRIX.length; i++) {
            for (int j=0; j<MATRIX[0].length; j++) {
                if (MATRIX[i][j] < minElem) {
                    minElem = MATRIX[i][j];
                }
            }
        }
        return minElem;
    }

    private void display() {
        for (int i=0; i<MATRIX.length; i++) {
            for (int j = 0; j < MATRIX[0].length; j++) {
                System.out.print(MATRIX[i][j] + " ");
            }
            System.out.println();
        }
        System.out.println();
    }

    private void solveWithSaving() {
        assert(MATRIX.length == MATRIX[0].length);
        int minValue = getMatrixMin();
        if (minValue < 0) {
            addToOriginalMatrix(- minValue); // make all values positive
            MAX_VALUE -= minValue; // update max possible 
        }

        // in place saving 90 degrees clockwise matrix rotation

        // extra loading matrix: Mij = MARKER + Mij * MAX_VALUE + Mij_rotated
        for (int i=0; i<MATRIX.length; i++) {
            for (int j=0; j<MATRIX[0].length; j++) {
                int rotatedMij = getCorrespondingElement90Cw(i,j);
                if (rotatedMij >= MARKER) {
                    int originalRotatedElement = (rotatedMij - MARKER) / MAX_VALUE;
                    MATRIX[i][j] = MARKER + MATRIX[i][j] * MAX_VALUE + originalRotatedElement;
                } else {
                    MATRIX[i][j] = MARKER + MATRIX[i][j] * MAX_VALUE + rotatedMij;
                }
            }
        }

        // cleanup to get only Mij_rotated
        for (int i=0; i<MATRIX.length; i++) {
            for (int j = 0; j < MATRIX[0].length; j++) {
                MATRIX[i][j] = (MATRIX[i][j] - MARKER) % MAX_VALUE;
            }
        }

        if (minValue < 0) {
            addToOriginalMatrix(minValue); // restore original values in matrix
        }

        display();
    }

    public static void main(String args[]) {
        new Exercise13().solveOnlyDisplay();
        new Exercise13().solveWithSaving();
    }
}