logo
Redian新闻
>未名空间
>JobHunting - 待字闺中
>
G 家电面题目， 欢迎讨论！
avatar
G 家电面题目， 欢迎讨论！# JobHunting - 待字闺中
m*l
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
里面。。
应该算是简单的题目了，感觉还是没有发挥好。。。大牛门有什么更好的方法， 欢饮
讨论：）
avatar
h*s
2 楼
直接生成所有0,1变化的字符串集合,每个串对应一个输出结果
输出时把字符串的每一个字符对到?的位置
行么
avatar
c*p
4 楼
第2题不会
avatar
z*e
6 楼
大部分是经验题
设计模式那题很难
两个模式都是有一定深度的模式
算法倒是简单
现在g也开始向传统靠拢了？
avatar
z*e
7 楼
bridge看jdbc，gfs可能用到类似的原理
把变和不变部分分离，分开实现
不变的部分用一个抽象类实现
可变部分用接口
strategy就是一个简单interface后的impl
可以认为bridge可变部分就是这个接口
?分为变和不变的部分
然后穷举可变部分的可能性
比如1?110?
->??
->00,01,10,11
->101100,101101,111100,111101
看到这里应该明白为什么它会问那两个模式了
这里就有变和不变的部分
这个白鬼水平比较高，算法和设计模式都问的是同一个领域
avatar
N*t
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");
}
}
}
avatar
s*n
9 楼
哎， 碰到基础题，还有design pattern, 心里就犯怵，
avatar
m*l
10 楼
谢谢大波妹同学的链接，刷题快乐！
avatar
l*e
11 楼
请问楼主面的是哪个组啥职位啊？
avatar
l*0
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, 比如说：
avatar
f*b
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, 比如说：
avatar
m*l
14 楼
to lotustree, 我是platform组的，所以估计他们派了一个也是做后台服务的来面试我
，好像是google+组platform组的 ～
avatar
t*2
15 楼
重要的是你的思考的过程。递归，非递归，复杂程度，limitation，error handling。
。。
虽然题目不难，但上面2个程序答案都是不完美的。再加上如果只是默不作声的写完，
那你祈祷吧。
avatar
E*m
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
avatar
s*p
17 楼
第三题string matching有人能给出非递归的简洁方法么？
avatar
E*m
18 楼

我16樓那個不就是？

【在 s****p 的大作中提到】
: 第三题string matching有人能给出非递归的简洁方法么？
avatar
g*s
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;
}
avatar
x*8
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有人能给出非递归的简洁方法么？
avatar
x*8
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) == '?') {
avatar
z*e
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();
avatar
x*8
23 楼
oh i updated gobbs's code
his original post missed a new copy

【在 z****e 的大作中提到】
: that is the new copy
avatar
L*e
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] = '?';
}
avatar
e*s
25 楼
Bridge and Strategy 是动态与静态的区别吗？
能不能解释一下？
我怎么认为是多维与一维变化的区别。
avatar
p*2
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?"
相关阅读
大批中国员工被辞退！国人愤怒表示不会再去特斯拉 和Verizon 都要裁员7% 还有哪些公司裁员？ (转载)加微信txm149,进入华人高端私密交友社区。freerider大妈连广东东莞和湖北荆州都区分不清楚哈哈哈这个傻入职不到一年就走人 sign on需要退么Top芯片公司无线射频系统工程师职位内推（湾区） (转载)求问有人了解netflix的一线eng mgr面试流程吗？以后难民给中国游客服务H1B extension可以加急吗中国人在google是不是地位不行啊？蚂蚁金服CS大讲堂【19年2月8日：CMG,HQY,等 333 个股票的最新预测】 (转载)新人工作几个月被terminated的情况常见不？问个推荐人的问题法国为何留不住有财者和有才者请问有人知道Rockset 这个公司吗？我这种情况，怎么去加州/德州/大西雅图找工作BAT之流在美国的职位如何？Phd毕业回国or留美 (转载)
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。