မှတ်ချက် – ဒီ Post သည် Algorithm Interview Preparation အပိုင်းဆက်ဖြစ်သည်။

ကျွန်တော်ဒီနေ့ Solve လုပ်မှာကတော့ Two Number Sum Problem ဘဲဖြစ်ပါတယ်။ ဘယ်လို Solve လုပ်မလဲဆိုတာမပြောခင် ဘာကပြဿနာလဲဆိုတာကို တစ်ချက်ကြည့်လိုက်ရအောင်…

Argument အနေနှင့် Number Array List တစ်ခုပါမယ် Second Argument Target Value တစ်ခုပါမယ်။ ကျွန်တော်တို့ရေးရမယ့် Function က Array ထဲက Number နှစ်ခုပေါင်းထည့်ပြီးရတဲ့ Target Value Pair ပါတယ်ဆိုရင် true return ပြန်ရမယ်။ တကယ်လို့မပါဘူးဆိုရင် false return ပြန်ရမယ်

ဥပမာ – [3, 5, 2, -4, 8, 11], 7 ပေးတယ်ဆိုရင် ကျွန်တော်တို့က [[5, 2], [-4, 11]] ဆိုပြီးရှိတဲ့အတွက် true return ပြန်ပေးရမယ်။ ဘာလို့လည်းဆိုရင် (5 + 2) နှင့် (-4 + 11) တွေရဲ့ Total Sum က Target 7 ဖြစ်နေတာကိုး။

ပုံမှန် Brute Force Soluction

ကျွန်တော်တို့ပုံမှန်ဆိုရင်ဒါမျိုးကိုဘယ်လိုရှင်းမလဲ… number list array ကို Double Loop ပတ်ပြီးတော့ ပထမ Loop ထဲက Array Value ကို ဒုတိယ Loop နှင့် တစ်ခုချင်းဆီပေါင်းထည့်မယ်။ Target Value ရတဲ့ Pair တွေ့တယ်ဆိုရင် initial array မှာသွား assign လုပ်လိုက်မယ်။ ပိုပြီးမြင်သာအောင် အောက်က JavaScript Code ကိုတစ်ချက်ကြည့်လိုက်ရအောင်…

Worst Case Time and Space Complexity

ဒီ Bruce Force Solution ရဲ့ Time Complexity က O(n^2) ဖြစ်ပါတယ်။ ဘာလို့လည်းဆိုရင် ကျွန်တော်တို့ worst-Case မှာ Array ကို Double Loop ပတ်ရမှာကိုး။

Array Sort Walking Inward အသုံးပြု Solution

ဒီနည်းကတော့ Array ကို Sort လုပ်ပြီးတော့အတွင်းပိုင်းတဖြည်းဖြည်းဝင်လာပြီး Target Value ရှာတဲ့နည်း။ ဘယ်လိုအလုပ်လုပ်လဲဆိုရင် Sort လုပ်ပြီးသား Array ကို left အငယ်ဆုံးနှင့် Right အကြီးဆုံးပေါင်းပြီးတော့ target value နှင့်ညီလားဆိုပြီးကြည့်တာပါ။ တကယ်ကြီးနေတယ်ဆိုသေချာတယ် Right အကြီးဆုံးကိုလျှော့ကမယ် ထိုနည်းအတိုင်းဘဲငယ်တယ်ဆို Left အငယ်ဆုံးကို တစ်ပေါင်းပေးပြီးတော့ target value ရှိလားဆိုတာရှာတာပေါ့။

ဒီ Array Sort Walking Inward Solution ရဲ့ Time Complexity ကတော့ Sorting Algorithm ပေါ်မူတည်ပါလိမ့်မယ်။ ပုံမှန် Sorting Algorithm ရဲ့ Time Complexity ကတော့ O(n log n)။

Hash Table အသုံးပြု Solution

hash table အသုံးပြုရှင်းတာကတော့ပိုပီးရှင်းမယ်ထင်တယ်။ Idea ကတော့ target – လက်ရှိ index value ကို hash မှာထည့်ထားတယ်။ နောက် loop ထဲမှာဘဲအဲ့ value ရှိလားစစ်တယ်။ ရှိတယ်ဆို true။ မရှိဘူးဆို false။

function towSum(arr, S) {
    const hash = {}
    for(let i=0; i < arr.length; i++) {
        const target = S - arr[i]
        
        if(hash[arr[i]] != undefined) {
            return true
        }

        hash[target] = i
    }
    return false
}

ဒီ Hash Table အသုံးပြုတဲ့ method မှာဆို Time Complexity က O(n) ဖြစ်ပီးတော့ Space Complexity ကလဲ O(n) ဖြစ်ပါတယ်။

ကြမ်းကိုးများ

• CS9: Problem-Solving for the CS Technical Interview