## Tuesday, September 16, 2014

### 有问题，问包子！Got question? Ask Baozi!

[例题1]

Given a string of 1, 0 or ?, return all the matching strings that ? could be either 0 or 1.

For example,

input : 1??

output: {100, 101, 110, 111}.

input: 100100?00?

output: {1001000000,1001000001,1001001000,1001001001}

[思路1]

[代码1]
```public static void returnAll(String input) {
if(input == null || input.isEmpty()) {
return;
}

StringBuilder current_string = new StringBuilder();
returnAllRecursion(input, 0, current_string);
}

public static void returnAllRecursion(String input, int current_location, StringBuilder current_string){
if (input.length() == current_location) {
System.out.println(current_string);
return;
}

while (input.length() > current_location && input.charAt(current_location) != '?') {
current_string.append(input.charAt(current_location));
current_location++;
}

if (input.length() == current_location) {
System.out.println(current_string);
current_string.deleteCharAt(current_location - 1);
return;
}

if (input.charAt(current_location) == '?') {
current_string.append(0);
returnAllRecursion(input, current_location + 1, current_string);
current_string.deleteCharAt(current_string.length() - 1);
current_string.append(1);
returnAllRecursion(input, current_location + 1, current_string);
current_string.deleteCharAt(current_string.length() - 1);
}
}

public static void main(String[] args) {
returnAll("0100");
System.out.println("---------------");
returnAll("01??");
System.out.println("---------------");
returnAll("???0");
System.out.println("---------------");
returnAll("????");
}

```

[思路2]

[代码2]
```public static void returnAllUsingStack(String input) {
if(input == null || input.isEmpty()){
return;
}

Stack positionToReVisit = new Stack();
positionToReVisit.push(-1);

StringBuilder currentString = new StringBuilder();
int currStartPosition = 0;

for (int i = 0; i < input.length(); i++) {
if (input.charAt(i) == '?') {
positionToReVisit.push(i);
currentString.append(0);
break;
}
currentString.append(input.charAt(i));
currStartPosition++;
}

if (currentString.length() == input.length()) {
System.out.println(currentString);
return;
}

while (!positionToReVisit.isEmpty()) {
for (int i = currStartPosition + 1; i < input.length(); i++) {
if (input.charAt(i)== '?') {
currentString.append('0');
positionToReVisit.push(i);
} else {
currentString.append(input.charAt(i));
}
}

if (currentString.length() == input.length()) {
System.out.println(currentString);
}

currStartPosition = positionToReVisit.pop();

if (currStartPosition == -1) break;

currentString = new StringBuilder(currentString.substring(0, currStartPosition));
currentString.append('1');
}

return;
}```

[思路3]

[代码3]

```public static void matchingQuestionMark(String s) {
if (s == null || s.isEmpty()) return;

List questionMarkIndex = new ArrayList();
int totalQuestionMarkCount = 0;

for (int i = 0; i < s.length(); ++i) {
if (s.charAt(i) == '?') {
totalQuestionMarkCount++;
}
}

if (totalQuestionMarkCount == 0) return;

for (int i = 0; i < (1 << totalQuestionMarkCount); i++) {
StringBuilder sb = new StringBuilder(s);
int j = 0;
int temp = i;
while (j < totalQuestionMarkCount) {
int index = questionMarkIndex.get(j);
if ((temp & 1) == 0) {
sb.replace(index, index + 1, "0");
} else {
sb.replace(index, index + 1, "1");
}
j++;
temp = temp >> 1;

}
System.out.println(sb.toString());
}
}
```

## Thursday, September 11, 2014

### 有问题，问包子！Got question? Ask Baozi!

【转载自mitbbs

== 入门 ==

1. http://www.hiredintech.com/app#system-design

Database replication, Database partitioning 还会提到很多基本思想比如avoid
single point of failure

3. http://www.lecloud.net/post/7295452622/scalability-for-dummies-part-1-clones
1里面提到的 Scalability for Dummies 还算不错 可以看一遍 知道基本思想

== 进阶 ==

4. http://highscalability.com/blog/2009/8/6/an-unorthodox-approach-to-database-design-the-coming-of-the.html
Database Sharding是一个很重要的概念 建议看一看

5. http://highscalability.com/all-time-favorites/

Pinterest, Google等等 我的建议是看5-6个 然后你应该已经建立起了一些基本的意识

Redis 说到
load balancer你会想到 Amazon ELB, F5一类的

6. http://www.infoq.com/
5里面很多的文章都会有链接 其中有很多会指向这个网站 这里面有很多的tech talk

8. 一些国内网站上的资料
http://blog.csdn.net/sigh1988/article/details/9790337
http://blog.csdn.net/v_july_v/article/details/6279498

9. 最后一些概念很有用 都是我再看这些资料的时候发现的 如果你没有遇到或者查过

Distributed Hash Table
Eventual Consistency vs Strong Consistency
Read Heavy vs Write Heavy
Consistent Hashing
Sticky Sessions

== 小结＝＝

heavy的时候应该倾向于时间 Write heavy的时候倾向于空间等等

design本来就是一个open ended question 所以不用害怕 能够自圆其说 就不会有问题

== FAQ ==
1. New Grad需要看System Design么?

## Sunday, September 7, 2014

### 包子IT面试培训 助你拿到理想的offer!

As commonly requested from Baozi’s Facebook and Wechat group, we are now accepting interviews questions that you find challenging to solve.

Please send us the detailed interview questions through either of the following ways:

WeChat Group: baozitraining,