Brown CS 18 fall 入学感受

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
高效直聘+内推,70%面试率
AI帮你免费完善简历
直击全美十万个科技职位
把贵司招聘信息放这里
查看: 2074|回复: 16
收起左侧

eBay新鲜面经

[复制链接] |试试Instant~
我的人缘0
格格笑 发表于 2017-11-14 03:30:53 | 显示全部楼层 |阅读模式
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  89% (42)
 
 
10% (5)  踩

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

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

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

x
Maximum Subarray at most k element

攒RP. 留学申请论坛-一亩三分地


评分

参与人数 2大米 +23 收起 理由
yzkst06100 + 3 很有用的信息!
sherry900629 + 20

查看全部评分


上一篇:巨硬实习电面面经..
下一篇:Citadel 全套OA
我的人缘0
 楼主| 格格笑 发表于 2017-11-14 23:54:55 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  89% (42)
 
 
10% (5)  踩
Update一下 GG 思密达了    烙印小哥  十分稳
回复

使用道具 举报

我的人缘0
 楼主| 格格笑 发表于 2017-11-14 23:56:55 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  89% (42)
 
 
10% (5)  踩
lylwill 发表于 2017-11-14 06:07
噢噢噢 lz有想出O(n) 的解法吗 如果双指针移的话reach到了length k 判断sum 如果大于0 我是想把begin 往 ...

预处理成prefix sum数组, Deque 维护一个 K范围内的最小值  遍历一遍求当前减去最小   遇到比global max 就update
回复

使用道具 举报

我的人缘0
 楼主| 格格笑 发表于 2017-12-8 03:00:40 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  89% (42)
 
 
10% (5)  踩
翻到自己这页,给大家发个我当时写的完整版吧 233

import java.util.*;

public class eBayIllustration{
    public static void main(String[] args) {
        int[] input = new int[]{10, 30, -40, 3};
        eBayIllustration sol = new eBayIllustration();
        int[] res = sol.maxSubarrayAtMostK(input, 2);
        if (res == null) {. visit 1point3acres for more.
            System.out.println("no one was selected");
        } else {
            System.out.println(res[0] + "~" + res[1]);
        }
    }

    // basically, my idea is maintain a deque to contains currently valid min value
    // valid means the min value must be in the scope of k from current i. 牛人云集,一亩三分地
    // Time: O(N). visit 1point3acres for more.
    // Space: O(N)
    public int[] maxSubarrayAtMostK(int[] input, int k) {
        if (input == null || input.length == 0) {. 牛人云集,一亩三分地
            return new int[0];
        }
        // Preprocessing
        // nums[i]  represents the sum : input[0] + ... input[i - 1]
        int[] nums = new int[input.length + 1];
        for (int i = 1; i < nums.length; i++) { 来源一亩.三分地论坛.
            nums[i] = nums[i - 1] + input[i - 1];
        }
        Deque<Integer> deque = new LinkedList<>();. Waral 博客有更多文章,
        int max = 0;
        int[] candidate = null;
        for (int i = 0; i < nums.length; i++) {. Waral 博客有更多文章,
            while (!deque.isEmpty() && nums[deque.peekLast()] >= nums[i]) {
                deque.pollLast();
            }
            deque.addLast(i);
            // out of scope
            if (deque.peekFirst() < i - k) {
                deque.pollFirst();. visit 1point3acres for more.
            }
            // if better subarray appear, update the result/candidate
            if (nums[i] - nums[deque.peekFirst()] > max) {
                max = nums[i] - nums[deque.peekFirst()];
                candidate = new int[]{deque.peekFirst(), i - 1}; //inclusive idx
            }
        }
        return candidate;// e.g  [1,3] 1 means the left bound 3 means the right bound of the subarray of input, bothe left and right bound are inclusive.
    }. 围观我们@1point 3 acres
}
回复

使用道具 举报

我的人缘0
 楼主| 格格笑 发表于 2017-11-14 23:53:57 | 显示全部楼层
本楼: 【顶】   100% (2)
 
 
0% (0)   【踩】
全局: 顶  89% (42)
 
 
10% (5)  踩
yzkst06100 发表于 2017-11-14 05:23. 一亩-三分-地,独家发布
楼主面的是哪个组呀?

backend  烙印黑的飞起来~
回复

使用道具 举报

我的人缘0
lylwill 发表于 2017-11-14 04:27:36 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  87% (143)
 
 
12% (21)  踩
问下lz 啥叫 at most k element? 和lc有啥区别吗
回复

使用道具 举报

我的人缘0
MarvinJ 发表于 2017-11-14 05:12:43 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  33% (3)
 
 
66% (6)  踩
楼主为啥我看ebay careers recent grad没有opening啊
回复

使用道具 举报

我的人缘0
 楼主| 格格笑 发表于 2017-11-14 05:17:25 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  89% (42)
 
 
10% (5)  踩
lylwill 发表于 2017-11-14 04:27
问下lz 啥叫 at most k element? 和lc有啥区别吗

subarray的size最多为k
回复

使用道具 举报

我的人缘0
skinsoctopus 发表于 2017-11-14 05:19:41 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (10)
 
 
0% (0)  踩
lz描述可以稍微详细点吗?请问是lc哪一题?

With React+D3v4 you'll learn the basics of building fast data visualization components in about an hour.


回复

使用道具 举报

我的人缘0
yzkst06100 发表于 2017-11-14 05:23:20 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  98% (56)
 
 
1% (1)  踩
楼主面的是哪个组呀?
回复

使用道具 举报

我的人缘0
lylwill 发表于 2017-11-14 06:07:51 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  87% (143)
 
 
12% (21)  踩
格格笑 发表于 2017-11-14 05:17
subarray的size最多为k

噢噢噢 lz有想出O(n) 的解法吗 如果双指针移的话reach到了length k 判断sum 如果大于0 我是想把begin 往后面移动一个 end再移动一个 不过这样出来的可能会ignore一些case eg cur_window = [7 -11 10 12], sum > 0, len = k => move cur_window = [-11 10 12 -13] 就会漏掉 10 + 12 = 22, lz是怎么解决的啊
回复

使用道具 举报

游客
请先登录

本版积分规则

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

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

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

GMT+8, 2018-10-19 19:36

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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