May 2009 - May 2017 论坛八周年-你的足迹,我的骄傲


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

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

09/23 脸家两轮店面

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

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

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

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

鏉ユ簮涓浜.涓夊垎鍦拌鍧.
之前第一次面的是sort color的变形,写了two pointer的方法, 后来面试官要求写stable的sorting方法,感觉交流上不太顺畅,所以给了加面。
结果加面也没面好。。5555555

评分

2

查看全部评分

本帖被以下淘专辑推荐:

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的写法
为了更明显地说明问题,以下code是counting stable sort一个structure. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

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

输出:
0-老张  0-老谢  1-老陈  2-老王  2-老林
  1. struct color {
  2.     int key;
  3.     string name;-google 1point3acres
  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. . 1point 3acres 璁哄潧
  15.     for (int i = n - 1; i >= 0; i--) {
  16.         int key = colors[i].key;
  17.         int pos = --counts[key];

  18.         sorted[pos] = colors[i];. more info on 1point3acres.com
  19.     }

  20.     return sorted;
  21. }

  22. int main()
  23. {. 鍥磋鎴戜滑@1point 3 acres
  24.     vector<color> colors = {{2, "老王"}, {0, "老张"}, {1, "老陈"}, {2, "老林"}, {0, "老谢"}};
  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 << "  ";. Waral 鍗氬鏈夋洿澶氭枃绔,
  31.     cout << endl;
  32. . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  33.     return 0;
  34. }
复制代码
回复 支持 1 反对 0

使用道具 举报

lyudison 发表于 2016-10-10 08:36:25 | 显示全部楼层
关注一亩三分地微博:
Warald
  1. struct Node {
  2.   Node* left, *right;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  3.   int val;
  4.   Node(int value) {
  5.     val = value;
  6.     left = right = nullptr;
    . more info on 1point3acres.com
  7.   }
  8. };

  9. Node* convert_to_linked_list(Node* root) {
  10.   if (root == nullptr) return nullptr;
  11.   Node dummy;
  12.   Node* pre = &dummy;
  13.   helper(root, pre);
  14.   dummy.right->left = nullptr;
  15.   return dummy.right;. 1point3acres.com/bbs
  16. }
  17. . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  18. void helper(Node* node, Node*& pre) {
  19.   if (!node) return;
  20.   helper(node->left, pre);
  21.   pre->right = node;
  22.   node->left = pre;
  23.   pre = node;. from: 1point3acres.com/bbs
  24.   helper(node->right, pre);
  25. }
复制代码
回复 支持 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能详细说一下吗
回复 支持 反对

使用道具 举报

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
stable sorting那部分lz能详细说一下吗

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

使用道具 举报

DreamBoy 发表于 2016-9-27 00:41:22 | 显示全部楼层
tjnkzll 发表于 2016-9-26 11:52
couting sort就是stable的
-google 1point3acres
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};
  4.     auto l=build(root->left);
  5.     DLL* mid=new DLL(root->val);. more info on 1point3acres.com
  6.     auto r=build(root->right);
  7.     mid->prev=l.second;. more info on 1point3acres.com
  8.     if(l.second). 1point 3acres 璁哄潧
  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. }
复制代码
.鏈枃鍘熷垱鑷1point3acres璁哄潧
求问第一题是这个意思?
回复 支持 反对

使用道具 举报

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. more info on 1point3acres.com
求问STABLE UNSTABLE是什么意思?

stable: 相同key的元素在排序后的数组中与原数组中的相对顺序是一样的. 1point3acres.com/bbs
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
比如,有下面4个数, 1是重复的,我用1a 1b来区分.鏈枃鍘熷垱鑷1point3acres璁哄潧

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. From 1point 3acres bbs
stable: 相同key的元素在排序后的数组中与原数组中的相对顺序是一样的

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

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

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-5-23 22:46

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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