“In the land of the blind, the one-eyed man is king”

“You can’t take it with you”

Dynamic programming has been one the hardest things for me to master. Why? Because it’s a totally different way of thinking that requires a different mindset when solving problems that can use dynamic programming.

So my way of learning dynamic programming is to just do many practice problems as possible to learn about all the tricks and try to apply it to future problems.

The following is a summary of various dynamic programming.

Max Value Contiguous Subsequence

Making Change

Longest Increasing Subsequence

Box Stacking

Billboards

(Same as Weighted Value Schedule)

Weight Values Schedule

Integer Knapsacks (Repeats)

Integer Knapsacks (No Repeats)

Edit Distance

I recently had an interview where we went over REST API design. I really never had any experience in designing APIs, but rather using them. After the interviewer and I talked about ways to design an API I decided I wanted to go back and really think about how to make a proper RESTful interface and the following are the notes that might be helpful for others to glance over when they are thinking about making a REST API. This conversation of RESTful will reference Rails at times because that was my experience with REST and lots of behaviors in Rails make sense once you consider how REST works.

Think Nouns

If you think about the API endpoints available when using a scaffold in Rails, the types of names associated with these endpoints tend to be nouns for a reason. Which makes sense and follows the guidelines for REST very well.

Also, think plural nouns.

Bad:

1
2

/all_dogs
/list_customers

Good

1
2

/dogs
/customers

Use Parameters

Parameters for urls are in the format /noun?name=value&name2=value2 and this should be the way to get more information for a REST command that might not fit within the REST-way of doing things. Think about queries which can filter the type of list being asked when using /noun or something similar.

The parameters can be used by using the params object in a controller’s method in Rails.

Examples for parameters: filtering the type of response, deciding what type of data to return, pagination

1
2

/dogs?fields=name,color,location
/dogs?field=name,color,location&limit=10&offset=20

Use camel casing for JSON property names.

Errors

Errors should be handled from the server and they should be returned definitely if something goes wrong and possibly if the query didn’t have an issue.

Error messages are usually in JSON format, the following shows some possible formats.

1
2

type: OAuthException
message: error_message_here

1
2
3
4

status: http_status_code
message: text
code: num
more_info: url

1
2

code: http_status_code
message: error_message

Response Format

Sometimes the response needed isn’t normal HTML or text, it could be JSON. Remember in Rails a method can respond in multiple formats, one of them could be JSON.

So for a client to request a response to a query in json, the client can either append a parameter, add .json to the end of the noun, or put application/json in the accept type in the header.

Non-Nouns

Use verbs for actions such as convert, calculate, etc.

/convert?from=EURO&to=CNY&amount=10

Limited HTTP Methods Alternatives

Put method type as a parameter to query, example:

/dogs?method=post

Problem

How do you find the number of unique words from a collection of letters contain duplicates?

Word here represents a specific orderings of letters.

Example: if a collection of letters is [a,b,b], possible words are aab, aba, baa.

Examples

Input: RRD

Output: 3, options are RRD, RDR, DRR

Input: RRDD

Output: 6, RDDR, DRRD, RDRD, DRDR, RRDD, DDRR

Why Can’t We Use Other Formulas?

Let’s suppose the collection of letters is: RRD.

To differentiate between the two Rs, let’s denote them as R1 and R2.

Permutation Formula (n!)

It doesn’t make sense to use the permutation formula, because even though R1-R2-D is a different permutation from R2-R1-D, it is the same word (using our definition from before).

Combination Formula (nCk)

But can we use the combinations formula? Kind of, we will use a related formula, but we can’t use it directly at the moment. Why?

Because what are we choosing? How does this formula work for repeated/duplicated letters? We’re not choosing 2 letters from all the letters, we want to make unique words!

So How To Think About This Problem?

Defining the formula

Let’s think about it this way, C is the number of unique letter combinations, or unique words.

But remember, for each C (aka unique word), if there are repeated letters, there can be more that one permutation which will still yield the same word. We need to account for that.

Next, there is a calculable total number of permutations, which can be found by the permutation formula, n!, where n is the size of the collection of letters.

So with that in mind, think about following equation and validate it to yourself:

(Number of unique letter combinations, or C) x (All of the permutations of C which result in the same word) = Total number of permutations

or

C * Number_Perms_For_Each = n!

Number of Permutations for Each Unique Word

Let’s think about the collection of letters as [D1, D2, R1, R2] and word DDRR.

We want to come up with the number of permutations of the letters that yield the same word.

The valid permutations: [D2, D1, R1, R2], [D1, D2, R2, R1], [D1, D2, R2, R1], [D2, D1, R2, R1].

One way to think about this is that the number of ways to switch letters and have the same word is to perform a permutation for each letter group i, which is equal to numLetters(i) and then multiplying all of these together.

Back to the formula

Our unknown is C, we can calculate the n!, and finally we can find the number of permutations of C because we know it will contain a specified number of letters types and their frequency.

So the formula turns into:

C = n! / Number_Perms_For_Each

Example

Say we have RRDD, we know R should show up twice and D should show up twice.

For each combination, there are many permutations of letters that result in the same word, this will be 2!2!

C = 4! / ( 2! * 2!) = 4 * 3 / 2 = 2 * 3 = 6

Which makes sense, since the valid six unique words are: RRDD, DDRR, RDDR, DRRD, RDRD, DRDR.

I want to think about this a bit more.

Though, honestly this is just a multinomial expansion, but this is just another way of looking at it.

Latex works!

Used this blog post.

I’ve been reviewing some material for interviews and something new I learned today is the difference between ArrayList and LinkedList.

The Big O Notes

For just review, the Big O for the operations for each data structure is:

For LinkedList

1
2
3
4

* get is O(n)
* add is O(1)
* remove is O(n)
* Iterator.remove is O(1)

For ArrayList <div class=’bogus-wrapper’>

But why the difference?

Well, something that’s obvious to me now, but wasn’t before is that ArrayList is actually backed by an array.

So what does that mean? That means that on average, adding an element to the ArrayList is constant time, since it just adds it to the next empty index. But there can be a case when the backing array is full and it needs to be made bigger. So then a new array is made, the elements are copied over, which leads to an operation of O(n).

And now the reason why remove is O(n) makes sense, if the first element was to be removed, the whole array must be shifted.

Conclusions

So when does LinkedList make sense? When you want to quickly add something to a data structure and the difference between ArrayList is that the operation is always O(1) instead of amortized O(1).

ArrayList is good for when O(1) operations are needed for adding/getting, but remember that if the list grows by a large amount that reinitializing the backing array will be costly.

By the way, an alternative for LinkedList is ArrayDeque which gives constant operations for adding/removing at both ends of the queue. I was first exposed to this data structure in Python, where it was called deque.

Update

I recently added notes for Java Collections on my GitHub Notes Repository. Check it out!

I had the chance to interview with Twilio this past week. I got the opportunity because a person with who I worked on an Android application called GT NextBus was around on campus interviewing.

And then I wanted to go back over my code just to refresh my mind about the project. As I was looking over the code base I realized that I wrote pretty good documentation describing the features I was working on and my expectations of other people working on the project.

GitHub Repo

One of the first things I do when using a new language for a project is spend a good amount of time reading language style guidelines There are many reasons for this, such as learning to write maintainable code and learning another view point on how code should be written. I did with Javascript (using online resources and JSLint), Java (Lots of reading of Apache coding style guides), and Android (used Google Android Style Guides).

I really liked the Android Styling Guideline and decided to put together a summary of all the major points for anyone who wants to skim it.

The notes are in my Notes repository which I use as a knowledge center for many Computer Science concepts.

So check out this document and others which include notes about Databases, Networking, or Object Oriented Programming.

Link to Android Styling Guide Notes

Want to know how to get comments on your Octopress blog?

It’s not difficult at all!

Steps

1. Go on over to disqus.com and make an account.

2. Click on “Universal” for the type of blog you are using.

3. Open _config.yml in your root directory for your Octopress blog.

4. Find the line that looks like the following:

1
2
3

# Disqus Comments
disqus_short_name:
disqus_show_comment_count: false

1. Look at the Disqus short name (mine is darkzeroman), use the following image as a guide for where to look.

2. Copy that over to the _config.yml entry for disqus_short_name you saw in Step 4. So mine looks like:

1
2
3

# Disqus Comments
disqus_short_name: darkzeroman
disqus_show_comment_count: false

1. You’re done!

Have fun!

Problem

While reading articles sometimes the writer doesn’t split the text up in paragraphs which can be a pain to try to read.

Paragraphs are a great way of helping a reader have landmarks in a large amount of text. Also they serve as great separators that tell the reader I’m ending on the previous idea and beginning a new one.

Solution

Some sort of extension for a browser with which a user can select a block of text and have the text automatically split into paragrahs.

This can be implemented by editing the HTML content directly and adding the line breaks after sentences end.

Context

When I browse Reddit or another similar website there are many images that I want to share with someone. The process currently looks like this:

• Copy URL to clipboard
• Paste URL to friend
• Friend clicks URL
• Friend notices funny image
• Repeat above

Problem

This process works great when I’m only sharing 1 or 2 images, but sometimes me and my buddy spend a good 10 minutes sending random images to each other and this process becomes inefficient.

I’m thinking about building a web app that will dynamically load any type of content for both users.

The use case is the following:

• User 1 sends User 2 a link to the web app
• User 1 can pass a link to the web app, which will load link automatically for User 2
• Both users can automatically load content for each other

How to build this?

Solution

Usually clients use AJAX to poll a server for status updates, but in this case, it would make sense for either the clients communicate directly or the server to push to clients updates.

I have looked into browser to browser communication platforms like WebRTC, but I don’t feel that is at a usable state for this type of project.

For the server to push updates to the client, the options are some sort of web sockets. That leaves two major tools: socket.io and SockJS.

After doing a little bit of Googling it seems the common consensus is that SockJS is better than socket.io.

Conclusion

This seems to be a pretty easy project to do, it seems like with SockJS lots of the hard implementation details are taken care of. I want to cover the concepts of SockJS in another blog post though!