當了一年的 Facebook Rotational Software Engineer 心得分享

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 2714|回复: 1
收起左侧

OA1 12.11Due OA2 12.18Due

[复制链接] |试试Instant~ |关注本帖
xiaobao9 发表于 2015-12-13 12:40:46 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类General 硕士 全职@Amazon - 内推 - 技术电面  | Other | fresh grad应届毕业生

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

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

x
从地里学了很多,来造福地里
OA1 12.11 due. debug 和逻辑题如地里所说,没什么新的。Coding题是merge 2 sorted lists。 OA1 结束后23~24 hrs 后收到OA2 邀。
.留学论坛-一亩-三分地
work simulation还是地里的老题,但不知道正确答案。随便选了选。Coding题是 minimal path sum 和 LRU cache。Minimum sum of the path in a tree 这道题里所有节点的值都是非负的。
.留学论坛-一亩-三分地
看地里的很多代码是Java的,这里用C++实现一下,回报地里,鄙人的代码都是优化后的,性能应该有保障。

1)
class Solution {
        ListNode* merge2Lists(ListNode* l1, ListNode* l2) {
                ListNode* dummy = new ListNode(0);
                ListNode* cur = dummy;
                while (l1 != NULL && l2 != NULL) {
                        if (l1->val < l2->val) {
                                cur->next = l1;. From 1point 3acres bbs
                                l1 = l1->next;
                        } else {
                                cur->next = l2;
                                l2 = l2->next;
                        }
                        cur = cur->next;
                }
                cur->next = (l1 == NULL) ? l2 : l1;
                return dummy->next;
        }
}


2)这道题下面的解法是高度优化的解法,鄙人考试时也没有想全。. more info on 1point3acres
int pathSum(TreeNode* root) {
        if (!root){
                return 0;
        }
        stack<TreeNode*> st;
        stack<int> stVal;
        minS = 1 << 15;. 1point3acres
        st.push_back(root);
        stVal.push_back(root->val);
        while(!st.empty()) {
                TreeNode* top = st.top();
                int val = stVal.top();
                st.pop();
                stVal.pop();
                if (top->left == NULL && top->right == NULL) {.1point3acres网
                        minS = min(minS, val);
                }
                if (top->right && val + top->right->val < minS) {
                        st.push_back(top->right);
                        stVal.push_back(val + top->right->val);
                }
                if (top->left && val + top->left->val < minS) {
                        st.push_back(top->left);. 留学申请论坛-一亩三分地
                        stVal.push_back(val + top->left->val);
                }
        }
        return minS;
}


3)这道题也是用map记录存储位置,从而优化性能。
int cacheMiss(int array[], int len, int size) {
        list<int> store;
        map<int, list<int>::iterator> m;. From 1point 3acres bbs
        int count = 0;
        for (int i = 0; i < len; i++) {
                int val = array[i];
                // hit
                if (m.count(val)) {
                        store.erase(m[val]);
                } else { //miss
                        count++;
                        if (store.size() == size) {
                                m.erase(store.back());
                                store.pop_back();
                        }
                }
                store.push_front(val);
                m[val] = store.begin();
        }
        return count;
}

. from: 1point3acres
可以关注http://codingmelon.com/2015/12/12/minimal-path-sum-from-root-to-leaves/  ,上面有多种方法的介绍。-google 1point3acres

强烈求大米
水逼一枚 发表于 2015-12-15 00:28:46 | 显示全部楼层
楼主你发的link那个min path sum的递归解法是有BUG的。
回复 支持 反对

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-5-21 01:31

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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