Geek asks and answers

A non-recursive way to display files in a directory and subdirectories without using a stack / queue

During the interview, I was asked to indicate the names of the files in the directory and its subdirectories¹, using neither recursion, nor stack, nor queues.

Since the only non-recursive way I know is using the stack, I was not able to answer this question.

The interviewer explained this decision, but I could not understand it. The only thing I remember is that it uses two methods instead of one.

What is this approach that allows you to list files in a directory and its subdirectories without recursion and without a stack or queue?

¹ The solution is a language agnostic. A list of subdirectories is provided by the method ListDirectories(string directoryPath), and files by ListFiles(string directoryPath). We do not know in advance the depth of the subdirectories.

+3
source share
2 answers

Deep in the first search, notice that the current path essentially serves as a stack. Listing names in depth-first order, continue, as you would expect, but don’t worry about writing a stack ... When you finish listing files in a directory, you can “pull out” the stack, noting that the last directory was what you were, and then continue from this point in the parent directory.

+3
source

Try something like this (pseudo code):

baseDirectory = "/usr"
list = [baseDirectory] // list of directories to traversal
files = []
while (list not empty) {
  d = list.getFirst(); // get directory
  directories = ListDirectories(d);
  files.add(ListFiles(d)); // add all files from current directory
  list.add(directories); //add all directories from current directory to traversal
  list.remove(d); // remove traversed dir
}

We only use lists :) But this approach is very similar to the stack / queue solution

+1
source

More articles:


All Articles