5

私は最近、評判の良い企業とソフトウェア開発者のポジションについて面接を受けました。これは尋ねられた質問の 1 つです。

「次の方法があるとします。

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

名前が示すように、最初のメソッドは入力ディレクトリ ('directoryName') 内の直接のサブディレクトリの名前のリストを返し、2 番目のメソッドはこのフォルダー内のすべてのファイルの名前のリストを返します。

ファイル システム内のすべてのファイルを印刷します。」

私はそれについて考え、インタビューに非常に明白な再帰的な解決策を与えました。彼女はそれから再帰なしでそれをするように私に言いました。再帰は呼び出しスタックを利用するので、代わりに補助スタックを使うと彼女に言いました。残念ながら、解決策を思いつくことができませんでした。再帰/スタックなしでそれを行う方法を尋ねましたが、彼女は言いませんでした.

これはどのように行うことができますか？

4

3 に答える 3

3

キューと BFS アルゴリズムを使用したい。

いくつかの疑似コードがいいと思います：

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
 }
于 2012-10-30T04:57:25.757 に答える
1

私の理解が正しければ、直下のサブディレクトリはそのフォルダ内のディレクトリのみです。つまり、I=3 つのパス/home/user,/home/config とがある場合、と/home/user/u001の両方が の直下のサブディレクトリであると言えますが、そうではありません。、 、およびがファイルの場合も同じことが当てはまります (は即時ですが、そうではありません)。userconfig/home/u001useru001useru001

したがって、直接のサブディレクトリまたはファイルのリストを返すために、再帰またはスタックは実際には必要ありません。

編集:subDirectories() OP はandfilesInDirectories()関数を実装したいと思っていました。

したがって、すべてのファイルを印刷するようなことができます (一種の擬似コード):

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()));
}
于 2012-10-30T04:43:03.400 に答える
1

@lqs が提案することは、彼女が探していたかもしれない実際に受け入れられる答えだと思います: 変数にフルパスを保存し、サブディレクトリを入力する場合はディレクトリ名をそれに追加し、最後のディレクトリ名を切り取りますそれを残します。このように、フル パスはファイル システム内の現在の場所へのポインターとして機能します。

フル パスは常に最後に変更されるため、フル パスは (当然のことながら) スタックとして動作します。

インタビューの質問はさておき、文字列操作よりも実際のスタックを選ぶと思います...

于 2012-10-30T11:28:53.783 に答える