HackerRank A Basic Data Structures and Algorithms Quiz #1
Source
HackerRank A Basic Data Structures and Algorithms Quiz #1
problem statement(コンテストページ)
問題概要
以下の10問のクイズに答える問題
- クイックソートの最悪時間計算量は?
- マージソートの最悪時間計算量は?
- マージソートの平均時間計算量は?
- $n$ 要素からなるヒープを作るのに必要な時間計算量は?
- ヒープは2分探索木の一種である,真か偽か?
- ダイクストラのノードをたどる順番は以下のどれと似ているか? BFS,DFS,トポロジカルソート,どれでもない
- スタックは2つのキューで作れる,キューは2つのスタックで作れる,はそれぞれ真か偽か?(push/popなどの平均時間計算量は中にある要素数に依存してはいけない)
- UnionFindは以下のどれに応用され使われるか? DFS,BFS,最小全域木の計算,全節点対の最短路の計算
- 二分探索木で,あるkeyを探すのに必要な最悪計算量は?
- 'make'/'ant build'が基本的なコンポーネントであるグラフ理論のアルゴリズムは次のうちどれか? 最大流,最小パス,最小全域木,二部マッチング,トポロジカルソート
解法
正直良くわからないのや納得出来ないのもあるが以下の通り.
- $O(n^2)$
- $O(n \log n)$
- $O(n \log n)$
- $O(n)$
- 偽
- BFS
- キューを2つのスタックで作ることのみできる
- 最小全域木の計算
- $O(n)$
- トポロジカルソート
スパゲッティ (?) なソースコード
1:c
2:b
3:b
4:a
5:b
6:a
7:a
8:c
9:a
10:e
Current time: 2024年03月29日10時32分49秒
Last modified: 2014年05月11日15時10分17秒 (by laycrs)
Tags: Competitive_Programming HackerRank
トップページに戻る
Logged in as: unknown user (not login)