Dizini Zig-Zag modasına çevirin

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Accenture Amazon Fourkites Teradata Xome
GeyimBaxılıb 96

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Problem bəyanat

"Diziyi Zig-Zag modasına çevir" problemi sizə verildiyini bildirir - tam ədədi. Problem ifadəsi massivi ziq-zag qaydasında sıralamağı xahiş edir ki, massivdəki elementlər à kimi görünsün  a <b> c <d> e <f.

misal

arr[] = {2,4,5,1,7,6,8}
[2, 5, 1, 7, 4, 8, 6]

Izahat

5 həm 1, həm də 2-dən böyükdür (bitişik elementləri), 7 həm bitişik elementlərdən, həm də 8-dən böyükdür.

Alqoritm

1. Mark flag is equal to true.
2. Traverse the array from 0 to n-2, where n is the length of the array.
  1. Check if the flag is true
    1. Check if the current element is greater than the next element.
      1. Swap those values.
    2. Else, check if the current element is greater than the next element,
      1. Check if the current element is lesser than the next element.
        1. Swap those values.
3. Flip the value of the flag.

Izahat

Biz verdik array of tamsayılar. Bizim vəzifəmiz massivi ziqzaq şəklində yenidən təşkil etməkdir. Bir şərt verdik ki, cüt ədəd elementləri ona bitişik iki elementdən daha böyük olsun, 'a <b> c <d> e <f '. Burada b və d-nin bitişik iki elementdən böyük olduğunu, 'a' və 'c' nin bitişik iki elementdən daha kiçik olduğunu görə bilərik. Bizim vəzifəmiz verilmiş massivi belə təşkil etməkdir. Bunun üçün ziqzaq şəklində düzülmüş dizini gəzərkən dəyərləri dəyişdirəcəyik.

Biri qeyd olunacaq Boolean value true, onda döngədən keçməyə başlayacağıq və bayrağın doğru olub olmadığını yoxlayacağıq. Doğrudursa, cari dəyər növbəti dəyərindən böyükdürsə, cari dəyəri yoxlayacağıq. Sonra bu dəyərləri dəyişdirəcəyik. Boole dəyərlərini yalan olaraq qeyd edin. Sadəcə dəyərini qaytarmaq məcburiyyətindəyik, doğrudursa, onu yalana, yalnışdırsa həqiqi vəziyyətə gətirməliyik. Beləliklə, hər alternativ keçidlə, hər təkrarlama üçün fərqli bayraq dəyərləri olacaqdır. Beləliklə, bununla yalnız bir hissəsi icra ediləcək, ya da bir hissəsi ya da başqa bir hissəsi.

Eyni şeyi dəyərləri dəyişdirmək üçün başqa hissə ilə edəcəyik. Bir cərgədə cərgənin cari dəyəri növbəti dəyərdən azdırsa. Keçiddən sonra yeniləmələr etdiyimiz serialı çap etməliyik.

Dizini Zig-Zag modasına çevirinPin

 

Kodu

Dizini Zig-Zag modasına çevirmək üçün C ++ kodu

#include <iostream>

using namespace std;

void sortZigZag(int arr[], int n)
{
    bool flag = true;

    for (int i=0; i<=n-2; i++)
    {
        if (flag)
        {
            if (arr[i] > arr[i+1])
                swap(arr[i], arr[i+1]);
        }
        else
        {
            if (arr[i] < arr[i+1])
                swap(arr[i], arr[i+1]);
        }
        flag = !flag;
    }
}
int main()
{
    int arr[] = {2,4,5,1,7,6,8};
    int n = sizeof(arr)/sizeof(arr[0]);
    sortZigZag(arr, n);
    for (int i=0; i<n; i++)
        cout << arr[i] << " ";
    return 0;
}
2 5 1 7 4 8 6

Dizini Zig-Zag modasına çevirmək üçün Java kodu

import java.util.Arrays;

class zigzagArray
{
    public static void sortZigZag(int arr[])
    {
        boolean flag = true;

        int temp =0;

        for (int i=0; i<=arr.length-2; i++)
        {
            if (flag)
            {
                if (arr[i] > arr[i+1])
                {
                    temp = arr[i];
                    arr[i] = arr[i+1];
                    arr[i+1] = temp;
                }

            }
            else
            {
                if (arr[i] < arr[i+1])
                {
                    temp = arr[i];
                    arr[i] = arr[i+1];
                    arr[i+1] = temp;
                }
            }
            if(flag==true)
                flag=false;
            else
                flag=true;
        }
    }
    public static void main(String[] args)
    {
        int arr[] = {2,4,5,1,7,6,8};
        sortZigZag(arr);
        System.out.println(Arrays.toString(arr));
    }
}
[2, 5, 1, 7, 4, 8, 6]

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (n) hara "N" massivdəki elementlərin sayıdır. Yalnız serialdakı elementlərin üstündən keçdiyimiz üçün. Zamanın mürəkkəbliyi xətti.

Kosmik Mürəkkəblik

O (1) əlavə yer tələb olunmadığı üçün. Əlavə bir yer istifadə etmədiyimiz üçün kosmik mürəkkəblik sabitdir.

Crack Sistemi Dizayn Müsahibələri
Translate »