<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Tseng1026 on Medium]]></title>
        <description><![CDATA[Stories by Tseng1026 on Medium]]></description>
        <link>https://medium.com/@tseng1026?source=rss-fe3b38a664ea------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/2*MvuhlCeZ6vuSjY1enTBWlg.jpeg</url>
            <title>Stories by Tseng1026 on Medium</title>
            <link>https://medium.com/@tseng1026?source=rss-fe3b38a664ea------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Thu, 19 Nov 2026 01:03:34 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@tseng1026/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[無線通訊技術原理 | IoT]]></title>
            <link>https://tseng1026.medium.com/%E7%84%A1%E7%B7%9A%E9%80%9A%E8%A8%8A%E6%8A%80%E8%A1%93%E5%8E%9F%E7%90%86-iot-5aadcc34c2bd?source=rss-fe3b38a664ea------2</link>
            <guid isPermaLink="false">https://medium.com/p/5aadcc34c2bd</guid>
            <dc:creator><![CDATA[Tseng1026]]></dc:creator>
            <pubDate>Tue, 29 Aug 2023 07:08:05 GMT</pubDate>
            <atom:updated>2023-08-29T07:57:24.774Z</atom:updated>
            <content:encoded><![CDATA[<h3>Zigbee</h3><p>ZigBee 標準由連接標準聯盟 CSA （前為 ZigBee 聯盟）建立，由數百家企業組成，創建、維護，提供開放的全球標準。</p><p>Zigbee 是一種短距離，架構簡單，低傳輸速率（10Kbps ~ 250Kbps），低消耗功率的無線通訊技術。具有 master / slave 的屬性達到雙向通訊的功用，並有以下特性 1. 省電；2. 可靠度高 3. 支援大量網路節點。Zigbee 底層採用IEEE 802.15.4標準規範，以下是他的架構。</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*IJg7yfTQMHmqq7DpkLhDTw.png" /></figure><h4>Physical Layer</h4><ol><li>定義於 IEEE 802.15.4 Specification</li><li>用來定義網路裝置之間的資料傳輸，實際接觸數位訊號 0 或 1，負責直接控制 device，啟動和停止無線電收發器</li><li>定義頻帶、資料傳輸速率和其他關鍵參數</li></ol><h4>MAC Layer</h4><ol><li>定義於 IEEE 802.15.4 Specification</li><li>封裝 physical layer 的數位訊號為符合邏輯的 data frame，包含 MAC address，而這個 address 是獨一無二的可以讓網路設備彼此識別</li><li>frame 在 802.15.4 標準設計中分為四種，分別為 beacon frame、data frame、acknowledge frame 以及 MAC command frame</li><li>Zigbee 的傳輸方式可以分為 slotted 以及 unslotted<br>slotted — coordinator 定時發出 beacon frame 來做同步化的動作，適合用以傳輸定時性或需要低延遲的資料<br>unslotted — device 靠 CSMA / CA 來搶頻寬傳輸資料，適合用以傳輸不定時的資料</li></ol><h4>Network Layer</h4><ol><li>定義於 Zigbee Specification</li><li>將 address 加入 data frame 組成 packet，告訴其他 device 這筆 data 的來源及目的地</li><li>對 packet 做安全性處理，並傳送到指定目的地</li><li>找尋並維護各個 node 之間的路徑，搜尋鄰近的 node 並儲存資訊</li><li>支援 star topology、tree topology 以及 mesh topology<br>star topology — 容易同步、低延遲 one-hop，但難以擴充<br>tree topology — 低路由成本、允許 multi-hop，但重建成本大<br>mesh topology — 低延遲、允許 multi-hop、網路形成具彈性，但 route discovery 成本大，且需空間儲存路由表</li><li>Zigbee 的網路角色可以分為 coordinator (ZC)、router (ZR) 以及 end device (ZED) <br>coordinator — 建立管理網路、維護和控制網路，需要的時候發出 beacon data frame 以同步資料<br>router — 負責轉傳資料<br>end device — 擁有最低程度的功能，只需保證能與 parent node 溝通即可</li></ol><h4>Application Layer</h4><ol><li>定義於 Zigbee Specification</li><li>application support sublayer 維護 binding 表，用以尋找擁有所需服務的 device，並轉發傳遞資料</li><li>zigbee device object 定義 device 的網路角色，discover 同一網路的 device，並建立安全連結，進而發出或回應請求</li></ol><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=5aadcc34c2bd" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Snowboard 單板 I | 滑雪]]></title>
            <link>https://tseng1026.medium.com/snowboard-%E5%96%AE%E6%9D%BF-i-%E6%BB%91%E9%9B%AA-92e6c81839d?source=rss-fe3b38a664ea------2</link>
            <guid isPermaLink="false">https://medium.com/p/92e6c81839d</guid>
            <category><![CDATA[snowboarding]]></category>
            <dc:creator><![CDATA[Tseng1026]]></dc:creator>
            <pubDate>Mon, 03 Apr 2023 13:12:15 GMT</pubDate>
            <atom:updated>2023-04-03T13:12:15.488Z</atom:updated>
            <content:encoded><![CDATA[<p>翻了一下 CISA Reference Guide 覺得寫得真好，雖然可能有很多中譯版，但還是推薦各位自己去翻一下會有很多小細節（？）首先列出單板的五個最重要關鍵！</p><h3><strong>Technique 1 — Position &amp; Balance</strong></h3><p>Snowboard required the dynamic balancing skills, and the position plays a key role to balance and control.<br>單板滑雪是一個需要動態平衡的運動，而站姿位置對平衡及控制單板有在非常關鍵的影響。</p><p><strong>Neutral Position</strong></p><ol><li>A ready position with the ankles, knees, and hip joints equally flexed. This position optimizes the length and strength of key muscles so a rider can be both stable and maximize mobility, as needed.<br>踝關節、膝關節、髖關節保持身體放鬆以維持穩定性並且提高可移動性。</li><li>Shoulders and hips positioned square to the front foot angle.<br>肩關節與髖關節連線應垂直於前腳。</li><li>Arms relaxed, and in a natural position alongside the body.<br>雙手置於身體兩側，自然抬起。</li><li>Directing the head and eyes to face the direction of travel.<br>眼睛注視行進方向。</li><li>Distributing the body weight evenly between both feet.<br>雙腳平行承重（不把重心放在任何一腳）。</li></ol><h3>Technique 2 — Pivot</h3><p>A rider can develop an effective steering angle, by using rotating movements towards the toe-side or heel-side edges, placing the board across the line of momentum (direction of travel).<br>滑雪者可以透過轉向腳指邊緣或腳後跟邊緣創造出有效的轉向角度，使行進的路線發生偏轉。</p><p><strong>Rotation</strong></p><ol><li>Upper body rotational movements can generate more rotational force, but is generally an <strong>inefficient</strong> movement in turning because the effects of rotation take a long time to affect the snowboard.<br>透過上半身旋轉可以產生更大的力量，然而卻是很沒效率的，因為傳遞到雪板需要較長的時間。</li><li>Lower body rotational movements will have a <strong>quicker effect</strong> on the path of the snowboard, but will result in less rotational force.<br>透過下半身旋轉能夠更加快速的傳遞旋轉的訊號，然而其力量較小。</li><li>Full body rotational movements is the most powerful way to create direction change or spinning force. However, it is only effective once the snowboard’s edge is engaged in the snow and moving.<br>全身旋轉是最有力量也最有效率造成轉旋或旋轉的方式，然而他只有在雪板邊緣接觸到雪地並在移動當中才有效。</li></ol><p><strong>Counter Rotation</strong></p><ol><li>Quickest way to change the direction of the snowboard, for a limited distance (up to 180 degrees).<br>最快速改變方向的方式，用於有線距離下的轉彎（最多只能轉 180 度）。</li><li>Can compromise the balance and stability of the rider, and will require excessive correction to return to the neutral position.<br>會導致滑雪者的不平衡或降低其穩定性，並且需要通過額外的矯正才能回到居中站姿。</li><li>A “speed check” or emergency stop is a good example of counter rotation.<br>「Speed Check」或是緊急煞車就是一個 counter rotation 的絕佳例子。</li></ol><h3>Technique 3 — Edging</h3><p>For every change of direction, riders need to lean or tilt their mass to the inside of turn to remain balanced against turning force.<br>每一次方向改變，滑雪者都需要傾斜或移動中心到彎道內側以保持平衡。</p><p><strong>Inclination (Leaning)</strong></p><ol><li>Riders must incline inside the turning arc to counteract the turning forces.<br>傾斜的方向一定是彎道內側以對抗轉彎的離心力。</li><li>Edging purely through inclination is only achievable with a limited number of factors (snow conditions, speed, slope).<br>單純靠傾斜壓刃只能在特定環境下達成（雪況、速度、坡度等因素）。</li><li>As speed and performance increases, the amount of inclination increases as well.<br>當速度越快，傾斜的角度也應該要越大。</li></ol><p><strong>Angulation (Bending)</strong></p><ol><li>Angulation allows for the increase in edge angle while maintaining the rider’s center of mass closer to the base of support (for stability).<br>彎折使得我們可以同時增加煞車角度，並維持重心位置。</li><li>Angulation combined with inclination will provide the best results when it comes to reliable edge grip.<br>彎折與傾斜提供最可靠的煞車效果。</li></ol><p>At higher speeds on flatter slopes, more inclination can be used, as the forces of speed will help hold the rider up. As the slope increases, more angulation is needed in order to maintain edge grip.<br>在平緩的坡度下，越高的速度應該搭配越大的傾斜角度，因為速度可以保持滑雪者的身體不接觸地面；當坡度增加，應該使用更多的彎折以維持煞車效果。</p><h3>Technique 4 — Pressure</h3><p>Pressure is a sensory skill in which the rider moderates the forces acting on the board using movements in the lower joints to manage the changes under the snowboard due to terrain, speed and deformation of the snowboard.<br>壓力是一個只可意會不可言傳（？）的技能，滑雪者用以調節作用於雪板的力，以應對由於地形、速度、變形的變化。</p><p><strong>Reactive Pressure Management (Control)</strong></p><ol><li>Reactive pressure control involves mostly vertical adjustments in the lower joints in relation to the forces felt in the board due to terrain, slope, snow texture, or speed.<br>反應式壓力控制主要由於地面、坡度、雪況或速度反饋再經由下半身關節垂直調整。</li><li>Controlling pressures will enhance the rider’s ability to keep the snowboard in contact with the snow.<br>控制這類型的壓力可以提昇滑雪者與雪地的接觸，並更好的控制煞車。</li></ol><p><strong>Proactive Pressure Management (Create &amp; Release)</strong></p><ol><li>Proactive pressure management involves the rider planning ahead to proactively create pressure changes as a means of either control, creating or releasing the pressure in the snowboard.<br>主動式壓力控制主要由滑雪者主動創造壓力變化以創造、釋放施加於滑雪板的壓力。</li><li>Up, down, and mid-weighting movements can be employed to create pressure at various points in the turn or maneuver.<br>向上減壓、向下減壓或結合兩者被用在不同點上製造壓力以利轉彎或其他動作。</li></ol><h3>Technique 5 — Timing &amp; Coordination</h3><p>Timing &amp; Coordination refers to the skill of harmonizing skills and movements so that they are performed at the appropriate time and for the appropriate duration (Timing) and that multiple movements are combined into a common effort (Coordination).<br>時機與協調代表能夠在適當時機執行多個協調動作的能力。</p><p><strong>Timing</strong></p><ol><li>Successful timing relies on using the appropriate movement for the appropriate duration, given the intended outcome.<br>成功把握時機意指能夠在適當的時間使用適當的動作，以達到預期中的結果。</li><li>Starting and stopping a selected movement at the appropriate point in the turn or maneuver is also an important element of timing.<br>在轉彎或其他動作中選擇適當的時機開始或停止動做也是相當重要的一個元素。</li></ol><p><strong>Coordination</strong></p><ol><li>Advanced coordination skills will make many complex movements appear as one single effort.<br>進階的協調技巧使得多重要素看起來像是輕鬆完成的單一動作。</li><li>Riders can develop coordination skills by challenging themselves with the speed and combination / sequence of movements.<br>滑雪者可以夠過挑戰自己的速度或是動作組合來培養協調能力。</li></ol><p>沒有意外的話後面應該會是動作的拆解跟運用到的重點要素之類的（吧）祝你各位滑雪快樂&gt;&lt;</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=92e6c81839d" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[燈火輝煌的勝地 Marina Bay | Singapore]]></title>
            <link>https://medium.com/tseng1026/%E7%87%88%E7%81%AB%E8%BC%9D%E7%85%8C%E7%9A%84%E5%8B%9D%E5%9C%B0-marina-bay-singapore-fd7b0fb31566?source=rss-fe3b38a664ea------2</link>
            <guid isPermaLink="false">https://medium.com/p/fd7b0fb31566</guid>
            <category><![CDATA[journal]]></category>
            <category><![CDATA[singapore]]></category>
            <category><![CDATA[marina-bay]]></category>
            <category><![CDATA[traveling]]></category>
            <dc:creator><![CDATA[Tseng1026]]></dc:creator>
            <pubDate>Sat, 25 Feb 2023 14:39:17 GMT</pubDate>
            <atom:updated>2023-02-25T14:39:17.055Z</atom:updated>
            <content:encoded><![CDATA[<p>重新看了下自己還有哪些文沒有發，發現 wow 都回來台灣多久了，還有好多新加坡的文章沒有發⋯⋯2023 年來發個 2021 到訪的紀錄，時光旅人 is me 哈哈ＸＤ</p><p>就算經過了這麼久，依稀還是記得當時到訪的悸動，不管是夜晚在 Marina Bay Sands 觀景台俯瞰城市繁華，還是清晨在魚尾獅 Merlion 看著太陽漸漸從飯店後升起。我想，我應該還算是喜歡這個地方的吧⋯⋯？</p><p>Marina Bay 位在新加坡的市中心，林立的大廈、熙來攘往的街道，在行色匆匆壓得人喘不過氣的混濁喧囂中，我逼迫自己放慢步調，駐足在繁忙的街頭，嘗試去捕捉每個擦肩而過的美好。</p><p><strong><em>都邑規劃<br></em></strong>Marina Bay 最剛開始是船隻進入 Singapore River 之後，乘客或是貨輪要換乘小船 bumboat 的碼頭。20 世紀後期，填海造陸的工程如火如荼的展開，660 公頃的腹地就此誕生，也就是在這裡孕育出了我們所熟知的商業區、住宅區、藝術中心。這裡乾淨整潔、燈火繁榮，成為整個新加坡規劃最完善（也是最貴）的一個地區。</p><p><em>3 Oct 2021</em></p><p>位在日夜喧囂的市中心，Marina Bay 完整的展現了世界金融中心的姿態，卻又告訴我們這裡不僅只於此。</p><p>第一站是不容錯過的金沙酒店 Marina Bay Sands。Marina Bay Sands 是個大型渡假飯店，包含三座摩天大樓，上面透過類似太空飛船外型的屋頂相連（我看倒像潛艇堡）。頂樓有世界上最大的空中泳池，泳池畔則是一間 bar，白天晚上各有不同風味。360 度露天觀景台，可以飽覽整個 Marina Bay ，可惜我很窮困，而且之前上去過了，不然是可以花（很）點（多）錢上去看看的。</p><p>後方是 Gardens by the Bay，讓新加坡「花園中的城市」之稱名符其實。溫室花園總共分成三區，甚至有是內瀑布（不知道現在還是不是最大的），裡面有幾十萬種來自各地的奇花異草。另外大家應該最有印象的是 Supertree Grove 吧，造型令人驚艷之外，這些樹本身就是 16 層樓高的垂直花園，晚上有燈光秀，白天也一定要到空中步道俯瞰整個花園的景緻。</p><p>前方是大型購物商場，本來覺得又是千篇一律的新加坡商場，但走進去看還是覺得挺特別的。最引人矚目的不是國際精品名牌，而是以拱形玻璃搭建成而成的屋頂，陽光傾瀉而下，沐浴在溫暖之中，安慰自己買不起兩旁商店的悲桑ＱＱ在長形設計之中，兩旁是商店，而中間則是向澳門的威尼人酒店一樣，是條人工水道，有錢又有閒的人不妨來趟悠閒的運河之旅（我是兩個都沒有拉）水道底端還有特別的「雨眼」，用以收集雨水匯入運河，每小時會有一次的水流瀑布，超！級！酷！（第二次看就覺得是個小型回收水槽 大誤<br>補充：在河上的 Apple 旗艦店就是從這個 shopping mall 進去的喔ＸＤ</p><p>Marina Bay 還有一個亮點是賭場！外國人是不需要付費就可以進去的，秉持著不入虎穴焉得虎子的精神，我就進去小試身手了一把，轉了個 100 新幣就果斷撤退，我覺得其實裡面還挺不錯，有吃有喝有冷氣（客家精神）ＸＤ如果要以一個詞形容這個地方，我想，紙醉金迷再適合不過了。</p><p>對面是魚尾獅 Merlion，在我初次到訪新加坡的時候位於新加坡河河口，應該是 2020 年搬到現在的位置（？），倚著浮爾頓飯店 The Fullerton Hotel，與 Marina Bay Sands 相望，氣勢滂薄。Fishing Village、Lion City，魚尾獅把新加坡展現的淋漓盡致；順帶一提，魚尾獅面朝東方，因為朝陽昇起會帶來無盡的希望，也因此很推薦大家清晨的時候逛逛魚尾獅，可以看到旭日從 Marina Bay Sands 緩緩上昇的美景喔。<br>補充：相傳在風雨交加的一日來自 Srivijayan（現蘇門答臘島）的 Sang Nila Utama 王子從 Singapore River 登陸，並隨即看到一隻神獸，便將這座島取名為 Singapura （梵文的獅子）。</p><p><strong><em>這裡的每一撇都是宏大手筆下的高樓大廈，這裡的每一捺皆是五光十色的車水馬龍，讓人明亮，這裡是 Marina Bay。</em></strong></p><ul><li><a href="https://eresources.nlb.gov.sg/infopedia/articles/SIP_2016-06-21_160714.html?s=marina%20bay">Marina Bay</a></li><li><a href="https://www.visitsingapore.com.cn/see-do-singapore/places-to-see/marina-bay-area/">滨海湾 Marina Bay</a></li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=fd7b0fb31566" width="1" height="1" alt=""><hr><p><a href="https://medium.com/tseng1026/%E7%87%88%E7%81%AB%E8%BC%9D%E7%85%8C%E7%9A%84%E5%8B%9D%E5%9C%B0-marina-bay-singapore-fd7b0fb31566">燈火輝煌的勝地 Marina Bay | Singapore</a> was originally published in <a href="https://medium.com/tseng1026">tseng1026</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Head First Design Patterns I | Book Report]]></title>
            <link>https://medium.com/tseng1026/head-first-design-patterns-i-book-report-5a1ead78664?source=rss-fe3b38a664ea------2</link>
            <guid isPermaLink="false">https://medium.com/p/5a1ead78664</guid>
            <category><![CDATA[coding]]></category>
            <category><![CDATA[head-first-design-pattern]]></category>
            <category><![CDATA[python]]></category>
            <category><![CDATA[book-reports]]></category>
            <category><![CDATA[programming]]></category>
            <dc:creator><![CDATA[Tseng1026]]></dc:creator>
            <pubDate>Sat, 09 Jul 2022 11:37:14 GMT</pubDate>
            <atom:updated>2022-07-09T11:38:55.846Z</atom:updated>
            <content:encoded><![CDATA[<h3>Chapter 2 — Observer Pattern 觀察者模式</h3><blockquote>Let you define a subscription mechanism to notify multiple objects about any events that happen to the object they’re observing.</blockquote><ul><li>Define a one-to-many relationship between subject and observers</li><li>Observers are loosely coupled<br>1. the subject know nothings about them;<br>2. they implement the subject interface</li><li>To implement<br>1. subjects can push data to observers;<br>2. observers can pull data from subjects (consider more “correct”)</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*0NmFuZhp2x9sqizNj2tmqA.png" /></figure><p><a href="https://github.com/tseng1026/SideProject-DesignPattern/blob/master/observer.py">SideProject-DesignPattern/observer.py at master · tseng1026/SideProject-DesignPattern</a></p><h3>Chapter 3 — Decorator Pattern 裝飾者模式</h3><blockquote>Let you attach new behaviors to objects by placing these objects inside special wrapper objects that contain the behaviors.</blockquote><ul><li>Attach additional responsibilities to an object dynamically</li><li>Provide a flexible alternative to subclassing for extending functionality</li><li>Decorators are transparent to the component</li><li>Overuse can be complex and lead to low readability</li><li>To implement<br>1. a set of decorators wrap the concrete components;<br>2. the decorators and the components are the same type</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*ahHXzN7yY-w3_AI1weA7nQ.png" /></figure><p><a href="https://github.com/tseng1026/SideProject-DesignPattern/blob/master/decorator.py">SideProject-DesignPattern/decorator.py at master · tseng1026/SideProject-DesignPattern</a></p><h3><em>Chapter 4 — Factory Pattern 工廠模式</em></h3><blockquote>Provide an interface for creating objects in a superclass, but allows subclasses to alter the type of objects that will be created.</blockquote><ul><li>Define an interface to create an object, but let subclasses decide which class to instantiate</li><li>Let a class defer instantiation to its subclasses</li><li>Rely on inheritance</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*81fZBa4QCmwa1HuAX4dh1w.png" /></figure><p><a href="https://github.com/tseng1026/SideProject-DesignPattern/blob/master/factory.py">SideProject-DesignPattern/factory.py at master · tseng1026/SideProject-DesignPattern</a></p><blockquote>Let you produce families of related objects without specifying their concrete classes.</blockquote><ul><li>Provide an interface to create families of related or dependent objects without having to depend on their concrete classes</li><li>Rely on object composition</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*U3FIMfOKjuYbuLoo9-6kIg.png" /></figure><p><a href="https://github.com/tseng1026/SideProject-DesignPattern/blob/master/abstract_factory.py">SideProject-DesignPattern/abstract_factory.py at master · tseng1026/SideProject-DesignPattern</a></p><h3>Chapter 5 — Singleton Pattern 單件模式</h3><blockquote>Let you ensure that a class has only one instance, while providing a global access point to this instance.</blockquote><ul><li>Ensure that a class has just a single instance.</li><li>Provide a global access point to that instance.</li><li>To implement<br>1. make the default constructor private, to prevent other objects to initiate the Singleton class;<br>2. create a static creation method that acts as a constructor. Under the hood, this method calls the private constructor to create an object and saves it in a static field</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*wqHikE_vgo0zH3Ti8klN2Q.png" /></figure><p><a href="https://github.com/tseng1026/SideProject-DesignPattern/blob/master/singleton.py">SideProject-DesignPattern/singleton.py at master · tseng1026/SideProject-DesignPattern</a></p><h3><em>Chapter 6 — Command Pattern 命令模式</em></h3><blockquote>Turn a request into a stand-alone object that contains all information about the request. Let you pass requests as a method arguments, delay or queue a request’s execution, and support undoable operations.</blockquote><ul><li>Decouple an object, making a request from the one that knows how to perform it.</li><li>Parameterize clients with different requests, queue or log requests, and support undoable operations</li><li>A command object is at the center of the decoupling and encapsulates a receiver with an action</li><li>An invokers makes a request of a command object by calling its execute() method</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*1OxlXtRyRvlnlIDH9W_e6Q.png" /></figure><p><a href="https://github.com/tseng1026/SideProject-DesignPattern/blob/master/command.py">SideProject-DesignPattern/command.py at master · tseng1026/SideProject-DesignPattern</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=5a1ead78664" width="1" height="1" alt=""><hr><p><a href="https://medium.com/tseng1026/head-first-design-patterns-i-book-report-5a1ead78664">Head First Design Patterns I | Book Report</a> was originally published in <a href="https://medium.com/tseng1026">tseng1026</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[The Clean Coder | Book Report]]></title>
            <link>https://medium.com/tseng1026/the-clean-coder-book-report-e0ffc451288e?source=rss-fe3b38a664ea------2</link>
            <guid isPermaLink="false">https://medium.com/p/e0ffc451288e</guid>
            <category><![CDATA[coding]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[the-clean-coder]]></category>
            <category><![CDATA[book-reports]]></category>
            <dc:creator><![CDATA[Tseng1026]]></dc:creator>
            <pubDate>Wed, 30 Mar 2022 09:53:50 GMT</pubDate>
            <atom:updated>2022-03-30T09:53:50.531Z</atom:updated>
            <content:encoded><![CDATA[<p>This book is kind of the sequel to “Clean Code.” You can read the book report of “Clean Code” via the following link.</p><p><a href="https://medium.com/tseng1026/clean-code-book-review-2cb371bdb96">Clean Code I | Book Report</a></p><h3>Chapter 1 — Professionalism 專業主義</h3><blockquote>Professionalism is a loaded term. Certainly it is a badge of honor and pride, but it is also a marker of <strong><em>responsibility and accountability</em></strong>.</blockquote><h4>Take Responsibility 擔當責任</h4><p>Bugs always occur in your code, but it doesn’t mean you are not responsible for them. As becoming more mature in your profession, the error rate should decrease toward zero.</p><h4>Do Not Harm 不行損害之事</h4><p>The fundamental assumption for all software projects is that software has a flexible and solid structure which makes it <strong><em>easy to change</em></strong> without exorbitant costs. The only way to prove the software is easy to change is to <strong><em>keep making changes</em></strong>. Don’t be afraid of doing that if you have <strong><em>an automated suite of tests</em></strong>. And those tests undoubtedly help you know how your code works.</p><h4>Work Ethic 職業道德</h4><p>You should <strong><em>know your field</em></strong> using your extra time.</p><ul><li>Design Patterns</li><li>Design Principles — SOLID, component principles</li><li>Methods</li><li>Disciplines — test driven development (TDD), object oriented design (OOD), structured programming, continuous integration, pair programming</li><li>Artifacts — unified modelling language (UML), data flow diagram (DFD), structure chart, state transition diagrams and tables, flow charts, decision tables</li></ul><p>Always practice to keep skills sharp and ready; kata is a good technique. Moreover, it is a must to <strong><em>know your domain</em></strong> of the solutions they are programming and also <strong><em>identify the employer’s problems</em></strong>. You should spend time with experts and try to understand their principles and values.</p><h3>Chapter 2 — Saying No 説「不」</h3><blockquote>Do; or do not. There is no trying.</blockquote><blockquote>Slave are not allowed to say no. Laborers may be hestitant to say no. But <strong><em>professionals are expected to say no</em></strong>.</blockquote><h4>Adversarial Roles 對抗角色</h4><p>Managers pursue and defend their objectives as aggressively as they can, and professionals also pursue and defend their objectives. The conversation might be adversarial or even uncomfortable, but it might work out the best possible outcome that is mutually agreed upon by both.</p><h4>Being a Team Player 要有團隊精神</h4><p>Developers should represent what could, and could not, be done to the best of our ability to their managers. The word “<strong><em>trying</em></strong>” has many definitions. If there is the extra effort that could apply, there must be some effort held in reserve. Moreover, the promise to try is a commitment to apply extra effort to achieve the goal and the burden would be put on you. On the other hand, if you are not making any change to your behavior, the promising to try is fundamentally dishonest. Saying “no” aggressively to defend the position shows professionalism and is what being a team player is really about.</p><h4>The Cost of Saying Yes 説「是」的成本</h4><p>The temptation to be a superhero and solve the problem is huge although the task might require horrific overtime and sacrifice. But one should realize is that saying yes to dropping our professional disciplines is not the way to solve problems.</p><h3>Chapter 3 — Saying Yes 説「是」</h3><blockquote>Professionals are not required to say yes to everything that is asked of them.</blockquote><blockquote>When professionals say yes, they use the <strong><em>language of commitment</em></strong> so that there is no doubt about what they’ve promised.</blockquote><h4><strong>A Language of Commitment 言必信 行必果</strong></h4><p>There are three parts to making a commitment:</p><ol><li>You <strong><em>say</em></strong> you’ll do it.</li><li>You <strong><em>mean</em></strong> it.</li><li>You <strong><em>actually do</em></strong> it.</li></ol><p>There are very few people who, when they say something, they mean it and actually get it done. We should be able to recognize lack of commitment, need/should and hope/wish are several words that how noncommitment usually sounds like. Compared to that, the real commitment should be something that is under full control and can be done with a clear end time.</p><h3>Chapter 4 — Coding 寫程式</h3><blockquote>A marathon runner takes care of her body both before and during the race. Professional programmers conserve their energy and creativity with the same care.</blockquote><blockquote>Programming is so hard, in fact, that it is beyond the capability of one person to do it well.</blockquote><h4>Preparedness 做好準備</h4><p>Be concentrate on your work because you should juggle many competing factors at once, such as</p><ol><li>You should understand what problem you are solving and how to solve it.</li><li>Your code must solve the problem set provided by the customer.</li><li>Your code must fit into the existing system, and remain consistent within the language, platform, and all the warts of the current system.</li><li>Your code must be readable by other programmers.</li></ol><h4>The Flow Zone 流態區</h4><p><strong><em>Avoid the zone</em></strong>, since this state of consciousness is not really hyper-productive and is certainly not infallible. You might lose some of the big pictures when you are in the zone, and this makes you reverse back later.</p><h4>Debugging 除錯</h4><p>Debugging time is just as expensive to the business as coding time is, and therefore anything we can do to avoid or diminish it is good. Clearly zero is an asymptotic goal, but it is the goal.</p><h4>Help 幫助</h4><p>Programming is hard. No matter how skilled you are, you will benefit from another programmer’s thoughts and ideas. And therefore, programmers are responsible to be available to help each other; besides, try to ask for help when you are stuck or befuddled.</p><p>There are a few more chapters that include interesting examples that explain the previous content well; you can get some useful suggestions and knowledge by reading them. But generally, the main concept is to <strong><em>stick to the principles and disciplines</em></strong>, which is the most important thing I’ve learned from this book. If you like the articles, please give me some claps.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=e0ffc451288e" width="1" height="1" alt=""><hr><p><a href="https://medium.com/tseng1026/the-clean-coder-book-report-e0ffc451288e">The Clean Coder | Book Report</a> was originally published in <a href="https://medium.com/tseng1026">tseng1026</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[經驗分享]]></title>
            <link>https://tseng1026.medium.com/%E7%B6%93%E9%A9%97%E5%88%86%E4%BA%AB-9b3a0cb3afb5?source=rss-fe3b38a664ea------2</link>
            <guid isPermaLink="false">https://medium.com/p/9b3a0cb3afb5</guid>
            <category><![CDATA[interview]]></category>
            <category><![CDATA[careers]]></category>
            <category><![CDATA[experience-sharing]]></category>
            <dc:creator><![CDATA[Tseng1026]]></dc:creator>
            <pubDate>Fri, 25 Mar 2022 10:36:16 GMT</pubDate>
            <atom:updated>2022-03-25T10:36:16.721Z</atom:updated>
            <content:encoded><![CDATA[<h3>經驗分享 — AICS 工作面試</h3><p>過了超過半年，突然在尚未發佈的文章海裡看到的，覺得再不發就太荒唐了，但看一看還是不知道要加什麼內容ＱＱＱ</p><h3>Intro</h3><p>應徵職位：Machine Learning Engineer (MLE) 內推</p><p>碩士都要畢業了呢，一個 coursework 的最後硬是寫了一篇 paper 把自己搞到發瘋，沒時間準備面試，我是不是有病＾＾</p><p>（甚至最後加入 AICS 還發現我碩士指導教授在裡面，超瞎ＸＤ）</p><p>前面有面了一些 computer vision / machine learning 相關的新加坡公司，有鑒於疫情想要比較容易的往返台灣跟新加坡，所以最後選擇加入 AICS。</p><h3>Background</h3><ul><li>112 CS 學士畢，專題跟 computer vision 有關</li><li>NUS CS AI track 碩士畢，專題跟 computer vision 有關</li><li>NUS Research Assistant</li></ul><h3>Timeline</h3><ul><li>3rd May, 1st round interview</li><li>7th May, 2nd round interview</li><li>12th May, offer gets</li></ul><p>時間上應該不太準，因為已經是最後一間公司，然後我又在收尾論文，有要求 process 加速，所以 2nd round 就一次面了 3.5 小時。</p><h3>Preparation</h3><p>誠如前言所述，我正在水深火熱中，所以刷的題目也很少，大概前三四天開始刷，甚至只有 11 個 submissionsＸＤ</p><p>花比較多時間的是把底下兩篇自己整理的文章看完，雖然都沒考</p><ul><li><a href="https://medium.com/tseng1026/deep-learning-interview-questions-1780b3690821">Deep Learning | Interview Questions</a></li><li><a href="https://medium.com/tseng1026/machine-learning-interview-questions-abc70be53e68">Machine Learning | Interview Questions</a></li></ul><p>如果再來一次的話，會建議大家認真刷 leetcode 的題目就好，以 medium 的難度為主，然後一些經典的上課有教的演算法看一看。</p><h3>Interview</h3><p>因為疫情的關係，都是採取 virtual onsite interview 的模式。每關都是一個小時，有四關 tech interview，還有最後一關姑且稱之為 behaviour interview 是跟 CTO 聊聊，總共五關。</p><h4>Technical Interview</h4><p>流程就是自我介紹，小問一點經驗，大約 15 分鐘，接下來就是進入 coding 的環節 45 分鐘，基本上就是考白板題，有些問一題有些問兩題，遇到的題目類型有：</p><p>Graph<br>Linked List<br>Design</p><p>難度我自己是覺得大概在 medium 而已，經歷的部分問得比較少，可能想像 google 看齊可是搶不到人只好降低難度（威）</p><p>因為難度沒有那麼高，所以幾乎每一關都提前結束了，剩下蠻多時間，本來以為至少會考一些簡單不用 coding 的 machine learning 相關問題之類的，結果沒有ＸＤ直接進入問問題環節，所以希望大家準備足夠多的問題（？）二面連續面三關，到後面問到沒梗了，我就有直接抓完成一題寫大約 30 分鐘左右。</p><h4>Behaviour Interview</h4><p>問的問題主要是資訊跟醫療結合的開放性問題，資訊＋醫療迸出新滋味&gt;&lt;有幸之前有面是一家也蠻大間的公司，有詢問他們一些經驗跟分享，所以回答得還算不錯。</p><h3>Conclusion</h3><p>整體而言，前面的面試官人都蠻好的，蠻樂於分享他們的看法，也有幫我提希望能夠加速我的面試流程，才能夠跟火箭一樣一個禮拜直接拿到 offer。</p><p>小傻眼是 HR 有些信 title 沒有 “interview” 或是我的名字覺得問號；面的是 machine learning engineer 考得跟 general software engineer 沒兩樣讓人覺得問號，還有在新加坡 onboard 但是不在新加坡的 team 也有一點小問號。</p><p>但反正既來之則安之，繼續待在這個熱到不行的新加坡，疫情ＱＱ</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=9b3a0cb3afb5" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Algorithm | Interview]]></title>
            <link>https://medium.com/tseng1026/algorithm-interview-cb7f698a9001?source=rss-fe3b38a664ea------2</link>
            <guid isPermaLink="false">https://medium.com/p/cb7f698a9001</guid>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[interview-questions]]></category>
            <category><![CDATA[algorithms]]></category>
            <dc:creator><![CDATA[Tseng1026]]></dc:creator>
            <pubDate>Fri, 25 Mar 2022 09:27:13 GMT</pubDate>
            <atom:updated>2022-03-25T09:27:13.575Z</atom:updated>
            <content:encoded><![CDATA[<h3>Graph</h3><h4>Some Facts</h4><ul><li>tree 其實也是 graph 的一種</li><li>graph 由 vertex (node) 和 edge 組成，其中 edge 可以為有向或是無向的</li><li>最常用的表示方法就是開一個 set 或是 list 紀錄他的 neighbor；也可以開成正方形 matrix，以 matrix[i][j] = 1 表示 i 跟 j 之間有一個 edge，但很放費空間</li><li>最常遇到的解法可分為兩種：<strong><em>breadth first search </em></strong>和 <strong><em>depth first search</em></strong></li><li>如果要訪問途中每一個 node，通常首選就是 depth first search</li></ul><h4>Programming Tips</h4><ul><li>LeetCode (<a href="https://leetcode.com/list/988sm6sm">Problems</a> / Solutions)</li></ul><h3>Breadth First Search</h3><h4>Some Facts</h4><ul><li>從 root 開始，先探索每個鄰居；在深入不同分支之前，要走得更廣</li><li>可以透過 queue 實現，分為帶層、不帶層兩種，優勢在於找到目標時可以提早 return，e.g. 最短距離問題、尋找一定距離的目標</li></ul><h3>Depth First Search</h3><h4>Some Facts</h4><ul><li>從 root 開始，轉移到下一個分支之前，徹底研究每一個分支；在向廣度發展之前，先深入探索</li><li>DFS 可以透過 stack 或 recursion 實現，分為 inorder、preorder、postorder 三種，優勢在於通常寫起來比較簡潔，主要用於盲目尋找目標，e.g. 暴力尋找所有可能路徑</li></ul><h3>Divide and Conquer</h3><h4>Some Facts</h4><ul><li>運用遞迴的優點解決問題，只要定義 base case 及 recursive case 就相當於間接定義了無限長的序列</li><li>三步驟解 divide and conquer 問題<br>1. 把大問題切割成較小的同樣問題<br>2. 遞迴呼叫自己解決小問題，並在問題足夠小的時候直接解決<br>3. 整合小問題重建大問題的答案</li><li>當 subproblems 彼此之間互相獨立，且有重複性的時候，最適合使用</li><li>常常會重複計算 overlapping 的部分，造成效能低下</li></ul><h4>Programming Tips</h4><ul><li>通常寫起來邏輯比較清楚，面試時建議用這種方式</li><li>可能結合了 linked list 要注意回傳的是頭還是尾</li><li>可能可以透過 pointer，而不用傳整個 array 以提升效能</li><li>時間複雜度可以用 recursion tree 去想，會比較清楚</li></ul><h3>Dynamic Programming</h3><h4>Some Facts</h4><ul><li>computing 的解決方式就是窮舉，而 dynamic programming 就是幫助你聰明的窮舉</li><li>是一種用空間換取時間的方式，可以先跟面試官確認時間複雜度比較重要還是空間複雜度比較重要</li><li>常用於有兩個 features 的問題之上<br>1. overlapping subproblems<br>2. optimal substructure<br>e.g. 經典範例包含鐵條切割問題及背包問題</li><li>解法可分為兩種 ：<strong><em>top down with memoization </em></strong>及 <strong><em>bottom up with tabulation</em></strong></li><li>三步驟解 dynamic programming 問題<br>1. 找出 overlapping subproblems 及 optimal substructure<br>2. 用小問題的 solution 不斷重複定義現在問題的 solution<br>3. 開始動手計算小問題的 solution，並建立表格避免重複計算 overlapping 的部分</li></ul><h4>Programming Tips</h4><ul><li>LeetCode (<a href="https://leetcode.com/list/98go7c2e">Problems</a> / Solutions)</li></ul><h3>Top Down with Memoization</h3><h4>Some Facts</h4><ul><li>用 recursion 解把小問題的答案記在備忘錄裡，可以想像成跳著填表</li><li>只會解需要小問題，因此適合用於不需要解決所有小問題的情況</li></ul><h4>Programming Tips</h4><ul><li>python 可以用 cache / lru_cache 紀錄，或是透過 dictionary 自己實作</li><li>通常解起來比較直觀，所以面試蠻建議用這種解法，時間複雜度要小心</li></ul><h3>Bottom Up with Tabulation</h3><h4>Some Facts</h4><ul><li>按照問題的大小順序填表，由小問題到大問題逐一解決</li><li>相較於 top down method 沒有 recursion 的 overhead，在 maintain 表格也有較低的 overhead，所以通常比較有效率（by constant）</li><li>每個問題都會計算答案，適合用於每個問題都得解決的情況</li></ul><h4>Programming Tips</h4><ul><li>每一格代表的通常就是到當前的最佳解，最右下方的格子就會是最終結果</li><li>如果需要一個二維表格紀錄，但不需要上上個 row 的資訊的時候，可以只要使用兩個 row，交替更新，把 space complexity 降低</li></ul><p>有些題目可能會有一種以上的解法，滿建議大家都去實作看看；撇除上面特別分開寫的 graph 及 dynamic programming，也包含要遍歷 tree 相關的問題，在絕大部分情況下可能用 recursion 比較好寫，但可以試試看用 iteration 的方式。</p><p>演算法還有很多種，例如</p><ul><li>searching and sorting</li><li>binary search（python 裡面有一個東西叫 bisect 很好用！）</li><li>sliding window</li><li>union find</li><li>greedy</li></ul><p>等等。因為我沒有特別標記類型，所以就不特別寫了，但還是建議大家加減看一下有個印象，才不會到面試的時候腦袋一片空白。</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=cb7f698a9001" width="1" height="1" alt=""><hr><p><a href="https://medium.com/tseng1026/algorithm-interview-cb7f698a9001">Algorithm | Interview</a> was originally published in <a href="https://medium.com/tseng1026">tseng1026</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Data Structure | Interview]]></title>
            <link>https://medium.com/tseng1026/data-structure-interview-1eea35a655fa?source=rss-fe3b38a664ea------2</link>
            <guid isPermaLink="false">https://medium.com/p/1eea35a655fa</guid>
            <category><![CDATA[interview-questions]]></category>
            <category><![CDATA[data-structures]]></category>
            <category><![CDATA[programming]]></category>
            <dc:creator><![CDATA[Tseng1026]]></dc:creator>
            <pubDate>Mon, 07 Feb 2022 12:03:14 GMT</pubDate>
            <atom:updated>2022-03-25T07:50:05.056Z</atom:updated>
            <content:encoded><![CDATA[<h3>Dynamic Array (List)</h3><h4>Some Facts</h4><ul><li><strong>Time Complexity</strong><br>1. Access O(1)<br>2. Search、insert 和 delete O(n)<br>3. Append O(1) in average, O(n) in amortised worst case</li><li><strong>Pros<br></strong>1. 容易 access<br>2. 可以動態改變大小，提升空間利用率<br>3. 使用連續的 memory，迭代速度較 linked list 快</li><li><strong>Cons</strong><br>1. 難以 access 和 search<br>2. 使用非連續的 memory，迭代速度較 linked list 慢<br>3. 如果需要移除第一個 element 或接近開頭的 element 則使用 deque 會是比較好的選擇；因為不用移動後面的每一個 element</li><li><strong>Others</strong><br>1. python 的 list 如果超過當前 allocate 的 memory，內容會被複製到更大的空間內，因此 append 最壞情況下是需要 O(n) 的時間的</li></ul><h4>Programming Tips</h4><ul><li>畫圖！！！</li><li>最容易出錯的地方為第一個與最後一個，要確認每個動作執行時，資料結構是否為空</li><li>可用來實作 complete binary tree 或 heap</li><li>相對於 linked list 更適合使用 quick sort，而非 merge sort</li></ul><h3>Linked List</h3><h4>Some Facts</h4><ul><li><strong>Time Complexity</strong><br>1. Access 和 search O(n)<br>2. Insert 和 delete O(1)</li><li><strong>Pros<br></strong>1. 容易 insert 和 delete<br>2. 可以動態生成 node，任意改變資料結構的 capacity</li><li><strong>Cons</strong><br>1. 難以 access 和 search<br>2. 使用非連續的 memory，迭代速度較 array 慢</li></ul><h4>Programming Tips</h4><ul><li>LeetCode (<a href="https://leetcode.com/list/988cpizt">Problems</a> / <a href="https://github.com/tseng1026/LeetCode-DataStructure/tree/master/LinkedList">Solutions</a>)</li><li>題目類型可分為兩大類：<strong><em>pointer 修改</em></strong> 及 <strong><em>linked list 合併</em></strong></li><li>畫圖！！！</li><li>最容易出錯的地方為第一個與最後一個（邊界）節點，要確認每個動作執行時，資料結構是否為空，並確認是否創造出 cycle</li><li>可以使用 dummy_head 避免一些 empty 的問題</li><li>可以使用 two pointer的技巧解決問題<br>如果沒有 cycle，則 fast_pointer 會以兩倍的速度更快到達終點<br>如果有 cycle，則 fast_pointer 會在 len(cycle) 步之後趕上 slow_pointer</li><li>可用來實作 stack 或是 queue</li><li>相對於 array 更適合使用 merge sort，而非 quick sort</li></ul><h3>Stack</h3><h4>Some Facts</h4><ul><li><strong>Time Complexity</strong><br>1. Access 和 search O(n)<br>2. Insert 和 delete O(1)</li><li><strong>Pros<br></strong>1. 容易 insert 和 delete</li><li><strong>Cons</strong><br>1. 難以 access 和 search</li><li><strong>Others</strong><br>First In Last Out (FILO)</li></ul><h4>Programming Tips</h4><ul><li>LeetCode (<a href="https://leetcode.com/list/9ta2sni2">Problems</a> / <a href="https://github.com/tseng1026/LeetCode-DataStructure/tree/master/StackAndQueue">Solutions</a>)</li><li>經典題目包含括號平衡問題等等</li><li>最容易出錯的地方為 stack 為空時，要確認每個動作執行時，資料結構是否為空</li><li>可以加上 set 用以確認是否已經遍歷過該節點</li><li>可以搭配 DFS，主要用於盲目尋找目標，e.g. 暴力尋找所有可能路徑</li><li>可以透過 dynamic array或是 linked list 來實現 stack</li></ul><h3>Queue</h3><h4>Some Facts</h4><ul><li><strong>Time Complexity</strong><br>1. Access 和 search O(n)<br>2. Insert 和 delete O(1)</li><li><strong>Pros<br></strong>1. 容易 insert 和 delete</li><li><strong>Cons</strong><br>1. 難以 access 和 search</li><li><strong>Others</strong><br>First In First Out (FIFO)</li></ul><h4>Programming Tips</h4><ul><li>LeetCode (<a href="https://leetcode.com/list/9ta2sni2">Problems</a> / <a href="https://github.com/tseng1026/LeetCode-DataStructure/tree/master/StackAndQueue">Solutions</a>)</li><li>經典題目包含白路問題等等</li><li>最容易出錯的地方為 queue 為空時，要確認每個動作執行時，資料結構是否為空</li><li>可以加上 set 用以確認是否已經遍歷過該節點</li><li>可以搭配 BFS，找到目標時可以提早 return，e.g. 最短距離問題、尋找一定距離的目標</li><li>可以透過 dynamic array或是 linked list 來實現 queue</li></ul><h3>HashMap (Dictionary)</h3><h4>Some Facts</h4><ul><li><strong>Time Complexity</strong><br>1. Search O(1) in average, O(n) in amortised worst case<br>2. Insert 和 delete O(1) in average, O(n) in amortised worst case<br>3. Access O(1) in average, O(n) in amortised worst case</li><li><strong>Pros<br></strong>1. key 可以為任何 hashable 的 dataType<br>2. 容易 insert 和 delete<br>3. 透過 key 容易取得相對應的 value<br>4. 沒有重複的 key</li><li><strong>Cons</strong><br>1. 透過 value 難以取得相對應的 key<br>2. 難以 concat 或 apart<br>3. 沒有順序性<br>4. 沒有重複的 key<br>5. 為了降低 collision 的出現次數，要保證稀疏性，因此相當耗費空間</li><li><strong>Others</strong><br>1. python 的 dictionary 會先將 key 經過 hash function；如果遇到 collision，新的 element 可能被安排到別的位置存放，所以 element 的順序與加入的次序有關<br>2. python 會保證 1/3 的 hash bucket 為空；如果超過 threshold，內容會被複製到更大的空間內，進而造成順序的改變<br>3. python 3.6 之後的 dictionary 已經改為有順序的結構（原來是根據 hash function 後的值），並把空間利用率提高</li></ul><h4>Programming Tips</h4><ul><li>以空間換取時間，常用來降低時間複雜度</li><li>基於 Some Facts / Others 的第一點及第二點，不要在 traverse 的同時進行 insert 的動作</li><li>常用於需要快速查找相對應的 key-value pair</li><li>enumerate / zip 其實也是 hashmap 的一種</li></ul><h3>HashSet (Set)</h3><h4>Some Facts</h4><ul><li><strong>Time Complexity</strong><br>1. Search O(1) in average, O(n) in amortised worst case<br>2. Insert 和 delete O(1) in average, O(n) in amortised worst case<br>3. Union O(len(s)+len(t))<br>4. Intersection O(min(len(s),len(t))<br>5. Difference O(len(s))</li><li><strong>Pros<br></strong>1. value可以為任何 hashable 的 dataType<br>2. 容易 insert 和 delete<br>3. 容易確認 value 是否存在<br>4. 沒有重複的 value</li><li><strong>Cons</strong><br>1. 難以 access<br>2. 沒有順序性<br>3. 沒有重複的 value</li><li><strong>Others</strong><br>1. python 的 set 就是沒有相對應 value 的 dictionary（預設 key = value）<br>2. python 的 dictionary 會先將 value 經過 hash function；如果遇到 collision，新的 element 可能被安排到別的位置存放，所以 element 的順序與加入的次序有關<br>3. python 會保證 1/3 的 hash bucket 為空；如果超過 threshold，內容會被複製到更大的空間內，進而造成順序的改變</li></ul><h4>Programming Tips</h4><ul><li>以空間換取時間，常用來降低時間複雜度</li><li>基於 Some Facts / Others 的第二點及第三點，不要在 traverse 的同時進行 insert 的動作</li><li>常用於消除重複的 value</li><li>常用於執行 union、intersection 及 difference</li></ul><h3>Tree</h3><h4>Some Facts (typically binary search tree)</h4><ul><li><strong>Time Complexity</strong><br>1. Access 和 search O(logn)<br>2. Insert O(logn) 和 delete O(logn) ~ O(n)</li><li><strong>Pros<br></strong>1. 容易 access、search、insert<br>2. 可以動態生成 node，任意改變資料結構的 capacity</li><li><strong>Cons</strong><br>1. 難以 delete（要考慮怎麼把改底下的 node）<br>2. 當樹不平衡時，performance 會急劇下降，而平衡需要一些 effort<br>3. 沒有複雜度 O(1) 的操作</li></ul><h4>Programming Tips</h4><ul><li>LeetCode (<a href="https://leetcode.com/list/988cpizt">Problems</a> / <a href="https://github.com/tseng1026/LeetCode-DataStructure/tree/master/Tree">Solutions</a>)</li><li>題目類型可分為兩大類：<strong><em>breadth first search </em></strong>和 <strong><em>depth first search</em></strong></li><li>注意題目當中樹的種類！不要自己假設是 binary search tree 等等<br>Binary Tree：每個節點最多有兩個子節點的樹<br>Binary Search Tree：符合特定排序屬性的 binary tree；有些定義中，不能有重複的值；有些則將重複的值至於右子樹，須問清楚定義<br>Balanced Tree：並不代表左右子樹的大小完全相同，但可以保證能在 O(logn) 以內做完 insert 和 search，e.g. 紅黑樹、AVL 樹<br>Complete Binary Tree：按照順序填滿每一個節點，填滿順序為上到下、左到右<br>Full Binary Tree：每個節點，都有 0 或 2 個子節點，也就是說不會存在只有 1 個子節點的節點</li><li>先釐清開始點、結束點、目標！最容易出錯的地方為空節點、根節點、葉子（邊界）節點，要確認每個動作執行時，資料結構是否為空</li><li>BFS 可以透過 queue 實現，分為帶層、不帶層兩種，優勢在於找到目標時可以提早 return，e.g. 最短距離問題、尋找一定距離的目標</li><li>DFS 可以透過 stack 或 recursion 實現，分為 inorder、preorder、postorder 三種，優勢在於通常寫起來比較簡潔，主要用於盲目尋找目標，e.g. 暴力尋找所有可能路徑</li><li>可以搭配 dynamic programming 降低時間複雜度</li></ul><h3>Heap (Priority Queue)</h3><h4>Some Facts</h4><ul><li><strong>Time Complexity</strong><br>1. Access 和 search O(n)<br>2. Insert 和 delete O(logn) <br>3. 尋找 min / max O(1)</li><li><strong>Pros<br></strong>1. 容易尋找 min / max</li><li><strong>Cons</strong><br>1. 難以 access 和 search<br>2. 相對於 queue，insert 和 delete 複雜度較差<br>3. 沒有 iterator</li></ul><h4>Programming Tips</h4><ul><li>LeetCode (<a href="https://leetcode.com/list/93rsdmzr">Problems</a> / <a href="https://github.com/tseng1026/LeetCode-DataStructure/tree/master/Heap">Solutions</a>)</li><li>題目類型為：<strong><em>動態取 min / max</em></strong></li><li>priority queue 是抽象的 data type；heap 是一種 data structure，實現 priority queue 的方法之一</li><li>heap 是 complete binary tree，每一個 node 的值是整個 subtree 的 min / max</li><li>python 只有支援 minHeap，如果需要 maxHeap 可以把 value 加上負號</li><li>BFS 當中 將一般的 queue 轉為 priority queue，可實現 dijkstra algorithm</li><li>如果 list 不需要動態新增、減少 element，則可以用一般的 queue 解決就不需要 priority queue，因為時間複雜度較差，insert 和 delete 由 O(n) 升為 O(logn)</li><li>如果 list 本身就是有順序的，則可以用 binary search的方式尋找</li><li>可以搭配 dynamic programming 降低時間複雜度</li><li>可以透過 skip linked list或是 tree 來實現 priority queue</li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=1eea35a655fa" width="1" height="1" alt=""><hr><p><a href="https://medium.com/tseng1026/data-structure-interview-1eea35a655fa">Data Structure | Interview</a> was originally published in <a href="https://medium.com/tseng1026">tseng1026</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Graph | LeetCode]]></title>
            <link>https://medium.com/tseng1026/graph-leetcode-59356db9fe45?source=rss-fe3b38a664ea------2</link>
            <guid isPermaLink="false">https://medium.com/p/59356db9fe45</guid>
            <category><![CDATA[topological-sort]]></category>
            <category><![CDATA[graph]]></category>
            <category><![CDATA[interview-questions]]></category>
            <category><![CDATA[leetcode]]></category>
            <category><![CDATA[programming]]></category>
            <dc:creator><![CDATA[Tseng1026]]></dc:creator>
            <pubDate>Sat, 15 Jan 2022 13:50:47 GMT</pubDate>
            <atom:updated>2022-01-15T13:50:47.340Z</atom:updated>
            <content:encoded><![CDATA[<h4><a href="https://leetcode.com/problems/find-the-town-judge/">997. Find the Town Judge</a></h4><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/133bf4a4e1da459a7a8c00d3cff5a4e8/href">https://medium.com/media/133bf4a4e1da459a7a8c00d3cff5a4e8/href</a></iframe><h4><a href="https://leetcode.com/problems/find-center-of-star-graph/">1791. Find Center of Star Graph</a></h4><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/06ea0d35e86d2efb29cd23b034da5050/href">https://medium.com/media/06ea0d35e86d2efb29cd23b034da5050/href</a></iframe><h4><a href="https://leetcode.com/problems/find-if-path-exists-in-graph/">1971. Find if Path Exists in Graph</a></h4><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/8654249ffb08cbb019797cdcae420c77/href">https://medium.com/media/8654249ffb08cbb019797cdcae420c77/href</a></iframe><h4><a href="https://leetcode.com/problems/clone-graph/">133. Clone Graph</a></h4><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/f10eeb999e3ebc857a074de07d8fc9b3/href">https://medium.com/media/f10eeb999e3ebc857a074de07d8fc9b3/href</a></iframe><h4><a href="https://leetcode.com/problems/course-schedule/">207. Course Schedule</a></h4><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/ecf242eae8035b49be62cc2029e22ece/href">https://medium.com/media/ecf242eae8035b49be62cc2029e22ece/href</a></iframe><h4><a href="https://leetcode.com/problems/course-schedule-ii/">210. Course Schedule II</a></h4><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/43a507f2f3af86ea2d56d81516c403d4/href">https://medium.com/media/43a507f2f3af86ea2d56d81516c403d4/href</a></iframe><h4><a href="https://leetcode.com/problems/minimum-height-trees/">310. Minimum Height Trees</a></h4><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/2410200bae2add0adc9015166fc87196/href">https://medium.com/media/2410200bae2add0adc9015166fc87196/href</a></iframe><h4><a href="https://leetcode.com/problems/evaluate-division/">399. Evaluate Division</a></h4><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/b822e01acc0b9fd58ce0e21a8c034190/href">https://medium.com/media/b822e01acc0b9fd58ce0e21a8c034190/href</a></iframe><h4><a href="https://leetcode.com/problems/number-of-provinces/">547. Number of Provinces</a></h4><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/d22099f0ed95eaa610962ace27326879/href">https://medium.com/media/d22099f0ed95eaa610962ace27326879/href</a></iframe><h4><a href="https://leetcode.com/problems/redundant-connection/">684. Redundant Connection</a></h4><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/7d0a955198c305738299cc537d72a0a1/href">https://medium.com/media/7d0a955198c305738299cc537d72a0a1/href</a></iframe><h4><a href="https://leetcode.com/problems/network-delay-time/">743. Network Delay Time</a></h4><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/e31805d55e0ffc8367bebe67411527a8/href">https://medium.com/media/e31805d55e0ffc8367bebe67411527a8/href</a></iframe><h4><a href="https://leetcode.com/problems/is-graph-bipartite/">785. Is Graph Bipartite?</a></h4><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/bd4729aca4df1d709d7abac25ec04ab3/href">https://medium.com/media/bd4729aca4df1d709d7abac25ec04ab3/href</a></iframe><h4><a href="https://leetcode.com/problems/cheapest-flights-within-k-stops/">787. Cheapest Flights Within K Stops</a></h4><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/0b74661c07d5e1e637c82dadd402aff3/href">https://medium.com/media/0b74661c07d5e1e637c82dadd402aff3/href</a></iframe><h4><a href="https://leetcode.com/problems/all-paths-from-source-to-target/">797. All Paths From Source to Target</a></h4><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/d082e3daee1420438db0b0392753dd2b/href">https://medium.com/media/d082e3daee1420438db0b0392753dd2b/href</a></iframe><h4><a href="https://leetcode.com/problems/find-eventual-safe-states/">802. Find Eventual Safe States</a></h4><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/6271b4b3d00e458beab763656d05fb30/href">https://medium.com/media/6271b4b3d00e458beab763656d05fb30/href</a></iframe><h4><a href="https://leetcode.com/problems/keys-and-rooms/">841. Keys and Rooms</a></h4><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/72b7aaa39161af961f4971ae058cfdec/href">https://medium.com/media/72b7aaa39161af961f4971ae058cfdec/href</a></iframe><h4><a href="https://leetcode.com/problems/loud-and-rich/">851. Loud and Rich</a></h4><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/919a14da1eea47a811e861c86f86acf4/href">https://medium.com/media/919a14da1eea47a811e861c86f86acf4/href</a></iframe><h4><a href="https://leetcode.com/problems/possible-bipartition/">886. Possible Bipartition</a></h4><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/977bdc56e272c9b7f0ff8034e3420626/href">https://medium.com/media/977bdc56e272c9b7f0ff8034e3420626/href</a></iframe><h4><a href="https://leetcode.com/problems/most-stones-removed-with-same-row-or-column/">947. Most Stones Removed with Same Row or Column</a></h4><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/8b89e3c7076462ee38fc58f4e171de0f/href">https://medium.com/media/8b89e3c7076462ee38fc58f4e171de0f/href</a></iframe><h4><a href="https://leetcode.com/problems/satisfiability-of-equality-equations/">990. Satisfiability of Equality Equations</a></h4><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/771c4f0a0de482b2272c596e71da8efd/href">https://medium.com/media/771c4f0a0de482b2272c596e71da8efd/href</a></iframe><h4><a href="https://leetcode.com/problems/flower-planting-with-no-adjacent/">1042. Flower Planting With No Adjacent</a></h4><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/60ce1e212d722886cfbcc40d3d74b3e6/href">https://medium.com/media/60ce1e212d722886cfbcc40d3d74b3e6/href</a></iframe><h4><a href="https://leetcode.com/problems/shortest-path-with-alternating-colors/">1129. Shortest Path with Alternating Colors</a></h4><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/6181f6952bbbb58ba9ca9006928f6fb6/href">https://medium.com/media/6181f6952bbbb58ba9ca9006928f6fb6/href</a></iframe><h4><a href="https://leetcode.com/problems/validate-binary-tree-nodes/">1361. Validate Binary Tree Nodes</a></h4><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/f91fb02e86f0e767d16acbbc551361a0/href">https://medium.com/media/f91fb02e86f0e767d16acbbc551361a0/href</a></iframe><h4><a href="https://leetcode.com/problems/path-with-maximum-probability/">1514. Path with Maximum Probability</a></h4><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/7704bfa9b48d5b97bdd44a9df3eb0c88/href">https://medium.com/media/7704bfa9b48d5b97bdd44a9df3eb0c88/href</a></iframe><h4><a href="https://leetcode.com/problems/number-of-operations-to-make-network-connected/">1319. Number of Operations to Make Network Connected</a></h4><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/09ea16978504a3411699ef9018b99ad4/href">https://medium.com/media/09ea16978504a3411699ef9018b99ad4/href</a></iframe><h4><a href="https://leetcode.com/problems/find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance/">1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance</a></h4><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/041d4418d3907e9abc8f93f423629887/href">https://medium.com/media/041d4418d3907e9abc8f93f423629887/href</a></iframe><h4><a href="https://leetcode.com/problems/course-schedule-iv/">1462. Course Schedule IV</a></h4><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/88b8e921790a90bab7c90d7f7dc0f844/href">https://medium.com/media/88b8e921790a90bab7c90d7f7dc0f844/href</a></iframe><h4><a href="https://leetcode.com/problems/reorder-routes-to-make-all-paths-lead-to-the-city-zero/">1466. Reorder Routes to Make All Paths Lead to the City Zero</a></h4><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/239e226443f20e76847fafe12603c43f/href">https://medium.com/media/239e226443f20e76847fafe12603c43f/href</a></iframe><h4><a href="https://leetcode.com/problems/minimum-number-of-vertices-to-reach-all-nodes/">1557. Minimum Number of Vertices to Reach All Nodes</a></h4><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/0e3bab80a61942632675d4f045d2d8ba/href">https://medium.com/media/0e3bab80a61942632675d4f045d2d8ba/href</a></iframe><h4><a href="https://leetcode.com/problems/maximal-network-rank/">1615. Maximal Network Rank</a></h4><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/ac9b9251738506a79e20bf2b5f6619bd/href">https://medium.com/media/ac9b9251738506a79e20bf2b5f6619bd/href</a></iframe><h4><a href="https://leetcode.com/problems/number-of-restricted-paths-from-first-to-last-node/">1786. Number of Restricted Paths From First to Last Node</a></h4><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/ae37313c5be791e6210352eb819697b5/href">https://medium.com/media/ae37313c5be791e6210352eb819697b5/href</a></iframe><h4><a href="https://leetcode.com/problems/number-of-ways-to-arrive-at-destination/">1976. Number of Ways to Arrive at Destination</a></h4><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/ba15f835648a33ec0f88335771b2103d/href">https://medium.com/media/ba15f835648a33ec0f88335771b2103d/href</a></iframe><h4><a href="https://leetcode.com/problems/the-time-when-the-network-becomes-idle/">2039. The Time When the Network Becomes Idle</a></h4><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/a89a2e9572de55c2bb1a82cd7821f028/href">https://medium.com/media/a89a2e9572de55c2bb1a82cd7821f028/href</a></iframe><h4><a href="https://leetcode.com/problems/detonate-the-maximum-bombs/">2101. Detonate the Maximum Bombs</a></h4><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/bf90c9a2a69329aa3543c0bee1bf5a0e/href">https://medium.com/media/bf90c9a2a69329aa3543c0bee1bf5a0e/href</a></iframe><h4><a href="https://leetcode.com/problems/find-all-possible-recipes-from-given-supplies/">2115. Find All Possible Recipes from Given Supplies</a></h4><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/775e3f1cb4bebc54dc308130877d9bff/href">https://medium.com/media/775e3f1cb4bebc54dc308130877d9bff/href</a></iframe><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=59356db9fe45" width="1" height="1" alt=""><hr><p><a href="https://medium.com/tseng1026/graph-leetcode-59356db9fe45">Graph | LeetCode</a> was originally published in <a href="https://medium.com/tseng1026">tseng1026</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Binary Tree | LeetCode]]></title>
            <link>https://medium.com/tseng1026/binary-tree-leetcode-f5e9f95990a9?source=rss-fe3b38a664ea------2</link>
            <guid isPermaLink="false">https://medium.com/p/f5e9f95990a9</guid>
            <category><![CDATA[binary-tree]]></category>
            <category><![CDATA[interview-questions]]></category>
            <category><![CDATA[leetcode]]></category>
            <category><![CDATA[programming]]></category>
            <dc:creator><![CDATA[Tseng1026]]></dc:creator>
            <pubDate>Tue, 04 Jan 2022 05:47:50 GMT</pubDate>
            <atom:updated>2022-01-31T07:09:18.715Z</atom:updated>
            <content:encoded><![CDATA[<h3>Tree | Data Structure | Interview</h3><h3>Data Structure</h3><h3>Basic Operations</h3><h3>Some Facts (typically binary search tree)</h3><ul><li><strong>Time Complexity</strong><br>1. Access 和 search O(logn)<br>2. Insert O(logn) 和 delete O(logn) ~ O(n)</li><li><strong>Pros<br></strong>1. 容易 access、search、insert<br>2. 可以動態生成 node，任意改變資料結構的 capacity</li><li><strong>Cons</strong><br>1. 難以 delete（要考慮怎麼把改底下的 node）<br>2. 當樹不平衡時，performance 會急劇下降，而平衡需要一些 effort<br>3. 沒有複雜度 O(1) 的操作</li></ul><h3>Programming Tips</h3><ul><li>題目類型可分為兩大類：<strong><em>breadth first search </em></strong>和 <strong><em>depth first search</em></strong></li><li>注意題目當中樹的種類！不要自己假設是 binary search tree 等等<br>Binary Tree：每個節點最多有兩個子節點的樹<br>Binary Search Tree：符合特定排序屬性的 binary tree；有些定義中，不能有重複的值；有些則將重複的值至於右子樹，須問清楚定義<br>Balanced Tree：並不代表左右子樹的大小完全相同，但可以保證能在 O(logn) 以內做完 insert 和 search，e.g. 紅黑樹、AVL 樹<br>Complete Binary Tree：按照順序填滿每一個節點，填滿順序為上到下、左到右<br>Full Binary Tree：每個節點，都有 0 或 2 個子節點，也就是說不會存在只有 1 個子節點的節點</li><li>先釐清開始點、結束點、目標！最容易出錯的地方為空節點、根節點、葉子（邊界）節點，要確認每個動作執行時，資料結構是否為空</li><li>BFS 可以透過 queue 實現，分為帶層、不帶層兩種，優勢在於找到目標時可以提早 return，e.g. 最短距離問題、尋找一定距離的目標</li><li>DFS 可以透過 stack 或 recursion 實現，分為 inorder、preorder、postorder 三種，優勢在於通常寫起來比較簡潔，主要用於盲目尋找目標，e.g. 暴力尋找所有可能路徑</li><li>可以用 dynamic programming 降低時間複雜度</li></ul><h3>LeetCode (<a href="https://leetcode.com/list/988cpizt">Link</a>)</h3><h4><a href="https://leetcode.com/problems/same-tree/">100. Same Tree</a></h4><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/5a96b1266ba78ec312bc361bca53774b/href">https://medium.com/media/5a96b1266ba78ec312bc361bca53774b/href</a></iframe><h4><a href="https://leetcode.com/problems/symmetric-tree/">101. Symmetric Tree</a></h4><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/de990dd17d99988be6e28c6f6df0b087/href">https://medium.com/media/de990dd17d99988be6e28c6f6df0b087/href</a></iframe><h4><a href="https://leetcode.com/problems/maximum-depth-of-binary-tree/">104. Maximum Depth of Binary Tree</a></h4><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/dd77918392caba484688a01debe360fc/href">https://medium.com/media/dd77918392caba484688a01debe360fc/href</a></iframe><h4><a href="https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/">108. Convert Sorted Array to Binary Search Tree</a></h4><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/1b0a2d46446bb5905035de22621b33e7/href">https://medium.com/media/1b0a2d46446bb5905035de22621b33e7/href</a></iframe><h4><a href="https://leetcode.com/problems/balanced-binary-tree/">110. Balanced Binary Tree</a></h4><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/79b3d31e159178270a6e80d4258e55b1/href">https://medium.com/media/79b3d31e159178270a6e80d4258e55b1/href</a></iframe><h4><a href="https://leetcode.com/problems/minimum-depth-of-binary-tree/">111. Minimum Depth of Binary Tree</a></h4><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/68760c836ab25cd2c47c5abf10cb5f31/href">https://medium.com/media/68760c836ab25cd2c47c5abf10cb5f31/href</a></iframe><h4><a href="https://leetcode.com/problems/path-sum/">112. Path Sum</a></h4><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/1633be5ff6f417dc78b5a2416179fa1a/href">https://medium.com/media/1633be5ff6f417dc78b5a2416179fa1a/href</a></iframe><h4><a href="https://leetcode.com/problems/invert-binary-tree/">226. Invert Binary Tree</a></h4><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/ae60e1c98fb72f9f1f546cdd9ad6a36c/href">https://medium.com/media/ae60e1c98fb72f9f1f546cdd9ad6a36c/href</a></iframe><h4><a href="https://leetcode.com/problems/subtree-of-another-tree/">572. Subtree of Another Tree</a></h4><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/27b2b7ad1905e807c38fa479b1e988b8/href">https://medium.com/media/27b2b7ad1905e807c38fa479b1e988b8/href</a></iframe><h4><a href="https://leetcode.com/problems/leaf-similar-trees/">872. Leaf-Similar Trees</a></h4><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/cb1d04fb416b3062f7109fedfb9a857d/href">https://medium.com/media/cb1d04fb416b3062f7109fedfb9a857d/href</a></iframe><h4><a href="https://leetcode.com/problems/univalued-binary-tree/">965. Univalued Binary Tree</a></h4><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/6e8a5f4db93579a90228f700369163e6/href">https://medium.com/media/6e8a5f4db93579a90228f700369163e6/href</a></iframe><h4><a href="https://leetcode.com/problems/unique-binary-search-trees-ii/">95. Unique Binary Search Trees II</a></h4><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/250df4498272b82ce39bebc7a6570b9c/href">https://medium.com/media/250df4498272b82ce39bebc7a6570b9c/href</a></iframe><h4><a href="https://leetcode.com/problems/unique-binary-search-trees/">96. Unique Binary Search Trees</a></h4><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/07a80cdab3903452de5d908510d086a7/href">https://medium.com/media/07a80cdab3903452de5d908510d086a7/href</a></iframe><h4><a href="https://leetcode.com/problems/validate-binary-search-tree/">98. Validate Binary Search Tree</a></h4><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/8422f6066fb8ca6793158559bd201cde/href">https://medium.com/media/8422f6066fb8ca6793158559bd201cde/href</a></iframe><h4><a href="https://leetcode.com/problems/binary-tree-level-order-traversal/">102. Binary Tree Level Order Traversal</a></h4><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/788fea87dab5c9aa1e85d2dbf47fa058/href">https://medium.com/media/788fea87dab5c9aa1e85d2dbf47fa058/href</a></iframe><h4><a href="https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/">103. Binary Tree Zigzag Level Order Traversal</a></h4><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/17b13dc7284d5f219ad9d67615450f7b/href">https://medium.com/media/17b13dc7284d5f219ad9d67615450f7b/href</a></iframe><h4><a href="https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/">105. Construct Binary Tree from Preorder and Inorder Traversal</a></h4><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/19a39873bea4de62402c7976623ed014/href">https://medium.com/media/19a39873bea4de62402c7976623ed014/href</a></iframe><h4><a href="https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/">109. Convert Sorted List to Binary Search Tree</a></h4><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/0119b7136f369f1738a4ac65d8cda692/href">https://medium.com/media/0119b7136f369f1738a4ac65d8cda692/href</a></iframe><h4><a href="https://leetcode.com/problems/flatten-binary-tree-to-linked-list/">114. Flatten Binary Tree to Linked List</a></h4><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/e43bf470e5c4c3b9cc2e57561352f702/href">https://medium.com/media/e43bf470e5c4c3b9cc2e57561352f702/href</a></iframe><h4><a href="https://leetcode.com/problems/populating-next-right-pointers-in-each-node/">116. Populating Next Right Pointers in Each Node</a></h4><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/943673324b37e2da025bafc0e725f0f1/href">https://medium.com/media/943673324b37e2da025bafc0e725f0f1/href</a></iframe><h4><a href="https://leetcode.com/problems/sum-root-to-leaf-numbers/">129. Sum Root to Leaf Numbers</a></h4><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/ec87fe9e65617a448571d995b0cdd5cb/href">https://medium.com/media/ec87fe9e65617a448571d995b0cdd5cb/href</a></iframe><h4><a href="https://leetcode.com/problems/kth-smallest-element-in-a-bst/">230. Kth Smallest Element in a Binary Search Tree</a></h4><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/3490a23a7ebb7a693a67921bec32af7d/href">https://medium.com/media/3490a23a7ebb7a693a67921bec32af7d/href</a></iframe><h4><a href="https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/">236. Lowest Common Ancestor of a Binary Tree</a></h4><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/c4d36d25dddb881a0de16c25d8ba689f/href">https://medium.com/media/c4d36d25dddb881a0de16c25d8ba689f/href</a></iframe><h4><a href="https://leetcode.com/problems/most-frequent-subtree-sum/">508. Most Frequent Subtree Sum</a></h4><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/0c06c00c97c702f43c9a4c36fc5da087/href">https://medium.com/media/0c06c00c97c702f43c9a4c36fc5da087/href</a></iframe><h4><a href="https://leetcode.com/problems/add-one-row-to-tree/">623. Add One Row to Tree</a></h4><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/bbb434833f09d0a6ac2c8b7644167e8a/href">https://medium.com/media/bbb434833f09d0a6ac2c8b7644167e8a/href</a></iframe><h4><a href="https://leetcode.com/problems/maximum-width-of-binary-tree/">662. Maximum Width of Binary Tree</a></h4><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/39f9bcff15098b4b06545a4367468c52/href">https://medium.com/media/39f9bcff15098b4b06545a4367468c52/href</a></iframe><h4><a href="https://leetcode.com/problems/trim-a-binary-search-tree/">669. Trim a Binary Search Tree</a></h4><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/50443154044c625805e8e5a23a423f0e/href">https://medium.com/media/50443154044c625805e8e5a23a423f0e/href</a></iframe><h4><a href="https://leetcode.com/problems/longest-univalue-path/">687. Longest Univalue Path</a></h4><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/12ef0c8aa0261f625d6be17d1a0247d6/href">https://medium.com/media/12ef0c8aa0261f625d6be17d1a0247d6/href</a></iframe><h4><a href="https://leetcode.com/problems/binary-tree-pruning/">814. Binary Tree Pruning</a></h4><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/21de5c7c050927f2153ad6ff041d02b5/href">https://medium.com/media/21de5c7c050927f2153ad6ff041d02b5/href</a></iframe><h4><a href="https://leetcode.com/problems/all-nodes-distance-k-in-binary-tree/">863. All Nodes Distance K in Binary Tree</a></h4><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/f1685bf9951df600a5241fbc784a47d1/href">https://medium.com/media/f1685bf9951df600a5241fbc784a47d1/href</a></iframe><h4><a href="https://leetcode.com/problems/smallest-subtree-with-all-the-deepest-nodes/">865. Smallest Subtree with all the Deepest Nodes</a></h4><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/474dd345d6b51fe7bfc1ee7d0397bba3/href">https://medium.com/media/474dd345d6b51fe7bfc1ee7d0397bba3/href</a></iframe><h4><a href="https://leetcode.com/problems/flip-equivalent-binary-trees/">951. Flip Equivalent Binary Trees</a></h4><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/f8e5fd9e602efc991b7aa561809b8045/href">https://medium.com/media/f8e5fd9e602efc991b7aa561809b8045/href</a></iframe><h4><a href="https://leetcode.com/problems/distribute-coins-in-binary-tree/">979. Distribute Coins in Binary Tree</a></h4><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/c9cb9d9730404839078dea3aeb7a882c/href">https://medium.com/media/c9cb9d9730404839078dea3aeb7a882c/href</a></iframe><h4><a href="https://leetcode.com/problems/maximum-difference-between-node-and-ancestor/">1026. Maximum Difference Between Node and Ancestor</a></h4><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/bf5338e7e3cc19229f72f16d6e4e30ac/href">https://medium.com/media/bf5338e7e3cc19229f72f16d6e4e30ac/href</a></iframe><h4><a href="https://leetcode.com/problems/insufficient-nodes-in-root-to-leaf-paths/">1080. Insufficient Nodes in Root to Leaf Paths</a></h4><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/78ffdbce170e3199a91370a6784b49f6/href">https://medium.com/media/78ffdbce170e3199a91370a6784b49f6/href</a></iframe><h4><a href="https://leetcode.com/problems/maximum-product-of-splitted-binary-tree/">1339. Maximum Product of Splitted Binary Tree</a></h4><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/bf56eccdaaa427c0b6fa4014d4789e92/href">https://medium.com/media/bf56eccdaaa427c0b6fa4014d4789e92/href</a></iframe><h4><a href="https://leetcode.com/problems/longest-zigzag-path-in-a-binary-tree/">1372. Longest ZigZag Path in a Binary Tree</a></h4><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/768c6560a8913fd5ba9769038b6278a9/href">https://medium.com/media/768c6560a8913fd5ba9769038b6278a9/href</a></iframe><h4><a href="https://leetcode.com/problems/count-good-nodes-in-binary-tree/">1448. Count Good Nodes in Binary Tree</a></h4><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/b5b83f88a138657d38a19658cf5128aa/href">https://medium.com/media/b5b83f88a138657d38a19658cf5128aa/href</a></iframe><h4><a href="https://leetcode.com/problems/number-of-good-leaf-nodes-pairs/">1530. Number of Good Leaf Nodes Pairs</a></h4><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/2c62f9a2e2583f2f381b48123e749348/href">https://medium.com/media/2c62f9a2e2583f2f381b48123e749348/href</a></iframe><h4><a href="https://leetcode.com/problems/even-odd-tree/">1609. Even Odd Tree</a></h4><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/8299812da3db7a5bd9ee8849a3dfe310/href">https://medium.com/media/8299812da3db7a5bd9ee8849a3dfe310/href</a></iframe><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=f5e9f95990a9" width="1" height="1" alt=""><hr><p><a href="https://medium.com/tseng1026/binary-tree-leetcode-f5e9f95990a9">Binary Tree | LeetCode</a> was originally published in <a href="https://medium.com/tseng1026">tseng1026</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
    </channel>
</rss>