贡献F家Onsite一题 - JobHunting版

本页内容为未名空间相应帖子的节选和存档，一周内的贴子最多显示50字，超过一周显示500字访问原贴

JobHunting版 - 贡献F家Onsite一题

相关主题
● Facebook interview 面经	● leetcode一题没看明白
● Amazon Summer Intern Offer, 发面经	● leetcode上的一题。
● nlogn for longest increasing subsequence	● 如果找两个array的intersection的题也没做出来
● 面试问题，最长翻转整数问题	● 一朋友被Google的电面干掉了 (转载)
● fb电面第一轮	● 寻找子序列/子段落
● Bloomberg面试题	● Longest common string问题
● 问一个题，求相同元素最多的两个数组	● please DIscuss Two similar alg questions
● DP通项公式	● 请教道算法题

相关话题的讨论汇总
话题: int话题: table话题: maxbridge话题: dp话题: rev

进入JobHunting版参与讨论

(共1页)

s*****l
发帖数: 45

见过的题目就不说了，说个没见过的，基本是这题把俺放倒了，大牛们可以看看怎么做
。
河对岸有两排数量相等的城市。
a1 a2 a3 a4.....an
-------------------
-------------------
b1 b2 b3 b4.....bn
每个城市ai都有对应的友好城市bj. 比如(a1, b3), (a2, b1), (a3, b2)...
问题是如果姐妹城市之间可以互相建桥，但是这些桥之间不能交叉，给定这些姐妹城市
的mapping，最多可以建多少个桥？

s******y
发帖数: 416

什么叫给定mapping？
目测是图论问题。planer graphs。可能是结论直接用就可以了。

a*****u
发帖数: 1712

dp，跟longest common subsequence一个思路

z***c
发帖数: 78

这个要用贪婪算法吧，感觉和排时间表很像
先找出最靠左边的一组(Ai,Bj)，然后相同方法找下一组A[max(i,j)+1],B[max(i,j)+1]
至于怎么找到最左边的，目前想到的是可以按照max(Ai,Bj)排序

A***o
发帖数: 358

a_i 到 b_j是一一对应吗？
感觉好像是要把 a 按在 b 中的位置排序，然后找排序后a下标的最长递增序列

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

: 见过的题目就不说了，说个没见过的，基本是这题把俺放倒了，大牛们可以看看怎么做
: 。
: 河对岸有两排数量相等的城市。
: a1 a2 a3 a4.....an
: -------------------
: -------------------
: b1 b2 b3 b4.....bn
: 每个城市ai都有对应的友好城市bj. 比如(a1, b3), (a2, b1), (a3, b2)...
: 问题是如果姐妹城市之间可以互相建桥，但是这些桥之间不能交叉，给定这些姐妹城市
: 的mapping，最多可以建多少个桥？

s*****l
发帖数: 45

回楼上的，给定mapping就是说给定这些a和b的友好城市关系了。
ai到bj是一一对应的

s***5
发帖数: 2136

用greedy怎么样？先看所有pair都建桥的话，有多少个交叉。然后remove那个能最大限
度减少交叉次数的桥，重复此过程直到没有交叉为止。
不过不能保证就是最佳结果。
可能要用DP？不过不知怎么搞。

l****o
发帖数: 315

看到最大先想到dp
f[i,j] = max{f[i - 1, j], f[i, j - 1]} + 1 (if [i,j] has mapping)
还能降一维空间。
瞎想的，可能不对。

s***5
发帖数: 2136

实在看不出怎么一样法。

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

: dp，跟longest common subsequence一个思路

a*****u
发帖数: 1712

你这个跟我说的方法都是对的。

【在 A***o 的大作中提到】

: a_i 到 b_j是一一对应吗？
: 感觉好像是要把 a 按在 b 中的位置排序，然后找排序后a下标的最长递增序列

相关主题
● Bloomberg面试题	● leetcode一题没看明白
● 问一个题，求相同元素最多的两个数组	● leetcode上的一题。
● DP通项公式	● 如果找两个array的intersection的题也没做出来
进入JobHunting版参与讨论

a*****u
发帖数: 1712

longest common subsequence里的两char相等，对应这道题的两城市有mapping

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

: 实在看不出怎么一样法。

a*****u
发帖数: 1712

我刚刚说错了，是subsequence，不是substring

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

: 实在看不出怎么一样法。

c***d
发帖数: 26

哇这个解法妙。
如果推广到每个城市可以有多个友好城市，那似乎就只能dp了。

【在 A***o 的大作中提到】

: a_i 到 b_j是一一对应吗？
: 感觉好像是要把 a 按在 b 中的位置排序，然后找排序后a下标的最长递增序列

i*****o
发帖数: 105

非一一对应也行
这问题比较有意思

【在 A***o 的大作中提到】

: a_i 到 b_j是一一对应吗？
: 感觉好像是要把 a 按在 b 中的位置排序，然后找排序后a下标的最长递增序列

s***5
发帖数: 2136

这个很好理解，很不错。

【在 A***o 的大作中提到】

: a_i 到 b_j是一一对应吗？
: 感觉好像是要把 a 按在 b 中的位置排序，然后找排序后a下标的最长递增序列

z***c
发帖数: 78

排序方法好巧妙

r*****e
发帖数: 792

mit的那个dp讲解里有这道题，连桥和城市的说服都一样。

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

g***9
发帖数: 159

贴个DP的完整代码给大家讨论，测了几个case感觉是对的解法，简单原理：
假设a1,a2 ... an 和 b1,b2...bn 都在 1.. n之间，便于讨论
table[i][j] 表示了只包含从 a1..ai 到 b1..bj 作为桥端点的结果
rev 是逆向映射。
DP是假设了ai bj是一一对应，不知道有重复映射的话，怎么做比较好？
有么有人能贴个排序的代码？谢谢
#include
#include
#include
using namespace std;
int MaxBridge(map &bridge, int n) {
map rev;
for (auto b : bridge) {
rev[b.second] = b.first;
}
vector> table(n+1, vector(n+1));
int i, j, t, a;
for (j = 0; j <= n; j++) {
table[0][j] = 0;
}
for (i = 0; i <= n; i++) {
table[i][0] = 0;
}
for (i = 1; i <= n; i++) {
for (j = 1; j <= n; j++) {
a = table[i-1][j-1];
if (bridge.count(i)) {
t = bridge[i];
if (t <= j) {
a = std::max(a, table[i-1][t-1]+1);
}
}
if (rev.count(j)) {
t = rev[j];
if (t <= i) {
a = std::max(a, table[t-1][j-1]+1);
}
}
table[i][j] = a;
}
}
return table[n][n];
}
void Test() {
int n;
n = 6;
map m;
m[1] = 3;
m[2] = 1;
m[3] = 6;
m[4] = 2;
m[6] = 4;
cout << MaxBridge(m, n) << endl;

m.clear();
n = 5;
m[1] = 1;
m[2] = 2;
m[3] = 3;
m[4] = 4;
m[5] = 5;
cout << MaxBridge(m, n) << endl;

m.clear();
n = 5;
m[1] = 5;
m[5] = 1;
m[2] = 2;
cout << MaxBridge(m, n) << endl;
return;
}
int main() {
Test();
return 0;
}

n****r
发帖数: 120

假设输入为数组A[]，B[]为mapping，A数组升序排列，一一对应，直接对B数组求
longest increasing subsequence 就是答案了吧

s*******s
发帖数: 1031

http://people.csail.mit.edu/bdean/6.046/dp/
第5题。

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

相关主题
● 一朋友被Google的电面干掉了 (转载)	● please DIscuss Two similar alg questions
● 寻找子序列/子段落	● 请教道算法题
● Longest common string问题	● 新人刚刚开始认真找工作，问个简单的题（1）
进入JobHunting版参与讨论

r*********n
发帖数: 4553

http://people.csail.mit.edu/bdean/6.046/dp/
第五题原题

S*********d
发帖数: 16

如果是一一对应的这题直接用longest common subsequence 不对吗？

S*********d
发帖数: 16

如果是一一对应的这题直接用longest common subsequence 不对吗？

S*********d
发帖数: 16

http://courses.csail.mit.edu/6.006/fall10/handouts/dpproblems-s
这个的problem 8 用的LCS

h****g
发帖数: 105

这题和cc150 1.9是一样的吧？1.9上是说人有两个属性，体重和身高，然后人排队要求
前面的人的身高和体重都小于后面的，问最多的可排队的人数。

w***t
发帖数: 1474

跟我想的一样，其实就是一道题。

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

: 这题和cc150 1.9是一样的吧？1.9上是说人有两个属性，体重和身高，然后人排队要求
: 前面的人的身高和体重都小于后面的，问最多的可排队的人数。

c********p
发帖数: 1969

dp?

f******p
发帖数: 173

2 this, have the same idea

【在 n****r 的大作中提到】

: 假设输入为数组A[]，B[]为mapping，A数组升序排列，一一对应，直接对B数组求
: longest increasing subsequence 就是答案了吧

(共1页)

进入JobHunting版参与讨论

相关主题
● 请教道算法题	● fb电面第一轮
● 新人刚刚开始认真找工作，问个简单的题（1）	● Bloomberg面试题
● 问一下dynamic programming的常见问题	● 问一个题，求相同元素最多的两个数组
● longest common prefix 和 longest common substring	● DP通项公式
● Facebook interview 面经	● leetcode一题没看明白
● Amazon Summer Intern Offer, 发面经	● leetcode上的一题。
● nlogn for longest increasing subsequence	● 如果找两个array的intersection的题也没做出来
● 面试问题，最长翻转整数问题	● 一朋友被Google的电面干掉了 (转载)

相关话题的讨论汇总
话题: int话题: table话题: maxbridge话题: dp话题: rev

#	版面	帖数(主题数)
-	全站	4871 (796)
1	Military	3777 (569)
2	Stock	341 (51)
3	Joke	117 (17)
4	History	116 (3)
5	Automobile	100 (9)
6	USANews	55 (9)
7	Midlife	45 (1)
8	Headline	41 (41)
9	Dreamer	33 (13)
10	FleaMarket	32 (20)
11	Living	30 (7)

boards

未名新帖统计// 7月16日

历史上的今天