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


一亩三分地论坛

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

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

OA1 12.11Due OA2 12.18Due

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

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

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

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

x
从地里学了很多,来造福地里
OA1 12.11 due. debug 和逻辑题如地里所说,没什么新的。Coding题是merge 2 sorted lists。 OA1 结束后23~24 hrs 后收到OA2 邀。
-google 1point3acres. from: 1point3acres.com/bbs
work simulation还是地里的老题,但不知道正确答案。随便选了选。Coding题是 minimal path sum 和 LRU cache。Minimum sum of the path in a tree 这道题里所有节点的值都是非负的。

看地里的很多代码是Java的,这里用C++实现一下,回报地里,鄙人的代码都是优化后的,性能应该有保障。
. more info on 1point3acres.com
1)
class Solution {.1point3acres缃
        ListNode* merge2Lists(ListNode* l1, ListNode* l2) {. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                ListNode* dummy = new ListNode(0);
                ListNode* cur = dummy;
                while (l1 != NULL && l2 != NULL) {
                        if (l1->val < l2->val) {.1point3acres缃
                                cur->next = l1;
                                l1 = l1->next;
                        } else {. 1point3acres.com/bbs
                                cur->next = l2;
                                l2 = l2->next;
                        }
                        cur = cur->next;
                }
                cur->next = (l1 == NULL) ? l2 : l1;
                return dummy->next;
        }. 1point3acres.com/bbs
}
. visit 1point3acres.com for more.

2)这道题下面的解法是高度优化的解法,鄙人考试时也没有想全。
int pathSum(TreeNode* root) {
        if (!root){
                return 0;
        }
        stack<TreeNode*> st;
        stack<int> stVal;
        minS = 1 << 15;
        st.push_back(root);
        stVal.push_back(root->val);
        while(!st.empty()) {
                TreeNode* top = st.top();. from: 1point3acres.com/bbs
                int val = stVal.top();
                st.pop();
                stVal.pop();
                if (top->left == NULL && top->right == NULL) {
                        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;
        int count = 0;
        for (int i = 0; i < len; i++) {. 1point3acres.com/bbs
                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();
        }. 1point 3acres 璁哄潧
        return count;
}


可以关注http://codingmelon.com/2015/12/12/minimal-path-sum-from-root-to-leaves/  ,上面有多种方法的介绍。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

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

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-5-23 00:00

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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