Longest Increasing Subsequence

September 9, 2018September 9, 2018 by omt

The Longest Increasing Subsequence (LIS) problem is to find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

Minimum Number of Platforms Required for a Railway/Bus Station Method 1

August 12, 2018August 24, 2018 by omt

Minimum Number of Platforms Required for a Railway/Bus Station Method 1

Job Sequencing Problem Find and Union

July 25, 2018 by omt

Given an array of jobs where every job has a deadline and associated profit if the job is finished before the deadline. It is also given that every job takes single unit of time, so the minimum possible deadline for any job is 1. How to maximize total profit if only one job can be… Read more

Job Sequencing Problem

July 19, 2018 by omt

Dijkstra’s shortest path algorithm

July 19, 2018July 19, 2018 by omt

Here we are going to take inspiration from MST Prim’s algorithm

Huffman Coding

July 17, 2018 by omt

Simple Huffman Coding algorithm in Java

Prim’s Minimum Spanning Tree (MST)

July 17, 2018 by omt

This algorithm to create MST using Prim’s algorithm

Kruskal’s Minimum Spanning Tree Algorithm

July 17, 2018 by omt

This algorithm to create MST using Kruskal’s algorithm

Find cycle/loop in the graph – Find and Union with Path Compression

May 27, 2018 by omt

To identify loop in the graph, We are going to use Find and Union technic with Path Compression. We are going to create subject of each vertex and we will represent one element of that subset as a parent, So next time we will take two vertex will check the parent of each, if both… Read more

May 17, 2018June 26, 2019 by omt

package com.omt.learn.leetcode.facebook;<br><br>import java.util.HashMap;<br>import java.util.Map;<br>import java.util.TreeMap;<br><br>public class IntegerToEnglishWord <strong>{<br></strong><strong>    <br></strong><strong>   <br></strong><strong>     <br></strong><strong>    <br></strong><strong>    </strong>public static void main(String args[])<strong>{<br></strong><strong>        </strong>System.out.println(getWord(<strong>44</strong>));<br>        System.out.println(getWord(<strong>1</strong>));<br>        System.out.println(getWord(<strong>123</strong>));<br>        System.out.println(getWord(<strong>12345</strong>));<br>        System.out.println(getWord(<strong>1234567</strong>));<br>        System.out.println(getWord(<strong>1234567891</strong>));<br>    <strong>}<br></strong><strong>    <br></strong><strong>    </strong>public static String getWord(int number)<strong>{<br></strong><strong>        </strong>String word = "";<br>        <br>        String numberString =  String.valueOf(number);<br>        <br>        if(numberString.length() &lt; <strong>3</strong>)<strong>{<br></strong><strong>            </strong>return getTwoCharsInteger(number);<br>        <strong>}</strong>else if(numberString.length() == <strong>3</strong>)<strong>{<br></strong><strong>            </strong>return getThreeCharsInteger(number);<br>        <strong>}<br></strong><strong>        <br></strong><strong>        </strong>String thousands = THOUSANDS_MAP.get(numberString.length());<br>        int partition = numberString.length() - PARTITION_THOUSANDS_MAP.get(thousands); <br>        String frontNumber = numberString.substring(<strong>0</strong>,partition);<br>        String backNumber = numberString.substring(partition,numberString.length());<br>        <br>        return getWord(Integer.parseInt(frontNumber))+" "+thousands+" "+getWord(Integer.parseInt(backNumber));<br>    <strong>}<br></strong><strong><br></strong><strong>    </strong>static Map&lt;Integer,String&gt; THOUSANDS_MAP = new TreeMap&lt;Integer,String&gt;()<strong>{<br></strong><strong>        {<br></strong><strong>            </strong>put(<strong>3</strong>,"Hundred");<br>            put(<strong>4</strong>,"Thousand");<br>            put(<strong>5</strong>,"Thousand");<br>            put(<strong>6</strong>,"Thousand");<br>            put(<strong>7</strong>,"Million");<br>            put(<strong>8</strong>,"Million");<br>            put(<strong>9</strong>,"Million");<br>            put(<strong>10</strong>,"Billion");<br>        <strong>}<br></strong><strong>    }</strong>;<br><br>    static Map&lt;String,Integer&gt; PARTITION_THOUSANDS_MAP = new TreeMap&lt;String,Integer&gt;()<strong>{<br></strong><strong>        {<br></strong><strong>            </strong>put("Hundred",<strong>2</strong>);<br>            put("Thousand",<strong>3</strong>);<br>            put("Million",<strong>6</strong>);<br>            put("Billion",<strong>9</strong>);<br>        <strong>}<br></strong><strong>    }</strong>;<br><br>    static Map&lt;Integer,String&gt; _1_TO_20_TENS = new TreeMap&lt;Integer,String&gt;()<strong>{<br></strong><strong>        {<br></strong><strong>            </strong>put(<strong>1</strong>,"One");<br>            put(<strong>2</strong>,"Two");<br>            put(<strong>3</strong>,"Three");<br>            put(<strong>4</strong>,"Four");<br>            put(<strong>5</strong>,"Five");<br>            put(<strong>6</strong>,"Six");<br>            put(<strong>7</strong>,"Seven");<br>            put(<strong>8</strong>,"Eight");<br>            put(<strong>9</strong>,"Nine");<br>            put(<strong>10</strong>,"Ten");<br>            put(<strong>11</strong>,"Eleven");<br>            put(<strong>12</strong>,"Twelve");<br>            put(<strong>13</strong>,"Thirteen");<br>            put(<strong>14</strong>,"Fourteen");<br>            put(<strong>15</strong>,"Fifteen");<br>            put(<strong>16</strong>,"Sixteen");<br>            put(<strong>17</strong>,"Seventeen");<br>            put(<strong>18</strong>,"Eighteen");<br>            put(<strong>19</strong>,"Nineteen");<br>            put(<strong>20</strong>,"Twenty");<br>            put(<strong>30</strong>,"Thirty");<br>            put(<strong>40</strong>,"Forty");<br>            put(<strong>50</strong>,"Fifty");<br>            put(<strong>60</strong>,"Sixty");<br>            put(<strong>70</strong>,"Seventy");<br>            put(<strong>80</strong>,"Eighty");<br>            put(<strong>90</strong>,"Ninety");<br>        <strong>}<br></strong><strong>    }</strong>;<br><br>    static String getTwoCharsInteger(int number)<strong>{<br></strong><strong>        </strong>if(_1_TO_20_TENS.containsKey(number))<strong>{<br></strong><strong>            </strong>return _1_TO_20_TENS.get(number);<br>        <strong>}<br></strong><strong><br></strong><strong>        </strong>return  getTwoCharsInteger((number/<strong>10</strong>)*<strong>10</strong>)+" "+getTwoCharsInteger(number%<strong>10</strong>);<br>    <strong>}<br></strong><strong><br></strong><strong>    </strong>static String getThreeCharsInteger(int number) <strong>{<br></strong><strong>        </strong>return _1_TO_20_TENS.get(number / <strong>100</strong>) +" "+THOUSANDS_MAP.get(<strong>3</strong>)+" "+ getTwoCharsInteger(number%<strong>100</strong>);<br>    <strong>}<br></strong><strong>    <br></strong><strong>}<br></strong>

package com.omt.learn.leetcode.facebook; import java.util.HashMap; import java.util.Map; import java.util.TreeMap; public class IntegerToEnglishWord { public static void main(String args[]){ System.out.println(getWord(44)); System.out.println(getWord(1)); System.out.println(getWord(123)); System.out.println(getWord(12345)); System.out.println(getWord(1234567)); System.out.println(getWord(1234567891)); } public static String getWord(int number){ String word = ""; String numberString = String.valueOf(number); if(numberString.length() < 3){ return getTwoCharsInteger(number); }else if(numberString.length() == 3){ return getThreeCharsInteger(number); } String thousands = THOUSANDS_MAP.get(numberString.length()); int partition = numberString.length() - PARTITION_THOUSANDS_MAP.get(thousands); String frontNumber = numberString.substring(0,partition); String backNumber = numberString.substring(partition,numberString.length()); return getWord(Integer.parseInt(frontNumber))+" "+thousands+" "+getWord(Integer.parseInt(backNumber)); } static Map<Integer,String> THOUSANDS_MAP = new TreeMap<Integer,String>(){ { put(3,"Hundred"); put(4,"Thousand"); put(5,"Thousand"); put(6,"Thousand"); put(7,"Million"); put(8,"Million"); put(9,"Million"); put(10,"Billion"); } }; static Map<String,Integer> PARTITION_THOUSANDS_MAP = new TreeMap<String,Integer>(){ { put("Hundred",2); put("Thousand",3); put("Million",6); put("Billion",9); } }; static Map<Integer,String> _1_TO_20_TENS = new TreeMap<Integer,String>(){ { put(1,"One"); put(2,"Two"); put(3,"Three"); put(4,"Four"); put(5,"Five"); put(6,"Six"); put(7,"Seven"); put(8,"Eight"); put(9,"Nine"); put(10,"Ten"); put(11,"Eleven"); put(12,"Twelve"); put(13,"Thirteen"); put(14,"Fourteen"); put(15,"Fifteen"); put(16,"Sixteen"); put(17,"Seventeen"); put(18,"Eighteen"); put(19,"Nineteen"); put(20,"Twenty"); put(30,"Thirty"); put(40,"Forty"); put(50,"Fifty"); put(60,"Sixty"); put(70,"Seventy"); put(80,"Eighty"); put(90,"Ninety"); } }; static String getTwoCharsInteger(int number){ if(_1_TO_20_TENS.containsKey(number)){ return _1_TO_20_TENS.get(number); } return getTwoCharsInteger((number/10)*10)+" "+getTwoCharsInteger(number%10); } static String getThreeCharsInteger(int number) { return _1_TO_20_TENS.get(number / 100) +" "+THOUSANDS_MAP.get(3)+" "+ getTwoCharsInteger(number%100); } }