How to Solve Print Folder Structure
Print Folder Structure Introduction
Print Folder Structure Introduction
The Print Folder Structure problem asks us to take an input of file paths and print out the files in each folder. This problem requires us to create a tree-like structure representing the folder hierarchy to make it easier for us to traverse.
Print Folder Structure Problem
Print Folder Structure Problem
Given a list of file paths, print all of the files in each of the folders.
For example:
Input: files = [ "/webapp/assets/html/a.html", "/webapp/assets/html/b.html", "/webapp/assets/js/c.js", "/webapp/index.html" ]
Output:
-- webapp -- assets -- html -- a.html -- b.html -- js -- c.js -- index.html
Print Folder Structure Solutions
Print Folder Structure Solutions
To solve this problem, we can create a tree-like structure to represent the folder hierarchy. We start with an empty root node and iterate through each file path. For each file path, we split it into individual folder names and traverse the tree from the root, creating new nodes as needed for each folder. By the end of it, we have a tree that represents the folder structure.
To print all the files in each folder, we use a depth-first search (DFS) approach. We define a recursive function that takes a current node and an indentation level. At each node, we print the folder name with the appropriate indentation. If the current node has children (sub-folders), we recursively call the function for each child, incrementing the indentation level. If a node does not have any children, it means it is a file, and we print it with the proper indentation.
class Node:
def __init__(self, name):
self.name = name
self.children = {}
class Tree:
def __init__(self):
self.root = Node("")
def insert_file(self, file_path):
folders = file_path.split("/")[1:] # Exclude the empty root folder
current = self.root
for folder in folders:
if folder not in current.children:
current.children[folder] = Node(folder)
current = current.children[folder]
def print_files(self):
self._dfs_print(self.root, "")
def _dfs_print(self, node, indent):
if not node.children:
print(indent + "-- " + node.name)
return
print(indent + "-- " + node.name)
for child in node.children.values():
self._dfs_print(child, indent + " ")
# Test case
files = [
"/webapp/assets/html/a.html",
"/webapp/assets/html/b.html",
"/webapp/assets/js/c.js",
"/webapp/index.html"
]
tree = Tree()
for file in files:
tree.insert_file(file)
tree.print_files()1class Node:
2 def __init__(self, name):
3 self.name = name
4 self.children = {}
5
6class Tree:
7 def __init__(self):
8 self.root = Node("")
9
10 def insert_file(self, file_path):
11 folders = file_path.split("/")[1:] # Exclude the empty root folder
12
13 current = self.root
14 for folder in folders:
15 if folder not in current.children:
16 current.children[folder] = Node(folder)
17 current = current.children[folder]
18
19 def print_files(self):
20 self._dfs_print(self.root, "")
21
22 def _dfs_print(self, node, indent):
23 if not node.children:
24 print(indent + "-- " + node.name)
25 return
26
27 print(indent + "-- " + node.name)
28 for child in node.children.values():
29 self._dfs_print(child, indent + " ")
30
31# Test case
32files = [
33 "/webapp/assets/html/a.html",
34 "/webapp/assets/html/b.html",
35 "/webapp/assets/js/c.js",
36 "/webapp/index.html"
37]
38
39tree = Tree()
40for file in files:
41 tree.insert_file(file)
42
43tree.print_files()Time/Space Complexity Analysis
- Time Complexity: O(N), where N is the number of file paths in the files input
- Space Complexity: O(M), where M is number of distinct folders in the path. We store each distinct folder as a node in the tree.
Watch These Related Mock Interviews
About interviewing.io
interviewing.io is a mock interview practice platform. We've hosted over 100K mock interviews, conducted by senior engineers from FAANG & other top companies. We've drawn on data from these interviews to bring you the best interview prep resource on the web.
