اپ ڈیٹس کے بغیر حد کے سوالات


مشکل سطح آرام سے
اکثر پوچھا جاتا ہے BlackRock GE صحت کا خیال مونفروگ لیبز Synopsys ٹیکسی 4 سوری Twilio
لڑی لارسن اینڈ توبرو سوال کا مسئلہ

مسئلہ یہ بیان

مسئلہ "اپ ڈیٹس کے بغیر رینج کے مجموعی سوالات" یہ بتاتا ہے کہ آپ کے پاس ایک سوال ہے صف of اشارے اور ایک حد ہے۔ مسئلہ بیان میں دی گئی حد کے اندر موجود تمام عناصر کا مجموعہ معلوم کرنے کے لئے کہا گیا ہے۔

مثال کے طور پر

arr[]={10, 9, 8, 7, 6}

Query: {(0, 4), (1, 3)}
40 24

وضاحت

مجموعی طور پر حد (0 ، 4) کے مابین تمام اعداد کا مجموعہ 40 ہے اور (1 ، 3) کے درمیان سبھی تعداد کا مجموعہ مجموعی طور پر 24 ہے۔

اپ ڈیٹس کے بغیر حد کے سوالات

 

الگورتھم

  1. دیئے گئے سرنی کی طرح ہی سائز کا ایک صفی ارے بنائیں۔
  2. دیئے ہوئے صفوں کو عبور کریں اور SumArray کے پچھلے عنصر اور جمع کردہ سرنی کے موجودہ عنصر کا مجموعہ جمع کریں اور اسے SumArray میں اسٹور کریں۔
  3. ہر سوال کے ل if ، اگر بائیں 0 کے برابر ہے تو ، پھر ارے [دائیں] کو واپس کریں ،
  4. بقیہ رقم ارے [دائیں] - خلاصہ آرای [بائیں - 1] واپس کریں۔

وضاحت

ہم نے عدد اور ایک رینج کی ایک صف دی ہے ، ہمیں ہر سوال کے ل for دی گئی حد کے اندر موجود تمام عناصر کا مجموعہ معلوم کرنے کے لئے کہا گیا ہے۔ ہر سوال میں ایک حد ہوتی ہے جس میں کسی حد کے آغاز اور اختتامی نقطہ ہوتا ہے۔ اس سوال میں کوئی تازہ کاری سوال شامل نہیں ہے۔ اس کا مطلب ہے کہ استفسار جواب تلاش کرتے وقت کسی بھی چیز کو اپ ڈیٹ کرنے کی ضرورت نہیں ہے۔ ہم صرف دیئے ہوئے صفوں کی تعمیر کریں گے تاکہ 0 انڈیکس سے موجودہ انڈیکس تک تمام عناصر کا مجموعہ بلٹ سرنی کی ایک پوزیشن پر ہو۔ اس طرح ، O (1) میں O (n) کی اضافی جگہ کے ساتھ ، ہر سوال کو حل کیا جائے گا۔

ہم نے جو رقم تیار کی ہے اس کی تعمیر ہم کریں گے۔ اس خلاصہ آری میں ، 0 سے i تک کے عناصر کا مجموعہ سمری ارے کی ith پوزیشن پر رکھا جائے گا۔ ہم اس کا حساب لگائیں گے کیوں کہ ہم SumArray کی پچھلی قیمت اور دیئے ہوئے صف کی موجودہ قیمت کو جوڑیں گے اور اس کو ٹریک کرتے ہوئے SumArray کی موجودہ انڈیکس پوزیشن میں جمع کریں گے۔ لہذا جب کسی نے پوچھا کہ اس پوزیشن پر موجود تمام اعداد کا مجموعہ کیا ہے ، ہمیں صرف ہر انوکھے عناصر کے ل that اس پوزیشن کی قدر واپس کرنے کی ضرورت ہے۔

جب ہمیں کسی بھی رینج پر مشتمل کوئی استفسار ملے گا ، اور اگر ہمیں پایا گیا ہے کہ رینج کا بایاں یا ابتدائی نقطہ 0 کے برابر ہے تو ، ہم صرف رقم ارای [دائیں] کی وہ قیمت واپس کردیں گے جس کی بات ہم نے اوپر کی ہے ، وہ بائیں رینج ہے 0 کے برابر نہیں ہم SumArray [دائیں] اور sumArray [بائیں -1] کا فرق واپس کریں گے۔ ان کے جوابات درکار ہوں گے۔ یہ نقطہ نظر بھی ایک آسان ترین طریقہ ہے جس میں ہم استعمال کرتے ہیں متحرک پروگرامنگ.

ضابطے

C ++ کوڈ برائے رینج کے بارے میں کچھ سوالات بغیر کسی اپ ڈیٹ کے

#include<iostream>

using namespace std;

void buildSumArray(int arr[], int n, int sumArray[])
{
    sumArray[0] = arr[0];
    for (int i = 1; i < n; i++)
        sumArray[i] = arr[i] + sumArray[i - 1];
}

int solveQuery(int left, int right, int sumArray[])
{
    if (left == 0)
        return sumArray[right];

    return sumArray[right] - sumArray[left -1];
}

int main()
{
    int arr[] = {10,9,8,7,6};
    int n = sizeof(arr)/sizeof(arr[0]);

    int sumArray[n];

    buildSumArray(arr, n, sumArray);

    cout << solveQuery(0, 4, sumArray) << endl;
    cout << solveQuery(1, 3, sumArray) << endl;

    return 0;
}
40
24

حد کے بارے میں سوالات کے لئے جاوا کوڈ بغیر اپ ڈیٹس کے

class RangeQueriesSum
{
    public static void buildSumArray(int arr[], int n, int sumArray[])
    {
        sumArray[0] = arr[0];
        for (int i = 1; i < n; i++)
            sumArray[i] = arr[i] + sumArray[i - 1];
    }

    public static int solveQuery(int left, int right, int sumArray[])
    {
        if (left == 0)
            return sumArray[right];

        return sumArray[right] - sumArray[left -1];
    }

    public static void main(String[] args)
    {
        int arr[] = {10,9,8,7,6};
        int n = arr.length;

        int sumArray[] = new int[n];

        buildSumArray(arr, n, sumArray);
        System.out.println(solveQuery(0, 4, sumArray));
        System.out.println(solveQuery(1, 3, sumArray));
    }
}
40
24

پیچیدگی کا تجزیہ

وقت کی پیچیدگی

O (N + Q) ،  کیونکہ ہمیں SumArray کی گنتی کرنے کے لئے O (N) کی ضرورت ہے اور پھر ہر سوال کے لئے O (1) وقت کی ضرورت ہے۔

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

یہاں دیئے گئے نقطہ نظر میں ، ہم نے 0 سے i تک عناصر کی رقم کو ذخیرہ کرنے کے لئے ایک نئی سرنی سمری تیار کی ہے۔ اس طرح اس نقطہ نظر کی ضرورت ہے O (N) جگہ. لیکن ہم اصل صف میں بھی ترمیم کرسکتے تھے۔ تب خلائی پیچیدگی کم ہوجاتی۔