이진 배열의 하위 배열에 대한 XNUMX 진수 값 쿼리

난이도 중급
자주 묻는 질문 아마존 구글
배열 쿼리 문제조회수 58

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

주어진 이진 배열에있는 이진 배열의 하위 배열에 대한 XNUMX 진수 값에 대한 쿼리를 작성합니다. 문제 설명은 이진 배열의 범위를 사용하여 형성된 십진수를 찾아야합니다.

입력:

arr [] = {1, 0, 1, 1, 0, 0, 1, 1}

쿼리 (1, 5)

쿼리 (3, 6)

출력:

12 9

설명 :

1에서 5까지의 범위 (01100)를 나타내는 이진수로 구성된 출력은 12입니다.

이렇게 형성된 출력은 이진수 3 ~ 6 (1001) 범위 내에서 나타내는 것은 9입니다.

이진 배열의 하위 배열의 XNUMX 진수 값에 대한 쿼리

 

이진 배열의 하위 배열의 XNUMX 진수 값에 대한 쿼리 알고리즘

  1. prefixArray로 배열을 만들고 0으로 초기화합니다.
  2. prefixArray의 마지막 요소를 정렬 주어진.
  3. 배열의 오른쪽에서 왼쪽으로 배열을 순회하고 주어진 배열 요소의 곱과 2의 거듭 제곱을 저장하고 prefixArray를 추가합니다.
  4. 쿼리를 가져오고 right 값이 주어진 배열의 마지막 인덱스 값과 같지 않으면 prefixArray [left]와 prefixArray [right + 1]의 차이를 나눈 값과 1과 오른쪽의 시프트 연산을 반환합니다. 배열의 인덱스.
  5. Else는 prefixArray [left]의 나눗셈과 배열의 1과 오른쪽 인덱스의 시프트 연산을 반환합니다.

이진 배열 하위 배열의 XNUMX 진수 값 쿼리에 대한 설명

이진 배열의 하위 배열의 십진수 값에 대한 쿼리 문제에 관해서는 이진 배열 그리고 왼쪽 인덱스와 오른쪽 인덱스로 인덱스 범위. 주어진 범위로 형성된 주어진 이진수의 십진수 형식을 찾으십시오. 범위를 지정한 쿼리가 제공됩니다. 범위와 함께 이진수로 구성된 십진수를 찾아야합니다. 이를 위해 배열 길이와 동일한 크기의 추가 배열을 만들 것입니다. 우리는 그 배열을 구축 할 것입니다. 또는 우리가 그 배열을 전처리하고 그 안에 몇 가지 값을 채워서 일정한 시간에 쿼리를 풀 수 있다고 말할 수 있습니다.

배열을 통과하되 배열을 통과하기 전에 배열을 0으로 채 웁니다. Java에서는 배열이 생성 될 때 자동으로 0으로 채워지지만 C ++에서는 자체적으로 수행해야합니다. 그 후 마지막 배열 요소와 1의 곱을 구하고 prefixArray의 마지막 요소에 값을 저장합니다. 이제 오른쪽에서 왼쪽으로 시작하면 2부터 시작합니다.nd 배열의 마지막 요소, 이제 2의 거듭 제곱 숫자와 주어진 배열 요소의 곱을 가져 와서 이전 값인 prefixArray와 함께 추가합니다. prefixArray의 값과 함께 계속 추가하고 prefixArray의 각 위치에 저장하십시오.

우리에게 주어진 각 쿼리에 대해 주어진 올바른 값이 배열의 마지막 인덱스와 같지 않은지 확인하십시오. 그것이 참이면, prefixArray [left]와 prefixArray [right]의 차이를 얻어서 2의 거듭 제곱으로 시프트 연산을 적용하고 그 값을 반환 할 때 형성된 값으로 나누고, 그렇지 않으면 단순히 차이를 반환합니다. prefixArray [left]의 오른쪽 값을 shift 연산으로 나누고 반환합니다.

실시

C ++ 프로그램

#include<iostream>
#include<stdio.h>
#include<math.h>
#include<string.h>

using namespace std;

void buildArray(int arr[], int n, int prefixArray[])
{
    memset(prefixArray, 0, n * sizeof(int));
    prefixArray[n - 1] = arr[n - 1] * pow(2, 0);
    for (int i = n - 2; i >= 0; i--)
        prefixArray[i] = prefixArray[i + 1] + arr[i] * (1 << (n - 1 - i));
}
int getDeimalNum(int arr[], int left, int right, int n, int prefixArray[])
{
    if (right!= n - 1)
        return (prefixArray[left] - prefixArray[right + 1]) / (1 << (n - 1 - right));

    return prefixArray[left] / (1 << (n - 1 - right));
}
int main()
{
    int arr[] = {1, 0, 1, 1, 0, 0, 1, 1 };
    int n = sizeof(arr) / sizeof(arr[0]);

    int prefixArray[n];
    buildArray(arr, n, prefixArray);
    cout << getDeimalNum(arr, 1, 5, n, prefixArray) << endl;
    cout << getDeimalNum(arr, 3, 6, n, prefixArray) << endl;
    return 0;
}
12
9

자바 프로그램

import java.util.Arrays;

class DecimalfromSubArray
{
    static void buildArray(int arr[], int n, int prefixArray[])
    {
        Arrays.fill(prefixArray, 0);
        prefixArray[n - 1] = arr[n - 1] * (int)(Math.pow(2, 0));
        for (int i = n - 2; i >= 0; i--)
        {
            prefixArray[i] = prefixArray[i + 1] + arr[i] * (1 << (n - 1 - i));
        }
    }
    
    static int getDeimalNum(int arr[], int left, int right, int n, int prefixArray[])
    {
        if (right != n - 1)
        {
            return (prefixArray[left] - prefixArray[right + 1]) / (1 << (n - 1 - right));
        }
        return prefixArray[left] / (1 << (n - 1 - right));
    }
    
    public static void main(String[] args)
    {
        int arr[] = {1, 0, 1, 1, 0, 0, 1, 1};
        int n = arr.length;

        int prefixArray[] = new int[n];
        buildArray(arr, n, prefixArray);

        System.out.println(getDeimalNum(arr,1, 5, n, prefixArray));

        System.out.println(getDeimalNum(arr,3, 6, n, prefixArray));
    }
}
12
9

이진 배열의 하위 배열에 대한 XNUMX 진수 값 쿼리에 대한 복잡성 분석

시간 복잡성

O (q) 어디에 "Q" 쿼리 수입니다.

공간 복잡성

O (N) 어디에 "엔" 배열의 요소 수입니다.

참고

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