由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 求助一面试题
相关主题
c/c++ qsort/sort 来 sort array of stringA challenging interview question: revert a string
我的面试题总结Google电面详细经历
发一个fb面经A家面试题
Riverbed 面经counting sort an array of objects怎么做
有向图判断有无环问个关于排序的面试题
小公司onsite面经(求bless)最近面试碰到的题目
如何判断一个图中是否有环?find k missing numbers in range [0, N].
F家电面:group Anagramsa电面面经
相关话题的讨论汇总
话题: char话题: string话题: mp话题: res话题: set
进入JobHunting版参与讨论
1 (共1页)
m***o
发帖数: 1738
1
大牛们给个思路,前段时间另一道题的逆转。
Given an string array sorted by characters in another string.
Return that sorting base string.
Example. give you
{foo, cat, cao, bag, bat, aac}
return: fcbagto
f***b
发帖数: 21
2
给字符串数组建图,然后求拓扑排序,返回排序结果即可
m***o
发帖数: 1738
3
谢谢大牛,再问一下这个题的 sample code。

【在 f***b 的大作中提到】
: 给字符串数组建图,然后求拓扑排序,返回排序结果即可
r****7
发帖数: 2282
4
首先这个结果不唯一,而且可能性很多,只能取一个
按位比较然后得到一个字符的有向图然后拓扑排序吧

【在 m***o 的大作中提到】
: 大牛们给个思路,前段时间另一道题的逆转。
: Given an string array sorted by characters in another string.
: Return that sorting base string.
: Example. give you
: {foo, cat, cao, bag, bat, aac}
: return: fcbagto

m*****k
发帖数: 731
f**********t
发帖数: 1001
6
// Given an string array sorted by characters in another string.
// Return that sorting base string.
// Example. give you
// {foo, cat, cao, bag, bat, aac}
// return: fcbagto
void buildGraph(vector &vs, unsigned col, unsigned up, unsigned down,
map> &res) {
char pre = '#';
unsigned count = 0;
unsigned uu = up;
for (unsigned i = up; i < down; ++i) {
if (vs[i].size() <= col) {
break;
}
if (vs[i][col] == pre) {
++count;
} else {
if (count > 1) {
buildGraph(vs, col + 1, uu, i, res);
}
if (pre != '#') {
res[pre].insert(vs[i][col]);
}
pre = vs[i][col];
count = 1;
uu = i;
}
}
if (count > 1) {
buildGraph(vs, col + 1, uu, down, res);
}
}
map> revert(const map> &mp) {
map> res;
for (auto item : mp) {
for (char c : item.second) {
res[c].insert(item.first);
}
if (res.find(item.first) == res.end()) {
res[item.first] = set();
}
}
return res;
}
void topoErase(map> &mp, map> &re,
char c, vector &res) {
res.push_back(c);
re.erase(re.find(c));
for (char child : mp[c]) {
re[child].erase(c);
if (re[child].empty()) {
topoErase(mp, re, child, res);
}
}
mp.erase(mp.find(c));
}
string topoSort(map> &mp) {
map> re = revert(mp);
vector vc;
while (!re.empty()) {
for (auto item : re) {
if (item.second.empty()) {
topoErase(mp, re, item.first, vc);
break;
}
}
}
return string(vc.begin(), vc.end());
}
string charOrder(vector &vs) {
map> mp;
buildGraph(vs, 0, 0, vs.size(), mp);
return topoSort(mp);
}
1 (共1页)
进入JobHunting版参与讨论
相关主题
a电面面经有向图判断有无环
find index of an element in sorted array小公司onsite面经(求bless)
BB家面经如何判断一个图中是否有环?
请教suffix array的问题F家电面:group Anagrams
c/c++ qsort/sort 来 sort array of stringA challenging interview question: revert a string
我的面试题总结Google电面详细经历
发一个fb面经A家面试题
Riverbed 面经counting sort an array of objects怎么做
相关话题的讨论汇总
话题: char话题: string话题: mp话题: res话题: set