google 电面 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

google 电面

google 电面# JobHunting - 待字闺中

d*42014-09-01 07:09

1 楼

问了一个就是dictionary的题：
给一个dictionary：“hello","world","opt","pot";
一个target： "pto",找出dictionary中的"opt" 和"pot"

d*42014-09-01 07:09

2 楼

第二题：
给一对票，分别代表出发站和终点站
b-c,c-d,a-b,d-e
排序：
a-b,b-c,c-d,d-e

j*82014-09-01 07:09

3 楼

这两题看着都还行阿，lz答得如何

l*a2014-09-01 07:09

4 楼

第一题就是pre-processing找anagrams
第二题有点麻烦吧，如果有cycle咋算，另外给定输入一定有结果？

【在 j*****8 的大作中提到】

: 这两题看着都还行阿，lz答得如何

j*82014-09-01 07:09

5 楼

嗯，从给的例子上看好像都是 end > start
你提的这些点需要和面试官交流一下，

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

: 第一题就是pre-processing找anagrams
: 第二题有点麻烦吧，如果有cycle咋算，另外给定输入一定有结果？

w*52014-09-01 07:09

6 楼

第二题topological sorting?

l*a2014-09-01 07:09

7 楼

基本这个意思，但是LZ条件说得不清楚

【在 w*****5 的大作中提到】

: 第二题topological sorting?

y*a2014-09-01 07:09

8 楼

第一题：
List anagram(Set dict, String target) {
Map> m=new HashMap<>();
for (String s:dict) {
char[] cc=s.toCharArray();
Arrays.sort(cc);
String key=new String(cc);
if (!m.containsKey(key))
m.put(key, new ArrayList());
m.get(key).add(s);
}
char[]cc=target.toCharArray();
Arrays.sort(cc);
String key=new String(cc);
if (m.containsKey(key)) return m.get(key);
return new ArrayList();
}
第二题：
List topSort(String[] tickets) {
Map m=new HashMap<>();
String start=null;
Comparator c=String.CASE_INSENSITIVE_ORDER;
for (String s:tickets) {
String[] items=s.split("-");
if (start==null)start=items[0];
else start=c.compare(items[0], start)<0?items[0]:start;
m.put(items[0], items[1]);
}
List rel=new ArrayList<>();
for (int i=0;iString s=start,t=m.get(start);
rel.add(s+"-"+t);
start=t;
}
return rel;
}

h*g2014-09-01 07:09

9 楼

第一题应该是找permutation吧？dictionary可以遍历么？

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

: 第一题就是pre-processing找anagrams
: 第二题有点麻烦吧，如果有cycle咋算，另外给定输入一定有结果？

m*p2014-09-01 07:09

10 楼

如果测试你的代码，你会发现没有考虑有这种票：
b -> d,
b->c,
c->d,
d-> c

【在 y**********a 的大作中提到】

: 第一题：
: List anagram(Set dict, String target) {
: Map> m=new HashMap<>();
: for (String s:dict) {
: char[] cc=s.toCharArray();
: Arrays.sort(cc);
: String key=new String(cc);
: if (!m.containsKey(key))
: m.put(key, new ArrayList());
: m.get(key).add(s);

h*t2014-09-01 07:09

11 楼

第一题用几个异或就出来了。
用不着用sort,hash,contains.add这种复杂的操作吧。

【在 y**********a 的大作中提到】

L*e2014-09-01 07:09

12 楼

processing the dictionary seems unnecessary. The dictionary could be huge. I
think get the permutation of target and lookup the dict would be sufficient.

【在 y**********a 的大作中提到】

W*y2014-09-01 07:09

13 楼

为什么第二题看不到了？

【在 d******4 的大作中提到】

: 问了一个就是dictionary的题：
: 给一个dictionary：“hello","world","opt","pot";
: 一个target： "pto",找出dictionary中的"opt" 和"pot"

h*e2014-09-01 07:09

14 楼

题目不清，第一题，target和found string的啥关系，
第二题，找出的序列满足什么条件。
给的例子不具有代表性，多给几个例子阿。

d*42014-09-01 07:09

15 楼

第一题找到所有字符相同顺序不同的串
第二题把所有的票按起始站排序，不是按 a b c的顺序排序

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

: 题目不清，第一题，target和found string的啥关系，
: 第二题，找出的序列满足什么条件。
: 给的例子不具有代表性，多给几个例子阿。

m*k2014-09-01 07:09

16 楼

会有false positive吧

【在 h*******t 的大作中提到】

: 第一题用几个异或就出来了。
: 用不着用sort,hash,contains.add这种复杂的操作吧。

m*k2014-09-01 07:09

17 楼

how about
hashmap, sorted as key, words list as value?

【在 d******4 的大作中提到】

: 第一题找到所有字符相同顺序不同的串
: 第二题把所有的票按起始站排序，不是按 a b c的顺序排序

l*22014-09-01 07:09

18 楼

能具体说下怎么用异或做么？

【在 h*******t 的大作中提到】

: 第一题用几个异或就出来了。
: 用不着用sort,hash,contains.add这种复杂的操作吧。

j*32014-09-01 07:09

19 楼

mark，好像这两题都常见。。。

【在 d******4 的大作中提到】

: 问了一个就是dictionary的题：
: 给一个dictionary：“hello","world","opt","pot";
: 一个target： "pto",找出dictionary中的"opt" 和"pot"

h*t2014-09-01 07:09

20 楼

#include
#include
using namespace std;
char XOR(string s)
{
char result = 0;
for(int i = 0; iresult ^= s[i];
return result;
}
int main()
{
char targetXOR = XOR("pto");
string dict[]={"hello", "world", "pot", "opt"};
char result = 0;
for (int i = 0; i{
result = XOR(dict[i]) ^ targetXOR;
if(!result)
cout << dict[i] <}
delete dict;
return 0;
}

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

: 能具体说下怎么用异或做么？

a*82014-09-01 07:09

21 楼

ran your program, found that XOR("hello") = 'b', XOR("world") = 'b'
but they are not anagrams

y*a2014-09-01 07:09

22 楼

static List anagram(List dict, String target){
int[] st=new int[256], ex=new int[256];
for (char c:target.toCharArray()) ++ex[c];
List rel=new ArrayList<>();
for (String s:dict) {
Arrays.fill(st, 0);
for (char c:s.toCharArray())++st[c];
if (Arrays.equals(st, ex)) rel.add(s);
}
return rel;
}

static List sortTickets(Listtickets) {
String[][] ts=new String[tickets.size()][2];
for (int i=0;iArrays.sort(ts, new Comparator(){
@Override
public int compare(String[] o1, String[] o2) {
return o1[0].compareTo(o2[0]);
}
});
List rel=new ArrayList<>();
for (int i=0;ireturn rel;
}

【在 d******4 的大作中提到】

: 第一题找到所有字符相同顺序不同的串
: 第二题把所有的票按起始站排序，不是按 a b c的顺序排序

E*12014-09-01 07:09

23 楼

手机党输个Python精简版：
1.
res=[]
for item in dictionary:
if sorted(list(target))==sorted(list(item)):
res.append[item]
return res
2. 定义一个叫Ticket的class，里面含有start和end，人给的那一堆票就是Tickets =
[tix1, tix2, tix3……]
然后：
sorted(Tickets, key=lambda x: x.start)

【在 d******4 的大作中提到】

: 第一题找到所有字符相同顺序不同的串
: 第二题把所有的票按起始站排序，不是按 a b c的顺序排序

w*m2014-09-01 07:09

24 楼

def q1(dictionary, target):
return [x for x in dictionary if sorted(x) == sorted(target)]
print q1(["hello","world","opt","pot"], 'pto')
def q2(input):
return sorted(input, key = lambda x: (x[0], x[2]))
print q2(['b-c','c-d','a-b','d-e'])

b*d2014-09-01 07:09

25 楼

mark

u*r2014-09-01 07:09

26 楼

delete 用错了吧？
而且这个异或不能保证出来的结果完全对吧？

【在 h*******t 的大作中提到】

: #include
: #include
: using namespace std;
: char XOR(string s)
: {
: char result = 0;
: for(int i = 0; i: result ^= s[i];
: return result;
: }

m*g2014-09-01 07:09

27 楼

My solution in Java. Permutation first then search
public class FindInDictionary {

private static int numOfPerm;
private static int index;
private static String [] allPerms;

private static void swap (char[] a, int i, int j){
char c = a[i]; a[i]=a[j]; a[j]=c;
}

//recursive way of creating permutation
private static void permutation (char[] a, int n)
{
if (n==1)
{
// System.out.println(String.valueOf(a));
allPerms [index]=String.valueOf(a);
index ++;
return;
}
for (int i=0;iswap (a,i,n-1);
permutation (a,n-1);
swap (a,i,n-1);
}
}

private static int factorial (int n){
int fact = 1;
for (int i=1;i<=n;i++){
fact *= i;
}
return fact;
}
public static void perm (String s){
if (s==null)
return;
else
{
int n = s.length();
int index = 0;
numOfPerm = factorial(n);
allPerms = new String [numOfPerm];
index = 0;
char[] array = s.toCharArray();
permulation (array,n);
}
}

public static void main(String[] args) {
String [] dict = {"hello", "world", "pot", "opt"};
String target = "pto";
perm (target);
for (String targetStr : allPerms)
{
for (String dictStr : dict)
{
if (targetStr.equals(dictStr) )
System.out.println("match found in dictionary: "+dictStr
);
}
}
}
}