Question

link

Excel中的行列数用A~Z 26个字母表示，A, B, C, D, …, Z, AA, AB, …, AZ, BA, BB, … 分别表示10进制数1, 2, 3, 4, …, 26, 27, 28, …, 52, 53, 54…。

请实现2个函数decToExcel和excelToDec，将10进制数转换为Excel数，以及将Excel数转换为10进制数。

Solution

Note the indexing starts from 1, not from 0. This caused some trouble for me.

Code

written by me

public String decToExcel(int decNum) {
    decNum--;
    int digits = 1;
    int exponen = 26;
    while (decNum >= exponen) {
        decNum -= exponen;
        exponen *= 26;
        digits++;
    }
    // now we know the total number of digits
    int num = decNum;
    int total = exponen / 26;
    String ans = "";
    for (int i = 0; i < digits; i++) {
        ans += (char) (num / total + 'A');
        num %= total;
        total /= 26;
    }
    return ans;
}

public int excelToDec(String excelNum) {
    int digits = excelNum.length();
    int total = 1;
    int sum = 1;
    for (int i = 1; i < digits; i++) {
        total *= 26;
        sum += total;
    }
    for (int i = 0; i < digits; i++) {
        sum += (excelNum.charAt(i) - 'A') * total;
        total /= 26;
    }
    return sum;
}

updated code: we can actually do it recursively. The code is much more concise.

//将十进制数转换为excel数
public String decToExcel(int decNum) {
    if (decNum == 0) {
        return "";
    }
    decNum--;
    char last = (char) ('A' + decNum % 26);
    return decToExcel(decNum / 26) + last;
}

//将excel数转换为十进制数
public int excelToDec(String excelNum) {
    if (excelNum.equals("")) {
        return 0;
    }
    int len = excelNum.length();
    int last = 1 + excelNum.charAt(len - 1) - 'A';
    return excelToDec(excelNum.substring(0, len - 1)) * 26 + last;
}

Question

link

有n个任务需要完成（编号1到n），任务之间有一些依赖关系，如果任务a依赖于任务b和c，那么只有当任务b和任务c完成之后才能完成任务a。给定所有的依赖关系，判断这些任务是否能够完成。如果能够完成，请给出一个合法的任务完成序列。

样例：

n=5

1->2,3

3->4

上述样例中任务1依赖于任务2和任务3，任务3依赖于任务4，那么存在合法的任务完成序列4,3,2,1,5

Solution

Classic topology sorting, refer to this nice answer.

My Code

public int[] myJobSchedulerWithoutQueue(Map<Integer, List<Integer>> deps,
        int n) {
    int[] ans = new int[n];

    int[] depCount = new int[n];
    // eg. job 1 depends on job 2 and 3, thus depCount[1-1] = 2
    Map<Integer, List<Integer>> graph = new HashMap<Integer, List<Integer>>();
    // graph would be reversed version of deps, used for topology sorting
    // eg. 2 would point to 1, and 3 would points to 1
    for (int i : deps.keySet()) {
        depCount[i - 1] = deps.get(i).size();
        for (int j : deps.get(i)) {
            // add (j, i) pair into graph
            if (!graph.containsKey(j)) {
                graph.put(j, new ArrayList<Integer>());
            }
            graph.get(j).add(i);
        }
    }
    // now we got depCount[] and graph ready, let's rock
    int sorted = 0;
    while (sorted != n) {
        // first find a 'p' so that depCount[p] = 0
        int p = 0;
        while (p < n && depCount[p] != 0) {
            p++;
        }
        if (p == n) {
            // unable to find a new node to sort, sorting failed
            break;
        }
        // remember p is only the index, the value should be +1
        int val = p + 1;
        ans[sorted++] = val;
        depCount[p] = -1;
        if (graph.containsKey(val)) {
            for (int i : graph.get(val)) {
                depCount[i - 1]--;
            }
        }
    }
    if (sorted == n)
        return ans; // sort sucess
    else
        return null; // sort failed
}

The following is very similar implementation, but using a Queue to store temporary nodes.

public int[] myJobSchedulerWithQueue(Map<Integer, List<Integer>> deps, int n) {
    int[] ans = new int[n];

    int[] depCount = new int[n];
    // eg. job 1 depends on job 2 and 3, thus depCount[1-1] = 2
    Map<Integer, List<Integer>> graph = new HashMap<Integer, List<Integer>>();
    // graph would be reversed version of deps, used for topology sorting
    // eg. 2 would point to 1, and 3 would points to 1
    for (int i : deps.keySet()) {
        depCount[i - 1] = deps.get(i).size();
        for (int j : deps.get(i)) {
            // add (j, i) pair into graph
            if (!graph.containsKey(j)) {
                graph.put(j, new ArrayList<Integer>());
            }
            graph.get(j).add(i);
        }
    }
    // now we got depCount[] and graph ready, let's rock
    int sorted = 0;
    Queue<Integer> queue = new LinkedList<Integer>();
    while (sorted != n) {
        for (int i = 0; i < depCount.length; i++) {
            if (depCount[i] == 0) {
                queue.offer(i + 1);
                depCount[i] = -1;
            }
        }
        if (queue.isEmpty()) {
            break; // sorting failed
        }
        int val = queue.poll();
        ans[sorted++] = val;
        if (graph.containsKey(val)) {
            for (int i : graph.get(val)) {
                depCount[i - 1]--;
            }
        }
    }
    if (sorted == n)
        return ans; // sort sucess
    else
        return null; // sort failed
}

Question

link

给定一个非负整数a（不超过10⁶），是否存在整数b，使得a和b的乘积全为1。如果存在，返回最小的乘积的位数。如果不存在，返回-1。

样例：a=3，存在b=37，使得3*37=111，则函数应返回3（111的位数）。

Solution

There’s 1 equation of mod operation, which is helpful:

(a * b) mod x = ((mx+a') * (nx+b')) mod x = (a' mod x) * (b' mod x) = (a mod x) * (b mod x)

i.e. (a * b) mod x = (a mod x) * (b mod x)

Altough I don’t understand why does it contribute to the incredibly short solution code posted below. I can’t solve this question, frankly speaking.

Code

int findMinAllOne(int a) {
    if (a < 0 || (a % 10) % 2 == 0 || a % 10 == 5)
        return -1;

    int ans = 1;
    for (int p = 1; p != 0; p %= a) {
        p = 10 * p + 1;
        ++ans;
    }
    return a == 1 ? ans - 1 : ans;
}

Question

link

有一个无限大的棋盘，棋盘上有一匹马，马可以从长宽分别为p和q的矩形一个角移动到对角。即假设马当前的位置为(x,y)，那么下一步可以移动到(x+p,y+q)，(x+p,y-q)，(x-p,y+q)，(x-p,y-q)，(x+q,y+p)，(x+q,y-p)，(x-q,y+p)或者(x-q,y-p)这8个位置。

问马是否能从坐标(x,y)按照上述移动规则移动到坐标(x2,y2)。

Solution

ref

1. 计算dx=x-x2,dy=y-y2。
2. 求出p,q的最大公约数g，如果dx或者dy不能被g整除，那么很显然无解。
3. 将p,q,dx,dy都除以g，现在p和q互质了。
4. 注意到马可以跳到点(0,2p)（先(p,q)跳一下，然后(p,-q)跳一下），重复这个过程，马可以跳到任意(0,2kp)的点，由于对称性，也可以跳到任意(2kp,0)的点。 5.下面这一步很关键，由于p,q互质，那么存在x,y满足px+qy=1（扩展欧几里德定理）。这样，马可以跳到(0,2)和和(2,0)，由于对称性，马可以跳到任意坐标都为偶数点。
5. 有了上面的结论，其实只用考虑(0,0),(0,1),(1,0),(1,1)这4个点是否可达。(0,0)是可达的，(0,1)和(1,0)由于对称性只用考虑(0,1)。
6. 对于(1,1)，其实是永远可达的。如果q,p都为奇数，可以先跳到(1+p,1+q)的点（利用5中的结论，可以跳到都是偶数的点），然后(-p,-q)跳到(1,1)。如果p,q一奇一偶，可以先跳到(1+p+q,1+q+p)的点（利用5中的结论），然后(-p,-q),(-q,-p)两步跳到(1,1)。
7. 对于(0,1)，如果p,q一奇一偶，那么也是永远可达的（同7可证）。如果p,q都是奇数，那么是不可能跳到(0,1)的，因为两个奇数不管怎么加减交替运算都不可能变成一奇一偶。

所以最后的结论就是：第3步之后，如果p,q一奇一偶，那么可达。否则dx,dy同奇或同偶才可达。

gcd的代码 (concise version):

int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}

Code

not written by me

int gcd(int a, int b){
    return b? gcd(b, a%b) : a;
}

bool canJump(int p, int q, int x, int y, int x2, int y2) {
    if(p==0 && q==0) return (x==x2)&&(y==y2);
    int xDist = x2 - x, yDist = y2 - y;
    int g1 = gcd(p, q);
    if( xDist % g1 || yDist % g1) 
        return false;
    p = p/g1;
    q = q/g1;
    xDist = xDist/g1;
    yDist = yDist/g1;
    if((p-q)%2 ) 
        return true;
    else 
        return (xDist-yDist)%2 == 0;
}

Question

Get GCD in more efficient code

Code

this is 掉渣天。

public int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

Question

link

每一种语言，都有自己的字母表，类似英文的a-z，但是顺序不相同。例如，有的语言可能是z是第一个之类的。现在给定这个语言的字典，请分析这个字典，得到这个语言的字母表的顺序。

例如：有如下的字母：C CAC CB BCC BA。 经过分析，得到字母表为C->A->B。

Solution

http://page.renren.com/601882592/channel-noteshow-927705419

1. C 2. CAC 3. CB 4. BCC 5. BA 经过分析，得到字母表为C->A->B。

分析 字典序相邻的位置的字符串，只会有如下两种情况：

（1）排在前面的字符串是下一个串的子串，如C与CAC

（2）两个字符串具有第一对不相同的字符对，如CAC和CBB，第一个不相同的字符对为（A，B），这是就要求A在字母表中的顺序在B前面。对于后面字符并没有要求，如并不要求第二个不相同的字符对（C，B）中的C在字母表中的顺序在B前面。

所以按照第（2）种情况建图，然后对该有向无环图求拓扑排序即可。

So this becomes a Topology Sorting question.

Code

not written by me

pair<char,char>  constructEdge(const string & src1, const string & src2)
{
     int min_len = min(src1.length(), src2.length());
     int i = 0;
     while(i < min_len && src1[i] == src2[i]){
           i++;
     }
     if(i < min_len){
           return  make_pair(src1[i], src2[i]);
     }else{
           return  make_pair('\0','\0');
     }
}
//-1, 0, 1
int  alphaTable(const vector<string> &  dict, vector<char> & alpha_table)
{
     unordered_map<char,set<char> >  edges;
     set<char> nodes;
     for(const string & word : dict){
          for(char c : word){
              nodes.insert(c);
          }
     }
     unordered_map<char,int>  in_degree;
     for(int i = 1; i < dict.length(); i++){
          pair edge = constructEdge(dict[i-1],dict[i]);
          if(edge.first != '\0'){
              edges[edge.first].insert(edge.second);
              in_degree[edge.second]++;
          }
     }
     queue<char>  q;
     for(char node : nodes){
         if(in_degree[node] == 0){
              q.push(node);
         }
     }
     alpha_table.clear();
     int result = 0;
     while(!q.empty()){
        if(q.size() > 1){
            result = 1;
        }
        char  c = q.front();
        q.pop();
        alpha_table.push_back(c);
        for(char node : edges[c]){
             in_degree[node] --;
             if(in_degree[node] == 0){
                  q.push(node);
             }
         }
     }//while
     if(alpha_table.size() < nodes.size()){
         result = -1;
     }
     return result;    
}

Question

link

有一个长度为n的字符串str，有非常多的关键字query（长度不超过10），需要判断每个关键字是否是str的子串。

注意：query是动态的输入进行查询的，预先并不知道所有的query。

Solution

Best idea of the solution is to use Suffix Tree and similar alternatives.

Solution 1 is an nice idea using HashMap.

我是把所有长度< =10的子串，哈希一下存放到10个哈希表中。

至于哈希函数的选取，随便选一个应该都不会超时。

Solution 2 is using ‘suffix array’. The most important point of this idea is to only make a substring instance for every 10 characters.

只用=10的子串。然后二分查找

用=10的字串排序即可，如包含更短的串会使得预处理变成O(10nlg(10n))。 查找的复杂度可能没什么变化，使用<=10会是O(lg(10n))，而只使用=10子串初始化的话，因为可能还要进行短query跟长子串间的前缀比较，复杂度会是O(10lgn)，稍微有点提高。

Which is to say, using substring length == 10, we comsume less time for pre-processing, and a little more time when querying.

Code

Suffix tree solution from here, note written by me

private List<String> prefixList;

// pre-process the large string
public void initWithString(String str) {
    Set<String> strs = new HashSet<String>();

    for(int i = 0; i < str.length(); ++i) {
        strs.add(str.substring(i, Math.min(str.length(), i + 10)));
    }
    prefixList = new ArrayList<String>(strs);
    Collections.sort(prefixList);
}

// find the query substring
public boolean existSubString(String query) {
    int low = 0;
    int high = prefixList.size() - 1;
    while(low <= high) {
        int mid = (low + high) / 2;
        int comp = prefixList.get(mid).compareTo(query);
        if(comp == 0)  {
            return true;
        }
        if(prefixList.get(mid).startsWith(query)) {
            return true;
        }
        if(comp > 0) //mid > query
        {
            high = mid - 1;
        }else{
            low = mid + 1;
        }
    }
    return false;
}

Question

A circus is designing a tower routine consisting of people standing atop one another’s shoulders. For practical and aesthetic reasons, each person must be both shorter and lighter than the person below him or her. Given the heights and weights of each person in the circus, write a method to compute the largest possible number of people in such a tower.

EXAMPLE:

Input: (ht, wt): (65, 100) (70, 150) (56, 90) (75, 190) (60, 95) (68, 110)

Output: The longest tower is length 6 and includes from top to bottom: (56, 90) (60,95) (65,100) (68,110) (70,150) (75,190)

Solution

The solution given in the book is unclear, but it’s a very simple idea which is pointed out here and here.

1. sort the input persons by ‘height’. O(nlogn)
2. find the longest increasing ‘weight’ sequence in the sorted list. This can be done in O(nlogn) with DP.

Code

written by me

public int longestTower(List<Man> list) {
    Collections.sort(list, new ManComparator());
    // now find the longest increasing sequence of 'weight' property
    int len = list.size();
    int maxLen = 1;
    int[] dp = new int[len];
    for (int i = 1; i < len; i++) {
        dp[i] = 1;
        for (int j = 0; j < i; j++) {
            if (list.get(i).weight > list.get(j).weight) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        maxLen = Math.max(maxLen, dp[i]);
    }
    return maxLen;
}

class ManComparator implements Comparator<Man> {
    @Override
    public int compare(Man o1, Man o2) {
        return o1.height - o2.height;
    }
}

Client/Server

link

Client have direct and full access to the physical database based on their login string. This is the major weakness of the Client/Server paradigm. The system is vulnerable to attacks.

Because all business logic was implemented on the client application, changes to business logic means redeploying new client software to all users again.

Another drawback is that the network interface provided by most back-end database systems has been designed for access over the local network, using fast connections and no firewalls. Nowadays, many clients’ software needs to run from employee’s home offices or from airport lounges. In many cases such connections will be unreliable or inefficient to work on.

Multi-Tier

The communication between clients and middle-tier server is no longer tied to a protocol dictated by the database (no database drivers or connection string on the client). Client applications can authenticate with a username and password (compare to login string).

Communication can be done via HTTP or HTTPS, alternatively or additionally, open standards such as SOAP, OData and JSON can be used to expose a middle tier to different clients using protocols that are widely understood.

Biggest advantage is that all the business logic is transferred from client application into the middle tier. And the middle tier holds the final control over what data goes in or out.

Still, there’re still some business logic on the client tier as well. But it only complement the rules that are enforced on the server. Eg. Twitter enforce the 140 character limit locally, and stop you from sending a tweet that is too long (by graying out the Send button).

That means, client side checks are for convenience, and for convenience only; the middle tier server is and must be authoritative for what is allowed and what is not.

Question

link

Given n numbers (both +ve and -ve), arranged in a circle, fnd the maximum sum of consecutive number

Solution

First pass: find max subarray sum.

Second pass: find min subarray sum, and subtract it from total sum.

Suggested on G4G

Code

written by me

public int maxConsSum2(int[] arr) {
    if (arr == null || arr.length == 0) {
        return 0;
    }
    int soFar = 0;
    int max = 0;
    int totalSum = 0;
    for (Integer i: arr) {
        totalSum += i;
        // totalSum is used in next step
        soFar += i;
        soFar = Math.max(soFar, 0);
        max = Math.max(max, soFar);
    }
    int min = 0;
    // calculate the min subarray
    for (Integer i: arr) {
        soFar += i;
        soFar = Math.min(soFar, 0);
        min = Math.min(min, soFar);
    }
    return Math.max(max, totalSum - min);
}