multiboject tracking code

Particle filter object tracking [1] [Project](http://blogs.oregonstate.edu/hess/code/particles/)

KLT Tracker [2-3] [Project](http://www.ces.clemson.edu/~stb/klt/)

MILTrack [4] [Code](http://vision.ucsd.edu/~bbabenko/data/MilTracker-V1.0.zip)

Incremental Learning for Robust Visual Tracking [5] [Project](http://www.cs.toronto.edu/~dross/ivt/)

Online Boosting Trackers [6-7] [Project](http://www.vision.ee.ethz.ch/boostingTrackers/index.htm)

L1 Tracking [8] [Matlab code](http://www.dabi.temple.edu/~hbling/code/L1_Tracking_v4_release.zip)

bloomberg phone interview questions

// This is the text editor interface.
// Anything you type or change here will be seen by the other person in real time.
1 -> 2 -> 3  123
4 -> 5 -> 6  456
struct ListNode
{
    int val;
    ListNode *next;
    ListNode (int _val):val(_val),next(NULL){};
}
ListNode *reverse(ListNode *A)
{
    ListNode *pre =NULL;
    ListNode *curr = A;
    ListNode *next;
    while(curr)
    {
        next = curr->next;
        curr->next = pre;
        pre = curr;
        curr = next;
    }
    return pre;
}


ListNode * addTwoNumbers(ListNode *_A,ListNode *_B)
{
    int carry = 0;
    ListNode dummy(0);
    ListNode *p = &dummy;
   
    ListNode *A = reverse(_A);
    ListNode *B = reverse(_B);
   
    while(A||B)
    {
        int a = A!=NULL?A->val:0;
        int b = B!=NULL?B->val:0;
        carry = (a+b+carry)/10; a = 3, b = 5, carry = 0
        int c = (a+b+carry)%10;
        p->next = new ListNode(c);
        p = p->next;
        A = A->next;
        B = B->next;
    }
    if(carry)
        p->next = new ListNode(carry);
    return dummy.next;
}


AAPL 50
MSFT 100
GOGL 75

new trade IBM 200
IBM 200
AAPL 50
MSFT 100

new trade AAPL 100
AAPL 100
IBM 200
MSFT 100
list mycompanylist;
list::iterator it;//tracking the position for the company in the list
unordered_map::iterator> mycompanymap;

Leetcode: Shortest Distance from All Buildings

You want to build a house on an empty land which reaches all buildings in the shortest amount of distance. You can only move up, down, left and right. You are given a 2D grid of values 0, 1 or 2, where:

• Each 0 marks an empty land which you can pass by freely.
• Each 1 marks a building which you cannot pass through.
• Each 2 marks an obstacle which you cannot pass through.

Example:
Given three buildings at (0,0), (0,4), (2,2), and an obstacle at (0,2):

1 - 0 - 2 - 0 - 1 | | | | | 0 - 0 - 0 - 0 - 0 | | | | | 0 - 0 - 1 - 0 - 0

1 2 3 4 5

1 - 0 - 2 - 0 - 1 |   |   |   |   | 0 - 0 - 0 - 0 - 0 |   |   |   |   | 0 - 0 - 1 - 0 - 0

The point (1,2) is an ideal empty land to build a house, as the total travel distance of 3+3+1=7 is minimal.
Return 7.
Note:
There will be at least one building. If it is not possible to build such house according to the above rules, return -1.

Solution

The shortest distance from any empty land to a building can be calculated by BFS starting from the building in O(mn) time. Therefore the we can calculate distance from all buildings to empty lands by t rounds of BFS starting from each building. t is the total number of buildings.
In each round, we need maintain two values for every empty land: the distance and the accessibility.

• dist[i][j] is the empty land (i, j) to all the buildings.
• grid[i][j] is reused as the accessibility.

What is accessibility? It is the number of buildings that are accessible from the empty land.
In each round of BFS we can maintain these two values. In the end we just need to find the minimum value of dist[i][j] where the accessibility equals t.
One interesting point is that the grid[i][j] can also be used to check if (i, j) is visited in this round. At round k (zero based), those has grid[i][j] == k is the empty land unvisited, visited land will have grid[i][j] == k + 1. Here comes the interesting part. One may ask what if grid[i][j] < k? Answer is we do not go into the lands with grid[i][j] < k as if it is an obstacle. Why can we do that? Because grid[i][j] < k means it is not accessible by at least one of the buildings in previous rounds. Which means not only this land is not our answer, all the lands accessible from (i, j) is also not our answer.
This might be why it runs faster than many implements. The Java version runs in 13 ms.
Java

int[] dx = {1, 0, -1, 0}, dy = {0, 1, 0, -1}; public int shortestDistance(int[][] grid) { int m = grid.length, n = grid[0].length; int[][] dist = new int[m][n]; // Initialize building list and accessibility matrix `grid` List<tuple> buildings = new ArrayList<>(); for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) { if (grid[i][j] == 1) buildings.add(new Tuple(i, j, 0)); grid[i][j] = -grid[i][j]; } // BFS from every building for (int k = 0; k < buildings.size(); ++k) bfs(buildings.get(k), k, dist, grid, m, n); // Find the minimum distance int ans = -1; for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) if (grid[i][j] == buildings.size() && (ans < 0 || dist[i][j] < ans)) ans = dist[i][j]; return ans; }

12 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

int[] dx = {1, 0, -1, 0}, dy = {0, 1, 0, -1}; public int shortestDistance(int[][] grid) {     int m = grid.length, n = grid[0].length;     int[][] dist = new int[m][n];     // Initialize building list and accessibility matrix `grid`     List buildings = new ArrayList<>();     for (int i = 0; i < m; ++i)         for (int j = 0; j < n; ++j) {             if (grid[i][j] == 1)                 buildings.add(new Tuple(i, j, 0));             grid[i][j] = -grid[i][j];         }     // BFS from every building     for (int k = 0; k < buildings.size(); ++k)         bfs(buildings.get(k), k, dist, grid, m, n);     // Find the minimum distance     int ans = -1;     for (int i = 0; i < m; ++i)         for (int j = 0; j < n; ++j)             if (grid[i][j] == buildings.size() && (ans < 0 || dist[i][j] < ans))                 ans = dist[i][j];     return ans; }

Java – BFS subroutine

public void bfs(Tuple root, int k, int[][] dist, int[][] grid, int m, int n) { Queue<tuple> q = new ArrayDeque<>(); q.add(root); while (!q.isEmpty()) { Tuple b = q.poll(); dist[b.y][b.x] += b.dist; for (int i = 0; i < 4; ++i) { int x = b.x + dx[i], y = b.y + dy[i]; if (y >= 0 && x >= 0 && y < m && x < n && grid[y][x] == k) { grid[y][x] = k + 1; q.offer(new Tuple(y, x, b.dist + 1)); } } } }

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

public void bfs(Tuple root, int k, int[][] dist, int[][] grid, int m, int n) {     Queue q = new ArrayDeque<>();     q.add(root);     while (!q.isEmpty()) {         Tuple b = q.poll();         dist[b.y][b.x] += b.dist;         for (int i = 0; i < 4; ++i) {             int x = b.x + dx[i], y = b.y + dy[i];             if (y >= 0 && x >= 0 && y < m && x < n && grid[y][x] == k) {                 grid[y][x] = k + 1;                 q.offer(new Tuple(y, x, b.dist + 1));             }         }     } }

Java – Definition of Tuple

class Tuple { public int y; public int x; public int dist; public Tuple(int y, int x, int dist) { this.y = y; this.x = x; this.dist = dist; } }

1 2 3 4 5 6 7 8 9 10 11

class Tuple {     public int y;     public int x;     public int dist;     public Tuple(int y, int x, int dist) {         this.y = y;         this.x = x;         this.dist = dist;     } }

Leetcode: Walls ang Gates

You are given a m x n 2D grid initialized with these three possible values.
-1 – A wall or an obstacle.
0 – A gate.
INF – Infinity means an empty room. We use the value to represent INF as you may assume that the distance to a gate is less than 2147483647.
Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should be filled with INF.


 public class Solution {
    public static final int[] d = {0, 1, 0, -1, 0};

    public void wallsAndGates(int[][] rooms) {
        if (rooms.length == 0) return;
        for (int i = 0; i < rooms.length; ++i)
            for (int j = 0; j < rooms[0].length; ++j)
                if (rooms[i][j] == 0) bfs(rooms, i, j);
    }

    private void bfs(int[][] rooms, int i, int j) {
        int m = rooms.length, n = rooms[0].length;
        Deque queue = new ArrayDeque<>();
        queue.offer(i * n + j); // Put gate in the queue
        while (!queue.isEmpty()) {
            int x = queue.poll();
            i = x / n; j = x % n;
            for (int k = 0; k < 4; ++k) {
                int p = i + d[k], q = j + d[k + 1];
                if (0 <= p && p < m && 0 <= q && q < n && rooms[p][q] > rooms[i][j] + 1) {
                    rooms[p][q] = rooms[i][j] + 1;
                    queue.offer(p * n + q);
                }
            }
        }
    }
}



 public class Solution {
    private static int[] d = {0, 1, 0, -1, 0};

    public void wallsAndGates(int[][] rooms) {
        for (int i = 0; i < rooms.length; i++)
            for (int j = 0; j < rooms[0].length; j++)
                if (rooms[i][j] == 0) dfs(rooms, i, j);
    }

    public void dfs(int[][] rooms, int i, int j) {
        for (int k = 0; k < 4; ++k) {
            int p = i + d[k], q = j + d[k + 1];
            if (0<= p && p < rooms.length && 0<= q && q < rooms[0].length &&
                rooms[p][q] > rooms[i][j] + 1) {
                rooms[p][q] = rooms[i][j] + 1;
                dfs(rooms, p, q);
            }
        }
    }
}

recover the height from relative array

recover the height from input array, firstly create one array which has order from hight to low

Implementation max heap

implementation max heap (1)

Leetcode: course scheule

// Class to represent a graph
class Graph
{
private:
    int V;    // No. of vertices'

    // Pointer to an array containing adjacency listsList
    vector> adj;
    vector result; // the order for vertics being sorted.
    vectorinDegree;
    int count;
public:
    Graph(int _V)// Constructor
    {
        V = _V;
        adj = vector>(V);
        inDegree = vector(V,0);
        count = 0;
    };  

    // function to add an edge to graph
    void addEdge(int v, int w)
    {
        adj[w].push_back(v);
        inDegree[v]++;
    };

    // prints a Topological Sort of the complete graph
    void topologicalSort()
    {
        // find all in_degree==0, and mark them as visited(set inDegree to -1)
        queue stack;
        for(int i=0; i            if(!inDegree[i]){
                stack.push(i);
                result.push_back(i);
                inDegree[i]=-1; // maked as visited
                count++;
            }
        }
        // pop a node from queue, decrease the degree of the neighbours and push the degree==0   
        while(!stack.empty()){
            int cur=stack.front();
            stack.pop();
            for(int i=0; i                inDegree[adj[cur][i]]--;
                if(inDegree[adj[cur][i]]==0){
                    count++;
                    stack.push(adj[cur][i]);
                    result.push_back(adj[cur][i]);
                    inDegree[adj[cur][i]]=-1;
                }
            }
        }
    };
  
    vector output()
    {
        if(count==V)    return result;
        else return vector();
    }
};


class Solution {
public:
    vector findOrder(int numCourses, vector>& prerequisites) {
        Graph  graph(numCourses);
        vector result;
        for(auto it = prerequisites.begin();it!=prerequisites.end();it++ )
            graph.addEdge((*it).first,(*it).second);
           
        graph.topologicalSort(); // sorting
      
        result = graph.output();
        return result;
    }
};

WeightedUnion2DFind algorithm

class WeightedUnion2DFind
{
public:
    WeightedUnion2DFind(int m, int n,int cnt)
    {
        for(int i = 0;i        for(int i = 0;i        count = cnt;
        M = m;
        N = n;
    }
    int size(){return count++;}
   
    // find root id for current node
    int find(int p)
    {
         while(p!=ids[p]) p= ids[p];
         return p;
    }
    bool connected(int p,int q)
    {
        return find(p) == find(q);
    }
    void Union(int p, int q) //replace the sets containing two items by their union.
    {
        int rootP = find(p);
        int rootQ = find(q);
        if (rootP == rootQ)
            return;
       
        if (szs[rootP] < szs[rootQ]) ids[rootP] = rootQ;
        else if (szs[rootP] == szs[rootQ]) {
            ids[rootQ] = rootP;
            szs[rootP] += 1;
        }
        else
            ids[rootQ] = rootP;
        count--;
    }
private:
      vector ids; // id[i] = parent of i
      vector szs; // sz[i] = number of objects in subtree rooted at i
      int M,N,count;
};

class Solution {
public:
    int numIslands(vector>& grid) {
        int m = grid.size();
        if(m == 0) return 0;
        int n = grid[0].size();
        int count = 0;
        for(int i = 0;i            for(int j = 0;j                if(grid[i][j]=='1') count++;
        WeightedUnion2DFind UF(m,n,count);
        vector> visited(m,vector(n));
        int direction[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
        for(int i = 0;i            for(int j = 0;j            {
                if(grid[i][j]=='1')
                {
                   
                    //check all neigboring pixels.
                    for(int k = 0;k<4 br="" k="">                    {
                        int dx = i+direction[k][0];
                        int dy = j+direction[k][1];
                        if(!(dx>=0 && dx=0 && dy                        if( grid[dx][dy]=='1')
                            UF.Union(i*n+j,dx*n+dy);
                    }
                }
            }
        return UF.size();
    }   
};

Trie Implementation

class TrieNode {
public:
    TrieNode* dict[26];
    bool hasWord;   
    // Initialize your data structure here.
    TrieNode() {
        memset(dict,0,sizeof(dict));
        hasWord = false;
    }
};

class Trie {
public:
    Trie() {
        root = new TrieNode();
    }

// Inserts a word into the trie.
void insert(string word) {
    int i = 0;
    TrieNode * curr = root;
    while(i
        if( curr->dict[word[i] - 'a'] == nullptr){
            curr->dict[word[i]-'a'] = new TrieNode();
        }
        if(i == word.size()-1){
        curr->dict[word[i]-'a']->hasWord = true;
        }
        curr = curr->dict[word[i] - 'a'];
        i++;
    }
    return;
}

// Returns if the word is in the trie.
    bool search(string word) {
        int i = 0;
        TrieNode *curr = root;
        while(i            if(curr->dict[word[i]-'a'] == nullptr){
                return false;
            }
            if( i == word.size()-1){
                return curr->dict[word[i]-'a']->hasWord;
            }
            curr = curr->dict[word[i] - 'a'];
            i++;
        }
        return false;       
    }

    // Returns if there is any word in the trie
    // that starts with the given prefix.
    bool startsWith(string prefix) {
        TrieNode *curr = root;
        for(auto c:prefix){
            if(curr->dict[c-'a'] == nullptr)
                return false;
            curr = curr->dict[c-'a'];   
        }
        return true;
    }

private:
    TrieNode* root;
};

KMP algorithm

LeetCode: KMP algorithm
	#include
	#include
	#include
	int *compute_prefix_function(char *pattern, int psize)
	{
	int k = -1;
	int i = 1;
	int *pi = malloc(sizeof(int)*psize);
	if (!pi)
	return NULL;
	pi[0] = k;
	for (i = 1; i < psize; i++) {
	while (k > -1 && pattern[k+1] != pattern[i])
	k = pi[k];
	if (pattern[i] == pattern[k+1])
	k++;
	pi[i] = k;
	}
	return pi;
	}
	int kmp(char *target, int tsize, char *pattern, int psize)
	{
	int i;
	int *pi = compute_prefix_function(pattern, psize);
	int k = -1;
	if (!pi)
	return -1;
	for (i = 0; i < tsize; i++) {
	while (k > -1 && pattern[k+1] != target[i])
	k = pi[k];
	if (target[i] == pattern[k+1])
	k++;
	if (k == psize - 1) {
	free(pi);
	return i-k;
	}
	}
	free(pi);
	return -1;
	}
	int main(int argc, const char *argv[])
	{
	char target[] = "ABC ABCDAB ABCDABCDABDE";
	char *ch = target;
	char pattern[] = "ABCDABD";
	int i;
	i = kmp(target, strlen(target), pattern, strlen(pattern));
	if (i >= 0)
	printf("matched @: %s\n", ch + i);
	return 0;
	}

Jump to Line