一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

一亩三分地官方iOS手机应用下载
查看: 3123|回复: 20
收起左侧

09/23 脸家两轮店面

[复制链接] |试试Instant~ |关注本帖
tjnkzll 发表于 2016-9-25 03:28:00 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 硕士 全职@Facebook - 内推 - 技术电面 |Otherfresh grad应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
今天加面的题,leetcode上没有,脑抽没写好,应该是跪了,就是把binary tree转换成doubly linked list。我看地里没提过这题,分享一下攒点rp吧
就是这题
http://www.geeksforgeeks.org/in- ... doubly-linked-list/


之前第一次面的是sort color的变形,写了two pointer的方法, 后来面试官要求写stable的sorting方法,感觉交流上不太顺畅,所以给了加面。
结果加面也没面好。。5555555

评分

1

查看全部评分

本帖被以下淘专辑推荐:

minggr 发表于 2016-10-10 12:02:16 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
mengmeng88717 发表于 2016-10-4 06:06
把快排改成稳定的,定义一个compare函数,先比较值,再比较index;或者直接merge sort,count sort不一定就 ...

活到老学到老,之前我写count sort也一直是写成unstable的
其实算法导论里面的实现就是stable的,但如果只是排序一些整数,非常容易忽略掉stable的写法. 1point 3acres 璁哄潧
为了更明显地说明问题,以下code是counting stable sort一个structure

输入:
2-老王  0-老张  1-老陈  2-老林  0-老谢  

输出:
0-老张  0-老谢  1-老陈  2-老王  2-老林
  1. struct color {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  2.     int key;
  3.     string name;
  4. };

  5. vector<color> stable_color_sort(vector<color> &colors)
  6. {
  7.     int n = (int)colors.size();
  8.     vector<color> sorted(n);.鐣欏璁哄潧-涓浜-涓夊垎鍦
  9.     vector<int> counts(3, 0);

  10.     for (color c: colors)
  11.         counts[c.key]++;

  12.     for (int i = 1; i < 3; i++)
  13.         counts[i] += counts[i-1];

  14.     for (int i = n - 1; i >= 0; i--) {
  15.         int key = colors[i].key;
  16.         int pos = --counts[key];

  17.         sorted[pos] = colors[i];
  18.     }

  19.     return sorted;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  20. }

  21. . 鍥磋鎴戜滑@1point 3 acres
  22. int main()
  23. { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  24.     vector<color> colors = {{2, "老王"}, {0, "老张"}, {1, "老陈"}, {2, "老林"}, {0, "老谢"}};. Waral 鍗氬鏈夋洿澶氭枃绔,
  25.     for (color c: colors)
  26.         cout << c.key << "-" << c.name << "  ";
  27.     cout << endl;

  28.     vector<color> sorted = stable_color_sort(colors);
  29.     for (color c: sorted)
  30.         cout << c.key << "-" << c.name << "  ";
  31.     cout << endl;

  32.     return 0;
  33. }
复制代码
回复 支持 1 反对 0

使用道具 举报

lyudison 发表于 2016-10-10 08:36:25 | 显示全部楼层
关注一亩三分地微博:
Warald
  1. struct Node {
  2.   Node* left, *right;. 1point 3acres 璁哄潧
  3.   int val;
  4.   Node(int value) {
  5.     val = value;
  6.     left = right = nullptr;
  7.   }
  8. };

  9. Node* convert_to_linked_list(Node* root) {
  10.   if (root == nullptr) return nullptr;
  11.   Node dummy;. 1point 3acres 璁哄潧
  12.   Node* pre = &dummy;
  13.   helper(root, pre);
  14.   dummy.right->left = nullptr;
  15.   return dummy.right;
  16. }

  17. void helper(Node* node, Node*& pre) {. more info on 1point3acres.com
  18.   if (!node) return;
  19.   helper(node->left, pre);
  20.   pre->right = node;
  21.   node->left = pre;
  22.   pre = node;
    . more info on 1point3acres.com
  23.   helper(node->right, pre);
  24. }
复制代码
回复 支持 1 反对 0

使用道具 举报

tigercode 发表于 2016-9-26 03:38:41 | 显示全部楼层
sort color要求stable,是说counting sort么?
回复 支持 反对

使用道具 举报

Camel_Yan 发表于 2016-9-26 04:48:00 | 显示全部楼层
stable sorting那部分lz能详细说一下吗
求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 反对

使用道具 举报

chaojiwan 发表于 2016-9-26 05:28:56 | 显示全部楼层
BT to DLL 有 I 和 II,II 是 circular 的。
回复 支持 反对

使用道具 举报

liyoulu 发表于 2016-9-26 07:11:54 | 显示全部楼层
chaojiwan 发表于 2016-9-26 05:28
BT to DLL 有 I 和 II,II 是 circular 的。

这个什么意思
回复 支持 反对

使用道具 举报

chaojiwan 发表于 2016-9-26 09:15:29 | 显示全部楼层

I 是 非circular的。
回复 支持 反对

使用道具 举报

 楼主| tjnkzll 发表于 2016-9-26 11:52:09 | 显示全部楼层
我碰到的是输出需要circular,头尾相接的
回复 支持 反对

使用道具 举报

 楼主| tjnkzll 发表于 2016-9-26 11:52:46 | 显示全部楼层
Camel_Yan 发表于 2016-9-26 04:48. Waral 鍗氬鏈夋洿澶氭枃绔,
stable sorting那部分lz能详细说一下吗

couting sort就是stable的
回复 支持 反对

使用道具 举报

DreamBoy 发表于 2016-9-27 00:41:22 | 显示全部楼层
tjnkzll 发表于 2016-9-26 11:52
couting sort就是stable的

counting sort怎么就stable了?为啥two pointer不stable呢?
回复 支持 反对

使用道具 举报

liurudahai 发表于 2016-9-27 23:58:12 | 显示全部楼层
这道题CC150上有原题,看来大家现在都只看LEETCODE,没人看CC150了
回复 支持 反对

使用道具 举报

Badger96 发表于 2016-9-28 01:13:31 | 显示全部楼层
lintcode有这题
回复 支持 反对

使用道具 举报

fantasiasango 发表于 2016-10-2 01:21:47 | 显示全部楼层
感谢分享,发米限额了!
回复 支持 反对

使用道具 举报

mengmeng88717 发表于 2016-10-4 04:47:04 | 显示全部楼层
http://articles.leetcode.com/convert-binary-search-tree-bst-to/
回复 支持 反对

使用道具 举报

mengmeng88717 发表于 2016-10-4 06:06:27 | 显示全部楼层
把快排改成稳定的,定义一个compare函数,先比较值,再比较index;或者直接merge sort,count sort不一定就是stable的
回复 支持 反对

使用道具 举报

xiangmo 发表于 2016-10-4 06:45:17 | 显示全部楼层
  1. pair<DLL*,DLL*> build(TreeNode* root){
  2.     if(root==NULL)
  3.         return {NULL,NULL};. From 1point 3acres bbs
  4.     auto l=build(root->left);
  5.     DLL* mid=new DLL(root->val); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  6.     auto r=build(root->right);
    .鏈枃鍘熷垱鑷1point3acres璁哄潧
  7.     mid->prev=l.second;
  8.     if(l.second)
  9.         l.second->next=mid;
  10.     mid->next=r.first;
  11.     if(r.first)
  12.         r.first->prev=mid;
  13.     return make_pair(mid->prev?l.first:mid,mid->next?r.second:mid);
  14. }
复制代码
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
求问第一题是这个意思?
回复 支持 反对

使用道具 举报

liurudahai 发表于 2016-10-12 11:20:34 | 显示全部楼层
minggr 发表于 2016-10-10 12:02
活到老学到老,之前我写count sort也一直是写成unstable的
其实算法导论里面的实现就是stable的,但如果 ...

求问STABLE UNSTABLE是什么意思?
回复 支持 反对

使用道具 举报

minggr 发表于 2016-10-12 12:00:03 | 显示全部楼层
liurudahai 发表于 2016-10-12 11:20
求问STABLE UNSTABLE是什么意思?

stable: 相同key的元素在排序后的数组中与原数组中的相对顺序是一样的

比如,有下面4个数, 1是重复的,我用1a 1b来区分
. more info on 1point3acres.com
3 1b 2 1a

unstable: 1a 1b 2 3,
stable: 1b 1a 2 3
回复 支持 反对

使用道具 举报

liurudahai 发表于 2016-10-12 12:06:57 | 显示全部楼层
minggr 发表于 2016-10-12 12:00
stable: 相同key的元素在排序后的数组中与原数组中的相对顺序是一样的

比如,有下面4个数, 1是重复的 ...

这样,懂了,要求这么高,对应到SORT COLOR,就是那些红白蓝颜色虽然是一样,还是希望保持原来的顺序?
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2017-2-24 23:02

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表