오른쪽의 NGE 수

난이도 쉽게
자주 묻는 질문 수행자 광신자 포카이트
배열 동적 프로그래밍 해시 스택조회수 83

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

올바른 문제에 대한 NGE의 수에서 우리는 정렬 a [] 크기 n 및 q 배열의 인덱스를 나타내는 쿼리 수. 각 쿼리에 대해 총 수를 인쇄합니다. 다음으로 큰 요소 맞습니다.

오른쪽의 NGE 수

입력

a [] = {3, 4, 2, 7, 5, 8, 10, 6}

q1 = 0

q2 = 5

산출 

4

1

입력 

a [] = {1, 2, 3, 4, 5, 6, 7}

q1 = 0

산출 

6

순진한 방법

암호알고리즘

  1. n 크기의 배열 a []를 초기화합니다.
  2. NGE를 계산하는 변수 c를 만들고 0으로 초기화합니다.
  3. lastEle 변수를 만들고 배열 a []의 값을 인덱스 q 즉 쿼리에 저장합니다.
  4. q + 1에서 n-1로 이동하여 현재 인덱스의 a [] 배열 값이 lastEle보다 큰지 확인하고 lastEle을 현재 인덱스의 배열 a [] 값으로 업데이트합니다. 개수를 늘립니다.
  5. 카운트를 인쇄하십시오.

오른쪽에있는 NGE의 수를 계산하는 C ++ 프로그램

#include <bits/stdc++.h> 
using namespace std; 
  
void count(int a[], int n, int q){ 
    int c = 0;
    int lastEle = a[q];
    
    for(int i=q+1; i<n; i++){
        if(a[i]>lastEle){
            lastEle = a[i];
            c++;
        }    
    }
    
    cout<<c<<endl;
} 
  
int main(){ 
    int a[] = {3, 4, 2, 7, 5, 8, 10, 6}; 
    int n = sizeof(a) / sizeof(a[0]); 
  
    count(a, n, 0); 
  
    count(a, n, 5); 
  
    return 0; 
}
4
1

오른쪽의 NGE 수를 계산하는 Java 프로그램

import java.util.*; 
  
class NGE{ 
  
    static void count(int a[], int n, int q){ 
        
        int c = 0;
        int lastEle = a[q];
        
        for(int i=q+1; i<n; i++){
            if(a[i]>lastEle){
                lastEle = a[i];
                c++;
            }    
        }
        
        System.out.println(c);
    } 
      
    public static void main(String args[]){ 
        int a[] = {3, 4, 2, 7, 5, 8, 10, 6}; 
        int n = a.length; 
      
        count(a, n, 0); 
      
        count(a, n, 5);
    } 
}
4
1

복잡성 분석

시간 복잡성 : O (n) 여기서 n은 배열 a []의 크기입니다.

보조 공간 : O (1) 우리는 일정한 추가 공간을 사용했기 때문입니다.

효율적인 방법

암호알고리즘

  1. 숫자를 포함하는 크기 n의 배열 a []와 동일한 크기의 dp 배열을 초기화합니다.
  2. n 크기의 배열 next []를 만들고 해당 요소를 0으로 설정합니다.
  3. 스택을 만들고 0을 밀어 넣으십시오.
  4. 1에서 n-1로 이동하고 스택이 비어 있지 않은 동안 스택의 맨 위와 같은 인덱스에있는 배열 a []의 값이 현재 인덱스의 배열 a []에있는 값보다 작은 지 확인하고 값을 업데이트합니다. 현재 인덱스로서 스택의 맨 위와 같은 인덱스의 다음 배열에서. 스택 상단을 팝합니다.
  5. 그렇지 않으면 루프를 끊으십시오.
  6. 스택의 현재 인덱스를 푸시합니다.
  7. 스택이 비어 있지 않은 동안 스택의 맨 위와 같은 인덱스에서 배열의 값을 -1로 업데이트하십시오. 스택 상단을 팝합니다.
  8. n-2를 0으로 이동하고 현재 인덱스에서 다음 배열의 값이 -1인지 확인하고 현재 인덱스에서 배열 dp의 값을 0으로 업데이트합니다. 그렇지 않으면 현재 인덱스에서 다음 배열의 값을 1 + dp [next [i]로 업데이트합니다. ].
  9. 각 쿼리는 i print dp [I]와 같습니다.

오른쪽에있는 NGE의 수를 계산하는 C ++ 프로그램

#include <bits/stdc++.h> 
using namespace std; 
  
void computeNext(int next[], int a[], int n){ 
    
    stack<int> s; 
  
    s.push(0); 
  
    for(int i = 1; i < n; i++){ 
  
        while(!s.empty()){ 
  
            int cur = s.top(); 
  
            if(a[cur] < a[i]){ 
                next[cur] = i; 
  
                s.pop(); 
            } 
  
            else{
                break;
            }    
        } 
  
        s.push(i); 
    } 
  
    while(!s.empty()){ 
  
        int cur = s.top(); 
  
        next[cur] = -1; 
  
        s.pop(); 
    } 
} 
  
void count(int a[], int dp[], int n){ 
     
    int next[n]; 
    memset(next, 0, sizeof(next)); 
  
    computeNext(next, a, n); 
  
    for(int i = n-2; i >= 0; i--){ 
  
        if(next[i] == -1){ 
            dp[i] = 0; 
        }    
  
        else{
            dp[i] = 1 + dp[next[i]]; 
        }    
    } 
} 
  
int answerQuery(int dp[], int index){ 
    return dp[index]; 
} 
  
int main(){ 
    int a[] = {3, 4, 2, 7, 5, 8, 10, 6}; 
    int n = sizeof(a) / sizeof(a[0]); 
  
    int dp[n]; 
  
    count(a, dp, n); 
  
    cout<<answerQuery(dp, 0)<<endl; 
  
    cout<<answerQuery(dp, 5)<<endl; 
  
    return 0; 
}
4
1

오른쪽의 NGE 수를 계산하는 Java 프로그램

import java.util.*; 
  
class NGE{ 
  
    static void computeNext(int next[], int a[], int n){ 
        
        Stack<Integer> s = new Stack<Integer>(); 
      
        s.push(0); 
      
        for(int i = 1; i < n; i++){ 
      
            while(s.size() > 0){ 
      
                int cur = s.peek(); 
      
                if(a[cur] < a[i]){ 
      
                    next[cur] = i; 
      
                    s.pop(); 
                } 
      
                else{
                    break;
                }    
            } 
      
            s.push(i); 
        } 
      
        while(s.size() > 0){ 
      
            int cur = s.peek(); 
      
            next[cur] = -1; 
      
            s.pop(); 
        } 
    } 
      
    static void count(int a[], int dp[], int n){ 
        
        int next[] = new int[n]; 
        for(int i = 0; i < n; i++){ 
            next[i] = 0; 
        }    
          
        computeNext(next, a, n); 
      
        for(int i = n-2; i >= 0; i--){ 
      
            if(next[i] == -1){ 
                dp[i] = 0; 
            }    
      
            else{
                dp[i] = 1 + dp[next[i]]; 
            }
        } 
    } 
      
    static int answerQuery(int dp[], int index){ 
        return dp[index]; 
    } 
      
    public static void main(String args[]){ 
        int a[] = {3, 4, 2, 7, 5, 8, 10, 6}; 
        int n = a.length; 
      
        int dp[] = new int[n]; 
      
        count(a, dp, n); 
      
        System.out.println(answerQuery(dp, 0)); 
      
        System.out.println(answerQuery(dp, 5)); 
    } 
}
4
1

복잡성 분석

시간 복잡성 : 모든 쿼리가 사전 계산으로 인해 일정한 시간이 걸리기 때문에 O (1).

보조 공간 : O (n) 여기서 n은 배열 a []의 크기입니다.

참조

균열 시스템 설계 인터뷰
Translate »