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.
Etibarlı mötərizədə sim problem olan bir simli verdik '(", ")'və'*', sətrin tarazlı olub olmadığını yoxlayın.'*'ilə əvəz edilə bilər'(',')'və ya boş bir simli.
Mündəricat
Nümunələr
Input
"()"
Buraxılış
doğru
Input
"*)"
Buraxılış
doğru
Input
"(*))"
Buraxılış
doğru
Valid Parentez Simli üçün sadəlövh yanaşma
"*'üç mümkün dəyər götürə bilər, bütün bu dəyərləri sınayın, əgər balanslaşdırılmış bir ciziq varsa, cari sətir etibarlıdır.
- Verilən simli keçin.
- Rekursiv şəkildə dəyişdirin '*'ilə'(',')'və boş simli.
- Hər hansı bir birləşmə balanslaşdırılmış bir simdirsə, verilmiş simli balanslaşdırılmışdır.
Bir nümunəyə baxaq, “*)”,
Valid Parentez Simli üçün JAVA Kodu
public class ValidParanthesisString {
private static boolean ans;
private static boolean isValid(String str) {
// Initialise ans as false
ans = false;
// Recur and try all the combinations possible for the string
recurStr(new StringBuilder(str), 0);
return ans;
}
private static void recurStr(StringBuilder str, int i) {
if (i == str.length()) {
// check validity of the string, as it is fully formed when i = str.length()
ans |= checkValidity(str);
} else if (str.charAt(i) == '*') {
// Replace * with (
str.setCharAt(i, '(');
recurStr(str, i + 1);
// Replace * with )
str.setCharAt(i, ')');
recurStr(str, i + 1);
// replace * with empty string
str.setCharAt(i, ' ');
recurStr(str, i + 1);
} else {
// If the current character is not * continue for next character
recurStr(str, i + 1);
}
}
// Function to check if given string is balanced or not
private static boolean checkValidity(StringBuilder str) {
int bal = 0;
for (int i = 0; i < str.length(); i++) {
if (str.charAt(i) == '(') {
bal++;
} else if (str.charAt(i) == ')') {
bal--;
}
if (bal < 0) {
break;
}
}
return bal == 0;
}
public static void main(String[] args) {
// Example 1
String str = "()";
System.out.println(isValid(str));
// Example 2
str = "(*)";
System.out.println(isValid(str));
// Example 3
str = "(*))";
System.out.println(isValid(str));
}
}
Valid Parentez Simli üçün C ++ Kodu
#include <iostream>
using namespace std;
bool ans;
// Function to check if given string is balanced or not
bool checkValidity(string str) {
int bal = 0;
for (int i = 0; i < str.size(); i++) {
if (str[i] == '(') {
bal++;
} else if (str[i] == ')') {
bal--;
}
if (bal < 0)
break;
}
return (bal == 0);
}
void recurStr(string str, int i) {
if (i == str.size()) {
// check validity of the string, as it is fully formed when i = str.length()
ans |= checkValidity(str);
} else if (str[i] == '*') {
// Replace * with (
str[i] = '(';
recurStr(str, i + 1);
// Replace * with )
str[i] = ')';
recurStr(str, i + 1);
// replace * with empty string
str[i] = ' ';
recurStr(str, i + 1);
} else {
// If the current character is not * continue for next character
recurStr(str, i + 1);
}
}
bool isValid(string str) {
// Initialise ans as false
ans = false;
// Recur and try all the combinations possible for the string
recurStr(str, 0);
return ans;
}
int main() {
string str = "()";
if (isValid(str)) {
cout<<"true"<<endl;
} else {
cout<<"false"<<endl;
}
// Example 2
str = "(*)";
if (isValid(str)) {
cout<<"true"<<endl;
} else {
cout<<"false"<<endl;
}
// Example 3
str = "(*))";
if (isValid(str)) {
cout<<"true"<<endl;
} else {
cout<<"false"<<endl;
}
return 0;
}
true true true
Mürəkkəblik təhlili
Zaman Mürəkkəbliyi = O (n * 3n)
Kosmik Mürəkkəblik = O (3n), rekursiyaya görə
burada n - verilən sətirdəki simvolların sayı.
Valid Parentez Simli üçün optimal yanaşma
Verilən sətrin hər bir simvolu üçün bu nöqtəyə qədər minimum və maksimum açıq mötərizə sayın.
- Açıq bir mötərizə minimum və maksimum dəyəri 1 artırır.
- Yaxın bir mötərizə minimum və maksimum dəyəri 1 azaldır, aşağı dəyər mənfi ola bilməz.
- Ulduz (*) minimum dəyəri 1 azaldır və maksimum dəyəri 1 artırır.
- Maksimum dəyər istənilən nöqtədə mənfi olursa, sətir balanslaşdırılmır.
Açıq mötərizənin aşağı dəyəri 0 olarsa, sətir etibarlıdır.
misal
Sətri düşünək “(***)"
- '(': Minimum və maksimumu 1 {İndeks 0} artırır (minimum = 1, maksimum = 1)
- '*': Minimumu 1-ə endirir və maksimumu 1-ə artırır {İndeks 1, 2 və 3} (minimum = 0 və maksimum = 4)
- '): Minimum və maksimumu 1 {İndeks 4} azaldır (minimum = 0 və maksimum = 3)
keçidin sonunda minimum 0, buna görə də sətir etibarlıdır.
JAVA Kodu
public class ValidParanthesisString {
private static boolean isValid(String str) {
// Initialise minimum and maximum as 0
int minimum = 0, maximum = 0;
for (int i = 0; i < str.length(); i++) {
if (str.charAt(i) == '(') {
// Open bracket increases minimum and maximum by 1
minimum++;
maximum++;
} else if (str.charAt(i) == ')') {
// Close bracket decreases minimum and maximum by 1
minimum--;
maximum--;
} else {
// asterisk(*) decreases minimum by 1 and increases maximum by 1
minimum--;
maximum++;
}
// If maximum becomes less than 0, string is not balanced
if (maximum < 0)
return false;
// minimum cannot be less than 0
minimum = Math.max(minimum, 0);
}
// If minimum is 0, then string is balanced
return minimum == 0;
}
public static void main(String[] args) {
// Example 1
String str = "()";
System.out.println(isValid(str));
// Example 2
str = "(*)";
System.out.println(isValid(str));
// Example 3
str = "(*))";
System.out.println(isValid(str));
}
}
C ++ kodu
#include <iostream>
using namespace std;
bool isValid(string str) {
// Initialise minimum and maximum as 0
int minimum = 0, maximum = 0;
for (int i = 0; i < str.size(); i++) {
if (str[i] == '(') {
// Open bracket increases minimum and maximum by 1
minimum++;
maximum++;
} else if (str[i] == ')') {
// Close bracket decreases minimum and maximum by 1
minimum--;
maximum--;
} else {
// asterisk(*) decreases minimum by 1 and increases maximum by 1
minimum--;
maximum++;
}
// If maximum becomes less than 0, string is not balanced
if (maximum < 0)
return false;
// minimum cannot be less than 0
minimum = std::max(minimum, 0);
}
// If minimum is 0, then string is balanced
return (minimum == 0);
}
int main() {
string str = "()";
if (isValid(str)) {
cout<<"true"<<endl;
} else {
cout<<"false"<<endl;
}
// Example 2
str = "(*)";
if (isValid(str)) {
cout<<"true"<<endl;
} else {
cout<<"false"<<endl;
}
// Example 3
str = "(*))";
if (isValid(str)) {
cout<<"true"<<endl;
} else {
cout<<"false"<<endl;
}
return 0;
}
true true true
Valid Parentez Simli üçün Mürəkkəblik Analizi
Zaman Mürəkkəbliyi = O (n)
Kosmik Mürəkkəblik = O (1)
burada n - verilən sətirdəki simvolların sayı.
