가장 가까운 왼쪽 및 오른쪽 작은 요소 간의 최대 차이 찾기-TutorialCup

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

Twitter Facebook 링크드인 버퍼 레딧 텀블러

차례

문제 정책

주어진 정렬 크기 n의 a []. "가장 가까운 왼쪽과 오른쪽 작은 요소의 최대 차이 찾기"문제는 함수를 생성하도록 요청합니다. 따라서 왼쪽에 가장 가까운 작은 요소와 오른쪽에 가장 가까운 작은 요소를 각각 나타내는 left [] 및 right [] 배열 두 개를 만듭니다. 그런 다음 왼쪽 [i] – 오른쪽 [i] 배열의 절대 차이의 최대 값을 찾습니다.

핀

예

a[ ] = {2, 1, 8}

a[ ] = {2, 4, 8, 7, 7, 9, 3}

가장 가까운 왼쪽 및 오른쪽 작은 요소 간의 최대 차이를 찾는 알고리즘

초기화 정렬 크기 n의 a [].
배열을 받아들이는 왼쪽과 오른쪽 배열의 작은 요소를 찾는 함수, 크기 및 매개 변수로 더 작은 요소를 저장할 배열을 만듭니다.
만들기 스택 정수 유형의 데이터 구조.
배열 a []를 통과합니다. 스택이 비어 있지 않고 스택 맨 위에있는 요소가 현재 인덱스의 배열 a []에있는 요소보다 크거나 같으면 스택의 tp에있는 요소를 팝합니다.
스택이 비어 있지 않은지 확인하고 스택의 맨 위에있는 요소로 더 작은 요소에 대한 배열의 현재 인덱스 값을 업데이트하십시오. 그렇지 않으면 더 작은 요소에 대해 배열의 현재 인덱스 값을 0으로 업데이트합니다.
스택에있는 배열 a []의 현재 인덱스에 값을 푸시 / 삽입합니다.
마찬가지로 배열과 크기를 매개 변수로 받아들이는 차이의 최대 값을 찾기 위해 다른 함수를 만듭니다.
가장 가까운 작은 요소를 왼쪽에 저장하기 위해 크기 n의 left [] 배열을 만듭니다. 주어진 배열, 크기 및 왼쪽 배열을 매개 변수로 사용하여 더 작은 요소에 대한 함수를 호출하십시오.
마찬가지로 오른쪽에 가장 가까운 작은 요소를 저장하기 위해 n 크기의 배열 right []를 만듭니다. 원래 배열 a []를 반대로하고 주어진 배열, 크기, 오른쪽 배열을 매개 변수로 사용하여 더 작은 요소에 대한 함수를 호출합니다.
0에서 n-1로 이동하여 좌우 배열의 절대 차이의 최대 값을 찾습니다.
결과를 인쇄하십시오.

암호

가장 가까운 왼쪽 및 오른쪽 작은 요소 간의 최대 차이를 찾는 C ++ 프로그램

#include<bits/stdc++.h> 
using namespace std; 
  
void SmallerElement(int a[], int n, int SE[]){ 
    stack<int>S; 
  
    for(int i=0; i<n; i++){ 
        
        while(!S.empty() && S.top() >= a[i]){ 
            S.pop(); 
        }
  
        if(!S.empty()){ 
            SE[i] = S.top();
        }
  
        else{
            SE[i] = 0;
        }
  
        S.push(a[i]); 
    } 
} 
  
int findMaxDiff(int a[], int n){ 
    int left[n]; 
  
    SmallerElement(a, n, left); 
  
    int right[n]; 
    
    reverse(a, a + n); 
    SmallerElement(a, n, right); 
  
    int result = -1; 
    for(int i=0 ; i< n ; i++){ 
        result = max(result, abs(left[i] - right[n-1-i]));
    }
   
    return result; 
} 
  
int main(){ 
    int a[] = {2, 4, 8, 7, 7, 9, 3}; 
    int n = sizeof(a)/sizeof(a[0]);
    
    cout << findMaxDiff(a, n) << endl; 
    
    return 0; 
}

가장 가까운 왼쪽 및 오른쪽 작은 요소 간의 최대 차이를 찾는 Java 프로그램

import java.util.*; 
  
class MaximumOfDifference{ 
  
    static void SmallerElement(int a[], int n, int SE[]){ 
        
        Stack<Integer> S = new Stack<>(); 
  
        for(int i = 0; i < n; i++){ 
            
            while(!S.empty() && S.peek() >= a[i]){ 
                S.pop(); 
            } 
  
            if(!S.empty()){ 
                SE[i] = S.peek(); 
            }  
            
            else{ 
                SE[i] = 0; 
            } 
  
            S.push(a[i]); 
        } 
    } 
  
    static int findMaxDiff(int a[], int n){ 
        int[] left = new int[n]; 
  
        SmallerElement(a, n, left); 
  
        int[] right = new int[n]; 
        
        reverse(a); 
        SmallerElement(a, n, right); 
  
        int result = -1; 
        for(int i = 0; i < n; i++){ 
            result = Math.max(result, Math.abs(left[i] - right[n - 1 - i])); 
        } 
 
        return result; 
    } 
  
    static void reverse(int a[]){ 
        int i, k, n = a.length, t; 
        
        for(i = 0; i < n / 2; i++){ 
            t = a[i]; 
            a[i] = a[n - i - 1]; 
            a[n - i - 1] = t; 
        } 
    } 
      
    public static void main(String args[]){ 
        int a[] = {2, 4, 8, 7, 7, 9, 3}; 
        int n = a.length; 
        
        System.out.println(findMaxDiff(a, n)); 
    } 
}