Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.
Mündəricat
Problem bəyanat
Alien Dictionary LeetCode Solution – İngilis əlifbasından istifadə edən yeni bir yad dil var. Bununla belə, məktublar arasındakı sıra sizə məlum deyil.
Sizə sətirlərin siyahısı verilir words sətirlərin daxil olduğu yad dilin lüğətindən words var leksikoqrafik olaraq sıralanır bu yeni dilin qaydaları ilə.
Qayıtmaq sıralanmış yeni yad dildə unikal hərflər silsiləsi leksikoqrafik cəhətdən artan sıra yeni dilin qaydaları ilə. Çözüm yoxdursa, geri qayıdın "". Bir neçə həll yolu varsa, geri qaytarın onlardan hər hansı biri.
Bir simli s is leksikoqrafik cəhətdən daha kiçikdir simdən daha çox t birinci hərfdə fərqlənirlərsə, hərf içərisindədir s daxil olan hərfdən əvvəl gəlir t yad dildə. Əgər birinci min(s.length, t.length) onda hərflər eynidir s yalnız və yalnız o halda kiçikdir s.length < t.length.
misal
Test işi 1:
Input:
sözlər = [“wrt”, “wrf”, “er”, “ett”, “rftt”]
Çıxış:
"vertf"
Test işi 2:
Input:
sözlər = [“z”, “x”, “z”]
Çıxış:
""
Izahat
i) Birinci sınaq vəziyyətində “wertf” düzgün sətir ola bilər.
ii) İkinci sınaq vəziyyətində sifariş etibarsızdır, ona görə də “” qaytarın.
Yanaşma:
Əvvəlcə problem ifadəsini anlayaq
- sözlər sıralanır leksikoqrafik cəhətdən yəni əgər
W[i]əvvəl lüğətdə görünürW[j]üçüni < j. - Qeyd edək ki,
individual words are not sorted. Əgərabcdeəvvəl görünürabpqrstbu o demək deyilbəvvəl görünüra.
Qeyd edilməli əsas şeylər:
1. Sözlər lüğətində hər hansı iki ardıcıl söz üçün sıra birinci qeyri-adi işarəyə baxmaqla müəyyən edilir.
2. Qeyri-adi simvoldan sonra gələn simvolları heç bir ardıcıllıqla yekunlaşdırmaq üçün etibar etmək olmaz. Səbəb sözlər arasındakı ardıcıllığın sırf ilk uyğunsuzluq simvoluna əsaslanaraq qərarlaşdırıldığı üçün ondan sonrakı hər hansı simvol yalnız tam sözü təşkil edir.
3. Hər hansı bir sözdə görünən ardıcıl simvolların sıra ilə heç bir əlaqəsi yoxdur, lakin onlar yalnız tam sözü yaratmaq üçün oradadırlar.
Yanaşma:
1. Qrafik yaradın: Yuxarıdakı nöqtələrdən istifadə edərək, biz ardıcıl söz cütləri arasında təkrar edirik və kənarlar yaratmağa çalışırıq.
2. Topoloji Sort: Bu, DFS və ya istifadə etməklə edilə bilər BFS. Mən burada BFS ilə getməyə qərar verdim
Kənar hallarda
["abc", "ab"]– etibarlı lüğət deyil, əgərW[i] < W[j]sonra lüğətdəW[j]ola bilməzprefixofW[i]. belə ki, bu halda sadəcə olaraq boş bir sətir qaytarın.["a", "b", "a"]– burada bu girişdə,a < bvəb < aHansı bir dövrü. lüğətdə dövr ola bilməz.
Yadplanetli lüğəti üçün kod
C ++ Proqramı
class Solution {
public:
// Finds the topological order of a directed Acyclic graph
string topologicalSortBFS(unordered_map<char, unordered_set<char>> &g) {
unordered_map<char, int> indegree;
queue<char> q;
// topological order
string order;
// Compute the indegree of each node
for(auto u: g) {
char src = u.first;
for(auto neighbor: g[src])
++indegree[neighbor];
}
// if current has no dependency, add and mark as visited
for(auto u: g) {
char src = u.first;
if(!indegree[src]) {
q.emplace(src);
}
}
// BFS traversal wrt to indegree of each node
while(!q.empty()) {
auto curr = q.front();
q.pop();
order += curr;
// reduce the indegree of its neighbors
for(auto neighbor: g[curr]) {
--indegree[neighbor];
if(!indegree[neighbor])
q.emplace(neighbor);
}
}
return order.size() < g.size() ? "" : order;
}
string alienOrder(vector<string>& words) {
// create a graph
// To create a graph using the lexographic order,
// we need to look at the consecutive word pairs and
// within the common length check for diff chars at the same
// index position, each unequal pair is a directed edge coming
// from words[i][j] to words[i+1][j]
unordered_map<char, unordered_set<char>> g;
// initialize the graph with nodes req
for(auto &word: words)
for(char &ch: word)
if(!g.count(ch))
g[ch] = unordered_set<char>();
// Imp: Add all the seen chars to graph even with 0 edges
for(int w = 0; w + 1 < words.size(); w++) {
int common_len = min(words[w].size(), words[w+1].size());
// check if the lexographic order is being followed or not
// P.S I dont think this case is even valid acc to problem description
// Eg: ["abc", "ab"] -> Invalid
if(words[w+1].size() < words[w].size()
&& words[w].substr(0, common_len) == words[w+1])
return "";
for(int i = 0; i < common_len; i++) {
// prevent self loop
char src = words[w][i], dst = words[w+1][i];
// If current pos has diff chars, then make an edge and
// break since, the current word ordering was due this positional char
// change and anything beyond this might not follow actual order.
if(src != dst) {
g[src].emplace(dst);
break;
}
}
}
string order = topologicalSortBFS(g);
return order;
}
};
Java Proqramı
class Solution {
public String alienOrder(String[] words) {
Map<Character, Set<Character>> dict = new HashMap<>();
Map<Character, Boolean> visited = new HashMap<>();
// add character to visited map, mark all of them as unvisited
for (String str: words) {
for (char ch: str.toCharArray()) {
visited.put(ch, false);
}
}
//
for (int i = 0; i < words.length-1; i++) {
if(!fillDict(dict, words[i], words[i+1])) {
// invalid input, ex:- ab,abc is not a valid dictionary word
return "";
}
}
StringBuilder builder = new StringBuilder();
for (char ch: visited.keySet()) {
if (!visited.get(ch)) {
// do the topological sorting from each unvisited dictionary character
if (!topological(dict, ch, visited, new HashSet<>(), builder)) {
// loop detected. topological sort can not be performed in graph with cycle
return "";
}
}
}
return builder.reverse().toString();
}
private boolean topological(Map<Character, Set<Character>> dict, char ch,
Map<Character, Boolean> visited,
Set<Character> dfsStack, StringBuilder builder) {
if (dfsStack.contains(ch)) {
// oops!! loop detected
return false;
}
if (visited.get(ch)) {
return true;
}
visited.put(ch, true);
dfsStack.add(ch);
for (char c : dict.getOrDefault(ch, new HashSet<>())) {
if (!topological(dict, c, visited, dfsStack, builder)) {
return false;
}
}
builder.append(ch);
dfsStack.remove(ch);
return true;
}
private boolean fillDict(Map<Character, Set<Character>> dict, String a, String b) {
for (int i = 0; i < Math.min(a.length(), b.length()); i++) {
if (a.charAt(i) != b.charAt(i)) {
dict.computeIfAbsent(a.charAt(i), x -> new HashSet<>()).add(b.charAt(i));
return true;
}
}
// minimum word is prefix of larger word, make sure word with less length comes before larger word
// why? because if one string is prefix of another then prefix must come before string for example,
// we are here becasue a,b = "abc" or "ab", since a is lexicographically smaller than b then a must
// be "ab" because "abc" can never come before "ab".
return a.length() <= b.length();
}
}
Alien Dictionary LeetCode Həlli üçün Mürəkkəblik Təhlili
Zamanın mürəkkəbliyi: O(V + E)
Kosmik Mürəkkəblik: Qrafik yaratmaq üçün O(V + E).
