Visual Search

It is a technical to search objects in visual environment, like search your friend in a crowd of people, search for food in a supermarket. My visual search have used a eye movements as means to measure to the degree of attention given to stimuli.

But vast research suggest that eye movements move independently of attention and therefore is not a reliable method to examine the role of attention. Much of the previous literature on visual search uses reaction time in order to measure the time taken to detect the target amongst its distractors.

==Search type:
Features search. The objects could be describe by the features. And the target could be quickly figured out by checking the value of the features. For example, from the red circle in a set of black circle. This search could be very efficient. It can be done in parallel.

Conjunction search. When the target and the distractors have more similarities in more than one single visual property such as size, color, orientation, and shape.

Image matching. Visual search via image matching can be used for a large variety of applications. It should have one or more search libraries containing images to be matched, associated with metadata such as descriptions, classifications, and links to further information. The advantages of this method


==Theory,

One way to visual search via image of regions can be accomplished is using a mathematical technique called vector quantization. It is like partitioning the image into kernels, similar to the technique of tokenizing the document into works or sentences. Then, the image is stored as indexes of these kernels.

Recommendation System Notes

In general, recommendation system could be summarized in two big classes. One is content-based recommendation, the other one is collaborative filtering recommendation.

==Classification
First, Non-Personalized System, or community based recommendation. which means the system does not reveal any personal information. It collects the most popular items in the system, regardless users' characteristics, like hotel, restaurant recommendation, such as yelp. You cannot filtering the result based on your personal preferences. For instance, I am in my 20s and I like some restaurant whose environment is very fancy and I do not care much about the tasty of the food.

Second, content-based recommendation. User ratings are correlated to item features. For each item, extract its features, then we can get the weighting of item features for each user. For an new item, we can predict the rating based on its features. Alternatively, no all the users like to provide the explicit ratings, for this type of systems, it is possible to get users information from the implicit information, like users' browsing/clicking/navigating information, like news feeds, some music, video recommendation systems.

Third, collaborative-filtering recommendation. The fundamental assumption is that people have similar preference would like to see the similar items. For instance, if both of us like horror romance movie, then you saw a movie that I have not seen before. It is highly likely that I would like the movie as well. The key information is the ratings information. And the problem is that the rating information is quite sparse for most the cases. Ways to handle this issue includes filling the missing values, selecting promising cells.

==Evaluation
First, Accuracy. Precision and Recall to see whether the predicted user preferences is really what user likes.

Second, Usefulness of recommendations. Such as diversity, non-obviousness.

Third, Computational performance.

==Details of Content-based Recommendation
The key is to build the attribute vectors for each item. TFIDF can be used to create a profile of a document/object. For instance, a movie could be described as a weighted vector of its tags. Three main steps:
1. computing vectors to describe items
2. building users' preference
3. predicting user interest in items.

From item vector to user profiles. There could be multiple methods to handle it.

1. Simply add together based on users preference, which is a dot-production of two vectors for each feature.

For instance, Item vectors are as following. The last column is vector rating vector.

	baseball	economics	politics	Europe	Asia	soccer	war	security	shopping	family	user_vec
doc1	1	0	1	0	1	1	0	0	0	1	1
doc2	0	1	1	1	0	0	0	1	0	0	-1
doc3	0	0	0	1	1	1	0	0	0	0
doc4	0	0	1	1	0	0	1	1	0	0
doc5	0	1	0	0	0	0	0	0	1	1
doc6	1	0	0	1	0	0	0	0	0	0
doc7	0	0	0	0	0	0	0	1	0	1
doc8	0	0	1	1	0	0	1	0	0	1	1
doc9	0	0	0	0	0	1	0	0	1	0
doc10	0	1	0	0	1	0	1	0	0	0
doc11	0	0	1	0	1	0	0	0	1	0
doc12	1	0	0	0	0	1	1	0	0	0
doc13	0	0	1	1	1	0	0	1	0	0
doc14	0	1	1	1	0	0	0	0	1	0
doc15	0	0	0	1	0	1	1	1	0	0
doc16	1	0	0	0	0	1	0	0	1	0	1
doc17	0	1	1	1	0	0	0	1	0	0
doc18	0	0	0	1	0	0	0	0	1	0
doc19	0	1	1	0	1	0	1	0	0	1	-1
doc20	0	0	1	1	0	0	1	0	1	0

A simple way to construct users' preference is:

User_Profile#baseball=baseball * user_vec

Based on the method, we can get results for other features as well. Here is the result:

User_Profile=(3, -2, -1, 0, 0, 2, -1, -1, 1, 0)

2. Normalize the vector. So that an vector with more features will not just simply become more important.

3. Weighted the features. Like, 1/DF or Log(1/DF). The occurrence of the features.

The most challenge part of Content-based recommendation is figuring out the right way to weights and factors

== Details for Collaborative filtering Recommendation
The fundamental assumption is that our past agreement predict our future agreement. The major steps for CF algorithm:
1. Selecting neighbors. which is to find the similar users. Normally, you can select top 25-100 neighbors. The more the better, the system will have higher coverage. The similarity algorithms could be pearson correlation. For this method, you can ignore******* normalization.
2. Scoring the items from neighbors. Predict item score based on similar users. Some methods include, average, weighted average, and multiple linear regression. Weighted average is common.
3. Normalize the data. This is due to users have different preference to rating items. Some give higher number, some give lower number. And normalized the data could reduce this difference.
4.

Rock your next interview

How to prepare your interviews for Google, Linkedin, Facebook, Amazon, Twitter, and etc. ? Based on the poster's own experiences, if you are able to solve 60% of the problems in Leetcode, you can easily pass all the phone interviews. But, system design are the critical ingredients for you to get the offer, especially for experienced engineers.

In this post, I will share the materials that helped me to pass the phone interviews first and I will summarize the materials that helped me to get an offer in the next post.

Leetcode  is a very helpful website for engineers to prepare their interview. If you have pretty time to prepare your next interview, I would suggest you to go through all the questions once, focusing on those ones that you have no idea to start. O, damn, there are only three days into my next interview, what should I do? 

1) Go to familiar with the basic data structure, such as Queue, Stack, HashMap, Binary Tree, Graph.

2) Go the Leetcode, check the right bottom panel, you should be able to Tag. "String", "LinkedList", "HashTable", "Binary Search" should be very goods one to start. You still have sometime left, go to  "Depth-first search", "Breath-first search", "Recursive".

3) This n00tc0d3r has excellent explanation for most of the classic problems in Leetcode . If you want to understand the solutions, definitely check this blogger.   

   

Minimum Window Substring

Problem

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

For example,
S = "ADOBECODEBANC"
T = "ABC"

Minimum window is "BANC".

from https://leetcode.com/problems/minimum-window-substring/

Solution:
There is a very nice post on this problem. Here is the link: http://n00tc0d3r.blogspot.com/2013/04/minimum-window-substring.html

Issue:

One the issue I found when I coded this problem is that I used LinkedList to store the next index of the needed characters. And the system throws an Time Limit Exceeded exception. Then, I start to carefully compare my code with code of the above link. I found the only difference is that that post used ArrayList instead of LinkedList.

Here is the difference between ArrayList and LinkedList
1. LinkedList implements it with a doubly-linked list. ArrayList implements it with a dynamically resizing array
2. LinkedList<E> allows for constant-time insertions or removals using iterators, but only sequential access of elements; ArrayList<E>, on the other hand, allow fast random read access, so you can grab any element in constant time.
3. Also, if you have large lists, keep in mind that memory usage is also different. Each element of a LinkedList has more overhead since pointers to the next and previous elements are also stored. ArrayLists don't have this overhead

Therefore, when you are not sure, start with ArrayList

Edit Distance

Problem:

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

a) Insert a character
b) Delete a character
c) Replace a character

Idea:

Think about the sub problems.  for any given length strings, i and j. How to get the min distance.  1) String i, to delete a character,  2) String j, to delete a character, 3) or replace a character.   

So minDistance(i ,j ) = Math.min  0f the following four sub problems

                                  minDistance(i-1,j) +1
                                 minDistance(i,j-1)+1
                                  minDistance(i-1,j-1) +1    if(stringI.charAt(i)!=stringJ.charAt(j)) ,
                                  minDistance(i-1,j-1)          if(stringI.charAt(i)==stringJ.charAt(j))

Then, we can use a two dimensional arrays to solve the problem by filling the array.

Solution:

public class Solution { 

              public int minDistance(String word1, String word2) { 

                      if(word1 == null && word2==null) return 0; if(word1==null) return word2.length();                           if(word2==null) return word1.length(); if(word1.length()==0) return word2.length();                           if(word2.length()==0) return word1.length(); int[][] result=new int[word1.length()][word2.length()]; 

                      result[0][0]=word1.charAt(0)==word2.charAt(0)?0:1; 

                      for(int i =1;i<word2.length();i++){ 

                             if(word2.charAt(i)==word1.charAt(0)){ 

                                     result[0][i]=i; 

                             }else{ result[0][i]=result[0][i-1]+1; } 

                       } 

                       for(int i =1;i<word1.length();i++){ 

                            if(word1.charAt(i)==word2.charAt(0)){ 

                                        result[i][0]=i;

                            }else{ result[i][0]=result[i-1][0]+1; } 

                       } 

                      for(int i=1;i<word1.length();i++){ 

                           for(int j=1;j<word2.length();j++){ 

                                 int localMin1 = Math.min(result[i-1][j]+1,result[i][j-1]+1); 

                                 int tmp=word1.charAt(i)==word2.charAt(j)?result[i-1][j-1]:result[i-1][j-1]+1;                                      result[i][j]=Math.min(localMin1,tmp); } } return result[word1.length()-1][word2.length()-1]; }

                     }

}

Decode Ways

Problem:

A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26

Given an encoded message containing digits, determine the total number of ways to decode it.

For example,
Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).

Idea:



Solution: 

public class Solution {
    public int numDecodings(String s) {
        if(s == null || s.length()<1) return 0;
     
        int store[]=new int[s.length()+1];
        store[0]=decodeable(s.substring(0,1))?1:0;
        if(s.length()<2) return store[0];
        store[1]=decodeable(s.substring(1,2))?store[0]:0;
        if(s.length()>1&&decodeable(s.substring(0,2))){
            store[1] +=1;
        }
       
        for(int i =2;i<s.length();i++){
            if(decodeable(s.substring(i,i+1))){
                store[i] = store[i-1];
            }
            if(decodeable(s.substring(i-1,i+1))){
                store[i] +=store[i-2];
            }
        }
       
        return store[s.length()-1];
       
    }
   
    public boolean decodeable(String str){
        int result = 0;
        if(str.charAt(0)=='0') return false;
        for(int i =0;i<str.length();i++){
            result =result *10+str.charAt(i)-'0';
        }
        if(result<=26 && result>0) return true;
        return false;
    }
}

Group Anagrams

The major part is to group strs by the same key. Here I used to a way to sort all the characters, and check whether after sorting, strings have the same key or not. If they have the same key, then they are anagrams. Otherwise, they are not.

public class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        if(strs == null) return null;
        List<List<String>> result =new ArrayList<List<String>>();
        if(strs.length==0) return result;
        HashMap<String, List<String>> map =new HashMap<String, List<String>>();
        for(int i =0;i<strs.length;i++){
            String key = getKey(strs[i]);
            if(map.containsKey(key)){
                List<String> vals = map.get(key);
                vals.add(strs[i]);
            }else{
                List<String> vals = new ArrayList<String>();
                vals.add(strs[i]);
                map.put(key, vals);
            }
        }
        for(Map.Entry<String, List<String>> element:map.entrySet()){
            result.add(element.getValue());
        }
        return result;
    }
 
    String getKey(String str){
        if(str==null || str.length()<=1) return str;
        char[] tmp = str.toCharArray();
        Arrays.sort(tmp);
        return new String(tmp);
    }
}

Generate Parentheses

The basic idea is to use recursive way to generate the parenthesis. When you add one additional parenthesis, check all the potential locations, and check the whether it has appeared before or not.

public class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<String>();
        if(n==0) return result;
        if(n==1) {result.add("()");return result;}
        List<String> sub = generateParenthesis(n-1);
        for(String val:sub){
            List<String> tmp = addOneParenthesis(val);
            for(String tmp1:tmp){
                if(!result.contains(tmp1)){
                    result.add(tmp1);
                }
            }
        }
        return result;
    }
   
    private List<String> addOneParenthesis(String val){
        List<String> result =new ArrayList<String>();
        if(val==null || val.isEmpty()){
            return result;
        }
        for(int i =0;i<val.length();i++){
            StringBuffer buf = new StringBuffer();
            buf.append(val.substring(0,i));
            buf.append("()");
            buf.append(val.substring(i,val.length()));
            result.add(buf.toString());
        }
        return result;
    }
}

Letter Combinations of a Phone Number

My java solution.

The basic idea is to have a helper function to get the corresponding characters for each digit; then use for-loops to get the combinations

public class Solution {
    // have a helper function to get all the corresponding letters, and then combine the result togeter by StringBuffer.
    public List<String> letterCombinations(String digits) {
        List<String> res = new ArrayList<String>();
        if(digits ==null ||digits.length()==0) return res;
        for(int i=0;i<digits.length();i++){
            List<Character> resChars=getChars(digits.charAt(i));
            if(res.size()==0){
                for(int j =0;j<resChars.size();j++){
                    res.add(resChars.get(j)+"");
                }
            }else{
                List<String> restmp = new ArrayList<String>();
                for(int p =0;p<res.size();p++){
                    for(int q =0;q<resChars.size();q++){
                        restmp.add(res.get(p)+resChars.get(q));
                    }
                }
                res=restmp;
            }
        }
        return res;
    }
   
    List<Character> getChars(char digit){
        List<Character> res = new ArrayList<Character>();
       
        switch(digit){
            case '2': res.add('a');res.add('b');res.add('c');break;
            case '3': res.add('d');res.add('e');res.add('f');break;
            case '4': res.add('g');res.add('h');res.add('i');break;
            case '5': res.add('j');res.add('k');res.add('l');break;
            case '6': res.add('m');res.add('n');res.add('o');break;
            case '7': res.add('p');res.add('q');res.add('r');res.add('s');break;
            case '8': res.add('t');res.add('u');res.add('v');break;
            case '9': res.add('w');res.add('x');res.add('y');res.add('z');break;
            default:break;
        }
       
        return res;
    }
}