G 家电面题目，欢迎讨论！ - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

G 家电面题目，欢迎讨论！

G 家电面题目，欢迎讨论！# JobHunting - 待字闺中

m*l2013-08-10 07:08

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*s2013-08-10 07:08

2 楼

直接生成所有0,1变化的字符串集合,每个串对应一个输出结果
输出时把字符串的每一个字符对到?的位置
行么

u*o2013-08-10 07:08

3 楼

以前讨论过的。。
http://www.mitbbs.com/article_t/JobHunting/32496747.html

c*p2013-08-10 07:08

4 楼

第2题不会

c*p2013-08-10 07:08

5 楼

大波妹太厉害了，看一眼就知道做过。

【在 u*****o 的大作中提到】

: 以前讨论过的。。
: http://www.mitbbs.com/article_t/JobHunting/32496747.html

z*e2013-08-10 07:08

6 楼

大部分是经验题
设计模式那题很难
两个模式都是有一定深度的模式
算法倒是简单
现在g也开始向传统靠拢了？

z*e2013-08-10 07:08

7 楼

bridge看jdbc，gfs可能用到类似的原理
把变和不变部分分离，分开实现
不变的部分用一个抽象类实现
可变部分用接口
strategy就是一个简单interface后的impl
可以认为bridge可变部分就是这个接口
?分为变和不变的部分
然后穷举可变部分的可能性
比如1?110?
->??
->00,01,10,11
->101100,101101,111100,111101
看到这里应该明白为什么它会问那两个模式了
这里就有变和不变的部分
这个白鬼水平比较高，算法和设计模式都问的是同一个领域

N*t2013-08-10 07:08

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*n2013-08-10 07:08

9 楼

哎，碰到基础题，还有design pattern, 心里就犯怵，

m*l2013-08-10 07:08

10 楼

谢谢大波妹同学的链接，刷题快乐！

l*e2013-08-10 07:08

11 楼

请问楼主面的是哪个组啥职位啊？

l*02013-08-10 07:08

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*b2013-08-10 07:08

13 楼

swap
mark

【在 m******l 的大作中提到】

m*l2013-08-10 07:08

14 楼

to lotustree, 我是platform组的，所以估计他们派了一个也是做后台服务的来面试我
，好像是google+组platform组的～

t*22013-08-10 07:08

15 楼

重要的是你的思考的过程。递归，非递归，复杂程度，limitation，error handling。
。。
虽然题目不难，但上面2个程序答案都是不完美的。再加上如果只是默不作声的写完，
那你祈祷吧。

E*m2013-08-10 07:08

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*p2013-08-10 07:08

17 楼

第三题string matching有人能给出非递归的简洁方法么？

E*m2013-08-10 07:08

18 楼

我16樓那個不就是？

【在 s****p 的大作中提到】

: 第三题string matching有人能给出非递归的简洁方法么？

g*s2013-08-10 07:08

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*82013-08-10 07:08

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*82013-08-10 07:08

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*e2013-08-10 07:08

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*82013-08-10 07:08

23 楼

oh i updated gobbs's code
his original post missed a new copy

【在 z****e 的大作中提到】

: that is the new copy

L*e2013-08-10 07:08

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*s2013-08-10 07:08

25 楼

Bridge and Strategy 是动态与静态的区别吗？
能不能解释一下？
我怎么认为是多维与一维变化的区别。

p*22013-08-10 07:08

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*l2013-08-10 07:08

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是用来描述设计的结构。