一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 2188|回复: 27
收起左侧

9月1日 G家电面

[复制链接] |试试Instant~ |关注本帖
alucardzhou 发表于 2015-9-1 23:59:57 | 显示全部楼层 |阅读模式

2015(7-9月) 码农类 硕士 全职@Google - 内推 - 技术电面 |Other在职跳槽

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
9月1号电面面经. 1point 3acres 璁哄潧
感觉是个白人姐姐,很和蔼,很亲切。一卡就给提示。
第一题
1.设计HTML DOM数据结构
信息是.鐣欏璁哄潧-涓浜-涓夊垎鍦
<html><body><p>Hello</p></body></html>
或者
<html><body><p><b>H</b>ello</p></body></html>
【提示是类似tree】
2.写一个方法比较两个HTML数据中存粹文本是否一样
上面两个例子都是Hello,所以此方法返回true

第二题
鏉ユ簮涓浜.涓夊垎鍦拌鍧. 给个字典,要求找出一对单词。所有字符都不同。然后长度乘积最大。
cat -google 1point3acres
dog
feed . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
pull
space
cat and dog share no letters, and have a product of 3*3 = 9
space and dog share no letters, and have a product of 15
space does not work with either feed (e) or pull (p)
feed and pull is the best answer for this dictionary (4*4 = 16)
The dictionary will only contain lower case letters (a-z) . Waral 鍗氬鏈夋洿澶氭枃绔,
=> return the numeric value of word length product, e.g. 16 for the example above

地里发过。没仔细想。太可惜了-google 1point3acres




评分

2

查看全部评分

本帖被以下淘专辑推荐:

hj867955629 发表于 2015-10-25 16:09:46 | 显示全部楼层
hulahu 发表于 2015-9-2 02:33
第二道怎么做啊?
. more info on 1point3acres.com
第二题,一个int 32位,用其中26位表示是否有某个字母,然后后面比较时直接异或,不用再遍历字符串。-google 1point3acres
class Solution {
        class Pair {
. 1point 3acres 璁哄潧                String s;
                int chaSign;
                public Pair(String s, int sign) {
                        this.s = s;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                        this.chaSign = sign;
                }
        }
    public void maxLen(Set<String> dict) {
            HashSet<Character> hash = new HashSet<>();
            Pair[] pairs = new Pair[dict.size()];
            int idx = 0;
            for (String s: dict) {
                    hash.clear();
                    for (int i = 0; i < s.length(); i++) {. from: 1point3acres.com/bbs
                            hash.add(s.charAt(i));
                    }
                    int chaSign = 0;. From 1point 3acres bbs
                    for (char c = 'a'; c <= 'z'; c++) {
                            chaSign <<= 1;
                            if (hash.contains(c)) {
                                    chaSign |= 1;
                            }
                    }
                    pairs[idx++] = new Pair(s, chaSign);-google 1point3acres
            }
            . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
            int maxLen = 0;. from: 1point3acres.com/bbs
            String word1 = null, word2 = null;
            for (int j = 0; j < pairs.length; j++) {
                    for (int i = j+1; i < pairs.length; i++) {
                            if ((pairs[j].chaSign & pairs.chaSign) == 0) {
                                    int curLen = pairs[j].s.length()*pairs.s.length(); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                                    if (curLen > maxLen) {
                                            maxLen = curLen;.鏈枃鍘熷垱鑷1point3acres璁哄潧
                                            word1 = pairs[j].s;
                                            word2 = pairs.s;
                                    }
                            }
                    }
            }
            if (maxLen == 0) { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                    System.out.println("No such words");
                    return;
            }.1point3acres缃
            System.out.println("Max length product is "+maxLen+", two words are: "+word1+", "+word2);
    }
}
回复 支持 2 反对 0

使用道具 举报

yyboyz 发表于 2015-10-5 13:33:58 | 显示全部楼层
不好意思 刚刚按错发出去了

代码(已经测试过,你们可以试试):
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

import java.util.*;
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
public class LongestStringProduct {

       
        public int longestProduct(String[] input){. more info on 1point3acres.com
//1.首先用一个map以字母为key, 一个单词集合为value存储单词. 1point 3acres 璁哄潧
Map<Character, Set<String>> map=new HashMap<Character,Set<String>>();
Set<String> set=new HashSet<String>();. From 1point 3acres bbs
for(String str:input){
        set.add(str);
}.1point3acres缃
int n=input.length;
.1point3acres缃
//2. 初始化这个map   O(n*k)
for(int i=0;i<n;i++){
        for(int j=0;j<input[i].length();j++){
                char current=input[i].charAt(j);
               
                Set<String> newSet=map.get(current);. 鍥磋鎴戜滑@1point 3 acres
                if(newSet==null){
                        map.put(current, new HashSet<String>());. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                }
                map.get(current).add(input[i]);
        }
}. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

//3. 开始找了:   
int max=0;

//O(n)
for(int i=0;i<n;i++){
      //凡是跟当前单词有share字母的单词都会被放进illegalStringSet.鏈枃鍘熷垱鑷1point3acres璁哄潧
      //O(k). more info on 1point3acres.com
      Set<String> illegalStringSet=new HashSet<String>();
      for(int j=0;j<input[i].length();j++){
        char current=input[i].charAt(j);
        illegalStringSet.addAll(map.get(current));
       }


     int longest=0;
     ////O(n)
     for(String str: set){. visit 1point3acres.com for more.
            //求反集  如果不在illegalStringSet这个集合里 说明没有共同字母
      if(!illegalStringSet.contains(str)){
           longest=Math.max(longest,str.length());
      }
     }
    //最后算最大的乘积
     max=Math.max(max, longest*input[i].length());
}
return max;
        }

. 1point 3acres 璁哄潧}


很清楚-google 1point3acres
总时间复杂度: O(n^2)   k是最长字符串长度 假设k<n
空间   O(n)



评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

zq13667243992 发表于 2015-9-2 05:27:49 | 显示全部楼层
第二题是不是先排序,然后暴力解啊?? 想不出更好的方法了
回复 支持 1 反对 0

使用道具 举报

wenqiang88 发表于 2015-9-2 00:05:49 | 显示全部楼层
LZ的速度真是太快了,膜拜
回复 支持 反对

使用道具 举报

 楼主| alucardzhou 发表于 2015-9-2 00:09:17 | 显示全部楼层
wenqiang88 发表于 2015-9-1 11:05
LZ的速度真是太快了,膜拜

.鏈枃鍘熷垱鑷1point3acres璁哄潧 是挂得太快了。第二题地里有没仔细想。现在肠子都悔青了。
回复 支持 反对

使用道具 举报

ppiglett 发表于 2015-9-2 00:12:15 | 显示全部楼层
能不能说说第一题怎么做的,谢谢楼主
回复 支持 反对

使用道具 举报

jiebour 发表于 2015-9-2 00:16:45 | 显示全部楼层
第二题淡定啊,不要被吓住啊。。。。
回复 支持 反对

使用道具 举报

 楼主| alucardzhou 发表于 2015-9-2 00:20:23 | 显示全部楼层
ppiglett 发表于 2015-9-1 11:12
能不能说说第一题怎么做的,谢谢楼主

写得不好,不懂HTML的内容。
算是在不断的提示中勉强写了下来。请将就着看吧。
  1. public class HTMLTree{.鐣欏璁哄潧-涓浜-涓夊垎鍦
  2.         HTMLNode root;
  3.         .1point3acres缃
  4.         public boolean compare(HTMLTree  t1, HTMLTree t2){. Waral 鍗氬鏈夋洿澶氭枃绔,
  5.                 // Dfs
  6.                 String s1 = getText(t1.root);
  7.                 String s2 = getText(t2.root);
  8.                 return s1.isEquals(s2);
  9.         }
  10.        
  11.         // get the text from a HTMLNode
  12.         public String getText(HTMLNode t){
  13.                 String res = “”;
  14.                 if(null == t) return res;
  15.                 if(null != t.child){
  16.                         for(HTMLNode n : child). more info on 1point3acres.com
  17.                                 res += n.getText;. from: 1point3acres.com/bbs
  18.                 }                
  19.                 res += text;
    .1point3acres缃
  20.                 return res;
  21.         }. more info on 1point3acres.com
  22. }
  23. class HTMLNode {
  24.         HTMLNode[] child;
  25.         String tag;
  26.         String text;
  27. }
复制代码
回复 支持 反对

使用道具 举报

wenqiang88 发表于 2015-9-2 00:30:05 | 显示全部楼层
alucardzhou 发表于 2015-9-2 00:09
是挂得太快了。第二题地里有没仔细想。现在肠子都悔青了。

没事,等等,说不定是好消息
回复 支持 反对

使用道具 举报

 楼主| alucardzhou 发表于 2015-9-2 00:53:30 | 显示全部楼层
wenqiang88 发表于 2015-9-1 11:30
没事,等等,说不定是好消息

谢谢啦。 借你吉言。
回复 支持 反对

使用道具 举报

meetweek 发表于 2015-9-2 01:12:58 | 显示全部楼层
lz面的是software engineer吗?
回复 支持 反对

使用道具 举报

hulahu 发表于 2015-9-2 02:33:57 | 显示全部楼层
第二道怎么做啊?
回复 支持 反对

使用道具 举报

Williamslg 发表于 2015-9-2 03:32:16 | 显示全部楼层
LZ加油,第一题能否详细解释一下要求呢?
回复 支持 反对

使用道具 举报

 楼主| alucardzhou 发表于 2015-9-2 10:59:07 | 显示全部楼层
meetweek 发表于 2015-9-1 12:12. 1point3acres.com/bbs
lz面的是software engineer吗?

. 鍥磋鎴戜滑@1point 3 acres(⊙v⊙)嗯,是普通的SDE
我发现之前也有人面试时遇到设计的。
可能是针对我在职跳槽。
回复 支持 反对

使用道具 举报

 楼主| alucardzhou 发表于 2015-9-2 11:20:26 | 显示全部楼层
Williamslg 发表于 2015-9-1 14:32
LZ加油,第一题能否详细解释一下要求呢?

不好意思没有详细描述。
HTML DOM (Document )请见链接
http://www.w3schools.com/js/js_htmldom.asp
. 鍥磋鎴戜滑@1point 3 acres
                               
登录/注册后可看大图

这个图其实已经很明显了。

题目要求就是设计一个数据结构(类似树)来存一个HTML DOM。
第二个要求就是
写一个方法,用你写好的数据结构,或者直接在数据结构中实现。
比较两个HTML DOM所包含的纯文本是否一样。返回boolean
举例:
HTML_DOM_1
<html><body><p>Hello</p></body></html>
包含的文本是Hello。
HTML_DOM_2. 1point 3acres 璁哄潧
<html><body><p><b>H</b>ello</p></body></html>
包含的文本也是Hello, b只是粗体的意思。
使用compare方法输入两个DOM 对象,返回true。. from: 1point3acres.com/bbs
回复 支持 反对

使用道具 举报

hello2pig 发表于 2015-9-2 12:05:23 | 显示全部楼层
第二题好难,有大神提供思路吗?
回复 支持 反对

使用道具 举报

meetweek 发表于 2015-9-2 22:14:05 | 显示全部楼层
alucardzhou 发表于 2015-9-2 10:59
(⊙v⊙)嗯,是普通的SDE. from: 1point3acres.com/bbs
我发现之前也有人面试时遇到设计的。
可能是针对我在职跳槽。

new grad 不知道考不考设计啊.....考的话我真是跪了TUT
回复 支持 反对

使用道具 举报

rb131108 发表于 2015-9-3 09:25:54 | 显示全部楼层
第二题应该怎么做?

只想到把每个单词用Integer 做个 bitmap,放在hashmap里
然后两两比较 O(n2)

. 1point 3acres 璁哄潧
回复 支持 反对

使用道具 举报

randyzhao 发表于 2015-9-8 03:25:48 | 显示全部楼层
所以第二题唯一的优化就是排好序之后从长的单词开始两两匹配?
回复 支持 反对

使用道具 举报

hj867955629 发表于 2015-10-5 07:04:43 | 显示全部楼层
alucardzhou 发表于 2015-9-2 00:20-google 1point3acres
写得不好,不懂HTML的内容。
算是在不断的提示中勉强写了下来。请将就着看吧。

17行是getText(n)?递归吧
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-7 05:53

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表