Minimum Number of Platforms Required for a Railway/Bus Station Method 1
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… Read more
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… Read more
Dijkstra’s shortest path algorithm
Huffman Coding
Prim’s Minimum Spanning Tree (MST)
Kruskal’s Minimum Spanning Tree Algorithm
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… Read more
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> |