d******4
发帖数: 3 | 1 问了一个就是dictionary的题：
给一个dictionary：“hello","world","opt","pot";
一个target： "pto",找出dictionary中的"opt" 和"pot" |
d******4
发帖数: 3 | 2 第二题：
给一对票，分别代表出发站和终点站
b-c,c-d,a-b,d-e
排序：
a-b,b-c,c-d,d-e |
j*****8
发帖数: 3635 | |
l*****a
发帖数: 14598 | 4 第一题就是pre-processing找anagrams
第二题有点麻烦吧，如果有cycle咋算，另外给定输入一定有结果？
【在 j*****8 的大作中提到】
: 这两题看着都还行阿，lz答得如何
|
j*****8
发帖数: 3635 | 5 嗯，从给的例子上看好像都是 end > start
你提的这些点需要和面试官交流一下，
【在 l*****a 的大作中提到】
: 第一题就是pre-processing找anagrams
: 第二题有点麻烦吧，如果有cycle咋算，另外给定输入一定有结果？
|
w*****5
发帖数: 75 | |
l*****a
发帖数: 14598 | 7 基本这个意思，但是LZ条件说得不清楚
【在 w*****5 的大作中提到】
: 第二题topological sorting?
|
y**********a
发帖数: 824 | 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;i
String s=start,t=m.get(start);
rel.add(s+"-"+t);
start=t;
}
return rel;
} |
h****g
发帖数: 105 | 9 第一题应该是找permutation吧？dictionary可以遍历么？
【在 l*****a 的大作中提到】
: 第一题就是pre-processing找anagrams
: 第二题有点麻烦吧，如果有cycle咋算，另外给定输入一定有结果？
|
m**p
发帖数: 189 | 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*******t
发帖数: 2679 | 11 第一题用几个异或就出来了。
用不着用sort,hash,contains.add这种复杂的操作吧。
【在 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);
|
L*******e
发帖数: 114 | 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 的大作中提到】
: 第一题：
: 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);
|
W*********y
发帖数: 481 | 13 为什么第二题看不到了？
【在 d******4 的大作中提到】
: 问了一个就是dictionary的题：
: 给一个dictionary：“hello","world","opt","pot";
: 一个target： "pto",找出dictionary中的"opt" 和"pot"
|
h*******e
发帖数: 1377 | 14 题目不清，第一题，target和found string的 啥关系，
第二题， 找出的序列满足什么条件。
给的例子不具有代表性，多给几个例子阿。 |
d******4
发帖数: 3 | 15 第一题 找到所有字符相同顺序不同的串
第二题 把所有的票按起始站排序，不是按 a b c的顺序排序
【在 h*******e 的大作中提到】
: 题目不清，第一题，target和found string的 啥关系，
: 第二题， 找出的序列满足什么条件。
: 给的例子不具有代表性，多给几个例子阿。
|
m*****k
发帖数: 731 | 16 会有false positive吧
【在 h*******t 的大作中提到】
: 第一题用几个异或就出来了。
: 用不着用sort,hash,contains.add这种复杂的操作吧。
|
m*****k
发帖数: 731 | 17 how about
hashmap, sorted as key, words list as value?
<"opt", ["opt","pot"]>
【在 d******4 的大作中提到】
: 第一题 找到所有字符相同顺序不同的串
: 第二题 把所有的票按起始站排序，不是按 a b c的顺序排序
|
l*******2
发帖数: 36 | 18 能具体说下怎么用异或做么？
【在 h*******t 的大作中提到】
: 第一题用几个异或就出来了。
: 用不着用sort,hash,contains.add这种复杂的操作吧。
|
j**********3
发帖数: 3211 | 19 mark，好像这两题都常见。。。
【在 d******4 的大作中提到】
: 问了一个就是dictionary的题：
: 给一个dictionary：“hello","world","opt","pot";
: 一个target： "pto",找出dictionary中的"opt" 和"pot"
|
h*******t
发帖数: 2679 | 20 #include
#include
using namespace std;
char XOR(string s)
{
char result = 0;
for(int i = 0; i
result ^= 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*********8
发帖数: 140 | 21 ran your program, found that XOR("hello") = 'b', XOR("world") = 'b'
but they are not anagrams |
y**********a
发帖数: 824 | 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;i
Arrays.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;i
return rel;
}
【在 d******4 的大作中提到】
: 第一题 找到所有字符相同顺序不同的串
: 第二题 把所有的票按起始站排序，不是按 a b c的顺序排序
|
E***1
发帖数: 2534 | 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********m
发帖数: 1137 | 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*****d
发帖数: 39 | |
u*******r
发帖数: 864 | 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******g
发帖数: 100 | 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;i
swap (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
);
}
}
}
} |
d*r
发帖数: 25 | 28 反例：“aaa”，“a”
这题复杂度比较低的做法是用26个素数做hash。
【在 h*******t 的大作中提到】
: #include
: #include
: using namespace std;
: char XOR(string s)
: {
: char result = 0;
: for(int i = 0; i: result ^= s[i];
: return result;
: }
|
