一亩三分地论坛

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

扫码关注一亩三分地公众号
查看: 487|回复: 1
收起左侧

OA1 12.11Due OA2 12.18Due

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

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

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

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

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 这道题里所有节点的值都是非负的。.1point3acres缃
. 鍥磋鎴戜滑@1point 3 acres
看地里的很多代码是Java的,这里用C++实现一下,回报地里,鄙人的代码都是优化后的,性能应该有保障。.鐣欏璁哄潧-涓浜-涓夊垎鍦

1)
class Solution {
        ListNode* merge2Lists(ListNode* l1, ListNode* l2) {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                ListNode* dummy = new ListNode(0);
                ListNode* cur = dummy;
. Waral 鍗氬鏈夋洿澶氭枃绔,                while (l1 != NULL && l2 != NULL) {
                        if (l1->val < l2->val) {
                                cur->next = l1;. 1point3acres.com/bbs
                                l1 = l1->next;
                        } else {
                                cur->next = l2;
                                l2 = l2->next;
                        }
                        cur = cur->next;
                }
                cur->next = (l1 == NULL) ? l2 : l1;. more info on 1point3acres.com
                return dummy->next;. from: 1point3acres.com/bbs
        }. From 1point 3acres bbs
}


2)这道题下面的解法是高度优化的解法,鄙人考试时也没有想全。
int pathSum(TreeNode* root) {
        if (!root){
                return 0;
        }
        stack<TreeNode*> st;.鐣欏璁哄潧-涓浜-涓夊垎鍦
        stack<int> stVal;
        minS = 1 << 15;
        st.push_back(root);.鏈枃鍘熷垱鑷1point3acres璁哄潧
        stVal.push_back(root->val); . from: 1point3acres.com/bbs
        while(!st.empty()) {
                TreeNode* top = st.top();
                int val = stVal.top();
                st.pop();
                stVal.pop();
                if (top->left == NULL && top->right == NULL) {
                        minS = min(minS, val);
.鏈枃鍘熷垱鑷1point3acres璁哄潧                }
                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);. 1point 3acres 璁哄潧
                }.鐣欏璁哄潧-涓浜-涓夊垎鍦
        }
        return minS;. visit 1point3acres.com for more.
}


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++) {
                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);-google 1point3acres
                m[val] = store.begin();
        }
        return count;
}. 鍥磋鎴戜滑@1point 3 acres


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

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

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-10 00:54

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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