[Leetcode] Unique Paths II

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

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

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

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

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

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!

WordPress Backup

Comments Off on WordPress Backup

WordPress Import/Export
Wordpress allows you to export your ‘content’ in xml format. it then allows you to imports that content in a wordpress instance. The tool allows you to import data from various sources (e.g. Live Journal, Tumblr etc). Seems quite straightforward however the wordpress import/export have some caveats.

  1. It requires you to add users on the site before you import.
  2. If the exported file is very large, the import script may run into your host’s configured memory limit for PHP.
  3. If the import process is run again with the same data file after stopping midway through, it could result in duplicate data, missing data or other errors in the destination database.
  4. Some discussion about whether this process does or does not import images, files (or content in general). In my experience the imported posts have links to content residing in the wp-content of the site that I exported from.

Manual Import Export
I instead choose to do a manual import export of my wordpress blog. Below are the steps that i carried out an exact clone of my blog www.softwareeverydayblog.com on my local box.

  1. Take a mysql backup of the my wordpress DB.
  2. mysql_backup

    mysql_backup2

  3. Manually create a database ‘softwareeveryday’ on my local mysql instance. Import the db using the mysql back script into this fresh db ‘softwareeveryday’ that we just created.
    C:\scipts>c:\wamp\bin\mysql\mysql5.5.24\bin\mysql -u root -p < softwareeveryday.sql softwareeveryday
    Enter password:
  4. Copy the wordpress files using FTP somewhere into our apache home directory. Change wp-config.php to reflect local box settings.
  5. At this point, we bring up our apache server and the wordpress blog should appear. There is one issue, there are yet some references to http://www.softwareeverydayblog.com. We’ll need to make some changes in the database to get rid of those references. Change wp_options table, set wp_options to point to localhost address where option_name is ‘siteurl’, ‘home’.
  6. All the content that I uploaded (like images) is yet pointing to http://www.softwareeverydayblog.com/wp-content/uploads/2013/05/some_image.jpg. Now I notice that within the wp_posts, all posts have href hardcoded to softwareeverydayblog.com. You can use this tool to replaces the urls. The advantage over SQL replace is that the tool know how to handle serialized info in the DB. Refer to stackoverflow answer for more.

If you want to skip the last step of making DB changes, we could change our hosts file so that requests to softwareeverydayblog.com point to 127.0.0.1. I personally prefer to change my hosts file. I also soon realized that it’s NOT possible to redirect using hosts file. For example the following entry is NOT possible.

# redirects not allowed in hosts file
127.0.0.1/softwareeverydayblog/wordpress-3.4.2/		softwareeverydayblog.com

Instead we could add a simple hosts entry, and add redirects in the local apache server to redirect all requests to softwareeverydayblog.com to the wordpress directory.

  1. Add the following entries in hosts file.
    127.0.0.1		www.softwareeverydayblog.com
    127.0.0.1		softwareeverydayblog.com
  2. Add the following entry to httpd-vhosts.conf for redirects. With this all requests to softwareeverydayblog.com on this apache server will be served files from “C:/www/softwareeverydayblog/wordpress-3.4.2” which is our wordpress directory.
    <VirtualHost *:80>
        ServerAdmin webmaster@dummy-host.example.com
        DocumentRoot "C:/www/softwareeverydayblog/wordpress-3.4.2"
        ServerName softwareeverydayblog.com
        ServerAlias www.softwareeverydayblog.com
        ErrorLog "logs/softwareeverydayblog.com-error.log"
        CustomLog "logs/softwareeverydayblog.com-access.log" common
    </VirtualHost>
  3. I also uncommented the following line from httpd.conf
    Include conf/extra/httpd-vhosts.conf

Blog works fine now. Links yet show http://www.softwareeverydayblog.com but files are being served from the local box.

Http Basic Authentication

Comments Off on Http Basic Authentication

Here’s a brief overview of Http Basic Authentication which is a (trivial) way of providing authentication in your application. Every-time you send a http request to the server, the username and password are sent as part of the HTTP header (in every request). They are encoded using base64, so yes it is NOT a safe way to do things. If you decide to use it, make sure you use SSL over it.

  1. Users sends a request.
  2. Server sends back response code 401 and Http response header WWW-Authenticate = Basic realm=”MyRealm”. Browser receives this (header and response code) and prompts user to enter username and password.
  3. Browser sends another GET request but with Http request header Authorization: Basic .
  4. Server receives this header, authenticates the user and sends back either a Response code 200 (OK) or 401 (Unauthorized).

If the response is 200 (Ok) browser will cache the username and password so that user doesn’t have to keep reentering it.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
import java.io.IOException;
import java.io.PrintWriter;
import javax.servlet.ServletException;
import javax.servlet.http.HttpServlet;
import javax.servlet.http.HttpServletRequest;
import javax.servlet.http.HttpServletResponse;
 
import org.apache.commons.codec.binary.Base64;
import org.apache.commons.codec.binary.StringUtils;
 
public class AuthenticateServlet extends HttpServlet {
 
  private static final long serialVersionUID = 1L;
 
  public void doGet(HttpServletRequest request, HttpServletResponse response) throws ServletException, IOException {
 
    if ( request.getHeader("Authorization") != null ) {
      String auth = request.getHeader("Authorization");
      String coded_user_password = auth.split(" ") [1];
      String decoded_user_password = StringUtils.newStringUtf8(Base64.decodeBase64(coded_user_password));
 
      String username = decoded_user_password.split(":")[0];
      String password = decoded_user_password.split(":")[1];
 
      PrintWriter out = response.getWriter();
      out.println("<p>Username: " + username + "</p><p>Password: " + password + "</p>");
 
    } else {
 
      response.setHeader("WWW-Authenticate", "Basic realm=\"MyRealm\"");
      response.setStatus(401);
 
    }
  }
}

Get the 8.3 (or short file name) of a folder in windows

Comments Off on Get the 8.3 (or short file name) of a folder in windows

It seems like on an NTFS partition there is something called 8.3 Name Creation. Its basically a short file name with a tilde ~. Problem i was facing was how to get the short file name for a folder? One way is just to keep trying different combinations, the other is is using the command dir /x /a. /a includes even hidden files.

XML Namespaces 101

Comments Off on XML Namespaces 101

XML Namespaces also carry typical advantages of using namespaces, i.e. all variables related to a particular category can go under that namespace.

Here is an example of namespaces being used for Spring.

Lets say in an xml file we have information about an html table and a real table.

<root>
  <item>
    <table>
      <name>Ikea Coffee table</name>
      <size>Large</size>
      <html>
        <table>
          <tr>
            <td>Name</td>
            <td>Size</td>
          </tr>
          <tr>
            <td>Ikea Coffee table</td>
            <td>Large</td>
          </tr>
        </table>
      </html>
    </table>
  </item>
</root>

Ok, there is a problem here. Clearly, there should be a distinction between an html table and real table. Namespaces to the rescue.

<root xmlns="http://www.softwareeverydayblog.com/" xmlns:table="http://www.softwareeverydayblog.com/realtable" xmlns:htmltable="http://www.softwareeverydayblog.com/htmltable"</strong> >
  <item>
    <table:table>
      <name>Ikea Coffee table</name>
      <size>Large</size>
      <html>
        <htmltable:table>
          <tr>
            <td>Name</td>
            <td>Size</td>
          </tr>
          <tr>
            <td>Ikea Coffee table</td>
            <td>Large</td>
          </tr>
        </htmltable:table>
      </html>
    </table:table>
  </item>
</root>

This works. An html table (xmlns:htmltable) and a real table (xmlns:table) have their own namespaces. xmlns is the default namespace. By default all the elements without a namespace go into this namespace (e.g. , etc).

Older Entries Newer Entries