Interviewer started of with below question
/*
A
|___ B
| |___ C <-- access
| |___ D
|___ E <-- access
|___ F
*/
class FileSystem{
private List<List<String>> folders;
private Set<String> access;
}
class Solution {
public static void main(String[] args) {
List<List<String>> folders = new ArrayList<>();
folders.add(Arrays.asList("A", null));
folders.add(Arrays.asList("B", "A"));
folders.add(Arrays.asList("C", "B"));
folders.add(Arrays.asList("D", "B"));
folders.add(Arrays.asList("E", "A"));
folders.add(Arrays.asList("F", "E"));
Set<String> access = new HashSet<>();
access.add("C");
access.add("E");
FileSystem fs = new FileSystem(folders, access);
}
}
Ask: Implement method hasAccess which takes folder name as input and returns whether the folder has access.
Here's how I tackled the problem:
Thinking out loud, in order to determine access in constant we need to perform some pre-computing. One of the way is to use HashMap which maintains permission for each file in the file system. The hasAccess method will return the value of the map.
Do you think this is a reasonable approach to start?
Interviewer: "Yes, go ahead"
While implementing I clarified whether I can assume that parent folder appears before child. This way, I can perform lookup whether parent has access. Interviewer confirment that I can assume so.
So, the algorithm is as sample as below:
Iterate each folder in the folder list. Check if access set contains the folder or the parent has access. If one of them is yes then set the value to true to indicate hasAccess. Otherwise set it to false.
Here's my implementation
import java.io.*;
import java.util.*;
class FileSystem{
private List<List<String>> folders;
private Set<String> access;
private HashMap<String, Boolean> accessMap = new HashMap<>();
public FileSystem(List<List<String>> folders, Set<String> access) {
this.folders = folders;
this.access = access;
initializeMap();
}
public boolean hasAccess(String folderName) {
// return whether the given folder has access or not
return this.accessMap.get(folderName);
}
private void initializeMap() {
folders.forEach(folder -> {
String currentFolder = folder.get(0);
String parentFolder = folder.get(1);
System.out.println(String.format("%s:%s",folder.get(0), folder.get(1)));
// Check if there is a direct access
if (access.contains(currentFolder)) {
accessMap.put(currentFolder, true);
} else {
// Check if access is inherited
if (parentFolder == null) {
// if parent is null then set it to false
accessMap.put(currentFolder, false);
} else if(access.contains(parentFolder) || accessMap.get(parentFolder)) {
// Very important not to forget to lookup parents access in accessMap
accessMap.put(currentFolder, true);
} else {
accessMap.put(currentFolder, false);
}
}
});
}
}
class Solution {
public static void main(String[] args) {
List<List<String>> folders = new ArrayList<>();
folders.add(Arrays.asList("A", null));
folders.add(Arrays.asList("B", "A"));
folders.add(Arrays.asList("C", "B"));
folders.add(Arrays.asList("D", "B"));
folders.add(Arrays.asList("E", "A"));
folders.add(Arrays.asList("F", "E"));
folders.add(Arrays.asList("G", "F"));
Set<String> access = new HashSet<>();
access.add("C");
access.add("E");
FileSystem fs = new FileSystem(folders, access);
System.out.println(fs.hasAccess("C")); // Expect true
System.out.println(fs.hasAccess("D")); // Expect False
System.out.println(fs.hasAccess("E")); // Expect true
System.out.println(fs.hasAccess("F")); // Expect true
System.out.println(fs.hasAccess("G")); // Expect true
}
}
Interviwer followed up with runtime of hasAccess method.
Since the permission is already pre-computed, the runtime of this solution is O(1).
Follow up question:
How will you detect the redundant access. For example in the given question let's say both E has access and F has access. In such case access to F is redundant. Can you fix the redundant access?
Brainstorming the solution:
I defined the solution of redundant access => If current node has direct access and inherits access from parent then it's redundant. So, remove the direct access to the given node.
Interviewer asked when will I perform the fix? I mentioned I can do this as part of pre-computation.
Interviewer asked me what if we need to do outside of pre-compution. He hinted me on writing a method to perform the fix as a separate method.
The approach I employed is iterating over the given folder list and filter the folders whose value is true. For the filtered folders check if it has both direct access and inherited acces. If it yes, remove the direct access.
Wrote the program quick
public void fixRedundantAccess() {
folders.forEach(folder -> {
if(accessMap.get(folder.get(0))) {
if (folder.get(1) == null) {
return;
}
if (access.contains(folder.get(0)) && accessMap.get(folder.get(1))) {
access.remove(folder.get(0));
}
}
});
}
Interviewer: Instead of iterating the list folder can you think of iterating just the nodes which has access.
I am not sure where my mind was, I was in a hurry... I took this hint as iterate accessMap . I am sure interviwer was hinting towards iterating access hash set.
Anyways, I told him that we could do that however our hashmap doesn't store the parent Id. So, we will have to store the parentId in the map too.
Interviwer asked me to implement the solution to track the parentId. So my final solution was below:
/*
* Click `Run` to execute the snippet below!
*/
import java.io.*;
import java.util.*;
/*
A
|___ B
| |___ C <-- access
| |___ D
|___ E <-- access
|___ F
|____ G <-- access
*/
class FileSystem{
private List<List<String>> folders;
private Set<String> access;
private HashMap<String, Node> accessMap = new HashMap<>();
public FileSystem(List<List<String>> folders, Set<String> access) {
this.folders = folders;
this.access = access;
initializeMap();
}
class Node {
String folder;
String parent;
boolean hasAcess;
}
public boolean hasAccess(String folderName) {
// return whether the given folder has access or not
return this.accessMap.get(folderName).hasAcess;
}
/*
Redundant Access - DirectAccess + Inherited Access
*/
public void fixRedundantAccess() {
accessMap.entrySet().forEach(entry -> {
// direct access && inherited access
if (entry.getValue().parent == null) {
return;
}
if (access.contains(entry.getKey()) && accessMap.get(entry.getValue().parent).hasAcess) {
access.remove(entry.getKey());
}
});
}
private void initializeMap() {
folders.forEach(folder -> {
System.out.println(String.format("%s:%s",folder.get(0), folder.get(1)));
if (folder.get(1)==null) {
if (access.contains(folder.get(0))) {
Node node = buildNode(folder.get(0), null, true);
accessMap.put(folder.get(0), node);
} else {
Node node = buildNode(folder.get(0), null, false);
accessMap.put(folder.get(0), node);
}
} else {
// Check if the hashset contains access to the folder name?
if (access.contains(folder.get(0))) {
Node node = buildNode(folder.get(0), folder.get(1), true);
accessMap.put(folder.get(0), node);
}
// Other wise check if the parent has the access
else if (access.contains(folder.get(1)) || accessMap.get(folder.get(1)).hasAcess) {
Node node = buildNode(folder.get(0), folder.get(1), true);
accessMap.put(folder.get(0), node);
} else {
Node node = buildNode(folder.get(0), folder.get(1), false);
accessMap.put(folder.get(0), node);
}
}
});
}
private Node buildNode(String folderName, String ParentFolder, boolean hasAccess) {
Node node = new Node();
node.parent = ParentFolder;
node.folder = folderName;
node.hasAcess = hasAccess;
return node;
}
}
class Solution {
public static void main(String[] args) {
List<List<String>> folders = new ArrayList<>();
folders.add(Arrays.asList("A", null));
folders.add(Arrays.asList("B", "A"));
folders.add(Arrays.asList("C", "B"));
folders.add(Arrays.asList("D", "B"));
folders.add(Arrays.asList("E", "A"));
folders.add(Arrays.asList("F", "E"));
folders.add(Arrays.asList("G", "F"));
Set<String> access = new HashSet<>();
access.add("C");
access.add("E");
FileSystem fs = new FileSystem(folders, access);
System.out.println(fs.hasAccess("C")); // Expect true
System.out.println(fs.hasAccess("D")); // False
System.out.println(fs.hasAccess("E")); // t
System.out.println(fs.hasAccess("F")); // t
System.out.println(fs.hasAccess("G")); // T
access.add("F");
System.out.printf("Before redundant fix, the size of access is %s \n", access.size());
fs.fixRedundantAccess();
System.out.printf("Afer redundant fix, the size of access is %s \n", access.size());
}
}
Reason for rejection
The interviewer was hinting me to just perform the logic on the list of nodes which has direct access... I understood it as I need to iterate the accessMap.
The hint he suggested was if there are L nodes what will be the timecomplexiy of my solution. -- Really didn't catch this hint :(
Anyways, an ideal method for fixRedundantAccess would have been
/*
Redundant Access = DirectAccess + Inherited Access
*/
public void fixRedundantAccess() {
access.forEach(entry -> {
// direct access && inherited access
if (accessMap.get(entry).parent == null) {
return;
}
String parent = accessMap.get(entry).parent;
if (accessMap.get(parent).hasAcess) {
access.remove(entry);
}
});
}He asked for the time complexity. I said in worst case, if the root has access and all of the children has access we will be visiting all the nodes. Hence it's still O(n).
He questioned why not iterate access set. I should have thought about this. <-- This was the hint for optimal solution.