시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.
차례
문제 정책
“지정된 시퀀스의 양식 최소 수는 사용자에게 현 문자 'I'즉 증가 및 'D'즉 감소하는 문자의 패턴을 나타내는 길이 / 크기 n. 1-9의 고유 한 숫자로 주어진 패턴의 최소 숫자를 인쇄하십시오.
예를 들어 –
예
s = "DD"
3 2 1
설명 : 숫자는 음수가 될 수 없으므로 3을 첫 번째 숫자로 선택한 다음 계속해서 다음 숫자를 줄입니다.
s = "DIDI"
2 1 4 3 5
방법 1
암호알고리즘
- 문자열 s를 초기화합니다.
- 주어진 문자열 s를 순회하고 문자열의 현재 문자가 'I'와 같은지 확인하고 주어진 문자열에서 'D'와 같은 다음 연속 문자의 총 수를 계산합니다.
- 문자 'I'가 문자열의 첫 번째 문자 인 경우 1부터 시작하는 증가 패턴을 인쇄하고 그렇지 않으면 다음 숫자를 인쇄합니다.
- 주어진 문자열에서 'D'와 같은 다음 연속 문자에 대해 감소하는 패턴을 인쇄합니다.
- 마찬가지로, 문자열의 현재 문자가 'D'와 같은지 확인하고, 문자 'D'가 문자열의 첫 번째 문자인지 확인하고, 문자열의 모든 'D'를 계산하고 그에 따라 패턴을 인쇄합니다.
- 그렇지 않으면 마지막 항목을 1 씩 감소시킵니다.
복잡성 분석
시간 복잡성
O (n) 여기서 n은 주어진 문자열 s의 길이입니다.
공간 복잡성
O (n) 주어진 문자열의 문자를 저장하기 위해 공백을 사용했기 때문입니다.
암호
주어진 시퀀스에서 최소 수를 형성하는 C ++ 프로그램
#include <bits/stdc++.h>
using namespace std;
void FormMinNumber(string arr){
int curr_max = 0;
int last_entry = 0;
int j;
for(int i=0; i<arr.length(); i++){
int noOfNextD = 0;
switch(arr[i]){
case 'I':
j = i+1;
while (arr[j] == 'D' && j < arr.length()){
noOfNextD++;
j++;
}
if (i==0){
curr_max = noOfNextD + 2;
cout << " " << ++last_entry;
cout << " " << curr_max;
last_entry = curr_max;
}
else{
curr_max = curr_max + noOfNextD + 1;
last_entry = curr_max;
cout << " " << last_entry;
}
for (int k=0; k<noOfNextD; k++){
cout << " " << --last_entry;
i++;
}
break;
case 'D':
if (i == 0){
j = i+1;
while (arr[j] == 'D' && j < arr.length()){
noOfNextD++;
j++;
}
curr_max = noOfNextD + 2;
cout << " " << curr_max << " " << curr_max - 1;
last_entry = curr_max - 1;
}
else{
cout << " " << last_entry - 1;
last_entry--;
}
break;
}
}
cout << endl;
}
int main(){
string s = "IDID";
FormMinNumber(s);
return 0;
}
1 3 2 5 4
주어진 시퀀스에서 최소 수를 형성하는 Java 프로그램
class MinNum{
static void FormMinNumber(String arr){
int curr_max = 0;
int last_entry = 0;
int j;
for (int i = 0; i < arr.length(); i++){
int noOfNextD = 0;
switch (arr.charAt(i)){
case 'I':
j = i + 1;
while (j < arr.length() && arr.charAt(j) == 'D'){
noOfNextD++;
j++;
}
if (i == 0){
curr_max = noOfNextD + 2;
System.out.print(" " + ++last_entry);
System.out.print(" " + curr_max);
last_entry = curr_max;
}
else{
curr_max = curr_max + noOfNextD + 1;
last_entry = curr_max;
System.out.print(" " + last_entry);
}
for (int k = 0; k < noOfNextD; k++){
System.out.print(" " + --last_entry);
i++;
}
break;
case 'D':
if (i == 0){
j = i + 1;
while (j < arr.length()&&arr.charAt(j) == 'D'){
noOfNextD++;
j++;
}
curr_max = noOfNextD + 2;
System.out.print(" " + curr_max + " " + (curr_max - 1));
last_entry = curr_max - 1;
}
else{
System.out.print(" " + (last_entry - 1));
last_entry--;
}
break;
}
}
System.out.println();
}
public static void main(String[] args){
String s = "IDID";
FormMinNumber(s);
}
}
1 3 2 5 4
방법 2
암호알고리즘
- 문자열 s를 초기화합니다.
- 정수 유형의 벡터 v를 만듭니다.
- 주어진 문자열의 첫 번째 문자가 'I'인지 확인하고 벡터에서 1과 2를 누르고 사용 가능한 최소 숫자를 3으로 설정하고 'I'의 위치를 1로 설정합니다.
- 그렇지 않으면 벡터에서 2와 1을 누르고 사용 가능한 최소 수를 3으로 설정하고 'I'의 위치를 0으로 설정합니다.
- 1부터 시작하는 문자열을 순회하고 주어진 문자열의 현재 문자가 'I'인지 확인하고, 벡터에서 사용 가능한 최소 수를 푸시하고, 사용 가능한 최소 수를 증가시키고, 'I'의 위치를 현재 인덱스 + 1로 업데이트합니다.
- 그렇지 않으면 벡터의 현재 요소를 다시 벡터로 밀고 사용 가능한 최소 수를 늘립니다.
- 벡터를 인쇄하십시오.
복잡성 분석
시간 복잡성
O (n) 여기서 n은 주어진 문자열 s의 길이입니다.
공간 복잡성
O (n) 주어진 문자열의 문자를 저장하기 위해 공백을 사용했기 때문입니다.
암호
주어진 시퀀스에서 최소 수를 형성하는 C ++ 프로그램
#include <bits/stdc++.h>
using namespace std;
void FormMinNumber(string arr){
int min_avail = 1, pos_of_I = 0;
vector<int>v;
if (arr[0]=='I'){
v.push_back(1);
v.push_back(2);
min_avail = 3;
pos_of_I = 1;
}
else{
v.push_back(2);
v.push_back(1);
min_avail = 3;
pos_of_I = 0;
}
for (int i=1; i<arr.length(); i++){
if (arr[i]=='I'){
v.push_back(min_avail);
min_avail++;
pos_of_I = i+1;
}
else{
v.push_back(v[i]);
for (int j=pos_of_I; j<=i; j++){
v[j]++;
}
min_avail++;
}
}
for (int i=0; i<v.size(); i++){
cout << v[i] << " ";
}
cout << endl;
}
int main(){
string s = "IDID";
FormMinNumber(s);
return 0;
}
1 3 2 5 4
주어진 시퀀스에서 최소 수를 형성하는 Java 프로그램
import java.util.*;
class MinNum{
static void FormMinNumber(String arr){
int min_avail = 1, pos_of_I = 0;
ArrayList<Integer> al = new ArrayList<>();
if (arr.charAt(0) == 'I'){
al.add(1);
al.add(2);
min_avail = 3;
pos_of_I = 1;
}
else{
al.add(2);
al.add(1);
min_avail = 3;
pos_of_I = 0;
}
for (int i = 1; i < arr.length(); i++){
if (arr.charAt(i) == 'I'){
al.add(min_avail);
min_avail++;
pos_of_I = i + 1;
}
else{
al.add(al.get(i));
for (int j = pos_of_I; j <= i; j++) {
al.set(j, al.get(j) + 1);
}
min_avail++;
}
}
for (int i = 0; i < al.size(); i++) {
System.out.print(al.get(i) + " ");
}
System.out.println();
}
public static void main(String[] args){
String s = "IDID";
FormMinNumber(s);
}
}
1 3 2 5 4
방법 3
암호알고리즘
- 문자열 s를 초기화합니다.
- 스택 데이터 구조를 만듭니다.
- 문자열을 순회하고 매 반복마다 스택의 현재 인덱스 + 1을 푸시합니다. 현재 인덱스가 문자열의 길이와 같거나 문자열의 현재 문자가 'I'와 같은 경우 Chcek를 사용하는 반면 스택이 비어 있지 않은 경우 스택의 모든 요소를 문자열로 연결합니다.
- 문자열을 인쇄하십시오.
복잡성 분석
시간 복잡성
O (n) 여기서 n은 주어진 문자열 s의 길이입니다.
공간 복잡성
O (n) 주어진 문자열의 문자를 저장하기 위해 공백을 사용했기 때문입니다.
암호
주어진 시퀀스에서 최소 수를 형성하는 C ++ 프로그램
#include <bits/stdc++.h>
using namespace std;
void FormMinNumber(string arr){
string result;
stack<int> stk;
for (int i = 0; i <= arr.length(); i++){
stk.push(i + 1);
if (i == arr.length() || arr[i] == 'I'){
while (!stk.empty()){
result += to_string(stk.top());
result += " ";
stk.pop();
}
}
}
cout << result << endl;
}
int main(){
string s = "IDID";
FormMinNumber(s);
return 0;
}
1 3 2 5 4
주어진 시퀀스에서 최소 수를 형성하는 Java 프로그램
import java.util.*;
class MinNum{
static void FormMinNumber(String arr){
String result = "";
Stack<Integer> stk = new Stack<Integer>();
for (int i = 0; i <= arr.length(); i++) {
stk.push(i + 1);
if (i == arr.length() || arr.charAt(i) == 'I') {
while (!stk.empty()) {
result += String.valueOf(stk.peek());
result += " ";
stk.pop();
}
}
}
System.out.println(result);
}
public static void main(String[] args){
String s = "IDID";
FormMinNumber(s);
}
}
1 3 2 5 4
방법 4
암호알고리즘
- 초기화 현 s.
- 주어진 문자열의 길이가 9보다 크거나 같은지 확인하고 -1을 인쇄 한 다음 반환합니다.
- 주어진 문자열을 순회하고 현재 색인이 문자열의 길이와 같거나 문자열의 현재 문자가 'I'인지 확인하고, 현재 색인에서 다시 순회 – 1에서 0으로 현재 색인의 결과를 업데이트합니다. + 1.
- 현재 인덱스가 0보다 크거나 같고 문자열의 현재 문자가 'I'와 같으면 루프를 중단합니다.
- 결과를 인쇄합니다.
복잡성 분석
시간 복잡성
O (n) 여기서 n은 주어진 문자열 s의 길이입니다.
공간 복잡성
O (n) 주어진 문자열의 문자를 저장하기 위해 공백을 사용했기 때문입니다.
암호
주어진 시퀀스에서 최소 수를 형성하는 C ++ 프로그램
#include <bits/stdc++.h>
using namespace std;
string FormMinNumber(string arr){
int n = arr.length();
if(n >= 9){
return "-1";
}
string result(n+1, ' ');
int count = 1;
for (int i = 0; i <= n; i++){
if (i == n || arr[i] == 'I'){
for (int j = i - 1 ; j >= -1 ; j--){
result[j + 1] = '0' + count++;
if(j >= 0 && arr[j] == 'I'){
break;
}
}
}
}
return result;
}
int main(){
string s = "IDID";
cout<<FormMinNumber(s);
return 0;
}
13254
주어진 시퀀스에서 최소 수를 형성하는 Java 프로그램
import java.util.*;
class MinNum{
static String FormMinNumber(String arr){
int n = arr.length();
if (n >= 9){
return "-1";
}
char result[] = new char[n + 1];
int count = 1;
for (int i = 0; i <= n; i++){
if (i == n || arr.charAt(i) == 'I'){
for (int j = i - 1; j >= -1; j--){
result[j + 1] = (char) ((int) '0' + count++);
if (j >= 0 && arr.charAt(j) == 'I'){
break;
}
}
}
}
return new String(result);
}
public static void main(String[] args){
String s = "IDID";
System.out.println(FormMinNumber(s));
}
}
13254
