c******a
发帖数: 789 | 1 18.12就调用一次，求最大sum的sub－matrix，熟max－run的立刻就能想到用max
histogram每行搞一搞max－run了。
这题鼓励pre-compute，多次调用，我晕了5分钟max－run不work我就去看答案了,555。
你这么一说的确是，关键就是：利用已有matrix们O(1)解要求的matrix。 |
|
r**h
发帖数: 1288 | 2 请问一下，循环数组是用来保持最近5分钟/1小时之内所有的数据吗？
那么每次要找出top5有没有什么比较好的方法呢？比线性搜索要快的话？
是每次保持并更新一个含有很多条目的histogram吗？这样如何能够有效动态的找到
top5呢？ |
|
r**h
发帖数: 1288 | 3 请问一下，循环数组是用来保持最近5分钟/1小时之内所有的数据吗？
那么每次要找出top5有没有什么比较好的方法呢？比线性搜索要快的话？
是每次保持并更新一个含有很多条目的histogram吗？这样如何能够有效动态的找到
top5呢？ |
|
l*n
发帖数: 529 | 4 先处理下原矩阵，mat[i][j]=mat[i][j]==0?0:mat[i-1][j]+1
然后用histogram最大面积的o(n)算法处理每一行. |
|
h********g
发帖数: 496 | 5
对，大致就是map/reduce的方法。具体划分还可以追问下，比如我划分方法是基于word
的首字母。那么26个字母开头的words，count都是多少，可以估计一个histogram，这
样均分任务就容易了。
=
frequency
theta |
|
b**m
发帖数: 1466 | 6 没想出用stack方法，我这个也是O(n)吧？
public class Solution {
public int largestRectangleArea(int[] height) {
if(height.length ==0 ){
return 0;
}
int[] left= new int[height.length]; // width on its left side(and
itself)
int[] right= new int[height.length]; // width on its right side(and
itself)
left[0] = 1;
right[right.length-1] = 1;
for(int i=1;i< height.length; i++){
if(height[i]> height[i-1]){
... 阅读全帖 |
|
b********g
发帖数: 28 | 7 public class Solution {
public int largestRectangleArea(int[] height) {
// Start typing your Java solution below
// DO NOT write main() function
if(height == null || height.length == 0) return 0;
int n = height.length;
int[] left = new int[n];
Stack stack = new Stack();
int max = 0;
for(int i = 0; i < n; i++){
if(stack.empty() || height[stack.peek()] <= height[i]){
left[i] = i;
... 阅读全帖 |
|
l*n
发帖数: 529 | 8 来自主题: JobHunting版 - 问一道题目 count+heap for exact solution
histogram for the appropriate |
|
z****e
发帖数: 54598 | 9 贴几个参考的课程描述
统计和ml
With exponential increases in the amount of data becoming available in
fields such as finance and biology, and on the web, there is an ever-greater
need for methods to detect interesting patterns in that data, and classify
novel data points based on curated data sets. Statistical machine learning
and evolutionary computation provide the means to perform this analysis
automatically, and in doing so to enhance understanding of general processes
or to predict future events.
Topics ... 阅读全帖 |
|
c*****e
发帖数: 67 | 10 个人觉得这题算是很难的，理解O(n)算法都需要些时间。
面试的时候难道就算你知道O(n)算法，还要写出来吗？考官不会一眼就知道你是预先知
道答案的？
在想要不要先写个最naive的算法，然后再跟考官讨论下怎么去优化？（但是O(n)算法
也不是能靠考官提示就做出来的吧？） |
|
d**e
发帖数: 6098 | 11 面试,大部分的情况下不是要你去创造算法,而是考你知不知道某个算法. |
|
|
|
A*********c
发帖数: 430 | 14 没错，考得不是创造力而是知识。半个小时也创造不出什么惊天地泣鬼神的算法。 |
|
A*********c
发帖数: 430 | 15 O(n^2)的算法不难，O(n)的算法现场想出来不可能。
O(n)的算法背过不难，但是细节挺多的。
就这句，curRect = h * (s.empty() ? i : (i-s.top()-1));
我画了好几个图才明白到底为什么这样搞。 |
|
A*********c
发帖数: 430 | 16 Valid Number我也觉得可以，就是linear scan，15行搞定。
Maximal Rectangle有 O(n^3)的算法，特简单。O(n^2)的一个算法是扩展max
histogram的，挺牛逼的。学会了还是有高潮的。 |
|
l*********8
发帖数: 4642 | 17 保存最后N个数字的histogram可以吗？
教： |
|
s******7
发帖数: 1758 | 18 这个leetcode上有 Largest Rectangle in Histogram， O(n) |
|
|
g******y
发帖数: 143 | 20 Interviewed with Kinect group
Phone interview
1.implement an image convolution and optimize it
2. find the intersection of two rectangles
Onsite
Round1
1. Implement strstr() and optimize it
2. Implement histogram equalization algorithm
3. Bayes conditional probability
Round2
1. Implement a fixed floating point class
2. Square root of a number (the number can be less than 1)
Round3
1. Find subarray which has max sum
2. Find the kth element in two sorted arrays
Round4
1. Im... 阅读全帖 |
|
|
A*****i
发帖数: 3587 | 22 这题stack这个就很好啊，便于理解
如果非为了DP去想DP就没意思了
其实公司里写代码就是图个省事，高深晦涩的代码只能让同事骂娘 |
|
v***n
发帖数: 562 | 23 多谢你的建议！
只是想看看解法，理解一下DP，这方面还不熟。 |
|
r****7
发帖数: 2282 | 24 无非就是有了第n个要不要第n+1个两种case呗
不过stack确实更自然一点儿 |
|
|
s******t
发帖数: 229 | 26 不用什么-1啊，压入index的想法在别的题里也有啊，比如histogram |
|
a***e
发帖数: 413 | 27 看着很容易，一写bruteforce的就TLE，后来看了idea是用stack，如下。
TLE的是O(N^2),用stack是因为每个元素只入栈出栈一次push 和pop都是O（1），所以
是O(N)是吧？一犯困就很糊涂。轻拍
int largestRectangleArea(vector &height) {
int maxArea=0;
int area=0;
int n = height.size();
if (n==1)
return height[0];
int j;
for (int i=0; i
{
j=i+1;
while(j
{
if (height[j]>=height[i])
{
area = height[i]*(j-i+1);
... 阅读全帖 |
|
|
y***n
发帖数: 1594 | 29 有道理，其实Largest Rectangle Histogram 那个土方法, 还有 Stock III 也有这个
味道。 |
|
b*******r
发帖数: 50 | 30 面试之前在这里看了很多面经。非常感谢大家。现在贡献一下我的。顺便求一下bless
，希望能拿到心仪的offer。
new grad full time position. 一个白人小哥面的。
上来先讲了讲research。感觉就没答好。他问了一个我简历里research的一个linear
programming的细节，但是我其实只是用了一点皮毛，对深层的原理不是很理解。结果
花了很多时间在这块还没答到重点。教训就是，不是特别在行的东西千万别放简历上。
然后就是coding，一共三题，这时候离结束就只有40分钟了，时间不怎么够。
1. 去除string中的空白
2. largest rectangle in histogram
3. 把regular expression tree 转换成表达式string
最后一题没写完就到只剩下五分钟了。小哥让我停下来跟我介绍了他的组，并且问问我
有什么问题之类。然后就结束了。题目都没答完肯定是没戏了。move on准备下一场。
祝各位找工作的都顺利！
忘了说了，电话打来晚了七分钟。有了这七分钟我最后一题肯定能写完的。郁闷！ |
|
b*******r
发帖数: 50 | 31 面试之前在这里看了很多面经。非常感谢大家。现在贡献一下我的。顺便求一下bless
，希望能拿到心仪的offer。
new grad full time position. 一个白人小哥面的。
上来先讲了讲research。感觉就没答好。他问了一个我简历里research的一个linear
programming的细节，但是我其实只是用了一点皮毛，对深层的原理不是很理解。结果
花了很多时间在这块还没答到重点。教训就是，不是特别在行的东西千万别放简历上。
然后就是coding，一共三题，这时候离结束就只有40分钟了，时间不怎么够。
1. 去除string中的空白
2. largest rectangle in histogram
3. 把regular expression tree 转换成表达式string
最后一题没写完就到只剩下五分钟了。小哥让我停下来跟我介绍了他的组，并且问问我
有什么问题之类。然后就结束了。题目都没答完肯定是没戏了。move on准备下一场。
祝各位找工作的都顺利！
忘了说了，电话打来晚了七分钟。有了这七分钟我最后一题肯定能写完的。郁闷！
update：
居然通知... 阅读全帖 |
|
w****3
发帖数: 110 | 32 largest rectangle in histogram
wo ca |
|
l***p
发帖数: 160 | 33 time series 的题和leetcode 的 Largest Rectangle in Histogram 很像
我的解法（把int 改成double) 是一样的。
class Solution {
public:
vector maxDays(vector nums) {
int size = nums.size();
vector result(size, 0);
nums.push_back(INT_MAX);
stack s;
int idx = 0;
while (idx <= size) {
if (s.empty() || nums[idx] < nums[s.top()]) {
s.push(idx++);
}
else {
int cur = s.top();
... 阅读全帖 |
|
m******a
发帖数: 84 | 34 滚动数组？
建一个300的数组（一秒一个元素）
然后i从0开始，每过一秒(i++)%300 ，累加 |
|
w****k
发帖数: 755 | 35 不是很明白题意，但这种通常是用现成的技术来做的，而不是算法。
比方说redis 或者 cassandra，能够给插入的元素设置expiration，这样超过5分钟自
动消失了。 |
|
b**********5
发帖数: 7881 | 36 1） 面了leetcode上的histogram catch rain water的
2） 面了在phone pad上， 按照国际象棋规则走下一步的， 输出可以走得all paths。
一个很简单地aabbc变成a2b2c
3） 让我在IDE上写一个simple stock portofolio， persisting to file
中间lunch， 最后mananger， 不问technical。。。
我觉得他们也没什么问题的。。。 写完了， 还有一通时间， 就让问问题。。我全部
唰唰唰的给他们写出来。。 最后来了个technically struggled a bit。。。 |
|
A*******e
发帖数: 2419 | 37 写了个O(n^2)的算法，从中心向两侧展开，超时了。
另外这题为何叫Container With Most Water？明明是max histogram area嘛。函数接
口也叫maxArea，跟容器、水有何关系？ |
|
A*******e
发帖数: 2419 | 38 谢谢提醒。是我看错了。这个和max histogram area不一样。
写了一个，是不是有点长？谁有更简洁的写法？
class Solution {
public:
int maxArea(vector& height) {
int head = 0;
int tail = height.size() - 1;
int result = GetArea(height, head, tail);
while (head < tail) {
if (height[head] < height[tail]) {
int next_head = head + 1;
while (next_head < height.size() &&
height[next_head] <= height[head]) {
++next_head;
... 阅读全帖 |
|
j**7
发帖数: 143 | 39 内循环+外循环 还是O(N).我本来想用LeetCode Largest Histogram 那道题的DP算法
来解这道题。不过看来用DP不对。 |
|
|
|
h*********2
发帖数: 192 | 42 给定一个单调递增的数列，找到一个partition into N bucket，使得所有bucket的数字
的variance最小。bucket个数是已知的。
听起来像binary search + dp
请问大家见过这题吗？ |
|
发帖数: 1 | 43 这不是algorithm design 里面的the partition problem吗 |
|
|
n******g
发帖数: 2201 | 45 使用递归
while N = n:
min_var = min_var
while N < n:
数字 |
|
o*q
发帖数: 630 | 46 # Title Editorial Acceptance Difficulty Frequency
1
Two Sum 28.3% Easy
292
Nim Game 54.4% Easy
344
Reverse String 57.3% Easy
136
Single Number 52.2% Easy
2
Add Two Numbers 25.6% Medium
371
Sum of Two Integers 51.6% Easy
4
Median of Two Sorted Arrays
20.4% Hard
6
ZigZag Conversion 25.6% Easy
13
Roman to Integer 42.7% Easy
237
... 阅读全帖 |
|
|
b********y
发帖数: 268 | 48 昨天参观了一个reggio emilia为基础得preschool, 非常赞同他们的一些教育理念，小朋友也玩的非常开心. 没有见过太多这种play based的学校， 想向研究早教的同学们
(rainlion !)，讲讲你们的见解.
1. 注重学生的为主. 学生出一些project的主意，大家感兴趣，一起做. 锻炼小孩的想
象力，创造力，发散性思维；激发学生兴趣，锻炼学生学习，研究的能力
2. 老师用照片给记录下来，放到网上，父母可以跟小朋友聊，温习，了解小朋友在想
什么，
3. 绝大部分时间在户外，4acre的校园，有山羊，鸡，鸭，菜园，wildness，mud pit
，"垃圾"户外乐队(垃圾桶，破锅碗瓢盆，之类）...
4. 以第一手的经验去学习各种自然科学，动物，地理；
5. 吃得很健康，local butcher，自己种的菜，
6. 以科学为主，尊重diversity，让小朋友分享，认同信仰差异，
学校实际案例
1： 一个小女生开始用block拼她的朋友的名字-》 大家注意到名字的长短不一样，开
始拼所有小朋友的名字，按长短归类-》然后注意到名字用的字母，开始总结多少个字... 阅读全帖 |
|
C*G
发帖数: 7495 | 49 鲁镇股票交易所的格局，是和别处相同的：都是当街一个曲尺形的大柜台，柜里面预备
着各种股票，可以随时买卖。炒股的人，每天一早起床,每每花七文铜钱，就可以买一
支股票，然后靠柜外站着，急切地等着上涨，就可以完成交易，出售赚钱，补贴通货膨
胀下生活的亏空;倘肯多花2万5千块做定存，就能不须支付每次七文的铜钱，免费下单
交易。但这里的顾客，多是散户，大抵没有这样阔绰。只有传说中股海发财的大户才可
以穿印着“据说我赚了几个密林”长衫，有资格踱进店面隔壁的大户室，要酒要菜，慢
慢地坐喝、下单。我从十二岁起，便在镇口的交易所里当BROKER，掌柜说，样子太傻，
怕侍候不了传说中的大户，就在外面做点事罢。外面的散户股民，虽然容易说话，但唠
唠叨叨缠夹不清的也很不少。他们往往要亲眼看着自己的股票上涨，看过自己确实买在
了最低价，又亲看我帮他们止赢，然后才放心：在这严重兼督下，心里负担过大，我的
操作屡屡失误，还得不少散户被套牢，所以过了几天，掌柜又说我干不了这事。幸亏荐
头的情面大，辞退不得，便改为专管出售股票的一种无聊职务了。我从此便整天的站在
柜台里，专管我的职务。虽然没有什么失职，但总觉得有些单调... 阅读全帖 |
|
C*G
发帖数: 7495 | 50 鲁镇股票交易所的格局，是和别处相同的：都是当街一个曲尺形的大柜台，柜里面预备
着各种股票，可以随时买卖。炒股的人，每天一早起床,每每花七文铜钱，就可以买一
支股票，然后靠柜外站着，急切地等着上涨，就可以完成交易，出售赚钱，补贴通货膨
胀下生活的亏空;倘肯多花2万5千块做定存，就能不须支付每次七文的铜钱，免费下单
交易。但这里的顾客，多是散户，大抵没有这样阔绰。只有传说中股海发财的大户才可
以穿印着“据说我赚了几个密林”长衫，有资格踱进店面隔壁的大户室，要酒要菜，慢
慢地坐喝、下单。我从十二岁起，便在镇口的交易所里当BROKER，掌柜说，样子太傻，
怕侍候不了传说中的大户，就在外面做点事罢。外面的散户股民，虽然容易说话，但唠
唠叨叨缠夹不清的也很不少。他们往往要亲眼看着自己的股票上涨，看过自己确实买在
了最低价，又亲看我帮他们止赢，然后才放心：在这严重兼督下，心里负担过大，我的
操作屡屡失误，还得不少散户被套牢，所以过了几天，掌柜又说我干不了这事。幸亏荐
头的情面大，辞退不得，便改为专管出售股票的一种无聊职务了。我从此便整天的站在
柜台里，专管我的职务。虽然没有什么失职，但总觉得有些单调... 阅读全帖 |
|
