Bugungi LeetCode masalasini ko'ramiz.
Implement the ProductOfNumbers class:

ProductOfNumbers() Initializes the object with an empty stream.
void add(int num) Appends the integer num to the stream.
int getProduct(int k) Returns the product of the last k numbers in the current list. You can assume that always the current list has at least k numbers.

The test cases are generated so that, at any time, the product of any contiguous sequence of numbers will fit into a single 32-bit integer without overflowing.

Yane sodda qilib aytganda sinfdagi berilgan metodlarni implement qilish kerak.
````
add(num) bu sinfga element qushadi
getProduct(int k) oxirgi k ta elementlarni ko'paytmasini qaytaradi.

Bu masalaga istalgan AI yechim bera oladi. Lekin biz Engineer sifatida uni kodlarini optimizatsiya qila olamizmi?
Oddiy yechimi quyidagi kurinishda bo'lishi mumkin.

```cpp
class ProductOfNumbers {
public:
    ProductOfNumbers() {

    }

    void add(int num) {
        data_.push_back(num);
    }

    int getProduct(int k) {
        long long pr = 1;

        for(int i = 0; i < k; i++) {
            pr *= data_[data_.size() - i - 1];
        }

        return pr;
    }

private:
    std::vector<int> data_;
};

Bu yechim qushishda O(1) getProduct da O(K) ta amal bajaradi.
Xotiradan esa T(N) N bu yerda nechi marta add qilingani.

Siz buni optimizatsiya qila olasizmi?
Barchasini O(1) gacha yane hammasida amallar soni maksimal minimum bulsin.
izohlarda yechimlaringizni yuborishingiz mumkin. (Istalgan tilda)

The image contains a solution to a LeetCode problem. Can you find a bug?
Problem link
#review
#bug

Leetcode Daily-Question
Sanoq tizimlar goyasidan kelib chiqadi.
Tassavur qiling 112(3-lik sanoq sistemasida) berilgan bo'lsin. Bu sonni 10 lik sanoq tizimiga o'girsak 1*3^2 + 1*3^1 + 2 * 3^0 Shartda aytilganidek har bir 3 ning darajasi bir marta qatnashi kerak. Demak bizni javobda 3^0 darajasi 2 marta qatnashaypti natija qoniqarsz.

Endi uziz yoqtirgan (Faqat uziz bu muhim chunki istlagan AI buni Middle darajada bemalol yozib beradi) dasturlash tilizda kodini yozishga harakat qiling. Eng optimal kodni kanalga joylashtiraman

Bugun ko‘zimga juda yoqimli bir yangilik tashlandi — shogirdimning videosi xabar.uzda chiqan ekan.
Dilafruzaxonning fikr va hayotiy mulohiza yuritishi yana bir karra o'sganini ko'rib juda xursand bo'ldim.

Постараюсь честно выразить своё мнение о том времени, когда я обучал Дилафруз.
За каждым успехом стоят годы труда и поддержки.
Мама, которая верила, вдохновляла и шла рядом, даже когда было трудно. Именно её забота, терпение и самоотверженность стали тем фундаментом, на котором сегодня строится каждое достижение Дилафруза.

Leetcode Daily Question
Given an array nums sorted in non-decreasing order, return the maximum between the number of positive integers and the number of negative integers.

In other words, if the number of positive integers in nums is pos and the number of negative integers is neg, then return the maximum of pos and neg.

Note that 0 is neither positive nor negative

Example 1:

Input: nums = [-2,-1,-1,1,2,3]
Output: 3
Explanation: There are 3 positive integers and 3 negative integers. The maximum count among them is 3.


Bir qarashda osongina masalaga uxshaydi va rostanham shunday. Shunchaki bir qator kod yozilsa buldi deyishadi Python dasturchilar taxminan quyidagicha

class Solution {
public:
    int maximumCount(vector<int>& nums) {
        return 
            std::max(std::ranges::count_if(nums,[](auto a){ return a < 0; }),
                    std::ranges::count_if(nums,[](auto a){ return a > 0; }));
                
    }
};

Lekin bu yechimni chuqur tahlillasak Manfiy sonlarni topish uchun bir marta aylanib chiqishimiz va musbat sonlar uchun ham shunday bir aylanib chiqishimiz zarur. Bu esa O(N)+O(N)=O(N) Time Complexity ga ega.

PS: Lekin bu eng optimal yechim emas. Bundanam optimal yechim mavjud. qanday deysizmi?
Bir o'ylab kuring nega bizga tartiblangan sonlar berilmoqda?
Bu nimadan darak.
Eng katta manfiy songa eng yaqin son qaysi?
Binar qidiruvda lower bound va upper bound nimani anglatadi?

Try to solve this problem with O(log N) time complexity and O(1) memory. Leave your code in a comment

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.