Minonnn
@Minonnn (Mi NO)

Are you sure you want to delete the question?

If your question is resolved, you may close it.

Leaving a resolved question undeleted may help others!

We hope you find it useful!

【質問】Java「hackerrank」のコーディングテスト

久しぶりの投稿です。
先日、コーディングテストを受けてきました。

自分でも合っているかどうか不安なので優しい有識者様、教えていただけると嬉しいです...

「hackerrank」のコーディングテストでした!
そのため、コンパイルやテストケースはこれでクリアしたのですが正直これで通るのが疑問になったので質問をしております。(現在自分でも解明中)

問題文は下記になります。英語だったため翻訳+私の和訳で補填しています。

問題文ーーーーーーーーーーーーーーーーーーーーーーーー

整数の配列が与えられた場合、順序を変更せずに任意の要素と以前の小さい要素との間に最大差を決定します。これより下位の先行要素がない場合は-1を返します。

例)
arr=[5,3,6,7,4]

arr[0]より前の要素はありません。
arr[1]より小さい値を持つ以前の読み取り値はありません。
arr[2]=6よりも低い値を持つ、以前の読み取り値が2つあります。

◼︎ arr[2] - arr[1] = 6-3-3
◼︎ arr[2] - arr[0] = 6-5=1

arr[3]=7 よりも低い値を持つ、以前の読み取り値が3つあります。
◼︎ arr[3] - arr[2] = 7-6=1
◼︎ arr[3] - arr[1] = 7-3=4
◼︎ arr[3] - arr[0] = 7-5=2

arr[4]=4 よりも低い値を持つ、以前の読み取り値が1つあります。
◼︎ arr[4] - arr[1] = 4-3=1

最大の末尾レコードはarr[3]-arr[1]=4です。

ーーーーーーーーーーーーーーーーーーーーーーーー

私が記述したコード
※問題文しかメモしていなかったのでうろ覚えで書いています...

class Result {
	public static int maxTrailing(List<Integer> arr) {
    	int min=arr.get(0), max=-1;
        	for(int i=0; i<arr.size(); i++)
        	{
        	if(arr.get(i)<min)
        	min=arr.get(i);

        	int x = arr.get(i) - min;

        	if(x!=0 && x>max)
        	max=x;
        	}
        	return max;
	}
	
}
下に続く...下は問題文のテンプレコードが続いています。

問題文の「以前の読み取り値が3つ」という箇所がクリアできていない?のではと思っていたので
テストケースがクリアできないと思っていました。

しかし、テストケースが通ってしまったので不思議に思っています。

書き方も調べれば調べるほどなぜこれでエラーがでなかったのか不思議です。

自分でも支離滅裂な質問だと思っていますが簡単に何を聞きたいかというと、
・このコードで問題文のお題をクリアできているのかどうか。
・このコードはどのようなコードになっているのか。

この2つをお聞きしたいです...

0

1Answer

・このコードで問題文のお題をクリアできているのかどうか。

まず、これについては、正確な原文の問題文が掲載されていない以上、完全な回答は不可能です。

質問文に記載された"直訳"と、「なんかわからんけど通った」というコードからエスパーを最大限発揮して読み取れる限りで意訳するならば、下記のようになるでしょうか。(日本語を意訳するというのも変な話ですが

【推測題意A】

以下のような関数 maxTrailing を実装せよ。
(1) この関数には、引数として整数の配列が与えられる。
(2) この関数の戻り値は(3)以降のように決定される
(3) 与えられた配列内のすべての各要素について、(4)の処理を実行する。
(4) 「『着目中の要素より前の位置にある要素(群)のうち、着目中の要素よりも小さく
  かつ要素(群)内で最小である要素』と『着目中の要素』との差」を記録する。
  (着目中の要素より前の位置に要素がない場合は処理対象を次の要素に移す)
(5) (4)で記録した値のうち最大値を返す。ただし、すべての各要素について、
  着目中の要素より前の位置に着目中の要素より小さい要素が存在しない場合は、
   -1 を返す。

・このコードはどのようなコードになっているのか。

読みやすいようにフォーマットしたのが下記です。

class Result {
    public static int maxTrailing(List<Integer> arr) {
        int min = arr.get(0), max = -1;
        for (int i = 0; i < arr.size(); i++) {
            if (arr.get(i) < min) {
                min = arr.get(i);
            }
            int x = arr.get(i) - min;
            if (x != 0 && x > max) {
                max = x;
            }
            return max;
        }
    }
}

上記のコードは、

  • 各要素について、「その要素より前の位置にある要素(群)」のうち、その要素よりも小さいものがあれば、それらの最小値との差を求めて記録する。最後に、記録した差の中で最大の値を返す。
  • 仮にすべての各要素について、その要素より前の位置にある要素が、その要素を下回っていない場合は、-1を返す
    ようになっているので、推測題意Aを満たしているといえます。

問題文の「以前の読み取り値が3つ」という箇所がクリアできていない?のではと思っていたので

この点については、一時的に問題文記載のサンプル説明によるミスリードにハマっていた可能性があります。
(仮に問題文の題意が推測題意Aである、という前提ですが)問題文記載のサンプル説明を見て素直に実装すると、2重ループで実装してしまう人が出てきそうです。
ですがそれだと計算量が $\mathcal{O}(n^2)$になり、おそらくタイムアウトになるようなケースが用意されているはず。
そうではなくて、質問者さんの回答コードのように $\mathcal{O}(n)$ で解ける問題であるという所がこの問題のミソなのではないかなと思います。
(問題文自体推測なので完全に推測ですけど)

0Like

Comments

  1. @Minonnn

    Questioner

    回答ありがとうございます!
    返信とても遅くなってしまい申し訳ございません...涙

    推測題意Aができているようでとても安心しました!

    引き続き問題の意図とコード回答ができるようにがんばります...

Your answer might help someone💌