読者です 読者をやめる 読者になる 読者になる

stMind

You'll never blog alone

Twitterのプログラミング面接を受けた人のブログ記事紹介

I Failed a Twitter Interview

こういうInterviewの内容ってNDAになってるんじゃないのかなと思ったりするんだけど大丈夫なのかな。

Hacker NewsにTwitterのプログラミング面接を受けた人のブログエントリーがあって、具体的にどのような問題だったかが載せてあったのでそれを紹介。

問題

次のような図を考えます。

図に示すように、異なる高さを持つ壁があります。また、この図はintergerの配列として表され、各インデックスにおける値は壁の高さになっています。上記の図であれば、[2,5,1,2,3,4,7,7,6]となります。
この状態で、雨が降ったと想像してください。どれくらいの水が壁の間の水たまりに溜まっているでしょうか?

このとき、容量は1x1の正方形ブロックでカウントします。上記であれば、インデックス1の左側とインデックス7の右側は水がこぼれてしまうので、残るのは1から6の間の水たまりで容量は10となります。

解答

解答はリンク先のブログに載っています。解答は読まずにトライするもよし、解答を読んで実際に実装してみるもよし、時間のあるときに頭の体操をしてみてはいかがでしょうか。