一亩三分地论坛

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

扫码关注一亩三分地公众号
查看: 2609|回复: 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 | 显示全部楼层
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;
  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)
    -google 1point3acres
  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. .鏈枃鍘熷垱鑷1point3acres璁哄潧
  18.         sorted[pos] = colors[i]; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  19.     }

  20.     return sorted;
  21. }

  22. int main()
  23. {
  24.     vector<color> colors = {{2, "老王"}, {0, "老张"}, {1, "老陈"}, {2, "老林"}, {0, "老谢"}};
  25.     for (color c: colors)
  26.         cout << c.key << "-" << c.name << "  ";
  27.     cout << endl;. 1point3acres.com/bbs

  28.     vector<color> sorted = stable_color_sort(colors);
  29.     for (color c: sorted)
  30.         cout << c.key << "-" << c.name << "  ";
  31.     cout << endl;. 1point 3acres 璁哄潧

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

使用道具 举报

lyudison 发表于 2016-10-10 08:36:25 | 显示全部楼层
  1. struct Node {
  2.   Node* left, *right;. 1point3acres.com/bbs
  3.   int val;.1point3acres缃
  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;
  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) {
  18.   if (!node) return;
  19.   helper(node->left, pre);
  20.   pre->right = node;
  21.   node->left = pre;
  22.   pre = node;-google 1point3acres
  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能详细说一下吗
回复 支持 反对

使用道具 举报

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的

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){.鏈枃鍘熷垱鑷1point3acres璁哄潧
  2.     if(root==NULL)
  3.         return {NULL,NULL};
  4.     auto l=build(root->left);
  5.     DLL* mid=new DLL(root->val); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  6.     auto r=build(root->right);
  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);. Waral 鍗氬鏈夋洿澶氭枃绔,
  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是什么意思?
.1point3acres缃
stable: 相同key的元素在排序后的数组中与原数组中的相对顺序是一样的

比如,有下面4个数, 1是重复的,我用1a 1b来区分

3 1b 2 1a. from: 1point3acres.com/bbs

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, 2016-12-4 07:47

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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