《数据科学面试40+真题讲解》,K神本年度最后一次开课


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 2577|回复: 1
收起左侧

OA1 12.11Due OA2 12.18Due

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

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

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

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

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

看地里的很多代码是Java的,这里用C++实现一下,回报地里,鄙人的代码都是优化后的,性能应该有保障。. Waral 鍗氬鏈夋洿澶氭枃绔,

1)
class Solution {
        ListNode* merge2Lists(ListNode* l1, ListNode* l2) {.鐣欏璁哄潧-涓浜-涓夊垎鍦
                ListNode* dummy = new ListNode(0);
                ListNode* cur = dummy;. 鍥磋鎴戜滑@1point 3 acres
                while (l1 != NULL && l2 != NULL) {
                        if (l1->val < l2->val) {
                                cur->next = l1;
                                l1 = l1->next;
                        } else { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                                cur->next = l2;
                                l2 = l2->next;
                        }
                        cur = cur->next;
                }
                cur->next = (l1 == NULL) ? l2 : l1;
                return dummy->next;. From 1point 3acres bbs
        }
}

. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
2)这道题下面的解法是高度优化的解法,鄙人考试时也没有想全。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
int pathSum(TreeNode* root) {
        if (!root){ 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                return 0;
        }
        stack<TreeNode*> st;
        stack<int> stVal;. 1point 3acres 璁哄潧
        minS = 1 << 15;
        st.push_back(root);
        stVal.push_back(root->val);
        while(!st.empty()) {
                TreeNode* top = st.top();. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                int val = stVal.top();. from: 1point3acres.com/bbs
                st.pop();. 1point3acres.com/bbs
                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);. more info on 1point3acres.com
                        stVal.push_back(val + top->left->val);
                }
        }
        return minS;
}
.1point3acres缃

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++;-google 1point3acres
                        if (store.size() == size) {
                                m.erase(store.back());
                                store.pop_back();
                        }
                }
                store.push_front(val);
                m[val] = store.begin();
        }
        return count;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
}
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
可以关注http://codingmelon.com/2015/12/12/minimal-path-sum-from-root-to-leaves/  ,上面有多种方法的介绍。

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

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-11-21 16:34

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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