3

コーディングインタビュー中に、私は次の質問をされました：

入力ストリームの単語と行の数をカウントするプログラムを作成します。
nextChar（）メソッドを持つリーダーがあると仮定します。

一見シンプルに見えます。しかし、その後、次のような多くの状態を処理する必要があることに気付きます。

  • 連続する単語/行のデリメータ
  • さまざまな単語の終わりの条件-単語の区切り文字または行の区切り記号またはEOF
  • 単語の区切り文字で始まる新しい文字列
  • 等

インタビューで、私は多くのif-elseとフラグを備えた一種のスパゲッティコードを思いつきました。

しかし、この種の問題には正式なアプローチが必要だと思います。これにより、考えられるすべてのケースを確実に処理でき、構造化されたソリューションを提供できます。

それはおそらくオートマタ理論かコンパイラ理論のどちらかからのものだと思います（私はこれまでこれら2つの分野のいずれかを深く掘り下げたことがありません）。

したがって、上記の問題で特定の種類の問題を認識した場合、またはどの理論がこのような問題をカバーしているかを知っている場合は、私に知らせてください。

4

1 に答える 1

4

有限状態マシン。

これは本質的に小さな字句解析タスクです。解決策は決してきれいではありませんが、次の方法でコードを書くと、正確さをかなり確信で​​きます。

curState <- NONE
while(c <- getChar)
    switch(curState) {
       case NONE:
           switch(c) {
               // ....
           }
           break;
       // .....
    }
}

データ構造を使用して遷移関数を格納することもできます（状態と文字が与えられた場合、次の状態は何ですか？）が、あなたの場合、コードを書くだけがおそらく最善の策です。

...テキストエンコーディングを忘れないでください！UTF-16でしょ？:)

wcUnixユーティリティの実装を調べたいと思うかもしれません。

これらは、インタビューで行うよりも洗練され、取り上げられますが、それでも見るのは素晴らしいことです。

于 2013-03-15T17:26:27.110 に答える