Bilgisayar temizliği ve organizasyonu işlerine bulaştım. Arşivimden
çıkan bir problemi paylaşmak istiyorum.
Kim olduğunu hatırlamamakla beraber IBM olabilir, kodlama mülakatında
aşağıdaki problemi sormuştu.
Size N elemanlı bir string dizisi veriliyor.
Sizin amacınız ise her kelimenin son harfinin bir sonraki kelimenin
ilk harfi olacak şekilde N elemanlı bir döngü bulmanız ve bu döngüyü
cevap olarak ekrana bastırmanız.
1
2
| arr = [ "ab", "az", "ba", "za"];
// Dogru konfigurasyonu ab -> ba -> az -> za -> ab;
|
Bu problem literatürde hamiltonian cycle olarak geçiyor. Bir vertexten
başlayıp tüm vertexleri sadece bir defa gezerek başladığınız noktaya
geliyorsanız buna hamilton cycle deniyor.
Mülakat sırasında doğru implementasyonu yapamamıştım. Backtracking
kısmını unuttuğum için segfault alarak elenmeyi garantiledim.
Mülakattan sonra salim kafayla oturup tekrar çözdüm. Basitçe dfs +
backtracking ile çözülüyormuş. Açıklamaları comment olarak ekledim.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
| #include <bits/stdc++.h>
using namespace std;
int isValidNextVertex(vector<vector<int>>& G, vector<int>& P, int v, int pos) {
// Bir once eklenen vertex in komsusu degilse bizim isimize yaramaz.
if (G[P[pos - 1]][v] == 0)
return 0;
// Vertex hali hazirda path e eklendiyse bizim isimize yaramaz.
for (int i = 0; i < pos; i++)
if (P[i] == v)
return 0;
return 1;
}
int hamiltonian(vector<vector<int>>& G, vector<int>& P, int n) {
// Turumuz bittiyse, buldugumuz son elemandan ilk elemana bir yol olup olmadigina bakalim.
if (n == G.size())
return G[P[n - 1]][P[0]] == 1;
for (int i = 1; i < G.size(); i++) {
if (isValidNextVertex(G, P, i, n)) {
P[n] = i; // vertexi yola ekleyelim.
if (hamiltonian(G, P, n + 1))
return 1;
P[n] = -1; // backtrack, ayni arama uzayina tekrar girmemek icin.
}
}
return false;
}
vector<int> findPath(vector<string>& words) {
int n = words.size();
vector<vector<int>> G(n, vector<int> (n, 0)); // komsuluk matrisi
vector<int> P(n, -1); // Takip edeceğimiz vertexlerin idleri
P[0] = 0; // ilk dugum olarak 0 dan baslasin.
// Graphımızı oluşturalım.
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
G[i][j] = words[i][words[i].size() - 1] == words[j][0];
if (hamiltonian(G, P, 1))
return P;
return vector<int>(0);
}
int main() {
vector<string> words = { "esra", "tahir", "mahmut", "faruk", "raziye", "kerim", "akif" };
vector<int> path = findPath(words);
int size = path.size();
if (size == 0) {
cout << "NO" << endl;
return 0;
}
cout << "YES" << endl;
for (int i = 0; i < size; i++){
if (i < size - 1) cout << words[path[i]] << " ";
else cout << words[path[i]];
}
return 0;
}
|