🤦 🧝 🤞🏻 Twitterインタビューに失敗した方法 🛌🏻 🖖🏿 👥

10月28日まで、インターンシップの最後にアマゾンで働くかどうかを決めなければなりませんでした。残り時間はほとんどありませんでしたが、友人のダニエルは、Twitterにアクセスしようとすると、すべてのインタビューを行う時間があると確信しました。抵抗できませんでした。

最初にCodilityのいくつかの問題を解決するように依頼され、1時間ですべてについてすべてを提供しました。質問には中程度の関心が寄せられました（「単語は回文のアナグラムです」、「2次元配列のin 点の数を数える」）。私は解決策についてあまり確信が持てませんでしたが、すぐにジュディは私に水曜日の17:30に電話インタビューをするように勧める手紙を送りました。

私はあなたのことを知りませんが、インタビューの前にたいてい非常に緊張します-面接官は私が十分に頭が良くないと思うかもしれないといつも恐れています。したがって、水曜日の17:20の空のテーブルには、すでに2本の鉛筆とノートがあり、私自身は完全な戦闘準備が整っていました... さらに15分待ってから、Googleに行き、時差を正しく計算したかどうか、そしてカリフォルニアで何時だったかを調べました。間違いはありませんでした。私はジュディのメールの購読を解除し、状況に対処するように頼みました。

10分後、サンフランシスコから電話がありました。ジュディは混乱のために謝罪し、ジャスティンが今すぐ私にインタビューできると言った。

深呼吸

「すごい、準備ができました！」

ジャスティンはまた、スケジュールの誤りについて謝罪し、プログラミングに直行しました。

次の写真を見てください。

この写真には、さまざまな高さの壁があります。画像は整数の配列で表されます。インデックスはX軸上の点で、各インデックスの値は壁の高さ（Y軸に沿った値）です。上の画像は配列[2,5,1,2,3,4,7,7,6]に対応しています。

想像してみてください：雨が降っています。壁の間の「水たまり」にどれくらいの水が集められますか？

水量の単位は1x1の正方形ブロックであると考えています。上の図では、ポイント1の左側のすべてが飛び散っています。ポイント7の右側の水も流出します。まだ1から6の間の水たまりがあるので、結果として生じる水の量は10です。

最もせっかちな人のために

問題の正しい解決策を含むヒストグラムにリンクします。これについては、投稿の最後で詳しく説明します。残りは簡単に読むことができます-ネタバレはありません。

まず、各インデックスにどれくらいの水を入れるかを決めようとしました。数学的分析と積分との関係がすぐに思い浮かびました-特に、極大値を検索するというアイデアは私にとって有用でした。実際、前の図では、ポイント2の上の水は、ポイント1と6で、それを囲む2つの最大値の小さい方によって制限されています。

「すべての局所的最大値を見つけて、それらの間の水で満たされたスペースを数えるとどうなりますか？これは機能しますか？」

「はい、うまくいくはずです」とジャスティンは答えました。

そのような答えの後、私は正しい方向に進んだと判断し、私の決定をコード化しました。次に、ジャスティンは私にいくつかのテストを書くように頼みました、それも私がしました。私たちが話したすべてのテストはうまくいったようです。

「私に質問はありますか？」ジャスティンは尋ねました。「まあ、どうやってこれをやるの？」「あなたの決断は2パスを行うが、十分ではないが、1パスのみを行う別の興味深いアルゴリズムがある」

それから私たちはTwitterで人生について少し話しました。

そして、私が電話を切ったその瞬間に、私は突然気付きました。私の決定は間違っていました。

次の入力を行います。

私の解決策は、局所的な最大値の間のすべての水を探し、次のように見えました：

しかし、その結果、2つの高い塔の間に1つの「水たまり」ができました。

翌日、私は理論計算機科学の身近な大学院生にこの課題を示しました。 40分の反省の後、彼も失敗しました。

しかし、今朝、目覚めた後、それは私に夜明けを迎えました-解決策は美しくシンプルであることが判明しました。

私は自問します：結果として何を学びましたか？実際、少し。インタビュアーが指示的な質問をしてくれなかったことに少し怒っています。実は私の判断が間違っていたのに、ジャスティンがこの「うまくいくはずだ」と言った理由はわかりません。これは彼が要求したテストで明らかになったはずですが、アルゴリズムの開発中に1つの重要なポイントを見逃していたため、推測できませんでした。

来年の夏、私はアマゾンで働きに行きます。

正しい解決策： gist

表示する

/* package whatever; // don't place package name! */
 
import java.util.*;
import java.lang.*;
import java.io.*;
 
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		int[] myIntArray = {2, 5, 1, 2, 3, 4, 7, 7, 6}; 
		System.out.println(calculateVolume(myIntArray));
	}
	
	public static int calculateVolume(int[] land) {
		
		int leftMax = 0;
		int rightMax = 0;
		int left = 0;
		int right = land.length - 1;
		int volume = 0;
		
		while(left < right) {
			if(land[left] > leftMax) {
				leftMax = land[left];
			}
			if(land[right] > rightMax) {
				rightMax = land[right];
			}
			if(leftMax >= rightMax) {
				volume += rightMax - land[right];
				right--;
			} else {
				volume += leftMax - land[left];
				left++;
			}
		}
		return volume;
	}
}

:

, , . , , - - , , . : , , , .

, : , . : , — .

, «» . , , , . , . , . ( , )

: Q & What?.

Twitterインタビューに失敗した方法

最もせっかちな人のために

More articles: