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.
Continue reading
Author Archives: omt
Minimum Number of Platforms Required for a Railway/Bus Station Method 1
Given arrival and departure times of all trains that reach a railway station, find the minimum number of platforms required for the railway station so that no train waits.
Job Sequencing Problem Find and Union
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 scheduled at a time.
Continue reading
Job Sequencing Problem
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 scheduled at a time.
Continue reading
Dijkstra’s shortest path algorithm
Here we are going to take inspiration from MST Prim’s algorithm
Continue reading
Huffman Coding
Simple Huffman Coding algorithm in Java
Prim’s Minimum Spanning Tree (MST)
This algorithm to create MST using Prim’s algorithm
Continue reading
Kruskal’s Minimum Spanning Tree Algorithm
This algorithm to create MST using Kruskal’s algorithm
Continue reading
Find cycle/loop in the graph – Find and Union with Path Compression
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 has same parent then loop found.
|
1 |
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() < <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<Integer,String> THOUSANDS_MAP = new TreeMap<Integer,String>()<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<String,Integer> PARTITION_THOUSANDS_MAP = new TreeMap<String,Integer>()<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<Integer,String> _1_TO_20_TENS = new TreeMap<Integer,String>()<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> |