CodingGyan

Permission Flags with Bits

medium Object-Oriented Programming

Problem

Each user has four possible permissions: read, write, exec, admin. Store them in one small integer, one bit for each permission. Commands: grant USER PERM, revoke USER PERM, has USER PERM (print true or false), show USER (print the permissions the user has, in the order read, write, exec, admin, separated by commas; print none if the user has none). A user not seen before has no permissions.

Constraints

  • 1 <= commands <= 100
  • PERM is one of read, write, exec, admin

Examples

Input

grant ann read
grant ann exec
show ann

Output

read,exec

Solutions

Best approachTime O(n)Space O(users)

One integer holds all four answers. OR sets a bit, AND with NOT clears it, and AND alone tests it. Granting a permission twice does no harm, because setting a set bit changes nothing.

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : Run the commands.
 * Input   : Command lines.
 * Output  : One line per answer.
 * Approach: Bit flags
 * Time    : O(n)
 * Space   : O(users)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
        // Step 1: One bit for each permission: read is bit 0, write is bit 1, exec is bit 2, admin is bit 3.
        static class Permissions {
            static final String[] NAMES = {"read", "write", "exec", "admin"};
            private int bits = 0;

            static int bitOf(String name) {
                return 1 << java.util.Arrays.asList(NAMES).indexOf(name);
            }

            // Step 2: OR sets a bit. AND with the opposite (NOT) clears a bit. AND tests a bit.
            void grant(String name) {
                bits |= bitOf(name);
            }

            void revoke(String name) {
                bits &= ~bitOf(name);
            }

            boolean has(String name) {
                return (bits & bitOf(name)) != 0;
            }

            String text() {
                StringBuilder sb = new StringBuilder();
                for (String name : NAMES) {
                    if (has(name)) {
                        sb.append(sb.length() == 0 ? "" : ",").append(name);
                    }
                }
                return sb.length() == 0 ? "none" : sb.toString();
            }
        }

    // This method solves the task. It receives the input and returns the answer.
    static String[] solve(String[] lines) {
        java.util.Map<String, Permissions> users = new java.util.HashMap<String, Permissions>();
        java.util.List<String> out = new java.util.ArrayList<String>();
        for (String line : lines) {
            String[] part = line.split(" ");
            Permissions user = users.computeIfAbsent(part[1], key -> new Permissions());
            if (part[0].equals("grant")) {
                user.grant(part[2]);
            } else if (part[0].equals("revoke")) {
                user.revoke(part[2]);
            } else if (part[0].equals("has")) {
                out.add(String.valueOf(user.has(part[2])));
            } else {
                out.add(user.text());
            }
        }
        return out.toArray(new String[0]);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        java.util.List<String> all = new java.util.ArrayList<>();
        while (scanner.hasNextLine()) {
            String line = scanner.nextLine().trim();
            if (!line.isEmpty()) {
                all.add(line);
            }
        }
        String[] lines = all.toArray(new String[0]);
        System.out.println(String.join("\n", solve(lines)));
    }
}
Hints (2)
  1. What does bits &= ~mask do?
  2. Why is granting twice safe?