Dear subscribers, today we have a slightly difficult task, but let’s sort it out!
Leetcode Daily question Zero Array Transformation II
You are given an integer array nums of length n and a 2D array queries where queries[i] = [li, ri, vali].

Each queries[i] represents the following action on nums:

Decrement the value at each index in the range [li, ri] in nums by at most vali.
The amount by which each value is decremented can be chosen independently for each index.

A Zero Array is an array with all its elements equal to 0.

Return the minimum possible non-negative value of k, such that after processing the first k queries in sequence, nums becomes a Zero Array. If no such k exists, return -1.

Example 1:

Input: nums = [2,0,2], queries = [[0,2,1],[0,2,1],[1,1,3]]

Output: 2

Explanation:

For i = 0 (l = 0, r = 2, val = 1):
Decrement values at indices [0, 1, 2] by [1, 0, 1] respectively.
The array will become [1, 0, 1].
For i = 1 (l = 0, r = 2, val = 1):
Decrement values at indices [0, 1, 2] by [1, 0, 1] respectively.
The array will become [0, 0, 0], which is a Zero Array. Therefore, the minimum value of k is 2.

Tarjimasini yozib utirmayman.
Demak bizga bir qancha so'rovlar beriladi.
So'rovlar quyidagi turda bo'ladi [l,r,val]
yane berilgan massivdagi l-indexidan boshlab r-indexigacha (l,r ham kiradi)
qiymatlarni val dan katta bo'lmagan qiymatga kamaytirishimiz mumkin.
Biz shunday k sonini topishimiz kerak ki k-ta so'rovdan keyin massiv barcha elementlari
0 ga teng bo'lsin va k eng kichik bo'lishi kerak.

Miyamizga keladigan eng birinchi yechim bu oddiy bir boshdan har bir so'rovlarni bajarish.
lekin so'rovlar soni 10^5 har bir marta katta diapozon berilsa bu ishni amalga oshirishimiz qiyin.

Endi kelilar bir tushunchani tushinib olamiz.
Differensal massiv tushunchasi bu massivdagi [l,r] oraliqdagi barcha elementlarni birdan kamaytirish yoki
oshirish usuli yane so'rovni konstanta vaqtda bajarish.

Bu usulni namunada tushuntirib beraman.
Masalan, quyidagi massiv berilgan:

nums = {2, 4, 6, 8, 10}

Agar biz [1,3] index oralig‘idagi barcha elementlarni 3 kamaytirmoqchi bo‘lsak, oddiy usulda quyidagi amallar bajarilar edi:

nums[1] -= 3;
nums[2] -= 3;
nums[3] -= 3;

Natijada massiv shunday ko‘rinishda bo‘ladi:

nums = {2, 1, 3, 5, 10}

Bu jarayon har bir so‘rov uchun O(N) vaqt talab qiladi va katta N uchun optimal emas.

Buning o‘rniga Differensial massiv (Difference Array) usulidan foydalansak, biz so‘rovlarni O(1) vaqt ichida qo‘llashimiz mumkin. Buning uchun diff deb nomlangan yordamchi massiv yaratamiz, va unda faqatgina o‘zgarishlarni saqlaymiz:

    diff[l] ga -val qo‘shamiz (bu l dan boshlab kamaytirish boshlanishini bildiradi).
    diff[r+1] ga +val qo‘shamiz (bu r dan keyin qayta tiklashni bildiradi).

Bu usulni diff massivi bilan qo‘llaymiz:

diff = {0, -3, 0, 0, 3, 0}

Oxirgi qadam sifatida diff ustida prefix sum bajarib, asl nums massivini tiklaymiz:

nums[0] = 2
nums[1] = 4 + (-3) = 1
nums[2] = 6 + (-3) = 3
nums[3] = 8 + (-3) = 5
nums[4] = 10 + 0 = 10

Ko‘rib turganingizdek, natija oddiy usul bilan bajarganimiz kabi chiqdi, lekin har bir so‘rov O(1) vaqt ichida qo‘llanildi, bu esa juda samarali yondashuvdir!

Qisqacha qilsak kod kurinishda quyidagiga ega bo'lamiz.

int main(){

    vector<int> nums = {2, 4, 6, 8, 10};
    vector<int> diff(nums.size() + 1, 0);
    
    //[1,3] oraligdagi barcha elementlarni 3 kamaytiramiz
    diff[1] -= 3;
    diff[4] += 3;//Qolganlari uchun +3 chunki [4...oxirgacha bu amal bajarilmasligi kerak]
    //Yuqoridagi amalni bir nechi marta bajarishimiz mumkin
    //endi natijaviy massivni hosil qilamiz
    int current = 0;
    for (int i = 0; i < nums.size(); i++) {
        current += diff[i];
        nums[i] += current;
    }

    for(auto& num: nums){
        std::cout << num << "\n";
    }
    return 0;
}

Leetcode Daily Question Divide Array Into Equal Pairs (Here's original version)

Sizga 2 * n ta butun sonlardan tashkil topgan nums massiv berilgan.

Siz ushbu massivni n ta juftlikka shunday ajratishingiz keraki:

Har bir element faqat bitta juftlikka tegishli bo‘lishi kerak.
Har bir juftlikdagi elementlar bir-biriga teng bo‘lishi kerak.

Agar nums massivini ushbu shartlarga mos ravishda n ta juftlikka ajratish mumkin bo‘lsa, true qaytaring, aks holda false qaytaring.

Xullas masalani juda oson va bir nechi xil usullarda ishlasa bo'ladi.
Qisqacha qilsak har bir elementni jufti borligiga tekshirishimiz kerak.
Buning uchun bizga Kalid va Qiymatni saqlaydigan (Dict) ma'lumotlar tuzilmasi
kerak bo'ladi.

Masalan:
Input: nums = [3,2,3,2,2,2]
Bo'lganda bizning Dictimiz
{
3—>2 marta
2—>4 marta
}
(2,2) (3,3) va yana bir marta (2,2) ajratishimiz mumkin.
Demak har bir kalid elementni juft juft qilsak bo'ladi (%2==0)

Yechim quyidagicha bo'ladi.

class Solution {
public:
    bool divideArray(vector<int>& nums) {
       std::unordered_map<int,int> cnt;

       for(auto& num: nums){
        cnt[num]++;
       } 

       for(auto& [key, value]: cnt){
        if(value % 2 != 0)
         return false;
       }

       return true;
    }
};

Bu yechimni o'zingizni Dasturlash tilingizga moslab yozishiz mumkin.
Yechim Eng yaxshi holatda O(N) eng yomon holatda O(N^2) ishlaydi
Chunki Xesh da kolliziya bo'lishi ehtimoli bor.

Lekin bunda muammo bor. Biz qo'shimcha xotira egallayapmiz. yane Dict (map) O(2*N) qo'shimcha xotirani ishlatmoqda.
Xo'sh siz ortiqcha xotirasz bu muammoga yechim bera olasiz?
Yechimingizni izohlarda qoldiring.(Shart emas aniq dasturlash tilida bo'lishi shunchaki yozma bo'lsa ham mayli)

Tasavvur qiling loyihangizda kartani (Oddiy debit yoki kredit kartasi — Humo Uzcard ....)
qo'llab quvvatlashni qo'shmoqchisiz.
Endi bu kartani foydalanuvchi ishlatishi uchun siz unga bir qancha statuslar berishiz kerak.
Masalan

CARD_BLOCK
CARD_EXPIRED
CARD_NOT_SUPPORT
TEMP_SYSTEM_BLOCK
DEBIT_CARD_LOCK
.............(10-15 dona)

Siz bu kartani DB-bazada saqlamoqchisz.
Xo'sh siz qanday yo'l tutasz?
Qanday qilib Backenda saqlaysz?
va qanday Qilib ma'lumotlar bazasida bu maydonni saqlaysz?
Izohlarda fikringizni qoldiring. (Bugungi leetcode masalasi ham aynan shu savolga mos keladi)

Dev MeetUP #2 yandex dan.
Ro'yxatdan vaqtliroq o'tishingizni maslahat beraman.

#yandex

Power of std::move in C++

C++ eng yaxshi tomonlaridan biri bu move-semantika hisoblanadi.
Kelilar buni oddiy namunada sizlarga ko'rsatib beraman.

Namuna uchun leetcode dan eng sodda masalani olamiz.

Transform array by parity

You are given an integer array nums. Transform nums by performing the following operations in the exact order specified:

Replace each even number with 0.
Replace each odd numbers with 1.
Sort the modified array in non-decreasing order.

Return the resulting array after performing these operations.

Bu masala juda ham oddiy uning yechimi quyidagi ko'rinishda bo'lishi mumkin.

class Solution {
public:
    vector<int> transformArray(vector<int>& nums) {
        for(auto& num: nums){
            num = num % 2;
        }

        std::ranges::sort(nums);

        return nums;
    }
};

Lekin bu yechimni o'tkazganimizdan so'ng Time bo'yicha 100% ammo xotira bo'yicha 25-30 % hisobni olamiz.

Aytishingiz mumkin biz umuman ortiqcha xotira ishlatmayapmizku?
Ha rostanam shunday lekin oxirida biz

std::vector 

ni qaytarayotganimizda
bu copy-yane nusxalanadi . Aslida esa nusxalamasdan turib ham buni qaytaraishimiz mumkin.
Ana shu narsa move-semantika yane ko'chirishimiz semantikasi deyiladi .
Yane sizda Iphone bor va u sizga endi kerak emas sizni do'stingizda bunga ehtiyoj bor va u yangi olish uchun pul (xotira vaqt) sarflaydi lekin uni sarflamasdan shunchaki siznikini olishi mumkin.

endi esa bundan foydalanib natijani ko'ramiz

class Solution {
public:
    vector<int> transformArray(vector<int>& nums) {
        for(auto& num: nums){
            num = num % 2;
        }

        std::ranges::sort(nums);

        return std::move(nums);
    }
};

Oxirgi qatordagi o'zgarish Xotirani deyarli 100% likka chiqaradi.

PS: yechim eng optimal emas uni yanada optimal qilishni iloji bor O(N) gacha

Ko'pchilik C++ da backend yozilishi haqida aytganimda hayron bo'ladi .
Murakkab tizimlar katta nagruzkada ishlaydigan barcha tizimlarni backendi C++ da yoziladi.

Tasavvur qiling tizimda bir sekunda 1-2 mln so'rov kelib tushadi.
albatta katta mablag sarflab oddiy Pythondaham yozsa bo'ladi. lekin bu har doimam C++ dagi effektni bermaydi.
bizni ko'pgina tizimlarimiz boost ASIO Drogon userver da yozilgan

Shaxsiy tajribamdan bu juda yomon deyishim mumkin chunki oddiygina bug ni ham qidirishga ko'plab vaqt sarflanadi.
Lekin server maksimum 5% nagruzkada ishlaydi (sekundiga bazan 2 million so'rovda 2mln/per second)
5 mln qatorlik kodan yigilgan eng gigant app esa bor yuqi 150 MB joyni oladi xolos
bu esa biznesga qimmat GPU lar yoki serverlarga bo'lgan ehtiyojni kamaytiradi .

Tassavur qiling 1 sekundda 1 mln so'rovni har biridan 1 millisekund yutulsa jami qancha yutishga erishish mumkin
va hattoki 1 nano sekund yutulsachi?
1 millisekunda 10^6 sekund yutish bu esa 11 kun
Yane sizni serveriz 11 kun tezroq berilgan ishni bajaradi.

Xo'sh Go chi?
Yoki Rust chi?

Go daham yaxshi natijaga erishsa bo'ladi Rust daham shunday.
Bizni bazi serverlarimiz Go da bazilari hattoki Pythonda
Buni esa faqat va faqat biznes aniqlaydi.

Har doim bu uchun C++ tanlanmiydi. C++ ni yana bir yaxshi tomoni bu o'ning Linuxdagi o'rni.
Bu moslashuvchanlik hisobiga serverga kelayotgan trafficni to'liq boshqarish mumkin (Xavfsizlik)

Buni davom etirishim mumkin.
Imkoniyatlari rostanam juda katta.

#pragma once

#include <drogon/HttpController.h>

using namespace drogon;

namespace api
{
class Agent : public drogon::HttpController<Agent>
{
public:
    METHOD_LIST_BEGIN
        
            // Exchange rate methods
            ADD_METHOD_TO(Agent::exchangeRate, "/api/agent/exchange_rate", Get, "LoginFilter");
    ADD_METHOD_TO(Agent::exchangeRateCalculate, "/api/agent/exchange_rate/calculate?amount={1}&currency_code={2}", Get, "LoginFilter");
    
    // P2P methods
    ADD_METHOD_TO(Agent::P2pCheckPersons, "/api/blabla/p2p/check_persons", Post);
    ADD_METHOD_TO(Agent::P2pTransfer, "/api/blabla/p2p/transfer", Post);
    ADD_METHOD_TO(Agent::P2pHistory, "/api/blabla/p2p/history", Get);
    
    // Client methods
    ADD_METHOD_TO(Agent::clientBalance, "/api/agent/client/balance", Post);
    ADD_METHOD_TO(Agent::clientTransactions, "/api/agent/client/transactions", Get);
    ADD_METHOD_TO(Agent::clientProfile, "/api/agent/client/profile", Get);
    ADD_METHOD_TO(Agent::clientUpdate, "/api/agent/client/update", Post);
    
    // Service methods
    ADD_METHOD_TO(Agent::serviceList, "/api/agent/service/list", Get);
    ADD_METHOD_TO(Agent::serviceList, "/api/agent/merchant/list", Get);
    ADD_METHOD_TO(Agent::serviceInfo, "/api/agent/service/info?id={1}", Get);
    ADD_METHOD_TO(Agent::serviceCreate, "/api/agent/service/create", Post);
    ADD_METHOD_TO(Agent::serviceUpdate, "/api/agent/service/update", Put);
    ADD_METHOD_TO(Agent::serviceDelete, "/api/agent/service/delete?id={1}", Delete);
    
    METHOD_LIST_END
        
        // Exchange rate methods
        void exchangeRate(const HttpRequestPtr& req, std::function<void (const HttpResponsePtr &)> &&callback);
    void exchangeRateCalculate(const HttpRequestPtr& req, std::function<void (const HttpResponsePtr &)> &&callback, double amount, int currency_code);
    
    // P2P methods
    void P2pCheckPersons(const HttpRequestPtr& req, std::function<void (const HttpResponsePtr &)> &&callback);
    void P2pTransfer(const HttpRequestPtr& req, std::function<void (const HttpResponsePtr &)> &&callback);
    void P2pHistory(const HttpRequestPtr& req, std::function<void (const HttpResponsePtr &)> &&callback);
    
};
}

Ana shunday Backend yozish mumkin C++ da
Xunuk kurindimi?
Yoki norm ekanmi?
Frameworkni yigish sal murakkab bo'lishi mumkin lekin keyinchalik unda kod yozish
eski C++ dan hech qanday asar qolmaydi.

Biror kompaniyada ishlash bu shunchaki qora ishchi bo'lish xolos!
To'gri boshida hamma shunday boshlaydi va ancha muddat ishlaydi.
lekin shu bilan birgalikda albatta o'zi qandaydir loyiha ustida ishlab borishi kerak.
Gap qaysidir dasturlash tilidiyam emas
yoki texnik bilimdayam emas. Hamma gap odamlarni ishini osonlashtirshda!
va yanada aniqroq qilib aytsik biznesni IT yordamida boshqarishda!


PS: Ertalab bitta shogirdim telfon qilib biz oz'imiz loyiha tuzdek unga hattoki mijoz ham topdik
deganiga juda xursand bo'ldim.

Bitta lampani kashf qilishda 1000 marta o'rinish qilishgan ekan
Xullas harakatdan to'xtagan odam boshqalarni maqsadlarini va orzularini shunchaki ruyobga chiqaradi(bizga uxshab).

Doimo harakatda bo'lish shart!
Maqsad quyish kerak va unga albatta erishish uchun maksimal harakat qilish kerak!

Xuddi oldizda qandaydir Task-Masala berilganda hamma tomonlama harakat qilayotgandek
kimdir GPTdan kimdir uzi yana kimdir ustozlaridan .... yane umumiy qilsak Qo'yilgan muammoni yechish uchun HARAKAT!

Let's solve the Daily Leetcode task. 2874. Maximum Value of an Ordered Triplet II

Bizga nums butun sonlar massivi berilgan. 
Biz shunday uchlikni topishimiz kerakki uchlik ketma ket (i,j,k va i < j < k) kelsin
va (nums[i] - nums[j]) * nums[k] mumkin bo'lgan eng katta manfiy bo'lmagan qiymatga ega bo'lsin.
Agar barcha uchliklarni qiymati  manfiy bo'lsa 0 qaytarilishi kerak. 

Kirish: nums = [12,6,1,2,7]
Chiqish: 77
biz (0,2,4) indexlarni tanlasak biz eng katta musbat qiymatga ega bo'lamiz.
(nums[0] - nums[2]) * nums[4] = (12-1) * 7 = 77

Kelilar masalani qism masalaga bo'lamiz va birgalikda ishlashga harakat qilamiz.
Qo'yidagicha oldimizga Task qo'yamiz
Bizga butun sonlar massivi berilgan biz undan shunday uchta son tanlashimiz kerakki (a,b,c)
(a - b) * c maksimal qiymatga ega bo'lsin

Masalan [1,2,3]
tartibni hisobga olmasak bizda bir nechi variant bor.
(1 - 2) * 3
(1 - 3) * 2
(3 - 1) * 2
(3 - 2) * 1

Xo'sh yechimni keyingi qismiga o'tishimiz uchun shu joyda to'xtalib bitta savolga izohlarda javob qoldirishga harakat qilamiz
Qachon (a-b)*c eng katta qiymatga ega bo'ladi?

Demak (i,j,k) uchta index tanlash kerak ki i < j < k bo'lsin
va (nums[i] - nums[j]) * nums[k] eng katta nomanfiy son bo'lishi kerak.
yuqoridagi namunaga bersak (3 - 1) * 2 eng katta qiymatga ega bo'ladi.
Bu degani nums[i]—>eng maximum son nums[j] esa eng minimum son nums[k]->esa ikkinchi eng katta son bo'lishi kerak
lekin muammo shunda ki bular ketma ket kelishi kerak
Tassavur qilamiz biz i- urinda turibmiz yane [12,6,1,7] sonlar berilganda
biz 6 sonini ko'rayotgan bo'lsak shu songacha bo'lgan chap tomondagi eng katta son bu 12
o'ng tomondan hisoblaganda esa eng katta son 7 bo'ladi
demak ikkita massiv tuzamiz
prefixMax - bu massiv 0..i - songacha bo'lgan eng katta elementni joylashtiramiz.
postfixMax - |n| .. i (o'ngdan chapga) bo'lgan eng katta elementni joylashtiramiz.

[12,6,1,7] shu massiv asosida bizni prefix postfix Maximumlarimiz qo'yidagicha bo'ladi.

prefixMax = [12, 12, 12, 12]
postfixMax =[12, 7, 7, 7]
bizda chap va o'ng tomondagi eng katta elementlar bor
massivni 1 - elementidan boshlab oxiridan bitta oldingacha bo'lgan elementlarni nums[j] o'rniga joylashtirib eng katta qiymatni olamiz

class Solution {
public:
    long long maximumTripletValue(vector<int>& nums) {
       int n = nums.size();    
       std::vector<int> leftPrefixMax(n), rightPostfixMax(n);

       leftPrefixMax[0]       = nums[0];
       rightPostfixMax[n - 1] = nums[n - 1];
       
       for(int i = 1; i < n; i++){
          leftPrefixMax[i]           = std::max(leftPrefixMax[i - 1], nums[i - 1]);
          rightPostfixMax[n - i - 1] = std::max(rightPostfixMax[n - i], nums[n - i]); 
       }

       long long maxTripletValue = 0;
       for(int j = 1; j < n - 1; j++){
           long long currentValue = (leftPrefixMax[j] - nums[j]) *1ll * rightPostfixMax[j];
           maxTripletValue        = std::max(maxTripletValue, currentValue);
       }

       return maxTripletValue;
    }
};

PS: bunda biz O(N) vaqt va O(N) xotira ishlataypmiz. qo'shimcha xotiradan voz kechish mumkin harakat qilib ko'ring!

👩‍💻🧑🏻‍💻Yandex Uzbekistan dasturlash va matematika bo‘yicha intellektual tanlov — Coding and Math Contest'ni tashkil etmoqda. Bu o‘z bilimlaringizni sinovdan o‘tkazish, dunyodagi yetakchi ekspertlar tomonidan tayyorlangan topshiriqlarni bajarish va qimmatbaho sovg‘alarni qo‘lga kiritish imkonini beradi.

Kimlar ishtirok etishi mumkin:
• O‘zbekiston oliy o‘quv yurtlari talabalari,
• O‘zbekistonda ishlaydigan IT-mutaxassislari.
Ishtirok etish uchun talablar: Zamonaviy dasturlash tillari, algoritmlar, statistika, ehtimollar nazariyasi, matematik analiz va chiziqli algebra bo‘yicha bilimlar talab etiladi.

Tanlov formati:
• Ikki onlayn bosqich — dasturlash va matematika bo‘yicha har biri 6-10 ta vazifadan iborat.
• Til: inglizcha.
• Ishtirok: bepul.
• Final: oflayn mukofotlash marosimi, Yandex Uzbekistan tomonidan sovg‘alar va mukofotlar.

Nega ishtirok etish kerak?
• O‘zingizni sinovdan o‘tkazing — vazifalar xalqaro olimpiadalar va ICPC darajasidagi topshiriqlarga teng.
• Tan olinish va mukofotlar olish — 65 mln so‘mlik mukofot fondi 8 ta eng yaxshi ishtirokchi orasida taqsimlanadi, qolgan ishtirokchilar esa qimmatbag‘o sovg‘alarga ega bo‘lishadi.
• Hamjamiyatga qo‘shiling — tanlov dasturlash va matematikadan ishtiyoqi baland talabalar va yosh mutaxassislarni birlashtiradi.

Qanday ishtirok etish mumkin?
Ro‘yxatdan o‘tish: 18 aprelga qadar havola orqali.
Hamkorlar: New Uzbekistan University, ML Community (INHA University), Yandex ma’lumotlarni tahlil qilish maktabi.

O‘z mahoratingizni sinovdan o‘tkazing, intellektual hamjamiyatga qo‘shiling va Yandex Uzbekistan Coding and Math Contest'da g‘olib bo‘ling!💥

Bunaqasu bulmagan 2:0
Hakam sotilgan bulsayam bizni jamoaa yutdi 🤩

Galati qurilmacha berishdi 😂

CLion endi bepul non commercial shaklda chiqdi.
C/C++ ning eng yaxshi IDE barcha commercial proektlarda aynan shu IDE ishlatiladi.
Endilikda talabalar yoki C++ qiziquvchilari bepul ko'rinishdan foydalanishi mumkin.

Let's find bug!

Leetcode linki shu yerda

Masala mazmuni qisqacha shunday

Sizga nums nomli butun sonlardan iborat massiv berilgan.
Shunday answer massivini qaytaringki, answer[i] qiymati nums[i] dan tashqari nums dagi barcha elementlar ko'paytmasiga teng bo'lsin.

Massivning har qanday prefiksi yoki sufiksining ko‘paytmasi 32-bitli butun songa sig‘ishi kafolatlangan.

Misol 1:

Kiritish: nums = [1, 2, 3, 4]
Chiqish: [24, 12, 8, 6]
Misol 2:

Kiritish: nums = [-1, 1, 0, -3, 3]
Chiqish: [0, 0, 9, 0, 0]
Cheklovlar:

2 <= nums.length <= 10⁵
-30 <= nums[i] <= 30
Kiritilgan qiymatlar shundayki, answer[i] 32-bitli butun songa sig‘ishi kafolatlangan.

Qo'yida kod keltirilgan sizning vazifangiz aynan qaysi holatlarda bu kod ishlamay qolishi mumkin.
Yane bug ni topish.
Javoblarni izohda kutib qolaman

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
         int n = nums.size();
         std::vector<int> ans;

         int prod = std::accumulate(nums.begin(), nums.end(), 1, 
                                                        std::multiplies<int>());//barcha elementlar ko'paytmasi
         for(int i = 0; i < n; i++){
            ans.emplace_back(prod / nums[i]);
         }

         return ans;
    }
};

Shu bugungacha drogon frameworkni contribut qilayotgan edim. Endi astalik bilan Yandex ning userver frameworkiga otaman.
Sizham biror nimaga contribut qilayapszmi?
Izohlarda yozib qoldiring