coding interview
Problem You run an e-commerce website and want to record the last N order ids in a log. Implement a data structure to accomplish this, with the following API: record(order_id): adds the order_id to the log get_last(i): gets the i-th last e…
Problem Implement a stack that has the following method. push(val), which pushes an element onto the stack pop(), which pops off and returns the topmost element of the stack. If there are no elements in the stack, then it should throw an e…
問題 double型の0から1の実数を２進数表記する。 考え方 簡単な例として0.5は２進数では0.1とかける。 つまり、２倍して1のくらいが1になれば１を立てる。 コード例 #include<iostream> #include<string> using namespace std; string bitRep(double x){ string ans = "0."; wh</string></iostream>…
問題 最大32bit整数N, Mが与えられたときにNのjビット目からiビット目にMを挿入する。 考え方 Nのjからiビットを0に変えて、Mを挿入する 注意 ビットは0から数える。一番右が0ビット目。 コード例 #include<iostream> #include<bitset> using namespace std; unsigned int inse</bitset></iostream>…
問題 連結リストとある値xが与えられたときにxの前にxよりも小さい値が、後にxよりも大きい値が来るようにする。 考え方 xよりも小さい数のリストと大きい数のリストを作り、最後にくっつける。 時間計算量はO(N) コード例 import random class Node(): def …
問題 間のnodeだけ与えられたときにそれを削除する 考え方 削除したいnodeが次のnodeに当たるように書き換えれば良い コード例 class Node(): def __init__(self, d): self.data = d self.next = None def appendToTail(self, d): end = Node(d) n = self wh…
問題 単方向連結リストにおいて末尾から数えてk番目の要素を返す。 考え方 連結リストの長さがわからないという前提で考える。 ランナーテクニックを利用する。 ２つのポインタを用意する。 前からk番目からスタート 初めからスタート １つ目のポインタが最…
問題 ハノイの塔 ３つの塔とN枚のサイズの異なる円盤がある。１つの塔から別の塔に移動させる。 １度に１つの円盤しか動かせない。 塔の一番上の円盤だけ移動できる 円盤はそれよりも大きいものの上にしか置けない。 考え方 まずは具体的にやってみる。塔をs…
問題 ある集合の全ての部分集合を返す 考え方 再帰的に考える。 N-1この要素の全ての部分集合がわかっているときに、次の部分集合はどうなるか？ N個目の要素を加えたsubsetsを元のsubsetsに加えれば良い。 f(n) = f(n-1) + {f(n-1), set[n]} コード例 def a…
問題 ソートされた配列からA[i] = iとなるindexを探す。配列が重複した値を持つ場合にどうするか。 考え方 2分探索的な方法で探す。 重複した値がある時は少しややこしくて、結局両側を探すしかない。ただし、探す範囲は mid > A[mid]ならば、左側はindexが0…
問題 Given the mapping a = 1, b = 2, ... z = 26, and an encoded message, count the number of ways it can be decoded. You can assume that the messages are decodable. For example, '001' is not allowed. 考え方 stringが与えられた時のデコード方…
問題 r行c列のグリッドに障害物がいくつかある。左上から右下にいく経路を探索する。ただし、動ける方向は右と下のみ。 考え方 グリッド (i,j)にたどり着けるかどうかをTrue or Falseで格納する。flg[i][j]は左側flg[i][j-1]と上側flg[i-1][j]を見れば到達で…
問題 n段の階段を上がるときに、１ステップで１段、２段、３段のどれかであがれるときに考えられる上がり方の合計は？ 考え方 n段目にはn-1段目から１段で、n−２段目からは2段、n-3段目には３段であがれる。 つまり、f(n) = f(n-1) + f(n-2) + f(n-3)である…
問題 ソートされていない連結リストから重複した要素を削除する。 考え方 一度出てきた値はhash tableに保存しておいて、もう一度出たら削除する。 一度リスト全体を見ればいいので、時間計算量はO(N) コード例 # 双方向連結リスト class LinkedList(): def …
問題 Given the root to a binary tree, implement serialize(root), which serializes the tree into a string, and deserialize(s), which deserializes the string back into the tree. 実装 再帰的に実装します。Noneでなければ展開するようにしています…
内容 lispで使うcar, cdrをpythonで実装してみました。 def cons(a, b): def pair(f): return f(a, b) return pair def car(pair): def f(a, b): return a return pair(f) def cdr(pair): def f(a, b): return b return pair(f) if __name__ == "__main__": …
問題 ２つの文字列str1, str2が与えられた時に、str2がstr1を回転させたものであるか調べる。 例えば str1 = "apple" str2 = "pplea" ならtrue である。 考え方 回転させたものなら str2 + str2としたものの中にstr1が含まれるはずである。 ただし、str1.len…
問題 M*N の行列において、(i, j)が0なら、その行iと列jを全て０にする。 考え方 (0, 0)から０の成分を見つけて、変換していくと全て０に変わってしまうので、まずは０の成分のある位置を格納する。 何個あるかわからないので、可変長配列(C++ではvector型)…
問題 N*Nの行列を90度回転させる 考え方 あまりたくさんのメモリを使いたくないので、１つの値だけを保持して回転させたい。 回転させると(i, j) -> (j, N-i)に移る。移った先を考えると、 (j, N-i)-> (N-i, N-j) (N-i, N-j) -> (N-j, i) (N-j, i) -> (i, j)…
問題 文字列を圧縮する。同じ文字が続いた数を使って表現する。 例：abbccccddd -> a1b2c4d3 とする。ただし、圧縮した方が、文字数が増えている場合は元の文字列を変えす。 考え方 元の文字列を１つずつ進んでいく。sに文字を入れて、s == str[i]である時に…
問題 ２つの文字列が与えられた際に、１回の変換(文字の追加、削除、置き換え）で等しくなるか 考え方 文字列の長さが等しい時は１文字だけ違ったら、置き換えで対応できます。 str1[i] != str2[i]となる数を判定して、これが１以下ならture。 文字列の長さ…
問題 整数を要素にもつarrayから、どれか１つの要素を除いた積のarrayを出力する。 ただし、割り算は使えない。 考え方 arrayの長さをNとする。 単純に全て計算するとの時間計算量がかかる。 出来るだけ前の値を用いて計算したい。 前の変数までの積と次の変…
問題 文字列から回文が作れるか判定する 考え方 文字の数を数えて、文字の種類Mに対して、M-1個の文字が偶数回出れば良い。 アクセスを早くするためにhashを利用する。 計算量 文字列の長さをN、文字の種類をMとする。N >= M である。 hashに記録する際にはO…
