Design browser history (leetcode)

Category: mm

Question ကိုဒီလင့်မှာသွားဖတ်နိုင်ပါတယ်။

Requirement

မေးထားတာကတော့ရှင်းရှင်းလေးပါမယ်။ URL တွေကို visit လုပ်မယ်နောက် browser တွေလိုမျိုး forward/backward လုပ်လို့ရရမယ်ပေါ့ဒါပါပဲ။ အဲ့မှာဥပမာကိုယ်က

• ပထမ google.com ကိုသွားတယ်။ နောက် facebook.com ကိုသွားတယ်။ Backward ပြန်လုပ်ရင် google.com ကိုသွားရမယ်။ နောက်အဲ့ကနေမှ forward ပြန်လုပ်ရင် facebook.com ကိုပြန်ရောက်သွားမယ်။
• ပြီးတော့ twitter.com ကို visit ထပ်လုပ်မယ်။ အဲ့မှာ history က၃ခုဖြစ်သွားပြီ။ 1) google.com 2) facebook.com 3) twitter.com
• backward (facebook.com ကိုပြန်ရောက်သွားပြီ) လုပ်ပြီး yahoo.com ကိုသွားရင် twitter.com ကိုအရင် delete ရမယ်။ ဆိုလိုချင်တာက history ကအောက်ကလိုဖြစ်ရမယ်ပေါ့။
• ဆိုတော့ 1) google.com 2) facebook.com 3) yahoo.com

implement ရမယ့် requirement ကဒါပါပဲ။ ဆိုတော့အပေါ်က example မှာက backward/forward ကို၁ခါပဲလုပ်ပြသွားတာ။ requirement က N steps move နိုင်တယ်တကယ်က။

Thought Process

Leetcode problem တစ်ခုကို solve မယ်ဆိုအဖြေတန်းရေးတာကကောင်းတာမဟုတ်ဘူး။ Requirement ကိုသေချာနားလည်အောင်ဖတ်ရမယ်။ နောက် edge cases တွေစဥ်းစားရမယ်။ ဒါကို pseudocode မရေးခင်မှာထဲက တွေးသင့်တယ်။

Edge cases

• Backward/Forward ကို N steps နဲ့လုပ်နိုင်တယ်ဆိုတော့အကယ်လို့သာ N steps က history size ထက်ကြီးနေရင်သို့မဟုတ် 0 ထက်ငယ်နေရင် move မလုပ်သင့်ဘူးပေါ့။ ဥပမာ browser မှာ latest page ဆို forward button ကို disabled လုပ်ထားသလိုပေါ့။

Solution idea

ဒီ question က leetcode က medium question ဆိုတော့သိပ်တော့ခက်ခဲတာတော့မဟုတ်ပါဘူး။ ဒီ question အတွက် stack ကိုသုံးတာ suitable ဖြစ်တယ်။နောက် forward/backward လုပ်ပြီဆိုအခုက ဘယ် page ကိုရောက်နေတယ်ဆိုတာသိဖို့လိုတယ်။ ဒီအတွက်က cursor လိုမယ် current index ကိုသိမ်းဖို့။

ဆိုတော့ python နဲ့ solve မယ်။ ဒီမှာနဲနဲပြောစရာရှိတယ်။ Competitive programming တွေမှာ C++ ကအသုံးများတယ်နောက် interview တွေမှာတော့ Python ကအသုံးနဲနဲများတယ်။ Unless position specific, ပြောရရင် frontend engineer ခေါ်ရင်တော့ Javascript သုံးခိုင်းကောင်းသုံးခိုင်းလိမ့်မယ်။ C++ ကတော့ speed အတွက် Hackerrank လုပ်ဖူးတဲ့သူဆိုသိလိမ့်မယ်။ Interview တွေမှာက performance အတွက်ပါ score သပ်သပ်ရှိတယ်။ ဆိုတော့ brute-force solution သမားတွေဆို fail မှာပဲ။ Leetcode solve ရင်အကြံပေးချင်တာက bruteforce solution လောက်နဲ့ တော်ပြီလုပ်နေလို့မရဘူး။ Optimize ဖြစ်တဲ့ solution မျိုးလုပ်တတ်ဖို့လိုတယ်။ Optimize ဖြစ်မဖြစ်သိဖို့က time complexity တွက်တတ်ဖို့လိုတယ်။ ပြောရရင် computer science fundamental လေးတီးမိခေါက်မိ ရှိထားဖို့ပေါ့။

နောက် Facebook ဆို code ကိုပေးမ run တာ။ ဆိုလိုချင်တာ code ဘလိုအလုပ်လုပ်တယ်ဆိုတာကပါးစပ်နဲ့ thought process ပြောရတယ်။ Heap သုံးထားတယ်ဆို heap ကို in-deapth မေးတာ။ ဥပမာ heap insertion ဘယ်လိုအလုပ်လုပ်တယ်နောက် time-complexity ကဘယ်လောက်လဲစသဖြင့်။ Bruteforce နဲ့ solve ပြီး CS fundamental မသိရင် follow-up question မှာ fail မှာပဲ။

ဒီ post ကိုတော့ Python နဲ့ပဲ solve ထားတယ်။ လူအများစုလဲနားလည်တော့။

ကုဒ်ကအောက်ကလိုပေးထားတယ်။

class BrowserHistory:
    def __init__(self, homepage: str):

    def visit(self, url: str) -> None:

    def back(self, steps: int) -> str:

    def forward(self, steps: int) -> str:

### 1. init

အပေါ်ကပြောသလို stack နဲ့ cursor လိုမယ်ဆိုတော့ init မှာအဲ့တာတွေကို initialize အရင်လုပ်မယ်။ အဲ့မှာတခါထဲ homepage ကိုပါ stack ထဲထည့်မယ်။ current ကလက်ရှိရောက်နေတဲ့ page index ကိုသိမ်းဖို့။

 class BrowserHistory:
    def __init__(self, homepage: str):
        self.stack = [homepage]
        self.current = 0
...

### 2. visit

နောက်ဒီကောင်မှာက user က browser input မှာရေးရင် website သွားတဲ့ behavior လုပ်ရမယ်။ ဆိုတော့ဒီမှာ facebook.com သွားတယ်ဆို stack ထဲကို facebook.com ကိုထည့်မယ်၊ နောက် current ကိုလဲ အဲ့ facebook.com ရဲ့ index ကို point ရမယ်ပေါ့။ လက်ရှိရောက်နေတဲ့ page က facebook.com ဖြစ်ရမှာကို။

 ...
     def visit(self, url: str) -> None:
        self.stack.append(url)
        self.current += 1
...

### 3. back

ဒီကောင်က browser backward functionality ကို implement ရမှာ၊ ဆိုတော့လက်ရှိက facebook.com ကို visit ထားတယ် (index 1) အဲ့မှာ backward နိုပ်တယ်ဆို google.com ကိုပြန်သွားရမယ်ဆိုတော့ index ကို ၁ပြန်နုတ်ရမှာပေါ့။ ဒါပေမယ့် question မှာက N times move မှာဆို index ကို -N လုပ်ရမှာ။ နောက်အပေါ်ကပြောခဲ့သလိုမျိူး edge case ရှိမယ်နုတ်လိုက်လို့ 0 ထက်ငယ်ရင် 0 ယူရမှာ။ မဟုတ်ရင် index out of bound ဖြစ်သွားလိမ့်မယ်။

 ...
     def back(self, steps: int) -> str:
        self.current -= steps
        
        if self.current < 0:
            self.current = 0
        
        return self.stack[self.current]
...

ဒီ function ရဲ့ time complexity က O(1) ဘာလို့လဲဆို arithmetic operation က O(1) နောက် if condition ကလဲ O(1).

### 4. forward

သူလဲခုနကလိုပဲ။ edge condition ကတော့ length - 1 ထက်ကြီးရင် length - 1 ကိုယူရမှာ။

 ...
     def forward(self, steps: int) -> str:
        self.current += steps
        
        if self.current > len(self.stack) - 1:
            self.current = len(self.stack) - 1
        
        return self.stack[self.current]
 ...

သူကလဲ O(1) ပဲ။ len method ကို O(N) ထင်ကောင်းထင်လိမ့်မယ်။ Python documentation သွားဖတ်ကြည့်ရင်သိပါလိမ့်မယ်။ O(1) ဆိုတာဒီမှာပြောချင်တာရှိတာကကိုယ်သုံးတဲ့ language ကိုသေချာသိအောင်လုပ်ထားပါ။ ဥပမာ Java ထားပါတော့ string ၂ခုကို concatenation လုပ်ရင် O(N + M) ဘာလို့ဖြစ်တယ်ဆိုတာရှငိးပြတတ်ဖို့လိုပါတယ်။ မေးလဲမေးခံရဖူးပါတယ်။ ဘာလို့လဲဒီမှာသွားဖတ်လို့ရပါတယ်။

ကုဒ်ကအောက်ကလိုပါ။

class BrowserHistory:
    def __init__(self, homepage: str):
        self.stack = [homepage]
        self.current = 0

    def visit(self, url: str) -> None:
        self.stack.append(url)
        self.current += 1

    def back(self, steps: int) -> str:
        self.current -= steps
        
        if self.current < 0:
            self.current = 0
        
        return self.stack[self.current]

    def forward(self, steps: int) -> str:
        self.current += steps
        
        if self.current > len(self.stack) - 1:
            self.current = len(self.stack) - 1
        
        return self.stack[self.current]

ပြီးပြီလို့ထင်ရင်မပြီးသေးပါဘူး။ Case တစ်ခု handle ဖို့ကျန်ခဲ့တယ်။ အကယ်လို့ current page ကနောက်ဆုံး page မဟုတ်ဘူးဆိုရင်အသစ် visit တဲ့အခါသူ့နောက်က stack ထဲက pop ဖို့ပါပဲ။ အပေါ်မှာ facebook.com ကနေ yahoo.com ကိုသွားတဲ့ example ကိုပြောချင်တာ။ ဆိုတော့အောက်ကလို modify ဖို့လိုတယ်။

...
    def visit(self, url: str) -> None:
        while self.current < len(self.stack) - 1:
            self.stack.pop()
        
        self.stack.append(url)
        self.current += 1
...

Run time က O(N) ဖြစ်လိမ့်မယ်။ worst case ကရှေ့ဆုံးက page ကိုသွားပြီးတော့ visit တာပဲ။ အဲ့တာဆို N - 1 pages တွေ stack ထဲကနေ pop လုပ်ရလိမ့်မယ်။ Solution ကတော့ဒါပါပဲ။ Solution ရဲ့ space complexity ကတော့ N ပါ။ တစ်ခုမှ pop မလုပ်ပဲ visit ပဲလုပ်နေရင်အကုန်လုံးကို stack ထဲမှာသိမ်းရမှာပါ။

---

Coding interview preperation အတွက် Leetcode premium ကစျေးကြီးပေမယ့်အသုံးတည့်ပါတယ်။ မဟုတ်ရင် clone ဖြစ်တယ့် Lintcode ဆိုတာမှာ premium တချို့ကို free ပေးထားတာတွေရှိတယ်။ Coding interview preperation အတွက် data structure နဲ့ algorithm topic တွေသင်ပေးတာမှာ Grokking the coding interview ဆိုတဲ့ course ကမဆိုးဘူးပြောလို့ရတယ်။

နောက်ကျွန်တော်အရင်က Leetcode solve ထားတာတွေကိုလဲ repo တစ်ခုလုပ်ထားတာရှိတယ်။ အောက်မှာသွားကြည့်လို့ရတယ်။

https://github.com/the-robot/coding-challenges

နောက်ပိုင်းလဲအားရင်အားသလိုတော့ Leetcode ကစိတ်၀င်စားစရာကောင်းတဲ့ question လေးတွေကို solve ပြီး explain တာမျိုးလေးတွေရေးချင်တာတော့ရှိတယ်။