Integer to English Words

Feb 04

softwareeverydayUncategorized No Comments

Convert a non-negative integer to its english words representation. Given input is guaranteed to be less than 231 – 1.

[Problem Link]

  1. Create a list of numbers for which you have to know the text. For example, there is no way you could come up with text for 1-9, 10-20, 30, 40… without knowing them!
  2. Create a subroutine that solves this problem for 3 digit numbers (up-to 999). If you find the number in the above map return string, else build it. For eg. 123 
    1            2 0          3
- - -      | - - -      | - - -
^ Hundred    ^ Twenty     ^ There
  3. Use the above routine to convert digits in batches of 3. Depending on the batch, add Thousand, Million and/or Billion to the converted batch of 3 digits. E.g. to convert 2,190,876,001 
    0 0 2          1 9 0        8 7 6         0 0 1
- - -        | - - -      | - - -       | - - -
^ Billion    ^ Million    ^ Thousand

Gotcha’s

  • If num is 0 output “Zero”. This is the only case you will use zero.
  • If any of the 3 digits in the batches are 0, output nothing! E.g. 1000123, make sure you don’t output an extra Thousand anywhere, meaning something like “One Million Thousand One Hundred Twenty Three”.
class Solution {
 
    Map<Integer, String> num2wordsMap = new HashMap<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");
        put(100, "One Hundred");
        put(200, "Two Hundred");
        put(300, "Three Hundred");
        put(400, "Four Hundred");
        put(500, "Five Hundred");
        put(600, "Six Hundred");
        put(700, "Seven Hundred");
        put(800, "Eight Hundred");
        put(900, "Nine Hundred");
    }};
 
    public String numberToWords(int num) {
        if (num == 0)
            return "Zero";
 
        String ret = "";
        int index = 0;
        while ( num > 0 ) {
            int lastThree = 0;
            lastThree += (num % 10);
            num /= 10;
            lastThree += ((num % 10)*10);
            num /= 10;
            lastThree += ((num % 10)*100);
            num /= 10;
 
            if (lastThree==0) {
                index++;
                continue;
            }
 
            String threeDigitRet = threeDigitNumberToWords(lastThree);
            if ( index == 0 ) {
                ret = threeDigitRet;
            } else if ( index == 1 ) {
                ret = threeDigitRet + " Thousand " + ret;
            } else if ( index == 2 ) {
                ret = threeDigitRet + " Million " + ret;
            } else if ( index == 3 ) {
                ret = threeDigitRet + " Billion " + ret;
            }
 
            index++;
        }
        return ret.trim();
    }
 
    /**
    * convert 3 numbers to text
    */
    public String threeDigitNumberToWords(int num) {
        int units = num % 10;
        int tens = (num/10) % 10;
        int hundreds = (num/100) % 10;
        int tensNum = tens*10 + units;
 
        String ret = "";
        if (!numberToWordsMap(num).equals("")) {
            ret += numberToWordsMap(num);
        } else {
            ret += hundreds != 0 ? numberToWordsMap(hundreds) + " Hundred " : "";
            if (!numberToWordsMap(tensNum).equals("")) {
                ret += numberToWordsMap(tensNum);
            } else {
                ret += (tens != 0 ? numberToWordsMap(tens*10) + " " : "");
                ret += numberToWordsMap(units);
            }
        }
 
        return ret;
    }
 
    public String numberToWordsMap(int n) {
        return num2wordsMap.getOrDefault(n, "");
    }
}

[Leetcode] Binary Tree Right Side View

Jan 14

softwareeverydayUncategorized No Comments

[Problem Link]

Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

Example:

Input: [1,2,3,null,5,null,4]
Output: [1, 3, 4]
Explanation:
 
   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---
  • Perform a breath first traversal of the tree also called a level order traversal.
  • Before you start processing any level, add the last node from your Q/list to the return list. That’s the node the user would see from the right side.
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> ret = new ArrayList<Integer>();
        LinkedList<TreeNode> q = new LinkedList<TreeNode>();
        if ( root != null )
            q.add(root);
        while ( q.size() > 0 ) {
            int levelSize = q.size();
            ret.add(q.getLast().val);
            for ( int i = 0 ; i < levelSize ; i++ ) {
                TreeNode curr = q.remove(0);
                if ( curr.left != null )
                    q.add(curr.left);
                if ( curr.right != null )
                    q.add(curr.right);
            }
        }
        return ret;
    }
}

[Leetcode] One Edit Distance

Jan 14

softwareeverydayUncategorized No Comments

[Problem Link]

If you’ve solved the edit distance dynamic programming problem, this problem should be straightforward.

  1. Make sure to return false if both strings are equal. The problem asks us to return true only if they’re one edit distance apart! Proceed if they’re unequal.
  2. Use two pointers set at the end of each string. Find the ‘first’ character thats a mismatch. Keep in mind to stop if either of the pointers reach the end. Even if you exhaust one of the strings and have remaining characters left in the other, its still a mismatch!
  3. Once we’ve found ‘one’ mismatch, we need to simply check if inserting, deleting or replacing a character gives us an equal string. For checking this we create a checkEquals() method.
  4. checkEquals() method simply checks if two (sub) strings are exactly equal! We’ll pass both the strings and ending indexes i and j to this method. Return whatever checkEquals() returns.
class Solution {
    public boolean isOneEditDistance(String s, String t) {
 
        if ( s.equals(t) )
            return false;
 
        int i = s.length() - 1;
        int j = t.length() - 1;
 
        while ( i >= 0 && j >= 0 ) {
            if ( s.charAt(i) != t.charAt(j) )
                break;
            i--; j--;
        }
 
        // check if insert, delete or replace returns a valid string!
        return checkEquals(s, t, i-1, j) || 
                checkEquals(s, t, i, j-1) || 
                    checkEquals(s, t, i-1, j-1);
    }
 
    public boolean checkEquals(String s, String t, int i, int j) {
        if ( i != j )
            return false;
 
        while ( i >= 0 ) {
            if ( s.charAt(i) != t.charAt(j) )
                return false;
            i--; j--;
        }
 
        return true;
    }
}

[Hackerrank] Pairs

Jan 10

softwareeverydayUncategorized No Comments

You will be given an array of integers and a target value. Determine the number of pairs of array elements that have a difference equal to a target value.

[Problem Link]

  • Add all elements to a Set
  • To figure if an element arr[i] and some X make a pair, we check if
    (arr[i] – Target) is in Set

    why?
    arr[i] – X = Target
    X = arr[i] – Target

    // Complete the pairs function below.
    static int pairs(int k, int[] arr) {
        Set<Integer> arrSet = new HashSet<Integer>();
        for ( int i = 0 ; i < arr.length ; i++ )
            arrSet.add(arr[i]);
 
        int ret = 0;
        for ( int i = 0 ; i < arr.length ; i++ )
            if (arrSet.contains(arr[i]-k))
                ret++;
        return ret;
    }

[Leetcode] Unique Paths II

Jan 09

softwareeverydayUncategorized No Comments

[Problem Link]

  • Total paths ending at [i, j] are 
  Total paths ending at [i+1, j]  +  Total paths ending at [i, j+1]
  • Typically we would keep track of the path we’re on (so as to not go around in circles). However, in this case since we can only move down or right, there is no way we can circle back to a visited cell.
  • Make sure you check for obstacle (and return 0) before checking for end of grid. That way you’ll correctly return 0 for test-case [[1]].
class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        return uniquePathsWithObstacles(obstacleGrid, 0, 0, new HashMap<String,Integer>());
    }
 
    public int uniquePathsWithObstacles(int[][] obstacleGrid, int i, int j, Map<String,Integer> memoized) {
 
        if ( i >= obstacleGrid.length || j >= obstacleGrid[0].length )
            return 0;
 
        if ( obstacleGrid[i][j] == 1 )
            return 0;
 
        if ( i == obstacleGrid.length-1 && j == obstacleGrid[0].length-1 )
            return 1;
 
        String key = String.valueOf(i) + "," + String.valueOf(j);
        if (memoized.containsKey(key))
            return memoized.get(key);
 
        int totalPaths = uniquePathsWithObstacles(obstacleGrid, i+1, j, memoized) + 
                    uniquePathsWithObstacles(obstacleGrid, i, j+1, memoized);
        memoized.put(key, totalPaths);
 
        return totalPaths;
    }
}

[Leetcode] Course Schedule II

Jan 05

softwareeverydayUncategorized No Comments

[Problem link]

What is topological sort? You simply keep picking nodes with no incoming edges (or with in-order 0).

No valid solution? You might encounter situations where none of the nodes (yet to be processed) have an inorder of 0. This means that the graph does not have a valid topological sort (and we need to account for that). Here is an example. After picking ‘2’, you’re stuck with this 1-0, 0-1 cycle where inorder’s for both nodes are 1.

Basic Idea:

  • Create a dependency graph using the dependencies. The topological sort of this graph is your solution. Represent your graph using a HashMap (node_id -> [ child_id1, child_id2, .. child_idN ]).
  • Use a Q to keep track of nodes with inorder 0. Don’t loop through all nodes to check for nodes with inorder 0 (except for the first time). Remember, at every step the only nodes that have a potential to have inorder 0 are the children of the last picked node!
  • Finally, if you haven’t processed all the nodes (which means there is no valid topological sort) remember to return empty array.
class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        Map<Integer, List<Integer>> graph = new HashMap<Integer, List<Integer>>();
        int inorders[] = new int[numCourses];
        int order[] = new int[numCourses];
        int orderIndex = 0;
 
        // build graph
        for ( int i = 0 ; i < prerequisites.length ; i++ ) {
            List<Integer> children = graph.getOrDefault(prerequisites[i][1], new ArrayList<Integer>());
            children.add(prerequisites[i][0]);
            graph.put(prerequisites[i][1], children);
            inorders[prerequisites[i][0]]++;
        }
 
        // have q keep track of all nodes with inorder = 0
        // we will keep adding nodes to this q as and when thier inorder get to 0
        Queue<Integer> q = new LinkedList<Integer>();
        for ( int i = 0 ; i < inorders.length ; i++ ) {
            if (inorders[i] == 0) {
                q.add(i);
            }
        }
 
        // pick nodes with zero indegree and add to list
        // make sure we update (decrement) indegrees of child nodes
        while ( !q.isEmpty() ) {
            int nextNode = q.remove();
            List<Integer> children = graph.get(nextNode);
            if ( children != null ) {
                for ( Integer child : children ) {
                    inorders[child]--;
                    if (inorders[child] == 0) {
                        q.add(child);
                    }
                }
            }
            order[orderIndex++] = nextNode;
        }
 
        // For cases where there are cycles in graphs we wont get a topological sort for all the nodes. T
        his is a way to detect that!
        // Examples: [[0,1],[1,0]], [[1,0],[1,2],[0,1]]
        if ( orderIndex < numCourses )
            return new int[0];
 
        return order;
    }
}

[Leetcode] Container With Most Water

Jan 01

softwareeverydayUncategorized No Comments

[Problem Link]

  • Use a typical 2 pointer approach to solve this problem. At step 1 assume your max container spans two ends.
  • What is the area of a container given i and j? It is the width of the container (j-i) x height of the container (which is bounded by the min(heights[i], heights[j]).
  • Moving which of these pointers might possibly increase the area of our container in the next step? It seems like the minimum of the two heights is holding back so lets move the pointer pointing to min(heights[i], heights[j]).
class Solution {
    public int maxArea(int[] height) {
        int i = 0 ; 
        int j = height.length-1;
        int max = Integer.MIN_VALUE;
 
        while ( i < j ) {
            int currwidth = j-i;
            int currheight = Math.min(height[i], height[j]);
            max = Math.max(max, currwidth*currheight);
 
            if ( height[i] < height[j] )
                i++;
            else
                j--;
        }
 
        return max;
    }
}

[Leetcode] Random Pick Index

Dec 31

softwareeverydayUncategorized No Comments

Given an array of integers with possible duplicates, randomly output the index of a given target number. You can assume that the given target number must exist in the array.

Note:
The array size can be very large. Solution that uses too much extra space will not pass the judge.

Example:

int[] nums = new int[] {1,2,3,3,3};
Solution solution = new Solution(nums);
 
// pick(3) should return either index 2, 3, or 4 randomly. Each index should have equal probability of returning.
solution.pick(3);
 
// pick(1) should return 0. Since in the array only nums[0] is equal to 1.
solution.pick(1);

[Problem Link]

  • Create a Map for every target -> range[]. Now, given a target we can query its range in O(1) time. Note, that length of this range is simply range[1]-range[0]+1.
  • Given a range (for any target), generate a random_number between 0 to length_of_range (Java’s Random class allows us to generate a random number between 0 (inclusive) to n (exclusive)). We then simple return i + random_number.
class Solution {
 
    Map<Integer, int[]> rangeMap;
    Random r;
 
    public Solution(int[] nums) {
        r = new Random();
        rangeMap = new HashMap<Integer, int[]>();
        int i = 0;
        while ( i < nums.length ) {
            int num = nums[i];
            int j = i;
            while ( j < nums.length && nums[j] == num )
                j++;
            int range[] = { i, j-1 };
            rangeMap.put(num, range);
            i = j;
        }        
    }
 
    public int pick(int target) {
        int range[] = rangeMap.get(target);
        return range[0] + r.nextInt(range[1]-range[0]+1);
    }
}
 
/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(nums);
 * int param_1 = obj.pick(target);
 */

[Leetcode] Moving Average from Data Stream

Dec 31

softwareeverydayUncategorized No Comments

Given a stream of integers and a window size, calculate the moving average of all integers in the sliding window.

Example:

MovingAverage m = new MovingAverage(3);
m.next(1) = 1
m.next(10) = (1 + 10) / 2
m.next(3) = (1 + 10 + 3) / 3
m.next(5) = (10 + 3 + 5) / 3

[Problem Link]

Use (and keep updating) the running total of the List to help calculate the moving average in O(1) time.

class MovingAverage {
 
    List<Integer> nums;
    double sum;
    int size;
 
    /** Initialize your data structure here. */
    public MovingAverage(int size) {
        this.nums = new ArrayList<Integer>();
        this.sum = 0;
        this.size = size;
    }
 
    public double next(int val) {
        nums.add(val);
        if ( nums.size() <= this.size ) {
            this.sum += val;
            return this.sum/nums.size();
        }        
        int num = nums.remove(0);
        this.sum = this.sum - num + val;
        return this.sum/nums.size();
    }
}
 
/**
 * Your MovingAverage object will be instantiated and called as such:
 * MovingAverage obj = new MovingAverage(size);
 * double param_1 = obj.next(val);
 */

Chemistry 101

Jan 26

softwareeverydayUncategorized No Comments

Basic Information

  • Number of protons in the element define the element. Neutrons can change, electrons can change, but if protons change you have a different element.
  • Fundamental elements (or elements with different number of protons in the nucleus) are found in the periodic table
  • Number of protons is the atomic number (Z) of the element
  • Number of neutrons (N) + number of protons (Z) = atomic mass number (A)
  • Isotopes are atoms of the same element which differ in number of neutrons (i.e. they differ in mass). [Image courtesy: https://www.youtube.com/watch?v=I-Or4bUAIfo]
  • Same number of protons and electrons means it’s neutral. Neutral atom can become +ve or -ve if they depending on shedding or adding electrons.
  • Most of all living things made out of carbon. ~1 million carbon atoms across width of the hair

What are ions?

  • Carbon has 6 protons (and that is what it makes it carbon atom).
  • A neutral carbon atom has 6 protons + 6 electrons. Usually when we use the term atom we refer to neutral atom.
  • The way you get an ion is when you DON’T have the same number of protons and electrons.
  • A carbon atom with 6 protons and 5 electrons is a positive ion (or Cation denoted by C+)
  • A carbon atom with 6 protons and 7 electrons is a negative ion (or Anion denoted by C–)

Electron configuration

  • The electron diagrams that we see follow the bohr model which depicts the atom as a small, positively charged nucleus surrounded by electrons that travel in circular orbits around the nucleus—similar to the structure of the Solar System.
  • It is used to predict reactivity in elements which refers to how likely an element is to form a compound with another element.
  • Valence electrons (the electrons on the last energy level) determine reactivity
  • Rules we follow when laying out the model
    1. Max no. of electrons in a shell given by 2n2, e.g. 2, 8, 16, 32, 50…
    2. Max no. of electrons in the outermost shell is 8
    3. Electrons are not accommodated in a given shell, unless the inner shells are filled.

Ionic bonding

[Images Courtesy: https://www.youtube.com/watch?v=Qf07-8Jhhpc]

  1. Every atom wants a full valance shell!
  2. Sodium gives its one (last) electron (from the valance shell) to chlorine. Now, both valance shells of sodium and chlorine are full.
  3. Sodium now becomes a +ve charged particle while Chlorine becomes a -ve charged particle.
  4. Opposite charges attract, so both these atoms are attracted to each other forming sodium-chloride
  5. Ok, so one of the sodium electrons went to chlorine. Why didn’t the 7 electrons from Chlorine come to sodium?
    Answer is electronegativity. A measure of how badly an atom wants electrons!

Older Entries Newer Entries