Let's start Scheme

2012-06-01

rotate left

さすがに落ちたかな、ちと課題が難しかった・・・

電話とネットコードシェアみたいなサービスをつかったインタビューを受けていた。課題はメモリアロケーションをしないリストの回転。いろいろ考えて大分力尽きた感じであった。さすがに残念である。

っで、 そのまま放っておくのももったいないと思い、調べてみたりした。
std::rotate を読んでみた - d.v.d
C++のSTLにはそのようなアルゴリズムがあるらしく、上記のサイトに解説があった。ということでSchemeで写経。swap部分は適当。
(define (rotete-left vec m)
  (define (itr s m e)
    (if (or (= s m) (= e m))
 vec
 (let loop ((s s) (mm m))
   (if (or (= s m) (= mm e))
       (if (= s m)
    (itr s mm e)
    (itr s m e))
       (let ((v1 (vector-ref vec s))
      (v2 (vector-ref vec mm)))
  (vector-set! vec s v2)
  (vector-set! vec mm v1)
  (loop (+ s 1) (+ mm 1)))))))
  (let ((len (vector-length vec)))
    (itr 0 m len)))
なにをやっているか分かるし、知っていれば直ぐに解けるんだろうなぁとは思うけど、正直知らなきゃ無理って感じのものだ。特に30分とかで解けるようなものではないと信じたい。凡才では閃かないよこんなの・・・
入れ替え、入れ替えでいけるよなぁとか考えてたけど違う路線で考えていた。基本的なアルゴリズムの知識が足りない。

あきら~めまっしょお~、あきらめまっしょお~♪

何がどうなったのか知らないけど、3度目の電話インタビューが行われることになりそうである。
首の皮一枚で繋がったのだろうか?

正直電話インタビューって結構しんどいので、ほっとしていたのだが・・・

No comments:

Post a Comment