m**q
发帖数: 189 | 1 从mitbbs59整理的题目列表中看到的，没什么思路大部分也找不到原来的链接了，大牛
们帮忙说说思路？先谢了
1. 你有一种语言的dictionary,你有一大串string,没有delimit,你如何interpret成字
典中的字呢？
http://www.mitbbs.com/article/JobHunting/31488093_3.html
2. 给你一个字典array of strings (you may preprocess it if necessary)
任意一个单词，求最小的edit distance
一个单位的distance定义为:
a. replace a letter
b. delete a letter
c. insert a letter (also at any position)
快速的code出来～ 你就可以拿facebook面试了
Pasted from <http://www.mitbbs.com/article/JobHunting/31501445_3.html
3. 有m个nuts, n个bolts，规格大小都不相同
只能nut和bolt之间比较
怎么把他们排序？要求复杂度最小
Pasted from <http://www.mitbbs.com/article_t/JobHunting/31502045.html
4. Find the shortest path to convert one string to another using the minimum
edits with each transformation string being a valid dictionary word in a
dictionary.
for example: for->fork->ford->word->sword
Pasted from <http://www.mitbbs.com/article/JobHunting/31429703_3.html
5. Given N points in a place with their (x,y) co-ordinates. Find two points
with least distance between them.
Pasted from <http://www.mitbbs.com/article/JobHunting/31437667_3.html
6. {1，5， -5， -8，2， -1，15 } 要把负的扫到左边，正的扫到后边。不能改变
顺序
得到{-5 -8 -1 1 5 2 15} 这个题有time 低于 n^2 space=O（1）的解法吗
Pasted from <http://www.mitbbs.com/article/JobHunting/31464055_3.html |
g**********y
发帖数: 14569 | 2 1. 你有一种语言的dictionary,你有一大串string,没有delimit,你如何interpret成字
典中的字呢？
http://www.mitbbs.com/article/JobHunting/31488093_3.html
这个刚讨论过，就是把一个句子分拆成单词，既可以用Trie, 也可以DP。去search
ihasleetcode的帖子。
2. 给你一个字典array of strings (you may preprocess it if necessary)
任意一个单词，求最小的edit distance
一个单位的distance定义为:
a. replace a letter
b. delete a letter
c. insert a letter (also at any position)
这个我不知道有什么高效的办法，我就brutal force: 反复调用minimumEditDistance(
String a, String b)，求最小值。
求最小值的时候可以加点智能，比如已知现在最小值为k, 那么word.length() +/- k以
外的词就不用搜了。另外，DP计算的时候，也可以用这个条件来剪枝，超过k的时候，
该路径直接赋值Integer.Max。
3. 有m个nuts, n个bolts，规格大小都不相同
只能nut和bolt之间比较
怎么把他们排序？要求复杂度最小
不清楚题意。
4. Find the shortest path to convert one string to another using the minimum
edits with each transformation string being a valid dictionary word in a
dictionary.
for example: for->fork->ford->word->sword
这个在CareerCup 150上有，BFS.
5. Given N points in a place with their (x,y) co-ordinates. Find two
pointswith least distance between them.
这是topcoder tutorial: Line Sweeping第一个例题。
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=
6. {1，5， -5， -8，2， -1，15 } 要把负的扫到左边，正的扫到后边。不能改变
顺序得到{-5 -8 -1 1 5 2 15} 这个题有time 低于 n^2 space=O（1）的解法吗
这个刚讨论过：
http://www.mitbbs.com/article_t/JobHunting/31928077.html
http://stackoverflow.com/questions/5347616/how-to-sort-an-integ |
s*****y
发帖数: 897 | 3 火鸡同学有line sweeep的代码可以让我们学习一下吗？ |
g**********y
发帖数: 14569 | 4 真正O(nlogn)的代码写起来太复杂，要是谁有可以贴。我就写了个简单的，觉得够
interview用了。
public class NearestPair {
public double minDistance(int[][] p) {
double min = Double.MAX_VALUE;
int N = p.length;
ArrayList points = new ArrayList();
for (int i=0; i
Collections.sort(points, new Comparator() {
public int compare(Point a, Point b) {
return a.x - b.x;
}
});
ArrayList processed = new ArrayList();
processed.add(points.remove(0));
while (!points.isEmpty()) {
Point next = points.remove(0);
while (!processed.isEmpty() && next.x > processed.get(0).x + min
) {
processed.remove(0);
}
for (Point i : processed) {
if (i.y <= next.y + min && i.y >= next.y - min) {
min = Math.min(min, Math.sqrt((i.x-next.x)*(i.x-next.x)
+
(i.y-next.y)*(i.y-next.y)));
}
}
processed.add(next);
}
return min;
}
private class Point {
int x, y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
}
}
【在 s*****y 的大作中提到】
: 火鸡同学有line sweeep的代码可以让我们学习一下吗？
|
s*****y
发帖数: 897 | |
q******8
发帖数: 848 | 6 mitbbs59总结贴的链接能给一下吗
谢谢
【在 m**q 的大作中提到】
: 从mitbbs59整理的题目列表中看到的，没什么思路大部分也找不到原来的链接了，大牛
: 们帮忙说说思路？先谢了
: 1. 你有一种语言的dictionary,你有一大串string,没有delimit,你如何interpret成字
: 典中的字呢？
: http://www.mitbbs.com/article/JobHunting/31488093_3.html
: 2. 给你一个字典array of strings (you may preprocess it if necessary)
: 任意一个单词，求最小的edit distance
: 一个单位的distance定义为:
: a. replace a letter
: b. delete a letter
|
b*******8
发帖数: 37364 | 7 第二题标准的DP方法，Edit Distance |
g**********y
发帖数: 14569 | 8 DP求的是两个字串之间的edit distance。如果给一个字串，和一本字典，让你找最短
距离，能把这个字串变成单词，这个怎么DP?
Peter Norvig的blog里有很好的解释：
http://norvig.com/spell-correct.html
【在 b*******8 的大作中提到】
: 第二题标准的DP方法，Edit Distance
|
r*******g
发帖数: 1335 | 9 你这个太复杂了
难道不能：http://en.wikipedia.org/wiki/Levenshtein_distance
在dp的基础上判断每一步是不是在字典中，没到达一个格子的时候同时维护一个string
，因为很多string本身就不属于字典，所以不用继续往下变化了。这个如何？
【在 g**********y 的大作中提到】
: DP求的是两个字串之间的edit distance。如果给一个字串，和一本字典，让你找最短
: 距离，能把这个字串变成单词，这个怎么DP?
: Peter Norvig的blog里有很好的解释：
: http://norvig.com/spell-correct.html
|
g**********y
发帖数: 14569 | 10 说说给你一个单词和一本字典，你怎么DP？
比如sanetiing -> sonetiing -> sometiing -> something
除了最后的结果，每一步都不是字典的单词。
string
【在 r*******g 的大作中提到】
: 你这个太复杂了
: 难道不能：http://en.wikipedia.org/wiki/Levenshtein_distance
: 在dp的基础上判断每一步是不是在字典中，没到达一个格子的时候同时维护一个string
: ，因为很多string本身就不属于字典，所以不用继续往下变化了。这个如何？
|
|
|
r*******g
发帖数: 1335 | 11 嗯，确实有问题，感觉这个题很难，google一下会发现有人说这个问题是Np hard
【在 g**********y 的大作中提到】
: 说说给你一个单词和一本字典，你怎么DP？
: 比如sanetiing -> sonetiing -> sometiing -> something
: 除了最后的结果，每一步都不是字典的单词。
:
: string
|
M**u
发帖数: 10158 | 12 BKtree应该可以
【在 g**********y 的大作中提到】
: DP求的是两个字串之间的edit distance。如果给一个字串，和一本字典，让你找最短
: 距离，能把这个字串变成单词，这个怎么DP?
: Peter Norvig的blog里有很好的解释：
: http://norvig.com/spell-correct.html
|
g**********y
发帖数: 14569 | 13 那个是近似算法吧
【在 M**u 的大作中提到】
: BKtree应该可以
|
m**q
发帖数: 189 | 14
1. 你有一种语言的dictionary,你有一大串string,没有delimit,你如何interpret成字
典中的字呢？
http://www.mitbbs.com/article/JobHunting/31488093_3.html
这个刚讨论过，就是把一个句子分拆成单词，既可以用Trie, 也可以DP。去search
ihasleetcode的帖子。
=> 收到，多谢啦
应该是trie + backtracking 或者 trie + DP吧
2. 给你一个字典array of strings (you may preprocess it if necessary)
任意一个单词，求最小的edit distance
一个单位的distance定义为:
a. replace a letter
b. delete a letter
c. insert a letter (also at any position)
这个我不知道有什么高效的办法，我就brutal force: 反复调用minimumEditDistance(
String a, String b)，求最小值。
求最小值的时候可以加点智能，比如已知现在最小值为k, 那么word.length() +/- k以
外的词就不用搜了。另外，DP计算的时候，也可以用这个条件来剪枝，超过k的时候，
该路径直接赋值Integer.Max。
3. 有m个nuts, n个bolts，规格大小都不相同
只能nut和bolt之间比较
怎么把他们排序？要求复杂度最小
不清楚题意。
=> 我理解是两个数组a和b，把他们排序，但是
a中的元素之间不能比较，b中的元素之间也不能比较，
只能是a与b的元素之间比较。
4. Find the shortest path to convert one string to another using the minimum
edits with each transformation string being a valid dictionary word in a
dictionary.
for example: for->fork->ford->word->sword
这个在CareerCup 150上有，BFS.
=> 今天看了一下，CareerCup上的原题是同样长度的单词，这个还是要复杂一些，思路
倒是类似的
5. Given N points in a place with their (x,y) co-ordinates. Find two
pointswith least distance between them.
这是topcoder tutorial: Line Sweeping第一个例题。
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=
=> 多谢了，看到你的帖子才想起来 编程之美 上也有:)
6. {1，5， -5， -8，2， -1，15 } 要把负的扫到左边，正的扫到后边。不能改变
顺序得到{-5 -8 -1 1 5 2 15} 这个题有time 低于 n^2 space=O（1）的解法吗
这个刚讨论过：
http://www.mitbbs.com/article_t/JobHunting/31928077.html
http://stackoverflow.com/questions/5347616/how-to-sort-an-integ
【在 g**********y 的大作中提到】
: 1. 你有一种语言的dictionary,你有一大串string,没有delimit,你如何interpret成字
: 典中的字呢？
: http://www.mitbbs.com/article/JobHunting/31488093_3.html
: 这个刚讨论过，就是把一个句子分拆成单词，既可以用Trie, 也可以DP。去search
: ihasleetcode的帖子。
: 2. 给你一个字典array of strings (you may preprocess it if necessary)
: 任意一个单词，求最小的edit distance
: 一个单位的distance定义为:
: a. replace a letter
: b. delete a letter
|
h**********8
发帖数: 267 | 15 mark
【在 m**q 的大作中提到】
: 从mitbbs59整理的题目列表中看到的，没什么思路大部分也找不到原来的链接了，大牛
: 们帮忙说说思路？先谢了
: 1. 你有一种语言的dictionary,你有一大串string,没有delimit,你如何interpret成字
: 典中的字呢？
: http://www.mitbbs.com/article/JobHunting/31488093_3.html
: 2. 给你一个字典array of strings (you may preprocess it if necessary)
: 任意一个单词，求最小的edit distance
: 一个单位的distance定义为:
: a. replace a letter
: b. delete a letter
|
w********s
发帖数: 11 | 16 第3题有点奇怪，如果所有的nuts对所有的bolts都是大（无法定量比较大多少），则没
法排序呀。
类似的只见过n个nuts和n个对应的bolts的，每一对规格大小不同。这种情况可以就用
quick sort的思路，先用一个nut做pivot对bolts做一轮quick sort，找到配对的bolt
后，用这个bolt再对nuts做一轮quick sort...... 相当于两个数组交错进行quick
sort。
【在 m**q 的大作中提到】
:
: 1. 你有一种语言的dictionary,你有一大串string,没有delimit,你如何interpret成字
: 典中的字呢？
: http://www.mitbbs.com/article/JobHunting/31488093_3.html
: 这个刚讨论过，就是把一个句子分拆成单词，既可以用Trie, 也可以DP。去search
: ihasleetcode的帖子。
: => 收到，多谢啦
: 应该是trie + backtracking 或者 trie + DP吧
: 2. 给你一个字典array of strings (you may preprocess it if necessary)
: 任意一个单词，求最小的edit distance
|
P**********c
发帖数: 3417 | 17 恩，你这个感觉比较象个完整的题目。
bolt
【在 w********s 的大作中提到】
: 第3题有点奇怪，如果所有的nuts对所有的bolts都是大（无法定量比较大多少），则没
: 法排序呀。
: 类似的只见过n个nuts和n个对应的bolts的，每一对规格大小不同。这种情况可以就用
: quick sort的思路，先用一个nut做pivot对bolts做一轮quick sort，找到配对的bolt
: 后，用这个bolt再对nuts做一轮quick sort...... 相当于两个数组交错进行quick
: sort。
|
g*****i
发帖数: 2162 | 18 第五题line sweeping里面说"This range can be extracted from the sorted set in
O(log N) time". 这是不是代表java里面TreeSet.subSet()能在O(log N)实现?具体是
如何实现的你知道吗? 谢谢
【在 g**********y 的大作中提到】
: 1. 你有一种语言的dictionary,你有一大串string,没有delimit,你如何interpret成字
: 典中的字呢？
: http://www.mitbbs.com/article/JobHunting/31488093_3.html
: 这个刚讨论过，就是把一个句子分拆成单词，既可以用Trie, 也可以DP。去search
: ihasleetcode的帖子。
: 2. 给你一个字典array of strings (you may preprocess it if necessary)
: 任意一个单词，求最小的edit distance
: 一个单位的distance定义为:
: a. replace a letter
: b. delete a letter
|
g**********y
发帖数: 14569 | 19 对sorted set，logN找左右边界，然后把这个range的数取出来。
TreeSet的实现，你可以去读Java source code. 是通过TreeMap来实现的，API里写的：
“A Red-Black tree based NavigableMap implementation. The map is sorted according to the natural ordering of its keys, or by a Comparator provided at map creation time, depending on which constructor is used.
This implementation provides guaranteed log(n) time cost for the containsKey, get, put and remove operations. Algorithms are adaptations of those in Cormen, Leiserson, and Rivest's Introduction to Algorithms. ”
in
【在 g*****i 的大作中提到】
: 第五题line sweeping里面说"This range can be extracted from the sorted set in
: O(log N) time". 这是不是代表java里面TreeSet.subSet()能在O(log N)实现?具体是
: 如何实现的你知道吗? 谢谢
|
g*****i
发帖数: 2162 | 20 假设这个range里有K个entry,那复杂度是不是O(logN+k)?
的：
according to the natural ordering of its keys, or by a Comparator provided
at map creation time, depending on which constructor is used.
containsKey, get, put and remove operations. Algorithms are adaptations of
those in Cormen, Leiserson, and Rivest's Introduction to Algorithms. ”
【在 g**********y 的大作中提到】
: 对sorted set，logN找左右边界，然后把这个range的数取出来。
: TreeSet的实现，你可以去读Java source code. 是通过TreeMap来实现的，API里写的：
: “A Red-Black tree based NavigableMap implementation. The map is sorted according to the natural ordering of its keys, or by a Comparator provided at map creation time, depending on which constructor is used.
: This implementation provides guaranteed log(n) time cost for the containsKey, get, put and remove operations. Algorithms are adaptations of those in Cormen, Leiserson, and Rivest's Introduction to Algorithms. ”
:
: in
|
|
|
m****t
发帖数: 555 | 21 5. Given N points in a place with their (x,y) co-ordinates. Find two points
with least distance between them.
这题可以用分而治之的方法来达到O(nlogn),但这还不是最好的算法．可以用
randomized algorithm 达到 O(n). 详见 Algorithm Design 这本书。 |
m**q
发帖数: 189 | 22 O(nlgn)的code好像是挺麻烦的
想了想可以用一个multi-map，key是y坐标，val是x坐标，因为
有可能两个点y坐标相同，所以不能用普通的set或者map。
比较麻烦的代码是查找map内 [y-h,y+h]区间内的点，这个好像
map没有现成的操作。或者不用map自己写一个BST来处理..
【在 g**********y 的大作中提到】
: 真正O(nlogn)的代码写起来太复杂，要是谁有可以贴。我就写了个简单的，觉得够
: interview用了。
: public class NearestPair {
: public double minDistance(int[][] p) {
: double min = Double.MAX_VALUE;
: int N = p.length;
: ArrayList points = new ArrayList();
:
: for (int i=0; i: Collections.sort(points, new Comparator() {
|
k*j
发帖数: 153 | 23 第一题没能找到1hasleetcode的帖子，麻烦火鸡同学给个链接吧。多谢！
【在 g**********y 的大作中提到】
: 1. 你有一种语言的dictionary,你有一大串string,没有delimit,你如何interpret成字
: 典中的字呢？
: http://www.mitbbs.com/article/JobHunting/31488093_3.html
: 这个刚讨论过，就是把一个句子分拆成单词，既可以用Trie, 也可以DP。去search
: ihasleetcode的帖子。
: 2. 给你一个字典array of strings (you may preprocess it if necessary)
: 任意一个单词，求最小的edit distance
: 一个单位的distance定义为:
: a. replace a letter
: b. delete a letter
|
k*j
发帖数: 153 | 24 我觉得这题难点就在如何维护一个BST，使得insert,delete，search都是lg(n)。只能
用BST。有同学写出来了吗？
【在 m**q 的大作中提到】
: O(nlgn)的code好像是挺麻烦的
: 想了想可以用一个multi-map，key是y坐标，val是x坐标，因为
: 有可能两个点y坐标相同，所以不能用普通的set或者map。
: 比较麻烦的代码是查找map内 [y-h,y+h]区间内的点，这个好像
: map没有现成的操作。或者不用map自己写一个BST来处理..
|
y******n
发帖数: 47 | 25 Algorithm design manual里面的题目是这样的:
Problem: The nuts and bolts problem is defined as follows. You are given a
collection
of n bolts of different widths, and n corresponding nuts. You can test
whether a
given nut and bolt fit together, from which you learn whether the nut is too
large,
too small, or an exact match for the bolt. The differences in size between
pairs of
nuts or bolts are too small to see by eye, so you cannot compare the sizes
of two
nuts or two bolts directly. You are to match each bolt to each nut.
bolt
【在 w********s 的大作中提到】
: 第3题有点奇怪，如果所有的nuts对所有的bolts都是大（无法定量比较大多少），则没
: 法排序呀。
: 类似的只见过n个nuts和n个对应的bolts的，每一对规格大小不同。这种情况可以就用
: quick sort的思路，先用一个nut做pivot对bolts做一轮quick sort，找到配对的bolt
: 后，用这个bolt再对nuts做一轮quick sort...... 相当于两个数组交错进行quick
: sort。
|
m****t
发帖数: 555 | 26
too
这题就是CLRS一书的习题8-4
【在 y******n 的大作中提到】
: Algorithm design manual里面的题目是这样的:
: Problem: The nuts and bolts problem is defined as follows. You are given a
: collection
: of n bolts of different widths, and n corresponding nuts. You can test
: whether a
: given nut and bolt fit together, from which you learn whether the nut is too
: large,
: too small, or an exact match for the bolt. The differences in size between
: pairs of
: nuts or bolts are too small to see by eye, so you cannot compare the sizes
|
m**q
发帖数: 189 | 27 翻了一下algorithm design的对应章节，好像还是挺复杂的
points
【在 m****t 的大作中提到】
: 5. Given N points in a place with their (x,y) co-ordinates. Find two points
: with least distance between them.
: 这题可以用分而治之的方法来达到O(nlogn),但这还不是最好的算法．可以用
: randomized algorithm 达到 O(n). 详见 Algorithm Design 这本书。
|
m**q
发帖数: 189 | 28 第5题我看编程之美/算法导论上有用分治的方法的，也是O(nlgn），
主要是合并子问题的时候要达到O(n)比较麻烦，需要把两个子问题
按y轴排序的结果合并，还有在合并前的结果中要找到与x轴划分点
水平距离h以内的元素序列，实现起来感觉比sweeping line还要复杂些
【在 g**********y 的大作中提到】
: 1. 你有一种语言的dictionary,你有一大串string,没有delimit,你如何interpret成字
: 典中的字呢？
: http://www.mitbbs.com/article/JobHunting/31488093_3.html
: 这个刚讨论过，就是把一个句子分拆成单词，既可以用Trie, 也可以DP。去search
: ihasleetcode的帖子。
: 2. 给你一个字典array of strings (you may preprocess it if necessary)
: 任意一个单词，求最小的edit distance
: 一个单位的distance定义为:
: a. replace a letter
: b. delete a letter
|
m**q
发帖数: 189 | 29 还是对STL不熟，multimap的话用lower_bound和upper_bound就够了，
找y坐标在lower_bound(y-h)和upper_bound(y+h)之间的点
或者用一个set，元素是pair，自动按先y坐标后x坐标排序，
然后还是用lower_bound+upper_bound.
【在 m**q 的大作中提到】
: O(nlgn)的code好像是挺麻烦的
: 想了想可以用一个multi-map，key是y坐标，val是x坐标，因为
: 有可能两个点y坐标相同，所以不能用普通的set或者map。
: 比较麻烦的代码是查找map内 [y-h,y+h]区间内的点，这个好像
: map没有现成的操作。或者不用map自己写一个BST来处理..
|
m**q
发帖数: 189 | 30 从mitbbs59整理的题目列表中看到的，没什么思路大部分也找不到原来的链接了，大牛
们帮忙说说思路？先谢了
1. 你有一种语言的dictionary,你有一大串string,没有delimit,你如何interpret成字
典中的字呢？
http://www.mitbbs.com/article/JobHunting/31488093_3.html
2. 给你一个字典array of strings (you may preprocess it if necessary)
任意一个单词，求最小的edit distance
一个单位的distance定义为:
a. replace a letter
b. delete a letter
c. insert a letter (also at any position)
快速的code出来～ 你就可以拿facebook面试了
Pasted from <http://www.mitbbs.com/article/JobHunting/31501445_3.html
3. 有m个nuts, n个bolts，规格大小都不相同
只能nut和bolt之间比较
怎么把他们排序？要求复杂度最小
Pasted from <http://www.mitbbs.com/article_t/JobHunting/31502045.html
4. Find the shortest path to convert one string to another using the minimum
edits with each transformation string being a valid dictionary word in a
dictionary.
for example: for->fork->ford->word->sword
Pasted from <http://www.mitbbs.com/article/JobHunting/31429703_3.html
5. Given N points in a place with their (x,y) co-ordinates. Find two points
with least distance between them.
Pasted from <http://www.mitbbs.com/article/JobHunting/31437667_3.html
6. {1，5， -5， -8，2， -1，15 } 要把负的扫到左边，正的扫到后边。不能改变
顺序
得到{-5 -8 -1 1 5 2 15} 这个题有time 低于 n^2 space=O（1）的解法吗
Pasted from <http://www.mitbbs.com/article/JobHunting/31464055_3.html |
|
|
g**********y
发帖数: 14569 | 31 1. 你有一种语言的dictionary,你有一大串string,没有delimit,你如何interpret成字
典中的字呢？
http://www.mitbbs.com/article/JobHunting/31488093_3.html
这个刚讨论过，就是把一个句子分拆成单词，既可以用Trie, 也可以DP。去search
ihasleetcode的帖子。
2. 给你一个字典array of strings (you may preprocess it if necessary)
任意一个单词，求最小的edit distance
一个单位的distance定义为:
a. replace a letter
b. delete a letter
c. insert a letter (also at any position)
这个我不知道有什么高效的办法，我就brutal force: 反复调用minimumEditDistance(
String a, String b)，求最小值。
求最小值的时候可以加点智能，比如已知现在最小值为k, 那么word.length() +/- k以
外的词就不用搜了。另外，DP计算的时候，也可以用这个条件来剪枝，超过k的时候，
该路径直接赋值Integer.Max。
3. 有m个nuts, n个bolts，规格大小都不相同
只能nut和bolt之间比较
怎么把他们排序？要求复杂度最小
不清楚题意。
4. Find the shortest path to convert one string to another using the minimum
edits with each transformation string being a valid dictionary word in a
dictionary.
for example: for->fork->ford->word->sword
这个在CareerCup 150上有，BFS.
5. Given N points in a place with their (x,y) co-ordinates. Find two
pointswith least distance between them.
这是topcoder tutorial: Line Sweeping第一个例题。
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=
6. {1，5， -5， -8，2， -1，15 } 要把负的扫到左边，正的扫到后边。不能改变
顺序得到{-5 -8 -1 1 5 2 15} 这个题有time 低于 n^2 space=O（1）的解法吗
这个刚讨论过：
http://www.mitbbs.com/article_t/JobHunting/31928077.html
http://stackoverflow.com/questions/5347616/how-to-sort-an-integ |
s*****y
发帖数: 897 | 32 火鸡同学有line sweeep的代码可以让我们学习一下吗？ |
g**********y
发帖数: 14569 | 33 真正O(nlogn)的代码写起来太复杂，要是谁有可以贴。我就写了个简单的，觉得够
interview用了。
public class NearestPair {
public double minDistance(int[][] p) {
double min = Double.MAX_VALUE;
int N = p.length;
ArrayList points = new ArrayList();
for (int i=0; i
Collections.sort(points, new Comparator() {
public int compare(Point a, Point b) {
return a.x - b.x;
}
});
ArrayList processed = new ArrayList();
processed.add(points.remove(0));
while (!points.isEmpty()) {
Point next = points.remove(0);
while (!processed.isEmpty() && next.x > processed.get(0).x + min
) {
processed.remove(0);
}
for (Point i : processed) {
if (i.y <= next.y + min && i.y >= next.y - min) {
min = Math.min(min, Math.sqrt((i.x-next.x)*(i.x-next.x)
+
(i.y-next.y)*(i.y-next.y)));
}
}
processed.add(next);
}
return min;
}
private class Point {
int x, y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
}
}
【在 s*****y 的大作中提到】
: 火鸡同学有line sweeep的代码可以让我们学习一下吗？
|
s*****y
发帖数: 897 | |
q******8
发帖数: 848 | 35 mitbbs59总结贴的链接能给一下吗
谢谢
【在 m**q 的大作中提到】
: 从mitbbs59整理的题目列表中看到的，没什么思路大部分也找不到原来的链接了，大牛
: 们帮忙说说思路？先谢了
: 1. 你有一种语言的dictionary,你有一大串string,没有delimit,你如何interpret成字
: 典中的字呢？
: http://www.mitbbs.com/article/JobHunting/31488093_3.html
: 2. 给你一个字典array of strings (you may preprocess it if necessary)
: 任意一个单词，求最小的edit distance
: 一个单位的distance定义为:
: a. replace a letter
: b. delete a letter
|
b*******8
发帖数: 37364 | 36 第二题标准的DP方法，Edit Distance |
g**********y
发帖数: 14569 | 37 DP求的是两个字串之间的edit distance。如果给一个字串，和一本字典，让你找最短
距离，能把这个字串变成单词，这个怎么DP?
Peter Norvig的blog里有很好的解释：
http://norvig.com/spell-correct.html
【在 b*******8 的大作中提到】
: 第二题标准的DP方法，Edit Distance
|
r*******g
发帖数: 1335 | 38 你这个太复杂了
难道不能：http://en.wikipedia.org/wiki/Levenshtein_distance
在dp的基础上判断每一步是不是在字典中，没到达一个格子的时候同时维护一个string
，因为很多string本身就不属于字典，所以不用继续往下变化了。这个如何？
【在 g**********y 的大作中提到】
: DP求的是两个字串之间的edit distance。如果给一个字串，和一本字典，让你找最短
: 距离，能把这个字串变成单词，这个怎么DP?
: Peter Norvig的blog里有很好的解释：
: http://norvig.com/spell-correct.html
|
g**********y
发帖数: 14569 | 39 说说给你一个单词和一本字典，你怎么DP？
比如sanetiing -> sonetiing -> sometiing -> something
除了最后的结果，每一步都不是字典的单词。
string
【在 r*******g 的大作中提到】
: 你这个太复杂了
: 难道不能：http://en.wikipedia.org/wiki/Levenshtein_distance
: 在dp的基础上判断每一步是不是在字典中，没到达一个格子的时候同时维护一个string
: ，因为很多string本身就不属于字典，所以不用继续往下变化了。这个如何？
|
r*******g
发帖数: 1335 | 40 嗯，确实有问题，感觉这个题很难，google一下会发现有人说这个问题是Np hard
【在 g**********y 的大作中提到】
: 说说给你一个单词和一本字典，你怎么DP？
: 比如sanetiing -> sonetiing -> sometiing -> something
: 除了最后的结果，每一步都不是字典的单词。
:
: string
|
|
|
M**u
发帖数: 10158 | 41 BKtree应该可以
【在 g**********y 的大作中提到】
: DP求的是两个字串之间的edit distance。如果给一个字串，和一本字典，让你找最短
: 距离，能把这个字串变成单词，这个怎么DP?
: Peter Norvig的blog里有很好的解释：
: http://norvig.com/spell-correct.html
|
g**********y
发帖数: 14569 | 42 那个是近似算法吧
【在 M**u 的大作中提到】
: BKtree应该可以
|
m**q
发帖数: 189 | 43
1. 你有一种语言的dictionary,你有一大串string,没有delimit,你如何interpret成字
典中的字呢？
http://www.mitbbs.com/article/JobHunting/31488093_3.html
这个刚讨论过，就是把一个句子分拆成单词，既可以用Trie, 也可以DP。去search
ihasleetcode的帖子。
=> 收到，多谢啦
应该是trie + backtracking 或者 trie + DP吧
2. 给你一个字典array of strings (you may preprocess it if necessary)
任意一个单词，求最小的edit distance
一个单位的distance定义为:
a. replace a letter
b. delete a letter
c. insert a letter (also at any position)
这个我不知道有什么高效的办法，我就brutal force: 反复调用minimumEditDistance(
String a, String b)，求最小值。
求最小值的时候可以加点智能，比如已知现在最小值为k, 那么word.length() +/- k以
外的词就不用搜了。另外，DP计算的时候，也可以用这个条件来剪枝，超过k的时候，
该路径直接赋值Integer.Max。
3. 有m个nuts, n个bolts，规格大小都不相同
只能nut和bolt之间比较
怎么把他们排序？要求复杂度最小
不清楚题意。
=> 我理解是两个数组a和b，把他们排序，但是
a中的元素之间不能比较，b中的元素之间也不能比较，
只能是a与b的元素之间比较。
4. Find the shortest path to convert one string to another using the minimum
edits with each transformation string being a valid dictionary word in a
dictionary.
for example: for->fork->ford->word->sword
这个在CareerCup 150上有，BFS.
=> 今天看了一下，CareerCup上的原题是同样长度的单词，这个还是要复杂一些，思路
倒是类似的
5. Given N points in a place with their (x,y) co-ordinates. Find two
pointswith least distance between them.
这是topcoder tutorial: Line Sweeping第一个例题。
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=
=> 多谢了，看到你的帖子才想起来 编程之美 上也有:)
6. {1，5， -5， -8，2， -1，15 } 要把负的扫到左边，正的扫到后边。不能改变
顺序得到{-5 -8 -1 1 5 2 15} 这个题有time 低于 n^2 space=O（1）的解法吗
这个刚讨论过：
http://www.mitbbs.com/article_t/JobHunting/31928077.html
http://stackoverflow.com/questions/5347616/how-to-sort-an-integ
【在 g**********y 的大作中提到】
: 1. 你有一种语言的dictionary,你有一大串string,没有delimit,你如何interpret成字
: 典中的字呢？
: http://www.mitbbs.com/article/JobHunting/31488093_3.html
: 这个刚讨论过，就是把一个句子分拆成单词，既可以用Trie, 也可以DP。去search
: ihasleetcode的帖子。
: 2. 给你一个字典array of strings (you may preprocess it if necessary)
: 任意一个单词，求最小的edit distance
: 一个单位的distance定义为:
: a. replace a letter
: b. delete a letter
|
h**********8
发帖数: 267 | 44 mark
【在 m**q 的大作中提到】
: 从mitbbs59整理的题目列表中看到的，没什么思路大部分也找不到原来的链接了，大牛
: 们帮忙说说思路？先谢了
: 1. 你有一种语言的dictionary,你有一大串string,没有delimit,你如何interpret成字
: 典中的字呢？
: http://www.mitbbs.com/article/JobHunting/31488093_3.html
: 2. 给你一个字典array of strings (you may preprocess it if necessary)
: 任意一个单词，求最小的edit distance
: 一个单位的distance定义为:
: a. replace a letter
: b. delete a letter
|
w********s
发帖数: 11 | 45 第3题有点奇怪，如果所有的nuts对所有的bolts都是大（无法定量比较大多少），则没
法排序呀。
类似的只见过n个nuts和n个对应的bolts的，每一对规格大小不同。这种情况可以就用
quick sort的思路，先用一个nut做pivot对bolts做一轮quick sort，找到配对的bolt
后，用这个bolt再对nuts做一轮quick sort...... 相当于两个数组交错进行quick
sort。
【在 m**q 的大作中提到】
:
: 1. 你有一种语言的dictionary,你有一大串string,没有delimit,你如何interpret成字
: 典中的字呢？
: http://www.mitbbs.com/article/JobHunting/31488093_3.html
: 这个刚讨论过，就是把一个句子分拆成单词，既可以用Trie, 也可以DP。去search
: ihasleetcode的帖子。
: => 收到，多谢啦
: 应该是trie + backtracking 或者 trie + DP吧
: 2. 给你一个字典array of strings (you may preprocess it if necessary)
: 任意一个单词，求最小的edit distance
|
P**********c
发帖数: 3417 | 46 恩，你这个感觉比较象个完整的题目。
bolt
【在 w********s 的大作中提到】
: 第3题有点奇怪，如果所有的nuts对所有的bolts都是大（无法定量比较大多少），则没
: 法排序呀。
: 类似的只见过n个nuts和n个对应的bolts的，每一对规格大小不同。这种情况可以就用
: quick sort的思路，先用一个nut做pivot对bolts做一轮quick sort，找到配对的bolt
: 后，用这个bolt再对nuts做一轮quick sort...... 相当于两个数组交错进行quick
: sort。
|
g*****i
发帖数: 2162 | 47 第五题line sweeping里面说"This range can be extracted from the sorted set in
O(log N) time". 这是不是代表java里面TreeSet.subSet()能在O(log N)实现?具体是
如何实现的你知道吗? 谢谢
【在 g**********y 的大作中提到】
: 1. 你有一种语言的dictionary,你有一大串string,没有delimit,你如何interpret成字
: 典中的字呢？
: http://www.mitbbs.com/article/JobHunting/31488093_3.html
: 这个刚讨论过，就是把一个句子分拆成单词，既可以用Trie, 也可以DP。去search
: ihasleetcode的帖子。
: 2. 给你一个字典array of strings (you may preprocess it if necessary)
: 任意一个单词，求最小的edit distance
: 一个单位的distance定义为:
: a. replace a letter
: b. delete a letter
|
g**********y
发帖数: 14569 | 48 对sorted set，logN找左右边界，然后把这个range的数取出来。
TreeSet的实现，你可以去读Java source code. 是通过TreeMap来实现的，API里写的：
“A Red-Black tree based NavigableMap implementation. The map is sorted according to the natural ordering of its keys, or by a Comparator provided at map creation time, depending on which constructor is used.
This implementation provides guaranteed log(n) time cost for the containsKey, get, put and remove operations. Algorithms are adaptations of those in Cormen, Leiserson, and Rivest's Introduction to Algorithms. ”
in
【在 g*****i 的大作中提到】
: 第五题line sweeping里面说"This range can be extracted from the sorted set in
: O(log N) time". 这是不是代表java里面TreeSet.subSet()能在O(log N)实现?具体是
: 如何实现的你知道吗? 谢谢
|
g*****i
发帖数: 2162 | 49 假设这个range里有K个entry,那复杂度是不是O(logN+k)?
的：
according to the natural ordering of its keys, or by a Comparator provided
at map creation time, depending on which constructor is used.
containsKey, get, put and remove operations. Algorithms are adaptations of
those in Cormen, Leiserson, and Rivest's Introduction to Algorithms. ”
【在 g**********y 的大作中提到】
: 对sorted set，logN找左右边界，然后把这个range的数取出来。
: TreeSet的实现，你可以去读Java source code. 是通过TreeMap来实现的，API里写的：
: “A Red-Black tree based NavigableMap implementation. The map is sorted according to the natural ordering of its keys, or by a Comparator provided at map creation time, depending on which constructor is used.
: This implementation provides guaranteed log(n) time cost for the containsKey, get, put and remove operations. Algorithms are adaptations of those in Cormen, Leiserson, and Rivest's Introduction to Algorithms. ”
:
: in
|
m****t
发帖数: 555 | 50 5. Given N points in a place with their (x,y) co-ordinates. Find two points
with least distance between them.
这题可以用分而治之的方法来达到O(nlogn),但这还不是最好的算法．可以用
randomized algorithm 达到 O(n). 详见 Algorithm Design 这本书。 |
|
|
m**q
发帖数: 189 | 51 O(nlgn)的code好像是挺麻烦的
想了想可以用一个multi-map，key是y坐标，val是x坐标，因为
有可能两个点y坐标相同，所以不能用普通的set或者map。
比较麻烦的代码是查找map内 [y-h,y+h]区间内的点，这个好像
map没有现成的操作。或者不用map自己写一个BST来处理..
【在 g**********y 的大作中提到】
: 真正O(nlogn)的代码写起来太复杂，要是谁有可以贴。我就写了个简单的，觉得够
: interview用了。
: public class NearestPair {
: public double minDistance(int[][] p) {
: double min = Double.MAX_VALUE;
: int N = p.length;
: ArrayList points = new ArrayList();
:
: for (int i=0; i: Collections.sort(points, new Comparator() {
|
k*j
发帖数: 153 | 52 第一题没能找到1hasleetcode的帖子，麻烦火鸡同学给个链接吧。多谢！
【在 g**********y 的大作中提到】
: 1. 你有一种语言的dictionary,你有一大串string,没有delimit,你如何interpret成字
: 典中的字呢？
: http://www.mitbbs.com/article/JobHunting/31488093_3.html
: 这个刚讨论过，就是把一个句子分拆成单词，既可以用Trie, 也可以DP。去search
: ihasleetcode的帖子。
: 2. 给你一个字典array of strings (you may preprocess it if necessary)
: 任意一个单词，求最小的edit distance
: 一个单位的distance定义为:
: a. replace a letter
: b. delete a letter
|
k*j
发帖数: 153 | 53 我觉得这题难点就在如何维护一个BST，使得insert,delete，search都是lg(n)。只能
用BST。有同学写出来了吗？
【在 m**q 的大作中提到】
: O(nlgn)的code好像是挺麻烦的
: 想了想可以用一个multi-map，key是y坐标，val是x坐标，因为
: 有可能两个点y坐标相同，所以不能用普通的set或者map。
: 比较麻烦的代码是查找map内 [y-h,y+h]区间内的点，这个好像
: map没有现成的操作。或者不用map自己写一个BST来处理..
|
y******n
发帖数: 47 | 54 Algorithm design manual里面的题目是这样的:
Problem: The nuts and bolts problem is defined as follows. You are given a
collection
of n bolts of different widths, and n corresponding nuts. You can test
whether a
given nut and bolt fit together, from which you learn whether the nut is too
large,
too small, or an exact match for the bolt. The differences in size between
pairs of
nuts or bolts are too small to see by eye, so you cannot compare the sizes
of two
nuts or two bolts directly. You are to match each bolt to each nut.
bolt
【在 w********s 的大作中提到】
: 第3题有点奇怪，如果所有的nuts对所有的bolts都是大（无法定量比较大多少），则没
: 法排序呀。
: 类似的只见过n个nuts和n个对应的bolts的，每一对规格大小不同。这种情况可以就用
: quick sort的思路，先用一个nut做pivot对bolts做一轮quick sort，找到配对的bolt
: 后，用这个bolt再对nuts做一轮quick sort...... 相当于两个数组交错进行quick
: sort。
|
m****t
发帖数: 555 | 55
too
这题就是CLRS一书的习题8-4
【在 y******n 的大作中提到】
: Algorithm design manual里面的题目是这样的:
: Problem: The nuts and bolts problem is defined as follows. You are given a
: collection
: of n bolts of different widths, and n corresponding nuts. You can test
: whether a
: given nut and bolt fit together, from which you learn whether the nut is too
: large,
: too small, or an exact match for the bolt. The differences in size between
: pairs of
: nuts or bolts are too small to see by eye, so you cannot compare the sizes
|
m**q
发帖数: 189 | 56 翻了一下algorithm design的对应章节，好像还是挺复杂的
points
【在 m****t 的大作中提到】
: 5. Given N points in a place with their (x,y) co-ordinates. Find two points
: with least distance between them.
: 这题可以用分而治之的方法来达到O(nlogn),但这还不是最好的算法．可以用
: randomized algorithm 达到 O(n). 详见 Algorithm Design 这本书。
|
m**q
发帖数: 189 | 57 第5题我看编程之美/算法导论上有用分治的方法的，也是O(nlgn），
主要是合并子问题的时候要达到O(n)比较麻烦，需要把两个子问题
按y轴排序的结果合并，还有在合并前的结果中要找到与x轴划分点
水平距离h以内的元素序列，实现起来感觉比sweeping line还要复杂些
【在 g**********y 的大作中提到】
: 1. 你有一种语言的dictionary,你有一大串string,没有delimit,你如何interpret成字
: 典中的字呢？
: http://www.mitbbs.com/article/JobHunting/31488093_3.html
: 这个刚讨论过，就是把一个句子分拆成单词，既可以用Trie, 也可以DP。去search
: ihasleetcode的帖子。
: 2. 给你一个字典array of strings (you may preprocess it if necessary)
: 任意一个单词，求最小的edit distance
: 一个单位的distance定义为:
: a. replace a letter
: b. delete a letter
|
m**q
发帖数: 189 | 58 还是对STL不熟，multimap的话用lower_bound和upper_bound就够了，
找y坐标在lower_bound(y-h)和upper_bound(y+h)之间的点
或者用一个set，元素是pair，自动按先y坐标后x坐标排序，
然后还是用lower_bound+upper_bound.
【在 m**q 的大作中提到】
: O(nlgn)的code好像是挺麻烦的
: 想了想可以用一个multi-map，key是y坐标，val是x坐标，因为
: 有可能两个点y坐标相同，所以不能用普通的set或者map。
: 比较麻烦的代码是查找map内 [y-h,y+h]区间内的点，这个好像
: map没有现成的操作。或者不用map自己写一个BST来处理..
|
m**q
发帖数: 189 | 59 同样，当检查一个新的点时，需要把x-h之前的点从map中去掉,
其实可以用一个map存[x-h,x]中的点，key是y坐标。在向map中
添加一个新的点时，先检查map里是否有y坐标相同的点，有则删除；
同时把x-h之前的点依据它们的y坐标，把它们从map中删除。
总复杂度不超过O(nlgn)。
#include
#include |
s****j
发帖数: 67 | 60 平面最近点对那题，提供一种方法供参考，该方法看似复杂度o(n^2)，但实际使用中几
乎是o(n)（不算nlgn排序的预处理）。主要是利用了三角形两边之差小于第三边的性质
，大大减枝。另外该方法实现简单，比传统o(nlgn)的实现简单很多也直观很多。
代码如下：
#include
#include
#include
#include
#include
using namespace std;
const int maxn=100005;
const double eps=1e-8;
struct Point
{
double x,y,dis;
} p[maxn];
int n;
bool cmpp(const Point &p1,const Point &p2)
{
return p1.dis
}
void solve()
{
sort(p,p+n,cmpp);
double ans=1e18,now;
int i,j;
for (i=0;i
for (j=i+1;j
{
if (p[j].dis-p[i].dis>ans-eps) break; //这里会减枝很多
now=sqrt((p[i].x-p[j].x)*(p[i].x-p[j].x)+(p[i].y-p[j].y)*(p[i].y-p[j].y)
)/2;
if (now+eps
}
printf("%.2lf\n",ans);
}
int main()
{
while (cin>>n&&n)
{
memset(p,0,sizeof(p));
for (int i=0;i
{
scanf("%lf %lf",&p[i].x,&p[i].y);
p[i].dis=sqrt(p[i].x*p[i].x+p[i].y*p[i].y);
}
solve();
}
return 0;
}
有兴趣的可以去http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2107上面测试不同复杂度的运行时间。
【在 m**q 的大作中提到】
: 从mitbbs59整理的题目列表中看到的，没什么思路大部分也找不到原来的链接了，大牛
: 们帮忙说说思路？先谢了
: 1. 你有一种语言的dictionary,你有一大串string,没有delimit,你如何interpret成字
: 典中的字呢？
: http://www.mitbbs.com/article/JobHunting/31488093_3.html
: 2. 给你一个字典array of strings (you may preprocess it if necessary)
: 任意一个单词，求最小的edit distance
: 一个单位的distance定义为:
: a. replace a letter
: b. delete a letter
|
|
|
m**q
发帖数: 189 | 61 赞！ 这个思路不错
【在 s****j 的大作中提到】
: 平面最近点对那题，提供一种方法供参考，该方法看似复杂度o(n^2)，但实际使用中几
: 乎是o(n)（不算nlgn排序的预处理）。主要是利用了三角形两边之差小于第三边的性质
: ，大大减枝。另外该方法实现简单，比传统o(nlgn)的实现简单很多也直观很多。
: 代码如下：
: #include
: #include
: #include
: #include
: #include
: using namespace std;
|
