i**********e
发帖数: 1145 | 1 Looks like an interesting problem. I coded a C++ solution using BFS here. The distance between words (Levenshtein distance) is calculated using DP. Anyone who's interested can take a look here:
http://www.ideone.com/enbHZ
The main idea is using BFS (with the help of a queue) to search for the
shortest length ladder word sequence.
Some notes about the code:
- The transformed word (the final word that you want to transform to) must
be in the dictionary.
- "Your code must determine the shortest wor... 阅读全帖 |
|
P**********c
发帖数: 3417 | 2 http://www.ihas1337code.com/page/2
A Distance Maximizing problem
后面那个O(n)解法。找出valid的starting points之后，后面怎么又要shortest
starting point了呢。如果要shortest，至少也要把valid的starting points弄个排序
或者heap什么的吧。就不是O(n)了啊。 |
|
s******e
发帖数: 108 | 3 Given a matrix, each element is either s(start), a(availbe), b(block).
There are many s in the matrix,
compute the shortest path of each a(availbe) element.
distance from s or a to ajacent element is 1。
from s or a to b（block) is +ulimited.
compute the shortest distance from a(available) element to all s (start)
node
for exmaple.
s a a a s
the result would be
0 1 2 1 0
for
s b s b s
a b a b a
a b a b a
a a a a a
the result would be
0 + 0 + 0
1 + 1 + 1
2 + 2 + 2
3 4 3 4 3 |
|
S**I
发帖数: 15689 | 4 ☆─────────────────────────────────────☆
sharc (sharc) 于 (Mon Aug 22 15:15:14 2011, 美东) 提到:
刚从G家onsite归来。新鲜面经奉上。
总共5轮，4轮technical interview, 一个thesis discussion。在technical里，有编
程题，有open design。我记得的问题有：
1. 编程题：一堆字符串。找longest common prefix。
我的方法就是找最短的字符串，对它的每个字符，逐个与其他字符串对应位置比较。（
求更好方法）
2. open question: 一堆文件，size差别极大( from KB to many GB). 找出所有内
容相同的文件。
3. 编程题： 有一个observer 类，监视另一个类foo 的成员变量的值，每当那个值被
修改，就要调用 该observer.updated() 方法。需要实现 foo.registerObserver(ob)
, foo.unregisterObserver( ob )... 阅读全帖 |
|
c***g
发帖数: 472 | 5 Given a word (assume every char is unique in this word) and a string, find
the length of the shortest snippet/substring that contains all characters of
the word. For example: with word "abc" and the string "a brilliant cat is
eating a big cake", the shortest snippet is"big ca", which has length 6.
我能想到的是，用两个index，keep 一个window，然后滑动，每当找到一个substring
满足后，后面的index就滑到下一个可能的字母那里去。
请问谁有更好的方法么？ |
|
l*********8
发帖数: 4642 | 6 1. BST Optimal Binary Search Tree Problem
2. COV Optimal Covering problem
3. ILP integer linear programming
4. KS Knapsack Problem
5. LCS Longest Common Subsequences
6. LSP Longest Simple path Problem
7. MCM Matrix chain multiplication
8. ODP Optimal Distribution Problem
9. SCP Stagecoach Problem
10. SPA Shortest Path in a Acyclic graph
11. SPC Shortest Path in a Cyclic graph
12. TSP Travelling salesman problem |
|
|
M******l
发帖数: 479 | 8 You are given a graph and an algorithm that can find the shortest path b/w
any two nodes
Now you have to find the second shortest path between same two nodes.
这个题怎么算呢？是说找出第一个点和其他所有点的最短距离，然后再合并其他所有点
和第二个点的最短距离，最后在里面找出第二小的？这样一共要call getShortestPath
() 2*(n-1)次。有没有更快的方法呢？
谢谢！ |
|
Y**Y
发帖数: 66 | 9 删node肯定不行，因为第二条完全可以包括第一天条的所有节点。简单的例子就是三角
形，三边相同。去edge也有问题，因为第二条可以包括所有的边，比如中间某点多走一
个weight很小的圈也可以是第二条
这题条件不清楚，比如
second shortest path可不可以和shortest path长度相同？
有没negative edge? 如果有的话，就很麻烦，因为第二条可以和第一条经过的节点完
全相同，只是顺序不同。 |
|
f*******t
发帖数: 7549 | 10 dijkstra变形一下，每次update shortest和second shortest |
|
c*****g
发帖数: 33 | 11 网上看到一道题 求O(n)的解法. n是document中的word数
You have a dictionary, D, that stores the positions of words in a document
by mapping words (strings) to positions in the document (arrays of ints.)
You also have a list of words, L. Your job is to find the shortest sequence
of words in the document that contains all the words in L.
E.g., if the document is "a b a c d x b a", then
D["a"] = [0 2 7]
D["b"] = [1 6]
...
If we are given that L=["a", "c", "x"]
Then we should return the start and end point of the sho... 阅读全帖 |
|
w***y
发帖数: 6251 | 12 去年面试被问到的hehe 一直不知道到底该怎么做
题目是 Write code to compute the shortest unique prefix of each word in a
set of words.
给的例子是：
譬如如果apple, bee, cat这三个词， 那找到的shortest unique prefix 就是｛a/b/c
｝; 如果是apple bee cat cedar, 就需要 {a/b/ca/ ce} |
|
h*****a
发帖数: 1718 | 13 No, certainly linear is not always the most efficient one. When this
algorithm is applied to the practical problem for merging reverse indexes of
search results, I guess it probably start from the shortest list and use
binary search in practice, at least for most cases when the length of the
shortest list is below some threshold. |
|
I**********s
发帖数: 441 | 14 这些是我以前做研究时一个项目涉及到的常见的DP问题. 我为了资料全面起见加上了,
但多数不会见于面试.
BST Optimal Binary Search Tree Problem
COV Optimal Covering Problem
ILP Integer Linear Programming Problem
KS01 0/1 Knapsack Problem
LCS Longest Common Subsequence Problem
LSP Longest Simple Path Problem
MCM Matrix Chain Multiplication Problem
ODP Optimal Distribution Problem
RAP Production: Reject Allowances Problem
SCP Stagecoach Problem
SPA Shortest Path in an Acyclic Graph Problem
SPC Shortest Path in an Cyclic Graph Problem
TSP Traveling S... 阅读全帖 |
|
j********r
发帖数: 25 | 15 题目：
Given two words (start and end), and a dictionary, find the length of
shortest transformation sequence from start to end, such that:
Only one letter can be changed at a time
Each intermediate word must exist in the dictionary
For example,
Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]
As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.
Note:
Return 0 if there is no such transformation sequence.
All words have the same len... 阅读全帖 |
|
A*********c
发帖数: 430 | 16 本来我是带着娱乐的态度来回帖的，但是既然碰到了大牛，请educate我。
请告诉我任意一个数据结构，比inverted list 更重要，并且广泛地应用到了实际的
text retrieval system中.
请告诉我任意一个document retrieval model，比vector space model 或者 Okapi
BM25, Statistically significantly better for general purpose document
retrieval. Either implemented in Lucene or Lemur.
请告诉我任意一个clustering algorithm，other than Kmeans，will be your safe
first choice of clustering when you see some arbitrary data.
对于Classification，Old Stuff Like KNN works well in many cases. Kernel
algorithms are go... 阅读全帖 |
|
A*********c
发帖数: 430 | 17 本来我是带着娱乐的态度来回帖的，但是既然碰到了大牛，请educate我。
请告诉我任意一个数据结构，比inverted list 更重要，并且广泛地应用到了实际的
text retrieval system中.
请告诉我任意一个document retrieval model，比vector space model 或者 Okapi
BM25, Statistically significantly better for general purpose document
retrieval. Either implemented in Lucene or Lemur.
请告诉我任意一个clustering algorithm，other than Kmeans，will be your safe
first choice of clustering when you see some arbitrary data.
对于Classification，Old Stuff Like KNN works well in many cases. Kernel
algorithms are go... 阅读全帖 |
|
l*********3
发帖数: 26 | 18
这道题不是NP-HARD的。
暴力法：建一个shortest path map。可以用Dijskstra算法。然后对每个点计算其到每
个器材所在点的距离。找最小值。
暴力法时间复杂度：shortest path map: n个点，每个O(nlog n)，总共O(n^2log n)。 |
|
l*****a
发帖数: 14598 | 19 sort by height
for the 1st shortest ,base on TValue, put it in the right place
then for the 2nd shortest,based on Tvalue and position of the first one,put
it in the right place
... |
|
r*******7
发帖数: 11 | 20 如果这个dis是shortest path distance的话，就先算all pair shortest path，然后
到其他所有点最短距离和最小的店。
如果只是要求联通其他点，这个dis可以不一定是最短距离的话，那第三题就变成
steiner tree problem。所以估计assumption是第一种情况
k, |
|
f**********e
发帖数: 288 | 21 given a dictionary and a license plate. find a shortest word that contains
all the characters of the license.
for instance, license st908i, the shortest word is "sit". |
|
o*q
发帖数: 630 | 22 Google
Show problem tags Hide locked problems
#
Title
Acceptance
Difficulty
Frequency
66 Plus One 35.4% Easy
146 LRU Cache 15.8% Hard
200 Number of Islands 29.7% Medium
288 Unique Word Abbreviation 15.7% Easy
163 Missing Ranges 30.3% Medium
56 Merge Intervals 26.7% Hard
228 Summary Ranges 26.0% Medium
308 Range Sum Query 2D - Mutable 20.8% Hard
279 Perfect Squares 34.1% Medium
388 L... 阅读全帖 |
|
h***b
发帖数: 1233 | 23 T-Bill has the shortest maturity < 1 yr, indicates the shortest term int
trend. a short term borrowing instrument.
T-Note--for intermediate term. < 10 yr maturity
T-Bond--long term w/ longest maturity. 15, 30 yrs...
T-Bill/Note/Bond are all US gov't debts w/ short/medium/long term maturities
. btw, "T" stands for (US) Treasury :p
欢迎访问＂言之有屋＂Irvine Mortgage & RE 俱乐部和我的博客
http://www.mitbbs.com/club_bbsdoc/charles.html
http://www.mitbbs.com/pc/index/hkmbb |
|
s***g
发帖数: 495 | 24 Just did a hair cut a few days ago. Here is my way to share.
1. Use No.1 (shortest clip) go vertically, then No.2 (second shortest) to
round up.
2. Do it on saw horse at backyard and cover with a piece of painter's
plastic. No need to clean.
了! |
|
a*******e
发帖数: 12169 | 25 选fastest就不是小路了，shortest会是小路。。。有一次开车要经过Baltimal，结果
之前GPS设定的是shortest，结果带我去downtown转了一圈，回来我换成fastest，就走
绕城高速了。 |
|
i***y
发帖数: 285 | 26 【 以下文字转载自 TAX 讨论区 】
发信人: iLucy (iLucy), 信区: TAX
标 题: My Mom stay here for 183 days, Can she count for my dependent? What is the shortest duration?
发信站: BBS 未名空间站 (Tue Sep 1 00:06:38 2009, 美东)
My Mom stay here for 183 days, Can she count for my dependent? What is the
shortest duration for her to be a dependent of mine?
I heard that if I add her as dependent, i can have $13,000 tax deduction. Is
that true? |
|
A*f
发帖数: 3067 | 27 (all yardage from Blue tee)
#1, the easiest opening hole, 331 par4, wide open fairway, Other than first
hole jitter, not much to worry. Drive as far as you can, if you are not
afraid of half/three-quater wedge shot. Otherwise, leave yourself 100 for
approaching.
#2, downhill 147 par3, straight forward, pick the right club for your
distance, the hole played as 5-10 yards short (due to the downhill) depends
on the wind.
#3, 362 par4, avoid right hand side, approaching the green from left side of
f... 阅读全帖 |
|
g*z
发帖数: 3227 | 28 zz
公开水域游泳技巧
In my many years in this sport, I have never seen any reasonably
complete article in the magazines dealing with open water swimming (they
seem to rehash the same basic stuff every few years). A lot of them talk
about how to draft, or tell you to look up every few strokes to stay on
course, but very few seem to deal with the subject in much detail.
在我多年的运动生涯中，我从未在任何杂志中看到过合理的、完整的对付公开水域
游泳的文章（他们似乎只是每几年训练一些新手）。很多文章只是谈一些如何跟随游，
或者告诉你几个动作后向上看，以保持航线，但是没有多少文章对这个话题说的足够详
细。
So last summer, I st... 阅读全帖 |
|
a*****s
发帖数: 838 | 29 since nobody answered it and i had done a little bit of reading about it, so
here is what i have found.
spinet is the smallest version of piano, uses a different type of mechanism
to generate the sounds compared to regular upright / grand piano. it was lar
gely made since 1930 upto recent emergence of electric piano. basically the
eletric piano elbows out the spinet piano due to its cost and convenience, w
hich were pretty much the reason why spinet was invented back in those days,
because it al... 阅读全帖 |
|
H********g
发帖数: 43926 | 30 10e-18 埃托秒
1 attosecond: the time it takes for light to travel the length of three
hydrogen atoms
12 attoseconds: record for shortest time interval measured as of 12 May 2010
[5]
24 attoseconds: the atomic unit of time
67 attoseconds: the shortest pulses of laser light yet created[6]原来现在有
这么短的脉冲啊
100 attoseconds: fastest ever view of molecular motion[7]
200 attoseconds (approximately): half-life of beryllium-8, maximum time
available for the triple-alpha process for the synthesis of carbon and
h... 阅读全帖 |
|
w*******g
发帖数: 9932 | 31 since the shortest path is already computed, you may assume that you know
the weight and the edge count of the shortest path between any two vertices. |
|
w*******g
发帖数: 9932 | 32 actually, that was not needed. Since this is a single-source shortest path
problem, you only assume the existing of the shortest path between the source
and other nodes. |
|
c******m
发帖数: 98 | 33 There is some algorithm can transform graph with negative edge to non-negative
graph, within O(E) time, while keep the shortest path, given the shortest path
solution
You can refer to section 5.5 in
http://www.cs.wisc.edu/wpis/abstracts/jalg96.abs.html
But the Dijkstra still needs O(E+VlogV) |
|
w*******g
发帖数: 9932 | 34
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
yeah, let's call this node u' where k(u') = i > 3 and
if (u', u) is an edge, then at ith iteration, we update the shortest path
to u based on the new path to u'.
The point is that the shortest path to a node u is finalized when we reach
ith iteration where i = k(u).
At this point, we can use this result to update the neighbors of u. |
|
v****s
发帖数: 1112 | 35 谢谢各位！这是create table statement, 请帮忙看看如何提高select 的速度。
我只用这个语句：
select * from shortest where ((p1=x and p2=y) or (p1=y and p2=y))
delimiter $$
CREATE TABLE `shortest` (
`id` int(10) unsigned NOT NULL AUTO_INCREMENT,
`p1` varchar(45) CHARACTER SET latin1 COLLATE latin1_bin NOT NULL DEFAULT
'',
`p2` varchar(45) CHARACTER SET latin1 COLLATE latin1_bin NOT NULL DEFAULT
'',
`dist` varchar(45) CHARACTER SET latin1 COLLATE latin1_bin NOT NULL
DEFAULT '',
PRIMARY KEY (`id`),
KEY `p1p2` (`p1`,`p... 阅读全帖 |
|
v****s
发帖数: 1112 | 36 I tried this query:
explain select count(*) from shortest where (p1=300 and p2=301);
and here is the result:
id select_type table type possible_keys key key_len ref
rows Extra
1 SIMPLE shortest ALL p1,p2 NULL NULL NULL 4296656
Using where |
|
v****s
发帖数: 1112 | 37 explain select count(*) from shortest;
这个好像用到了index,结果里面写了。。。用了p1
id select_type table type possible_keys key key_len ref
rows Extra
1, SIMPLE, shortest, index, , p1, 47, , 4296656, Using index |
|
z**r
发帖数: 17771 | 38 2 scenarios:
1. the RP is not on the shortest path. the upstream router will use a
different interface as the RPF check, and send a prune message to the RP
removing itself from the source tree. so on RP, the interface facing this
upstream router will be removed from the OIL. So your understanding is right.
2. the RP is on the shortest path, (s, g) will not be pruned after switching
over to SPT. of coz this depends on the spt-threshold, if the threshold is
set to infinity, the router will not eve |
|
f********r
发帖数: 50 | 39 post some analysis from topcoder
A key observation is that, to make the shortest possible palindrome out of
base, you should never add letters to both the front and back of the string.
If you were to do so, then you could make an even shorter palindrome by
removing the first and last characters that you added. Therefore, the
shortest palindrome that you can make out of base must either start with the
first letter of base or end with the last letter of base (or both, if the
first and last letters |
|
s***t
发帖数: 113 | 40 Just use standard shortest path algorithm.
any edge incident to point that has killer monster has cost = +inf
points has dragon has cost = 1000.
Look for a shortest path from (0,0) to (n-1,n-1).
1
.
squares
[n
squares
dragons. |
|
|
n*****n
发帖数: 100 | 42 在Stochastic Shortest Path Problem中, 其转换概率在control action U 下从状态S
_i 到 S_j, P(S_i,U,S_j)一般来说是事先确定的,在整个计算过程不变.但是如果每到
一个状况后,由于新的信息到达,P(S_i,U,S_j)会被更新.在这种情况下,有没有现成的算
法?有人给我讲,这是imperfect information Stochastic Shortest Path Problem, 不
知道是不是对的? |
|
o****o
发帖数: 8077 | 43 in real application, you have to consider efficiency, flexibility,
expandibility, readibility....
the shortest code is not always the best code, even though I sometimes
prefer the shortest code |
|
j*****n
发帖数: 943 | 44 【 以下文字转载自 Swimming 讨论区 】
发信人: gxz (大狗熊), 信区: Swimming
标 题: zz公开水域游泳技巧
发信站: BBS 未名空间站 (Mon Jul 18 14:44:51 2011, 美东)
zz
公开水域游泳技巧
In my many years in this sport, I have never seen any reasonably
complete article in the magazines dealing with open water swimming (they
seem to rehash the same basic stuff every few years). A lot of them talk
about how to draft, or tell you to look up every few strokes to stay on
course, but very few seem to deal with the subject in much detail.
在我多年的运动生涯中，我从未在任何杂志中看... 阅读全帖 |
|
l****g
发帖数: 761 | 45 我也负责我们组ML面试, 我对你的出题很难苟同
你出的这些题背得怎么熟，如果我要solve一个 PB level data problem, 怎么用?
所以我就不拍了，以前有个贴总结的挺好我就直接贴过来吧:
发信人: Algorithmic (Zeal), 信区: JobHunting
标 题: Re: 为什么你么都说现在招聘走做题路线
发信站: BBS 未名空间站 (Mon Dec 23 17:31:14 2013, 美东)
本来我是带着娱乐的态度来回帖的，但是既然碰到了大牛，请educate我。
请告诉我任意一个数据结构，比inverted list 更重要，并且广泛地应用到了实际的
text retrieval system中.
请告诉我任意一个document retrieval model，比vector space model 或者 Okapi
BM25, Statistically significantly better for general purpose document
retrieval. Either implemented in Lucene or Le... 阅读全帖 |
|
l****g
发帖数: 761 | 46 我也负责我们组ML面试, 我对你的出题很难苟同
你出的这些题背得怎么熟，如果我要solve一个 PB level data problem, 怎么用?
所以我就不拍了，以前有个贴总结的挺好我就直接贴过来吧:
发信人: Algorithmic (Zeal), 信区: JobHunting
标 题: Re: 为什么你么都说现在招聘走做题路线
发信站: BBS 未名空间站 (Mon Dec 23 17:31:14 2013, 美东)
本来我是带着娱乐的态度来回帖的，但是既然碰到了大牛，请educate我。
请告诉我任意一个数据结构，比inverted list 更重要，并且广泛地应用到了实际的
text retrieval system中.
请告诉我任意一个document retrieval model，比vector space model 或者 Okapi
BM25, Statistically significantly better for general purpose document
retrieval. Either implemented in Lucene or Le... 阅读全帖 |
|
j*****n
发帖数: 943 | 47 熊大转的一篇，感觉很有道理，俺再转。
【 以下文字转载自 Swimming 讨论区 】
发信人: gxz (大狗熊), 信区: Swimming
标 题: zz公开水域游泳技巧
发信站: BBS 未名空间站 (Mon Jul 18 14:44:51 2011, 美东)
zz
公开水域游泳技巧
In my many years in this sport, I have never seen any reasonably
complete article in the magazines dealing with open water swimming (they
seem to rehash the same basic stuff every few years). A lot of them talk
about how to draft, or tell you to look up every few strokes to stay on
course, but very few seem to deal with the subject in much detail.
在我... 阅读全帖 |
|
m******l
发帖数: 2472 | 48 haha
有一次我去娃班上帮忙，有好几个白人妈妈。
完了，女儿对我说：you are the shortest mom in my class!
我很愤怒：谁让其他中国妈妈不来？
后来，女儿安慰我说，it's ok, I am the shortest in my class too!
我更无语了。
our |
|
