CODEWITHSUNDEEP
algorithmdata-structureslanguage-agnostic
user1784540
user1784540

Reputation: 53

Print all the files in a given folder and sub-folders without using recursion/stack

I recently had an interview with a reputable company for the position of Software Developer and this was one of the questions asked:

"Given the following methods:

List subDirectories(String directoryName){ ... }; 
List filesInDirectory(String directoryName) { ... };

As the names suggest, the first method returns a list of names of immediate sub-directories in the input directory ('directoryName') and the second method returns a list of names of all files in this folder.

Print all the files in the file system."

I thought about it and gave the interview a pretty obvious recursive solution. She then told me to do it without recursion. Since recursion makes use of the call stack, I told her I will use an auxillary stack instead, at which point point she told me not to use a stack either. Unfortunately, I wasn't able to come up with a solution. I did ask how it can be done without recursion/stack, but she wouldn't say.

How can this be done?

Upvotes: 5

Views: 4132

Answers (3)

Leon Bouquiet
Leon Bouquiet

Reputation: 4372

I think that what @lqs suggests is indeed an acceptable answer that she might have been looking for: store the full path in a variable, and append the directory name to it if you enter a subdirectory, and clip off the last directory name when you leave it. This way, your full path acts as the pointer to where you currently are in the file system.

Because the full path is always modified at the end, the full path behaves (not surprisingly) as your stack.

Interview questions aside, I think I would still pick a real stack over string manipulation though...

Upvotes: 1

Michael
Michael

Reputation: 10474

You want to use a queue and a BFS algorithm.

I guess some pseudo-code would be nice:

files = filesInDirectory("/")
foreach (file in files) {
   fileQ.append(file)
}

dirQ = subDirectories("/")
while (dirQ != empty) {
   dir = dirQ.pop
   files = filesInDirectory(dir)
   foreach (file in files) {
      fileQ.append(file)
   }
   dirQ.append(subDirectories(dir))
}

 while (fileQ != empty) {
   print fileQ.pop
 }

Upvotes: 3

Murilo Vasconcelos
Murilo Vasconcelos

Reputation: 4827

If I understood correctly, immediate sub-directories are only the directories in that folder. I mean if I=we have these three paths /home/user, /home/config and /home/user/u001, we can say that both user and config are immediate subdirectories of /home/, but u001 isn't. The same applies if user, and u001 are files (user is immediate while u001 isn't).

So you don't really need recursion or stack to return a list of immediate subdirectories or files.

EDIT: I thought that the OP wanted to implement the subDirectories() and filesInDirectories() functions.

So, you can do something like to print all files (kind of pseudocode):

List subd = subDirectories(current_dir);
List files = filesInDirectories(current_dir);

foreach (file in files) {
    print file.name();
}

while (!subd.empty()) {
    dir = subd.pop();

    files = filesInDirectory(dir.name());

    foreach (file in files) {
        print file.name();
    }

    subd.append(subDirectories(dir.path()));
}

Upvotes: 1

Related Questions