معلوم ٿيو ته هڪ ذيلي جبل واري شڪل ۾ آهي يا نه


تڪليف جي سطح سخت
بار بار پڇڻ ۾ Amazon ڪاروڪ Cisco Citrix حقيقت جو جائزو Honeywell Tesla ياندڪس
ڪيريو سوال جو مسئلو

مسئلي جو بيان

مسئلو ”معلوم ڪريو ته هڪ ذيلي زمين جبل جي صورت ۾ آهي يا نه“ ٻڌائي ٿي ته توهان کي هڪ ڏنو ويو آهي انٽرويو صف ۽ هڪ حد. مسئلي جو بيان اهو معلوم ڪرڻ لاءِ پڇي ٿو ته ڇا ڏنل ضمني ترتيب ڏنل حد جي وچ ۾ ٺهيل جبل جي شڪل ۾ آهي يا نه؟ جبه انگ اکر ٺاهيا ويا آهن جيڪڏهن انگ وڌڻ واري ترتيب ۾ آهن يا گهٽائي ترتيب ۾ آهن يا پهرين وڌندا آهن پوءِ گهٽندا آهن.

مثال

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

Left, right = (0, 3)
Mountain Form

وضاحت

ڇاڪاڻ ته ذيلي قطار {3 ، 4 ، 5 ، 6} وڌي رهي آهي ، تنهنڪري اها جبل واري قطار جي شڪل ۾ آهي.

معلوم ٿيو ته هڪ ذيلي جبل واري شڪل ۾ آهي يا نه

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

Left, right = (5, 7)
Not a Mountain form

وضاحت

ڇاڪاڻ ته ذيلي قطار {5 ، 1 ، 2} گهٽ ٿي رهي آهي پوءِ وڌندي رهي ٿي. تنهنڪري اهو جبل جي قطعي جي صورت ۾ ناهي.

الورورٿم

  1. ٻه ٺاھيو ٺاھيو صف ۽ صف آر اهڙي ئي سائيز جيتري اصلي صف جي ڊيگهه.
  2. صف آر جو پهريون عنصر ۽ صف جو آخري عنصر شروع ڪريو.
  3. جيڪڏهن موجوده صف جو عنصر پوئين عنصر کان وڌيڪ وڏو آهي.
    1. اپڊيٽ ڪريو وڌندڙ نمبر انڊيڪس ڏانهن.
    2. قدر وڌائڻ لاءِ نمبر مقرر ڪيو ايل کي.
  4. صف کي سا theي کان کاٻي طرف ڪريو ۽ چيڪ ڪريو ته ڇا گذريل عنصر کان وڏو تعداد (موجود عنصر کي موجوده عنصر جي سا toي طرف)
    1. وري اپ ڊيٽ ڪريو نمبر گهٽجڻ انڊيڪس ڏانهن
    2. نمبر گهٽائڻ لاءِ آر آر آر لڳايو.
  5. هر ڏنل سوال لاءِ ، صف آر [کاٻي] صف ايل کان وڏو آهي [سا ]و] سچو موٽڻ ، ٻيو ڪو غلط موٽ.

وضاحت

اسان هڪ لازمي انٽيليج ترتيب ڏني آهي ۽ هڪ کاٻي پاسي ، سا rightي. اسان کي اهو معلوم ڪرڻ لاءِ چيو ويو آهي ته جيڪڏهن ڏنل گدوڙ ڏنل حد سان ٺهيل ٻيٽ جي سرزمين ٿي سگهي ٿي يا نه. جيڪڏھن سبار جي ٺاھيل جبل جي صف آھي ته پوءِ اسان سچائي آڻينداسين ، ٻي صورت ۾ غلط موٽي اينداسين. اسان اعلان ڪندي ٻه پڪڙ. هڪڙو صف جي کاٻي پاسي لاءِ آهي ۽ ٻيو صف جي سا sideي طرف آهي. پوءِ اسان اهي اڏاوتون ٺاهي رهيا آهيون ته جيئن هر سوال مستقل جاءِ تي حل ڏئي سگهي.

اسان صف جو پهريون ۽ آخري عنصر ٺاھينداسين جيڪو اسان ترتيب ڏنو ليار ترتيب سان ترتيب ڏنل ايل ۽ آر. پوءِ اسان صف کان پاسو ڪيون ٿا ليفٽ جي کاٻي پاسي يا اسان چئي سگهجي ٿو سا leftي کان کاٻي طرف. اسان حالت چيڪ ڪنداسين جيڪڏهن هاڻوڪي ترتيب وارو عنصر پوئين عنصر کان گهٽ آهي. جيڪڏهن اهو سچو ثابت ٿيو ته ، اسان نمبر جي اشاري ڏانهن وڌندڙ نمبر کي اپڊيٽ ڪنداسين. ۽ ارلي ايل جي موجوده عنصر کي وڌائڻ تي نمبر لڳايو هر دفعي بغير ڪنهن شرط جي صحيح هجي يا نه.

ايندڙ مرحلي ۾ اسان صف کان سا rightي ۽ کاٻي طرف وڃي رهيا آهيون ، بنيادي طور تي ٻيو آخري عنصر کان صف جي پهرين عنصر تائين ، ۽ جانچ ڪجي ٿو ته صف جو موجوده عنصر ايندڙ عنصر کان وڏو آهي. جئين اسان کاٻي کان کاٻي طرف سفر ڪري رهيا آهيون ، اسان پوئين عنصر سان چيڪ چئي سگهون ٿا. جيڪڏھن حالت صحيح يا صحيح آھي ، پوءِ گھٽجي نمبر جي قيمت موجوده انڊيڪس ڏانھن تبديل ڪئي وئي. شرطن جي لحاظ کان بغير نمبر جي ترتيب کي يقيني بڻايو وڃي. سچ کي واپس آڻيو ، جيڪڏهن صف آر [کاٻي] صف ايل کان وڌيڪ يا انهي جي برابر آهي [سا ]و] ، ٻي صورت ۾ غلط واپس.

ڪوڊ

سي ++ ڪوڊ ڳولهڻ لاءِ معلوم ڪيو ته هڪ ذيلي جبل هڪ جبل جي شڪل ۾ آهي يا نه

#include<iostream>

using namespace std;

void buildArrays(int arr[], int N, int arrayL[], int arrayR[])
{
    arrayL[0] = 0;
    int increasingNumber = 0;

    for (int i = 1; i < N; i++)
    {
        if (arr[i] > arr[i - 1])
            increasingNumber = i;
        arrayL[i] = increasingNumber;
    }
    arrayR[N - 1] = N - 1;
    int decreasingNumber = N - 1;

    for (int i = N - 2; i >= 0; i--)
    {
        if (arr[i] > arr[i + 1])
            decreasingNumber = i;
        arrayR[i] = decreasingNumber;
    }
}

bool solveQuery(int arr[], int arrayL[], int arrayR[], int Left, int Right)
{
    return (arrayR[Left] >= arrayL[Right]);
}

int main()
{
    int arr[] = {3,4,5,6,1,5,1,2,1};
    int N = sizeof(arr) / sizeof(int);

    int arrayL[N], arrayR[N];
    buildArrays(arr, N, arrayL, arrayR);

    int L = 0;
    int R = 3;
    if (solveQuery(arr, arrayL, arrayR, L, R))
        cout << "Mountain form\n";
    else
        cout << "Not a mountain form\n";

    L = 5;
    R = 7;
    if (solveQuery(arr, arrayL, arrayR, L, R))
        cout << "Mountain form\n";
    else
        cout << "Not a mountain form\n";

    return 0;
}
Mountain form
Not a mountain form

جاوا ڪوڊ اهو معلوم ڪرڻ لاءِ ته ڇا هڪ آبدوز جبل جي شڪل ۾ آهي يا نه

class MountainArray
{
    static void buildArrays(int arr[], int N, int arrayL[], int arrayR[])
    {
        arrayL[0] = 0;
        int increasingNumber = 0;

        for (int i = 1; i < N; i++)
        {
            if (arr[i] > arr[i - 1])
                increasingNumber = i;
            arrayL[i] = increasingNumber;
        }
        arrayR[N - 1] = N - 1;
        int decreasingNumber = N - 1;

        for (int i = N - 2; i >= 0; i--)
        {
            if (arr[i] > arr[i + 1])
                decreasingNumber = i;
            arrayR[i] = decreasingNumber;
        }
    }
    
    static boolean solveQuery(int arr[], int arrayL[], int arrayR[], int Left, int Right)
    {
        return (arrayR[Left] >= arrayL[Right]);
    }

    public static void main(String[] args)
    {
        int arr[] = {3,4,5,6,1,5,1,2,1};
        int N = arr.length;
        int arrayL[] = new int[N];
        int arrayR[] = new int[N];
        buildArrays(arr, N, arrayL, arrayR);
        int L = 0;
        int R = 3;

        if (solveQuery(arr, arrayL, arrayR, L, R))
            System.out.println("Mountain form");
        else
            System.out.println("Not a mountain form");

        L = 5;
        R = 7;

        if (solveQuery(arr, arrayL, arrayR, L, R))
            System.out.println("Mountain form");
        else
            System.out.println("Not a mountain form");
    }
}
Mountain form
Not a mountain form

پيچيدگي تجزيي

وقت جي پيچيدگي

اي (اين + ق) ، اسان کي ٻن قريب جي تعمير لاءِ O (N) وقت جي ضرورت آهي. ۽ هڪ ڀيرو ٺاهيا ويا آهن. اسان O (1) ۾ سوالن جو جواب ڏئي سگهون ٿا.

خلائي پيچيدگي

اي (ن) جتي “ن” صف ۾ موجود عنصرن جو تعداد آهي.