给出下面这个图 设计数据结构和算法求出图中所有的正方形数量 (count the number of squares).
Pre-processing: 从每一个点开始存储上下左右四个方向最多延伸到的位置
Main algorithm: 枚举右下角位置 然后枚举正方形边长
根据预处理的延伸情况判断是否能够有一个正方形被构造出来
Total time complexity is O(n3).
预处理可以O(n2) 预处理是有递推关系的
但是后面枚举的部分，只能O(n3)
不能动态规划的原因是：他给定了一个可以变化的图，这个图上规模为n的图和规模为n-1的图中正方形个数之间不存在递推关系。
And 一般来说处理矩阵的问题，大部分都是O(n3)
Given n dice each with m faces, numbered from 1 to m, find the number of ways to get sum X. X is the summation of values on each face when all the dice are thrown.
DP
Sum(m, n, X) = Sum(m, n - 1, X - 1) +
Sum(m, n - 1, X - 2) + .................... + Sum(m, n - 1, X - m)
So we can have dp(n)(X) and for each, iterate m time. Total time is O(m * n * X).
not written by me.
int findWays(int m, int n, int x)
{
// Create a table to store results of subproblems. One extra
// row and column are used for simpilicity (Number of dice
// is directly used as row index and sum is directly used
// as column index). The entries in 0th row and 0th column
// are never used.
int table[n + 1][x + 1];
memset(table, 0, sizeof(table)); // Initialize all entries as 0
// Table entries for only one dice
for (int j = 1; j <= m && j <= x; j++)
table[1][j] = 1;
// Fill rest of the entries in table using recursive relation
// i: number of dice, j: sum
for (int i = 2; i <= n; i++)
for (int j = 1; j <= x; j++)
for (int k = 1; k <= m && k < j; k++)
table[i][j] += table[i-1][j-k];
/* Uncomment these lines to see content of table
for (int i = 0; i <= n; i++)
{
for (int j = 0; j <= x; j++)
cout << table[i][j] << " ";
cout << endl;
} */
return table[n][x];
}
Count Set Bit in Binary Number.
3 = 00000011 => 2
128 = 10000000 => 1
Bits counting algorithm (Brian Kernighan). Basic idea is clear 1 bit at a time.
This algorithm goes through as many iterations as there are set bits. In the worst case, it will pass once per bit. An integer n has log(n) bits, hence the worst case is O(log(n)).
public int countSetBit(String binary) {
int num = Integer.parseInt(binary, 2);
int count = 0;
while (num != 0) {
num &= num - 1;
count++;
}
return count;
}
Singleton design pattern is one of the 2 most frequent topics for OOD.
Singleton pattern is a design pattern that restricts the instantiation of a class to one object.
Since Java 5.0, the easiest way to create a Singleton is the enum type approach. Here the code is not given.
We will instead cover a very popular implementation: Lazy initialization using double-checked locking:
public class SingletonDemo {
private static volatile SingletonDemo instance = null;
private SingletonDemo() { }
public static SingletonDemo getInstance() {
if (instance == null) {
synchronized (SingletonDemo.class) {
if (instance == null) {
instance = new SingletonDemo();
}
}
}
return instance;
}
}
An alternate simpler and cleaner version may be used at the expense of potentially lower concurrency in a multithreaded environment:
public class SingletonDemo {
private static SingletonDemo instance = null;
private SingletonDemo() { }
public static synchronized SingletonDemo getInstance() {
if (instance == null) {
instance = new SingletonDemo();
}
return instance;
}
}
Factory Method design pattern is one of the 2 most frequent topics for OOD.
Factory method pattern is a creational pattern which uses factory methods to deal with the problem of creating objects without specifying the exact class of object that will be created.
This is done by creating objects via factory method, either:
A normal Maze Game:
public class MazeGame {
public MazeGame() {
Room room1 = makeRoom();
Room room2 = makeRoom();
room1.connect(room2);
this.addRoom(room1);
this.addRoom(room2);
}
protected Room makeRoom() {
return new OrdinaryRoom();
}
}
A magic game:
public class MagicMazeGame extends MazeGame {
@Override
protected Room makeRoom() {
return new MagicRoom();
}
}
A perfect binary tree, i.e. each node in the tree is either a leaf node, or has two children, and all leaf nodes are on the same level. Each node has an index in depth-first order.
0
/ \
1 4
/ \ / \
2 3 5 6
Given the index (k) of a particular node, calculate its level.
This is a magical solution. It divides the tree in the middle with number k decrease by 1 each time.
Beautiful, and hard to understand.
not written by me.
public int countLevel(TreeNode root, int k, int n) {
int level = 0;
while (k != 0) {
k--;
n = (n - 1) / 2;
k = k % n;
level++;
}
return level + 1;
}
数组nums中有n个非负整数（整数用字符串表示），将它们以一定的顺序拼接，得到最大的整数。
样例：
nums: [“54”, “546”, “548”, “60”]
可以拼接得到的最大整数为"6054854654"，因此函数应该返回"6054854654"。
I will first list out 2 special cases:
{40, 20, 201} => 4020201
{40, 20, 203} => 4020320
Knowing about this 2 cases helps us to come up with a sorting-based algorithm. We only need to achieve this:
201 < 20
20 < 203
So the best comparator implementation would be:
String firstNum = s1 + s2;
String secondNum = s2 + s1;
return firstNum.compareTo(secondNum);
written by me.
public String biggestNum(String[] nums) {
Arrays.sort(nums, new SpecialComparator());
StringBuilder sb = new StringBuilder();
for (int i = nums.length - 1; i >= 0; i--) {
sb.append(nums[i]);
}
return sb.toString();
}
class SpecialComparator implements Comparator<String> {
public int compare(String s1, String s2) {
// eg.
// 40 > 20
// 20 > 201
// 203 > 20
String firstNum = s1 + s2;
String secondNum = s2 + s1;
return firstNum.compareTo(secondNum);
}
}
对于包含n个结点的二叉树（树中结点编号从1到n），已知前序和后序遍历序列，我们知道不一定能唯一的恢复这棵树。请计算出满足条件的二叉树的总数。
Example
前序遍历序列preorder：1 2
后序遍历序列postorder：2 1
一共有2棵满足条件的二叉树：
1 1
/ \
2 2
先看两种遍历的性质:
pre-order: root, left *************, right #########
post-order: **************left, ########right, root
所以 pre-order 的第一个元素一定等于 post-order 的最后一个元素. 然后在post-order中由前往后找, 找出等于pre-oder[left]的位置 p.
如果 p 位置不是倒数第二个, fine, 对左右子树递归调用后用乘法原理.
如果 p 是倒数第二个, 说明either left branch or right branch为空, return的值就是 2 * 递归调用非空子树.
not written by me. This code is REALLY 叼炸天。
int helper(vector<int>& preorder, vector<int>& posorder,
int i1, int j1, int i2, int j2){
if(i1 == j1) return 1;
if(preorder[i1+1] == posorder[j2-1]){
return 2*helper(preorder, posorder, i1+1, j1, i2, j2-1);
}
int k = i2;
while(posorder[k] != preorder[i1+1]){ k++; }
return helper(preorder, posorder, i1+1,i1+1+k-i2 ,i2 , k)
* helper(preorder, posorder, i1+2+k-i2, j1, k+1, j2-1);
}
int countValidTrees(vector<int>& preorder, vector<int>& posorder) {
int n = preorder.size();
return helper(preorder, posorder, 0, n-1, 0, n-1);
}
给定一个表达式字符串，其中只包含非负整数，加法，减法以及乘法符号，例如7+345+2+4-3-1。请写程序计算该表达式的值。
提示：可以尝试使用递归算法，程序将非常简洁易写，很适用于面试场合。
Trying to solve this problem iteratively is like suicide. The code would be lengthy and buggy, and very hard to make it right.
The most important point about this question, is how to handle minus(-) sign. We know that when we see * and /, we evaluate immediately, and when sees + and -, we postpone it. However this case:
1 - 2 - 3
If we postpone the first minus sign, we would end up getting:
1 - (-1)
So it’s wrong (outputing 2 in this case).
The solution to this issue is, consider (a - b) as (a + (-b)). That’s why later in the code, you’ll see a variable preNum being modified.
written by me
int p;
public int evaluate(String expr) {
p = 0;
int firstNum = getNumber(expr);
return helper(firstNum, expr);
}
private int helper(int preNum, String expr) {
// now p points to a operator (or end of string)
if (p == expr.length()) {
return preNum;
}
char operator = expr.charAt(p);
p++;
int nextNum = getNumber(expr);
switch (operator) {
case '+':
return preNum + helper(nextNum, expr);
case '-':
return preNum + helper(-1 * nextNum, expr);
case '*':
return helper(preNum * nextNum, expr);
default:
return helper(preNum / nextNum, expr);
}
}
private int getNumber(String expr) {
// now p points to a number
int num = 0;
while (p < expr.length() && expr.charAt(p) >= '0'
&& expr.charAt(p) <= '9') {
num = num * 10 + expr.charAt(p) - '0';
p++;
}
return num;
}
有一个n*m（n和m都不超过50）的棋盘，有k个目标格子需要访问。需要访问的格子的横纵坐标存放在数组x[]和y[]中(0<=x[i]<n, 0<=y[i]<m)。
遍历的规则为：
每一步只能从一个目标格子水平或者竖直跳跃移动到另一个目标格子。
连续的两步必须形成直角。即如果前一步是水平移动，那么下一步只能竖直移动。
问是否存在一种遍历顺序，使得每个目标格子有且仅被访问一次。
样例：k=8, x=[0, 0, 0, 0, 2, 2, 4, 4], y=[0, 2, 4, 6, 4, 6, 2, 4],对应于下图中A, B, C, D, F, E, G, H 8个目标格子，存在满足条件的遍历A->D->E->F->C->B->G->H。
n,m的棋盘，建一个包含n+m个顶点的图G（为了方便说明，类似二分图将其分为两列，左边n个顶点，右边m个顶点，分别代表n行和n列）。
对于目标格子(i,j)，左边第i个顶点和右边第j个顶点连一条边。最后的问题其实就是问转换之后的图G是否存在欧拉欧拉回路或者欧拉路径。