m******l
发帖数: 4 | 1 昨天下午首次和G家进行电面，因为目前有工作， 所以心态还比较好，就是包着试一试
的态度挑战一下自己。整个过程如下：
1. 一白哥哥自报姓名，上来先问为什么选择谷歌？然后问了问简历上做过的一些项目
的细节（我还蛮奇怪的，因为听说G家都是上来就编程了啊）
2. 然后就开始问面向对象设计和设计模问题，比如如何设计 java io package,可以用
什么模式等
3. 由2引申， 问bridge pattern 和strategy pattern的区别 （一个是可以动态swap
implementation,一个只能静态）
3. 编程问题：给一个由1， 0 和 ?组成的字符串，返回所有的matching strings， “
?” 可以 match 0 and 1, 比如说：
input : 1??
output: {100, 101, 110, 111}.
input: 100100?00?
output: {1001000000,1001000001,1001001000,1001001001}
关于这个，我用了递归函数，递归call 输入字符串的 substring(1, n)，但是发现空
间复杂度太大了， 因为每次递归函数返回以后， 我都重新建立新的set, 把递归返回
的 set中每一个字符串，append 1 or 0, or both(in case of ?), 然后加到新的 set
里面。。
应该算是简单的题目了，感觉还是没有发挥好。。。大牛门有什么更好的方法， 欢饮
讨论：） | h******s
发帖数: 86 | 2 直接生成所有0,1变化的字符串集合,每个串对应一个输出结果
输出时把字符串的每一个字符对到?的位置
行么 | u*****o
发帖数: 1224 | | c********p
发帖数: 1969 | | c********p
发帖数: 1969 | | z****e
发帖数: 54598 | 6 大部分是经验题
设计模式那题很难
两个模式都是有一定深度的模式
算法倒是简单
现在g也开始向传统靠拢了？ | z****e
发帖数: 54598 | 7 bridge看jdbc，gfs可能用到类似的原理
把变和不变部分分离，分开实现
不变的部分用一个抽象类实现
可变部分用接口
strategy就是一个简单interface后的impl
可以认为bridge可变部分就是这个接口
?分为变和不变的部分
然后穷举可变部分的可能性
比如1?110?
->??
->00,01,10,11
->101100,101101,111100,111101
看到这里应该明白为什么它会问那两个模式了
这里就有变和不变的部分
这个白鬼水平比较高，算法和设计模式都问的是同一个领域 | N******t
发帖数: 43 | 8 大概写了一下编程题
// http://www.mitbbs.com/article_t/JobHunting/32505211.html: Original Question
// discussion: http://www.mitbbs.com/article_t/JobHunting/32496747.html
import java.util.*;
public class CharacterMatch {
// use recursion to solve this question
public ArrayList findMatch(String testCase) {
ArrayList res = new ArrayList();
if (testCase == null || testCase.length() == 0) {
return res;
}
// if the testCase do not contain the ? character, then just return
the original string
if (!testCase.contains("?")) {
res.add(testCase);
return res;
}
// do recusion, kind of depth first search
findMatch(testCase, 0, "", res);
return res;
}
public void findMatch(String testCase, int index, String re, ArrayList<
String> res) {
// if index equals to the length of the testCase
if (index == testCase.length()) {
res.add(re);
return;
}
// current character
char cur = testCase.charAt(index);
if (cur != '?') {
findMatch(testCase, index + 1, (re + testCase.substring(index,
index + 1)), res);
} else {
// two actions, substitute the ? with 1 and 0
findMatch(testCase, index + 1, (re + "0"), res);
findMatch(testCase, index + 1, (re + "1"), res);
}
}
public static void main(String[] args) {
String[] cases = {"1??", "100100?00?", "adg?b?dd?g"};
// result
// test case 1 : {100, 101, 110, 111}.
// test case 2 : {1001000000,1001000001,1001001000,1001001001}
CharacterMatch matcher = new CharacterMatch();
for (String ca : cases) {
System.out.println("TEST CASE : " + ca);
ArrayList res = matcher.findMatch(ca);
System.out.println(res);
System.out.println("\n\n");
}
}
} | s*******n
发帖数: 305 | 9 哎， 碰到基础题，还有design pattern, 心里就犯怵， | m******l
发帖数: 4 | | | | l*******e
发帖数: 127 | | l*******0
发帖数: 63 | 12 这不是针对fresh grad的吧？不懂设计模式啊。。。
不过第二题你的基本思路是对的。要想少一点空间的话，可以把string先转成char
array. FYI:
char[] p=str.toCharArray();
static void dfs(char[] p, int idx, ArrayList sol){
if(idx==p.length){ //find one string
sol.add(new String(p));
}else{ //replace ? to either 0 or 1
if(p[idx]=='?'){
p[idx]='0';
dfs(p,idx+1,sol);
p[idx]='1';
dfs(p,idx+1,sol);
p[idx]='?'; //backtracking
}else{
dfs(p,idx+1,sol); //do nothing
}
}
}
swap
【在 m******l 的大作中提到】
: 昨天下午首次和G家进行电面，因为目前有工作， 所以心态还比较好，就是包着试一试
: 的态度挑战一下自己。整个过程如下：
: 1. 一白哥哥自报姓名，上来先问为什么选择谷歌？然后问了问简历上做过的一些项目
: 的细节（我还蛮奇怪的，因为听说G家都是上来就编程了啊）
: 2. 然后就开始问面向对象设计和设计模问题，比如如何设计 java io package,可以用
: 什么模式等
: 3. 由2引申， 问bridge pattern 和strategy pattern的区别 （一个是可以动态swap
: implementation,一个只能静态）
: 3. 编程问题：给一个由1， 0 和 ?组成的字符串，返回所有的matching strings， “
: ?” 可以 match 0 and 1, 比如说：
| f*******b
发帖数: 520 | 13
swap
mark
【在 m******l 的大作中提到】
: 昨天下午首次和G家进行电面，因为目前有工作， 所以心态还比较好，就是包着试一试
: 的态度挑战一下自己。整个过程如下：
: 1. 一白哥哥自报姓名，上来先问为什么选择谷歌？然后问了问简历上做过的一些项目
: 的细节（我还蛮奇怪的，因为听说G家都是上来就编程了啊）
: 2. 然后就开始问面向对象设计和设计模问题，比如如何设计 java io package,可以用
: 什么模式等
: 3. 由2引申， 问bridge pattern 和strategy pattern的区别 （一个是可以动态swap
: implementation,一个只能静态）
: 3. 编程问题：给一个由1， 0 和 ?组成的字符串，返回所有的matching strings， “
: ?” 可以 match 0 and 1, 比如说：
| m******l
发帖数: 4 | 14 to lotustree, 我是platform组的，所以估计他们派了一个也是做后台服务的来面试我
，好像是google+组platform组的 ～ | t****2
发帖数: 138 | 15 重要的是你的思考的过程。递归，非递归，复杂程度，limitation，error handling。
。。
虽然题目不难，但上面2个程序答案都是不完美的。再加上如果只是默不作声的写完，
那你祈祷吧。 | E*****m
发帖数: 25615 | 16 閒逛到這裡， 我手賤，做了第三題， 用 Python, 5行
def BinaryMatching(s):
n=len([c for c in s if c=='?'])
for i in range(2**n):
b=bin(i)
print s.replace("?", "%s") % tuple(['0']*(n-len(b)+2)+list(b[2:]))
測試
>>> BinaryMatching("1??")
100
101
110
111
>>> BinaryMatching("100100?00?")
1001000000
1001000001
1001001000
1001001001
>>> BinaryMatching("adg?b?dd?g")
adg0b0dd0g
adg0b0dd1g
adg0b1dd0g
adg0b1dd1g
adg1b0dd0g
adg1b0dd1g
adg1b1dd0g | s****p
发帖数: 124 | 17 第三题string matching有人能给出非递归的简洁方法么？ | E*****m
发帖数: 25615 | 18
我16樓那個不就是？
【在 s****p 的大作中提到】
: 第三题string matching有人能给出非递归的简洁方法么？
| g***s
发帖数: 30 | 19 The Python is super, but if you do not know it, try to refer java below:
public List BinaryOutput(String input) {
if (input == null || input.empty())
return null;
List output = new ArrayList();
List temp = new ArrayList("");
for (int i = 0; i < input.length(); i++) {
output.clear();
for (String s : temp) {
if (input.charAt(i) == '?') {
output.add(s + '0');
output.add(s + '1');
}
else {
output.add(s + t);
}
}
temp = output;
}
return output;
} | x****8
发帖数: 127 | 20 private static void printCombinations(String string) {
List positions = new ArrayList();
List values = new ArrayList();
for(int i = 0; i < string.length(); ++i){
if(string.charAt(i) == '?'){
positions.add(i);
values.add(-1);
}
}
int pos = 0;
while(pos >= 0){
int val = values.get(pos) + 1;
if(val == 2){
values.set(pos--, -1);//reset current and move back 1
position
continue;
}
values.set(pos, val);
if(pos == values.size() - 1){
char[] comb = string.toCharArray();
for(int ip = 0; ip < positions.size(); ++ip){
comb[positions.get(ip)] = (char)('0' + values.get(ip));
}
System.out.println(comb);
}else{
pos++;
}
}
}
【在 s****p 的大作中提到】
: 第三题string matching有人能给出非递归的简洁方法么？
| | | x****8
发帖数: 127 | 21 a small bug below: temp = new ArrayList(output);
public static List BinaryOutput(String input) {
if (input == null || input.isEmpty())
return null;
List output = new ArrayList();
List temp = new ArrayList();
temp.add("");
for (int i = 0; i < input.length(); i++) {
output.clear();
for (String s : temp) {
if (input.charAt(i) == '?') {
output.add(s + '0');
output.add(s + '1');
}
else {
output.add(s + input.charAt(i));
}
}
temp = new ArrayList(output); <========= need a new copy
}
return output;
}
【在 g***s 的大作中提到】
: The Python is super, but if you do not know it, try to refer java below:
: public List BinaryOutput(String input) {
: if (input == null || input.empty())
: return null;
: List output = new ArrayList();
: List temp = new ArrayList("");
: for (int i = 0; i < input.length(); i++) {
: output.clear();
: for (String s : temp) {
: if (input.charAt(i) == '?') {
| z****e
发帖数: 54598 | 22 that is the new copy
【在 x****8 的大作中提到】
: a small bug below: temp = new ArrayList(output);
: public static List BinaryOutput(String input) {
: if (input == null || input.isEmpty())
: return null;
: List output = new ArrayList();
: List temp = new ArrayList();
: temp.add("");
:
: for (int i = 0; i < input.length(); i++) {
: output.clear();
| x****8
发帖数: 127 | 23 oh i updated gobbs's code
his original post missed a new copy
【在 z****e 的大作中提到】
: that is the new copy
| L*******e
发帖数: 114 | 24 试着写了一个recursive solution。
public static List match(String s){
List res = new ArrayList();
match(s.toCharArray(), 0, res);
return res;
}
private static void match(char[] array, int start, List res){
// search the first '?'
while (start < array.length && array[start] != '?'){
start++;
}
// no more '?', done
if (start == array.length){
res.add(new String(array));
return;
}
// replace '?' with 0 and 1
array[start] = '0';
match(array, start+1, res);
array[start] = '1';
match(array, start+1, res);
// restore '?'
array[start] = '?';
} | e***s
发帖数: 799 | 25 Bridge and Strategy 是动态与静态的区别吗？
能不能解释一下？
我怎么认为是多维与一维变化的区别。 | p*****2
发帖数: 21240 | 26 p = (x)->
console.log x
dfs=(input, i, res)->
if i==input.length
p res
return
if input[i]!='?'
dfs input, i+1, res+input[i]
else
dfs input, i+1, res+'0'
dfs input, i+1, res+'1'
f=(input)->
dfs input, 0, ""
f "1??"
f "100100?00?" | m******l
发帖数: 4 | 27 bridge和strategy pattern的区别， 请看这里http://stackoverflow.com/questions/464524/what-is-the-difference-between-the-bridge-pattern-and-the-strategy-pattern
总结为如下： bridge is a structural pattern, strategy is behavioral pattern
， 所以 strategy可以实现动态的swapping algorithm at runtime, 比如一个排序算
法，可以根据输入的大小选择不同的算法。而bridge是用来描述设计的结构。 |
|
