주어진 시퀀스에서 양식 최소 번호

난이도 중급
자주 묻는 질문 아마존 골드만 삭스
배열 스택 조회수 84

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

문제 정책

“지정된 시퀀스의 양식 최소 수는 사용자에게 문자 'I'즉 증가 및 'D'즉 감소하는 문자의 패턴을 나타내는 길이 / 크기 n. 1-9의 고유 한 숫자로 주어진 패턴의 최소 숫자를 인쇄하십시오.

예를 들어 –

주어진 시퀀스에서 양식 최소 번호

s = "DD"
3 2 1

설명 : 숫자는 음수가 될 수 없으므로 3을 첫 번째 숫자로 선택한 다음 계속해서 다음 숫자를 줄입니다.

s = "DIDI"
2 1 4 3 5

방법 1

암호알고리즘

  1. 문자열 s를 초기화합니다.
  2. 주어진 문자열 s를 순회하고 문자열의 현재 문자가 'I'와 같은지 확인하고 주어진 문자열에서 'D'와 같은 다음 연속 문자의 총 수를 계산합니다.
  3. 문자 'I'가 문자열의 첫 번째 문자 인 경우 1부터 시작하는 증가 패턴을 인쇄하고 그렇지 않으면 다음 숫자를 인쇄합니다.
  4. 주어진 문자열에서 'D'와 같은 다음 연속 문자에 대해 감소하는 패턴을 인쇄합니다.
  5. 마찬가지로, 문자열의 현재 문자가 'D'와 같은지 확인하고, 문자 'D'가 문자열의 첫 번째 문자인지 확인하고, 문자열의 모든 'D'를 계산하고 그에 따라 패턴을 인쇄합니다.
  6. 그렇지 않으면 마지막 항목을 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

암호알고리즘

  1. 문자열 s를 초기화합니다.
  2. 정수 유형의 벡터 v를 만듭니다.
  3. 주어진 문자열의 첫 번째 문자가 'I'인지 확인하고 벡터에서 1과 2를 누르고 사용 가능한 최소 숫자를 3으로 설정하고 'I'의 위치를 ​​1로 설정합니다.
  4. 그렇지 않으면 벡터에서 2와 1을 누르고 사용 가능한 최소 수를 3으로 설정하고 'I'의 위치를 ​​0으로 설정합니다.
  5. 1부터 시작하는 문자열을 순회하고 주어진 문자열의 현재 문자가 'I'인지 확인하고, 벡터에서 사용 가능한 최소 수를 푸시하고, 사용 가능한 최소 수를 증가시키고, 'I'의 위치를 ​​현재 인덱스 + 1로 업데이트합니다.
  6. 그렇지 않으면 벡터의 현재 요소를 다시 벡터로 밀고 사용 가능한 최소 수를 늘립니다.
  7. 벡터를 인쇄하십시오.

복잡성 분석

시간 복잡성

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

암호알고리즘

  1. 문자열 s를 초기화합니다.
  2. 스택 데이터 구조를 만듭니다.
  3. 문자열을 순회하고 매 반복마다 스택의 현재 인덱스 + 1을 푸시합니다. 현재 인덱스가 문자열의 길이와 같거나 문자열의 현재 문자가 'I'와 같은 경우 Chcek를 사용하는 반면 스택이 비어 있지 않은 경우 스택의 모든 요소를 ​​문자열로 연결합니다.
  4. 문자열을 인쇄하십시오.

복잡성 분석

시간 복잡성

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

암호알고리즘

  1. 초기화 s.
  2. 주어진 문자열의 길이가 9보다 크거나 같은지 확인하고 -1을 인쇄 한 다음 반환합니다.
  3. 주어진 문자열을 순회하고 현재 색인이 문자열의 길이와 같거나 문자열의 현재 문자가 'I'인지 확인하고, 현재 색인에서 다시 순회 – 1에서 0으로 현재 색인의 결과를 업데이트합니다. + 1.
  4. 현재 인덱스가 0보다 크거나 같고 문자열의 현재 문자가 'I'와 같으면 루프를 중단합니다.
  5. 결과를 인쇄합니다.

복잡성 분석

시간 복잡성

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
균열 시스템 설계 인터뷰
Translate »