<?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 Sulakshana Ranawake on Medium]]></title>
        <description><![CDATA[Stories by Sulakshana Ranawake on Medium]]></description>
        <link>https://medium.com/@sula.ranawake?source=rss-b569f8a2a8d8------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*UdaGUyGkwS6mmYrl1JYPNA.jpeg</url>
            <title>Stories by Sulakshana Ranawake on Medium</title>
            <link>https://medium.com/@sula.ranawake?source=rss-b569f8a2a8d8------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Fri, 20 Nov 2026 17:19:05 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@sula.ranawake/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[My Interview experience at Google]]></title>
            <description><![CDATA[<div class="medium-feed-item"><p class="medium-feed-image"><a href="https://medium.com/@sula.ranawake/my-interview-experience-at-google-8e612c5bac61?source=rss-b569f8a2a8d8------2"><img src="https://cdn-images-1.medium.com/max/929/1*yjmyTyOxrU3J38nQdj-Cuw.jpeg" width="929"></a></p><p class="medium-feed-snippet">I was reached out by a Google Recruiter via LinkedIn in March 2022.</p><p class="medium-feed-link"><a href="https://medium.com/@sula.ranawake/my-interview-experience-at-google-8e612c5bac61?source=rss-b569f8a2a8d8------2">Continue reading on Medium »</a></p></div>]]></description>
            <link>https://medium.com/@sula.ranawake/my-interview-experience-at-google-8e612c5bac61?source=rss-b569f8a2a8d8------2</link>
            <guid isPermaLink="false">https://medium.com/p/8e612c5bac61</guid>
            <category><![CDATA[google-interview]]></category>
            <dc:creator><![CDATA[Sulakshana Ranawake]]></dc:creator>
            <pubDate>Tue, 30 Aug 2022 11:33:29 GMT</pubDate>
            <atom:updated>2022-08-30T11:33:29.515Z</atom:updated>
        </item>
        <item>
            <title><![CDATA[Calculating Boyer Moore Bad Character Table with examples]]></title>
            <link>https://medium.com/@sula.ranawake/calculating-boyer-moore-bad-character-table-with-examples-d855e04d5bd8?source=rss-b569f8a2a8d8------2</link>
            <guid isPermaLink="false">https://medium.com/p/d855e04d5bd8</guid>
            <category><![CDATA[string-matching]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[boyer-moore]]></category>
            <category><![CDATA[data-structures]]></category>
            <dc:creator><![CDATA[Sulakshana Ranawake]]></dc:creator>
            <pubDate>Mon, 11 Nov 2019 17:39:46 GMT</pubDate>
            <atom:updated>2020-08-21T18:15:08.949Z</atom:updated>
            <content:encoded><![CDATA[<p>Let’s look at how to calculate the Boyer Moore bad character table with an example. Boyer Moore is a string matching algorithm. So what it basically does is, finding the occurrence of a pattern within a text. There are many string matching algorithms including,</p><ol><li>Naive String Matching Algorithm</li><li>KMP (Knuth-Morris-Pratt) Algorithm</li><li>Rabin Carp Algorithm</li><li>Boyer Moore Algorithm</li><li>Boyer Moore Horsepool Algorithm</li></ol><p>In this article, we are focusing on the 2 Boyer Moore Algorithms. Assuming you already have enough background knowledge about how to use the bad character table, I will describe how to calculate the crucial part in these algorithms, the bad character table because when I learned this, there were not enough resources on the internet on how to calculate them.</p><h4>First Let’s look at the <strong>Boyer Moore Algorithm</strong>.</h4><p>You are given two strings. One is the pattern and the other one is the text. You have to find the pattern within the text. Let’s look at an example,</p><blockquote>Text =&gt; “<strong>THIS IS A TEST</strong>”</blockquote><blockquote>Pattern =&gt; “<strong>TEST</strong>”</blockquote><p>You can clearly see that the Text has the pattern but the computer cannot identify that just like that. This is what string matching algorithms are for. So now let’s see step by step how to calculate the bad character table.</p><p>Steps are as follows,</p><ol><li>Take the pattern and index each character starting from 0</li></ol><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*0_bCYD5L2kVmvUzlrTOL8w.jpeg" /><figcaption>pattern indexing</figcaption></figure><p>2. Take the length of the pattern as length like above.</p><p>3. Now let’s draw the skeleton of the table.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*zFzdRKgnlHQoNfix1t4ocg.jpeg" /><figcaption>initial bad character table</figcaption></figure><p>Notice the Letters in the above picture. We have to get the unique characters in the pattern as letters. And the star (*) is for any other character we may come upon when going through the Text that is not in the pattern. Now we have to fill this table.</p><p>4. Now, for every character in the pattern, calculate max(1, length-index-1) and put it in the table.</p><p>Here, <strong><em>max(1, length-index-1)</em></strong> means that you have to choose the maximum number between 1 and the calculated <strong><em>length-index-1 </em></strong>value for every letter. Which simply means that the value can’t be less than 1.</p><blockquote>length = length of the pattern</blockquote><blockquote>index = index of the character</blockquote><blockquote><strong>NOTE</strong> : If the same character repeats, update the table by the values from the new character (or simply consider the rightmost occurrence of the character in the pattern and calculate the value for it)</blockquote><p><strong>The value for the * is the length of the pattern</strong></p><blockquote>Letter | T | E | S | * |</blockquote><blockquote>Value | 1 | 2 | 1 | 4 |</blockquote><blockquote>Value( T ) = max (1, 4–0–1) = max ( 1, 3) = 3</blockquote><blockquote>Value( E ) = max (1, 4–1–1) = max ( 1, 2) = 2</blockquote><blockquote>Value( S ) = max (1, 4–2–1) = max ( 1, 1) = 1</blockquote><blockquote>Value( T ) = max (1, 4–3–1) = max ( 1, 0) = 1 &lt;= update the T value &lt;= Rightmost occurrence of T</blockquote><h4>Now let’s look at the Boyer Moore Horsepool Algorithm</h4><p>In the <strong>Boyer Moore Horsepool</strong> Algorithm, the bad character table is a little bit different. Let’s take an example,</p><blockquote>Text =&gt; “TRUSTHARDTOOTHBRUSHES”</blockquote><blockquote>Pattern =&gt; “TOOTH”</blockquote><p>The steps in the Horsepool algorithm are,</p><p>1) Take the pattern and index each character starting from 0 ( You may ignore the last character )</p><p>2) Take the length of the pattern as length</p><p>3) <strong>Ignore</strong> the last character.</p><p>For every other character in the pattern, calculate (length-index-1), and put it in the table.</p><p>length = length of the pattern</p><p>index = index of the character</p><p>4) If the same character repeats, update the table by the values from the new character (or simply consider the rightmost occurrence of the character in the pattern and calculate the value for it)</p><p>5) Add another column for any other letter which doesn’t exist in the pattern as *</p><p>6) The value for the * is the length of the pattern</p><p>7) If the last letter has occurred before &amp; you have calculated its value and updated it in the table,<strong> leave it as it is without updating. </strong>If not, take the length of the pattern as the value.</p><p>Ex:</p><blockquote>Pattern =&gt; TOOTH</blockquote><blockquote>index =&gt; 0123</blockquote><blockquote>length = 5</blockquote><blockquote>Bad match table</blockquote><blockquote>Letter | T | O | H | * |</blockquote><blockquote>Value | 1 | 2 | 5 | 5 |</blockquote><blockquote>Value ( T ) = 5–0–1 = 4</blockquote><blockquote>Value ( O ) = 5–1–1 = 3</blockquote><blockquote>Value ( O ) = 5–2–1 = 2 &lt;= Update O Value &lt;= Rightmost O</blockquote><blockquote>Value ( T ) = 5–3–1 = 1 &lt;= Update T Value &lt;= Rigthmost T</blockquote><blockquote><strong>Value ( H )</strong> = Not previously found, so Value ( H ) = length</blockquote><p><strong><em>If there is a value for H before, leave it as it is, do NOT update!</em></strong></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=d855e04d5bd8" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>