[Leetcode] Unique Path II


Follow up for “Unique Paths”:
Now consider if some obstacles are added to the grids. How many unique paths would there be?
An obstacle and empty space is marked as 1 and 0 respectively in the grid.
For example,
There is one obstacle in the middle of a 3×3 grid as illustrated below.
The total number of unique paths is 2.
Note: m and n will be at most 100.


  • Similar to Unique Path except that we need to decide whether a position has obstacle or not
    • If yes, the number of ways to it is 0


[Leetcode] Unique Path


A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).
How many possible unique paths are there?


  • 对于每一格,有两种到达它的方式,即从左边,或者从上边
    • 所以 count[i][j] = count[i-1][j] + count[i][j-1]
  • Time: O(n^2)
  • Space: O(n^2)
    • Space可以进行优化为O(n), 因为计算count每一行的值的时候只需要上一行的信息


How to come up with new ideas in security domain

The followings are my own experience in finding research ideas in security domain.

Ideas from Security Threat

  • What the defenders can do to improve security?
    • How to detect attackers?
    • How to defend against attackers?

For the cloud computing problem, the defenders can be further divided into two categories: (1) Cloud provider (2) Cloud benign users

    • What the attackers can do to increase damage?

    Ideas from Existing Work

    • Improve
      • Scalability of their mechanism
    • Combine
      • Can we combine other mechanisms with their mechanism
    • New Problem
      • Can we use the proposed mechanism to solve a different problem
    • New Mechanism
      • Can we solve the problem with a better mechanism


    Naming Entities

    • A name in a distributed system is a string of bits or characters that is used to refer to an entity 
    • Type of names
      • Address
        • The name of an access point of an entity
      • Identifiers
        • A name that uniquely identifies an entity
      • Location-independent name
        • A name that is independent from its addresses

    Name Resolution

    • A naming system maintains a name-to-address binding for resources
    • Main problem in naming
      • How to do name resolution in a distributed systems in a scalable way
    • Approaches for name resolution closely tied to naming scheme
    • Flat vs Structure naming
      • In a flat name space, identifiers are random bit strings
      • No information on location embedded in name

    Name Resolution in a Flat Name Space

    • Simple solutions that work in a LAN environment
      • Broadcasting & Multicasting
        • Message containing identifier of the entity is boardcast
        • Machine with access point for the entity replies with the address of the access point
          • ARP protocol for finding the data-link address of a machine given the IP address
          • When network grows, multicast is more efficient
      • Forwarding pointers
        • When an entity moves from A to B, it leaves behind a reference to its new location at B
    • Home-based Approaches
      • Home agent keeps track of current location of mobile entity
    • Hierarchical Approaches
      • Similar to DNS

    What is a DHT

    • Distributed Hash Table
      • key = hash(data)
      • lookup(key) -> IP address
      • send-RPC(IP address, PUT, key, value)
      • Send-RPC(IP address, GET, key)  -> value
    • Chord

    Structure Naming Systems

    • Names are organized into name spaces
      • A name space can be represented as a labeled, directed graph wit two types of nodes
        • Leaf nodes and directory nodes
        • Absolute vs relative path names
        • Local names vs global names
      • Name resolution: the process of looking up a name
        • Closure mechanism
          • Knowing where and how to start name resolution
    • Unix File Name Spaces

    Linking and Mounting

    • Symbolic link

    • Mounting remote name spaces

    Implementing Name Spaces

    • Naming service
      • A service that allows users and processes to add, remove, and lookup names
    • Name spaces for large-scale widely distributed systems are typically organized hierarchically
    • Three layers used to implement such distributed name spaces
      • Global layer
        • root node and its children
      • Administrational layer
        • Directory nodes within a single organization
      • Managerial layer
    • Example: DNS name space

    Iterative vs Recursive Resolution

    • Recursive

      • puts a higher performance demand on each name server
      • cons
        • Too high for global layer name servers
      • Pros
        • Caching is more effective
        • Communication costs may be reduces
      • Example

    • Iterative
      • Example

    Attribute-based Naming

    • An entity is described in terms of (attribute, value) pairs
    • Each entity can have several attributes
    • Attribute-based naming service are called directory services
    • LDAP (Lightweight directory access protocol) defacto industry standard
      • Based on OSI X.500 directory service
    • Another example: UDDI for web services

    Cloud Virtual Machine Allocation


    When a user request for a virtual machine in the cloud, the cloud provider needs to allocate a VM for the user.

    There are three concerns a cloud provider needs to take into account when doing the VM allocation.

    • Load Balance
    • Power Consumption
    • Security
      • For security, we aim to avoid the cloud covert channel attacks in which an attacker seeks to be co-locate with the target VM in order to extract private information from the victims. 

    Popular VM Allocation Policies

    The following table [1] shows the popular VM allocation policies.

    [1] Using Virtual Machine Allocation Policies to Defend against Co-resident Attacks in Cloud Computing, by Yi Han et al, in Transactions on Dependable and Secure Computing

    Vickrey-Clarke-Groves (VCG) Mechanism


    • VCG can maximize the social welfare given the individuals are all “selfish”


    • Players
      • There are n game players, P_1, P_2, cdots, P_n
    • Actions
      • The actions of the players are denoted as X = (x_1, x_2, cdots, x_n)
    • Payoff
      • v_i(X)
    • Real demand
      • v_i
    • Cost
      • p_i for its action
    • Utility
      • u_i = v_i - p_i


    Following Nisan’s work, the terms “mechanisms” and “incentive compatible” are defined as


    • Given a set of n players, and a set of outcomes, A, let v_i be the set of possible valuation functions of the form v_i(a) which player i could have for an outcome a in A. A mechanism is a function f: V_1 cdot V_2 cdot cdots cdot V_n rightarrow A. Given the evaluations claimed by the players, f selects an outcome, and n payment functions, p_1, p_2, cdots, p_n, where p_i = V_1 cdot V_2 cdot cdots V_n rightarrow R.

    The above defines Action and Reward.

      Incentive Compatible

      • For every player i, every v_1 in V_1, v_2 in V_2, cdots, v_n in V_n, and every v'_i in V_i, where a = f(v_i, v_{-i}) and a' = f(v'_i, v_{-i}), then
        • v_i(a) - p_i(v_i, v_{-i}) geq v_i(a') - p_i(v'_i, v_{-i}), then the mechanism is incentive compatible.
      Specifically, among those incentive compatible mechanisms, the Vickrey-Clarke-Groves (VCG) mechanism is the mostly used one.
      The VCG generally seeks to maximize the social welfare of all players in one game, where the social welfare is calculated as sum^n_{i=1} v_i. So the goal function of VCG is argmax_{a in A} sum^n_{i=1} v_i
      The VCG mechanism and the rule to design VCG mechanisms are defined as follows.

      VCG Mechanism

      • A mechanism, consisting of payment functions p_1, p_2, cdots, p_n and a function f, for a game with outcome set A, is a Vickrey-Clarke-Groves mechanism if f(v_1, v_2, cdots, v_n) = argmax_{a in A} sum^n_{i=1} v_i(a) ( f maximizes the social walfare) for some functions h_1, h_2, cdots, h_n, where h_i : V_{-i} rightarrow R (h_i does not depend on v_i)
        • forall v_i in V, p_i(v_i) = h(v_{-i}) - sum_{j neq i} v_j.

      My understanding

      • For user i, its reward is depended on others, and not related to its action
      • But why in the payment function, it deducts other users’ true value?

      Clarke Pivot Rule

      • The choice h_i(v_{-i}) = max_{b in A} sum_{j neq i} v_i(b) is called the Clark pivot payment. Under this rule the payment of player i is
        • p_i(v_1, v_2, cdots, v_n) = max_{b} sum_{j neq i} v_i(b) - sum_{j neq i} v_i(a) where a= f(v_1, v_2, cdots, v_n).

      My understanding

      • I didn’t understand it yet.

      [Leetcode] Best Time to Buy and Sell Stock II


      Say you have an array for which the ith element is the price of a given stock on day i.
      Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).


      • Sum up all possible increase
      • Time; O(n)
      • Space; O(1)



      [Leetcode] Best Time to Buy and Sell Stock III


      Say you have an array for which the ith element is the price of a given stock on day i.
      Design an algorithm to find the maximum profit. You may complete at most two transactions.


      • 用一个数组pre记录在第i天或之前完成一个transaction的左右收益
      • 用一个数组back记录从第i天或之后开始完成一个transaction的最大收益
      • 则完成两个transactions的最大收益为 max(pre[i], back[i])


      [1] https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/

      [Leetcode] Best Time to Buy and Sell Stock


      Say you have an array for which the ith element is the price of a given stock on day i.
      If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.


      • 遍历数组,记录当前最小值,记录当前最大profit
        • 当前profit = 当前值 – 当前最小值
      • 时间复杂度: O(n)
      • 空间复杂度: O(1)


      [1] https://leetcode.com/problems/best-time-to-buy-and-sell-stock/