첫 번째 요소를 두 배로 늘리고 XNUMX을 끝까지 이동

난이도 중급
자주 묻는 질문 Microsoft 조호 (Zoho)
배열조회수 70

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

문제 정책

배열이 있다고 가정합니다. 정수. 여기서 "0"은 입력으로 간주되는 숫자가 아닙니다. 여기에 유효한 입력이 아닙니다. "첫 번째 요소를 두 배로하고 0을 끝으로 이동"문제는 0 이외의 숫자가 발견되고 그 다음 숫자가 동일한 숫자 인 경우 배열을 재 배열하도록 요청한 다음 숫자를 두 배로 표시하고 다음 숫자는 XNUMX입니다. 마지막으로 끝에있는 모든 XNUMX을 누릅니다.

arr[] = {3, 3, 5, 0, 1, 0, 0, 1, 0}
6 5 1 1 0 0 0 0 0

설명 : 3은 연속적으로 발생하는 숫자이므로 먼저 3을 두 배로 만들어 6으로 만들고 다음 3을 0으로 표시합니다. 또한 모든 XNUMX은 last.x로 이동되었습니다.

첫 번째 요소를 두 배로 늘리고 XNUMX을 끝까지 이동하는 알고리즘

1. Traverse the array from 0 to n-1(inclusively).
2. Check if arr[i] is not equal to 0 and arr[i]==arr[i+1](next value is same as current value).
  1. If true, then make the current value twice of the self.
  2. Update next element as 0 and do i++.
3. Traverse the array from i = 0 to n-1(step of shifting all the zeroes to the end).
  1. Check if arr[i] != 0.
    1. Arr[count]=arr[i] and do count++.
4. From the traversal of till count is less than n.
  1. Arr[count]=0 and do count++.
5. Print the array.

설명

주어진 방식으로 재정렬 할 배열이 주어집니다. 현재 번호가 다음 번호와 같으면 다음 번호를 변경하도록 요청했습니다. 변화는 현재 숫자를 두 배로 늘려야한다는 것입니다. 그리고 주어진 조건이 만족되면 다음 숫자를 0으로 표시하십시오. 이 수정 후에는 우리가 만들었거나 이미 배열에있는 배열의 마지막에있는 모든 XNUMX을 이동해야합니다. 그런 다음 출력이 반환되어야합니다.

0에서 n – 1까지 배열을 탐색합니다. 각 값이 0이 아닌지 확인합니다. 0의 값을 변경할 수 없기 때문입니다. 그리고 현재 요소가 arr [i] = = arr [i + 1]로 다음 요소와 같은지 확인합니다. 현재 번호의 다음 번호를 검색하기 때문에 n-1을 마지막 순회 지점으로 사용했습니다. 따라서 검색 할 마지막 요소로 n을 찾으면 null 포인터 예외가 발생합니다. 주어진 조건이 충족되면 현재 요소를 선택하고 현재 값의 두 배로 다음 값을 0으로 업데이트합니다. 배열의 모든 값에 대해이 작업을 수행해야합니다.

이제 모든 값을 0으로 마지막으로 이동하십시오. 이를 위해 배열을 다시 탐색하고 값이 같지 않은지 확인한 다음 왼쪽으로 이동합니다. 모든 값을 왼쪽으로 이동 한 후 마지막으로 이동 한 값의 인덱스를 갖게됩니다. 루프를 반복하고 그 카운트에서 n 값까지 모든 값을 0으로 업데이트합니다. 마지막으로 배열을 인쇄합니다.

첫 번째 요소를 두 배로 늘리고 XNUMX을 끝까지 이동

암호

첫 번째 요소를 두 배로 늘리고 XNUMX을 이동하여 문제를 끝내기위한 C ++ 코드

#include<iostream>

using namespace std;

void shiftZeroAtLast(int arr[], int n)
{
    int count = 0;

    for (int i = 0; i < n; i++)
        if (arr[i] != 0)
            arr[count++] = arr[i];

    while (count < n)
        arr[count++] = 0;
}
void arrayModification(int arr[], int n)
{
    if (n == 1)
        return;
    for (int i = 0; i < n - 1; i++)
    {
        if ((arr[i] != 0) && (arr[i] == arr[i + 1]))
        {
            arr[i] = 2 * arr[i];

            arr[i + 1] = 0;

            i++;
        }
    }
    shiftZeroAtLast(arr, n);
}
void printArray(int arr[], int n)
{
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
}
int main()
{
    int arr[] = {3,3,5,0,1,0,0,1,0};
    int n = sizeof(arr) / sizeof(arr[0]);

    arrayModification(arr, n);

    cout << "Modified array: ";
    printArray(arr, n);

    return 0;
}
Modified array: 6 5 1 1 0 0 0 0 0

첫 번째 요소를 두 배로 늘리고 XNUMX을 이동하여 문제를 끝내기위한 Java 코드

class arrayRearrange
{
    public static void shiftZeroAtLast(int arr[], int n)
    {
        int count = 0;

        for (int i = 0; i < n; i++)
            if (arr[i] != 0)

                arr[count++] = arr[i];

        while (count < n)
            arr[count++] = 0;
    }
    public static void arrayModification(int arr[], int n)
    {
        if (n == 1)
            return;

        for (int i = 0; i < n - 1; i++)
        {
            if ((arr[i] != 0) && (arr[i] == arr[i + 1]))
            {
                arr[i] = 2 * arr[i];

                arr[i + 1] = 0;

                i++;
            }
        }
        shiftZeroAtLast(arr, n);
    }
    public static void printArray(int arr[], int n)
    {
        for (int i = 0; i < n; i++)
            System.out.print(arr[i] + " ");
        System.out.println();
    }
    public static void main(String[] args)
    {
        int arr[] = {3,3,5,0,1,0,0,1,0};
        int n = arr.length;


        arrayModification(arr, n);

        System.out.print("Modified array: ");
        printArray(arr, n);
    }
}
Modified array: 6 5 1 1 0 0 0 0 0

복잡성 분석

시간 복잡성

의 위에) 어디에 "엔" 배열의 요소 수입니다. 우리는 단순히 배열을 두 번 탐색하여 알고리즘이 선형 시간으로 실행되도록했습니다.

공간 복잡성

알고리즘에는 O (1) 추가 공간이 있지만 프로그램은 입력을 저장하는 데 O (N) 총 공간을 사용합니다.

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