b******7
发帖数: 92 | 1 要求inplace，和cc150上题不一样。你仔细想想，并注意这个case
"abcddddddddddefg"==> a1b1c1d10e1f1g1
我想不到除我给的方法外更简便的方法了 |
|
r**h
发帖数: 1288 | 2 的确如果要求inplace且1也算的话，要扫两遍了 |
|
J****3
发帖数: 427 | 3 2*len+1 是这种情况 abc-> a1b1c1
第二个是啥意思？没大看明白？你是说要在原字符串上操作 Inplace的意思么？ |
|
J****3
发帖数: 427 | 4 客气 这个是要O(n) space的 方法吧 不是inplace的 |
|
f*********d
发帖数: 140 | 5 将书组里的所有负数排在所有正数前面，保持正数和负数原来的相对顺序不变
inplace 时间复杂度越低越好~
eg
input
-5 2 -3 4 -8 -9 1 3 -10
output
-5 -3 -8 -9 -10 2 4 1 3 |
|
l*n
发帖数: 529 | 6 inplace counting，用0~(k-1)的位置记录相应的数字的个数。不过在此之前要先把0~(
k-1)的位置置换好。 |
|
|
q*****w
发帖数: 62 | 8 如果输入是数组都话感觉可以inplace做．
因为所有数都是属于１－N的，假设k个数twice，输入数组都长度肯定是N + Ｋ．然后
就想变换方法让最后k的数都是出现２次的数。 |
|
|
s********u
发帖数: 1109 | 10 还只是胡思乱想，也不太严谨。欢迎指正。（只讨论目前算法面试题一般涵盖的范围）
前言：
我知道大家都会说当满足最优子结构、subproblem overlap的时候可以用dp。但其实这
个条件个人感觉不太实用。
1.比如不overlap的时候也可以用dp，只是效率不提高，还增加了space cost而已。（
所以这个原则应该是“适合用dp”，而不是“可以用dp”
另外且不说最优子结构，overlap有时候也较难判断，比如boggle game这个，路径一定
是有重复的，但是
subproblem却未必，因为前驱的访问节点会影响后驱节点的"胜利条件"。
2.另外，就算是有overlap，从实用的角度来说，dp（bottom-up）未必方便实现。比如
用DFS来判定二叉树中是否有某个节点(cc150的4.7），bool cover( root, p )本身是
单纯的DFS访问，subproblem不存在overlap；但对整个问题而言，cover不停的调用，
对整个问题而言subproblem存在overlap。同样的还有4.1.因为这两个题目都在DFS中使
用了DFS，递归函数中调用了递归... 阅读全帖 |
|
s********u
发帖数: 1109 | 11 哦 我大致明白意思了，就是颠倒整个句子，但是每个utf8编码不能颠倒对吧? 就是相
当于有很多word的单词，颠倒word的顺序，但不颠倒word？ 每个编码之间用空格隔开
么？
lz思路应该是不错的，就是先颠倒全部再逐个颠倒。不过inplace颠倒的话，lz是记录
begin和end，然后往中间走，逐个swap么？ |
|
m********l
发帖数: 791 | 12 希望斑竹不要置顶。
先来个背景：纯属给其他人找自信的哈哈。
09年机械本科毕业，10年来美150开外学校转过三次专业，彷徨过也和小本混过耽误了
很多时间，最后在CS落脚，是统计和CS的Dual Master。虽然学校的CS和统计的课程都
已经修完，但是学校课程实在太水所以大多数的知识还都是自己自学的。去年有过一次
web 开发的非IT 公司summer实习经历（这貌似是我第一次写超过100行的代码 = = ）
，实习之后就基本把统计给放掉了，当然基本功还是有。目前还是学生身份但在一家公
司做full-time合同工，基本上就是修补bug打打杂，基本啥事没有白领工资，当然工资
必须很低。真正开始认真准备面试大概就是今年9月份，反正公司也不忙，自己就花大
量的时间在算法/leetcode/cc150/刷真题上，基本上还是会花10+小时以上在准备。
- CC150 重点章节基本都过了一遍
- Leetcode 做了大概80题，但是属于临时抱佛脚的状态。很多题目想个几分钟没什么
思路就在网上找答案了。但是自己还是花时间把答案认真研读过也总结过。每题也都做
了2-3遍，差不多是看到题目就把答案写... 阅读全帖 |
|
k*******r
发帖数: 355 | 13 我觉得这个题用标准的next permutation法不就行了，保证inplace啊。
serializ方法的第2个参数就是需要运行next permutation的次数，用一个整数即可 |
|
s******d
发帖数: 424 | 14 给两个字符串，判断第一个字符串能否用第二个字符串中的字符构成。先给一个int
ncount[256]的方案，提示可以节省空间，换成unordered_map，
这个inplace的办法， 时间复杂度O(MlogM + NlogN)
sort(s1.begin(),s1.end());
sort(s2.begin(),s2.end());
return s2.find(s1) != string::npos; |
|
x****1
发帖数: 118 | 15 Linkedin
phone1：烙印
lowest common ancestor w/ and w/o parent pointer
phone2：国人
search in rotated sorted array
onsite:
1.两个国人
implement addInterval(start, end) and getcoverage(),
2.两个国人
talk projects and some behavior question
3.烙印
lunch, talk about technologies interest
4.亚裔，不确定是否国人
Manager, talked a lot of behavior questions, interest and projects
5.烙印
Design: tinyurl
6.烙印+小白
1.exclusive array, give an arr1, return a new arr2, arr2[i] is the
multiplication of all elements in arr1 except arr1[i]
... 阅读全帖 |
|
s******d
发帖数: 424 | 16 用python,perl,API,stack的都在耍流氓好吗？这题就该用纯C做不许call库函数。。。
inplace, O(N) O(1)
class Solution {
private:
void DoReverse(string& w, int first, int last)
{
while(first < last)
{
swap(w[first++], w[last--]);
}
}
public:
void reverseWords(string &s) {
int ns = s.size();
int start=0, end = ns-1;
while(start < ns && s[start] == ' ') ++start;
while(end >=0 && s[end] == ' ') --end;
if(start > end)
{
s = "";
re... 阅读全帖 |
|
f******h
发帖数: 45 | 17 也找工作了一段时间了，从版上学了很多，上周G家面完了，求个bless。
之前的一些都挂了，还在继续找其他的。等定下来之后一定发面经回报本版。
谢谢大家啦！！
1. http://www.mitbbs.com/article_t/JobHunting/32005597.html
1) Implement a simple calculator (+,-,*,/);
2) Implement "+1" for a large integer;
3) How to match Ads to users;
4) How to extract useful information from a forum webpage (list all
kinds of useful signal you can think of)
5) How to detect the duplicate HTML pages (large scale);
6) Find all the paths between two places on Google map;
7)... 阅读全帖 |
|
s********f
发帖数: 510 | 18 第一题不是要求inplace么， 为什么给了递归解法呢。
第三题没太看明白你说的Inorder Traverse。是不是面的人觉得解法不够清晰？ |
|
l****i
发帖数: 2772 | 19 第2题不是那个意思。inplace flatten变为linkedlist，再变回去。不是普通的BT的
serialize、deserialize |
|
l****i
发帖数: 2772 | 20 这样不是inplace了。。。三哥要求constant space |
|
R******9
发帖数: 267 | 21 M面经
两个月前面的，乘着记得回报本版。
Phone: lowest common ancestor of two nodes in a binary tree. Binary tree
node doesn’t have parent pointer.
What if the nodes have parent pointer?
Onsite:
1. Print the boundary of binary tree anti-clockwise.
2. a. Given a linked list, put all the even numbers before odd numbers.
e.g. 3->4->2->7->null
should become 4->2->3->7->null
b. A small design problem. Shuttle is picking up passages on a lane. The
arrival of passengers are random. Design such a system.
3. Find t... 阅读全帖 |
|
h*******e
发帖数: 1377 | 22 这样的话，看代码的意思， 镂空的内沿就不算了，题目主要让计算左边，右边 加上叶
子节点 。楼主leftmost rightmost两个 状态参数用得好，这样就inplace 一次遍历成
功结果也不用在外面存了。谢谢楼主。 |
|
h*******e
发帖数: 1377 | 23 inplace 算法： 快排20个数，然后 左至右扫描， 2个iterator 每次两个循环，
evenI 0开始每次加 2 找到第一个元素为odd的 evenI oddI 1开始每次加2， 找到
第一个元素为 even的oddI swap evenI oddI 的元素 然后继续扫描 直到 evenI 指向
20~~停止。 |
|
i**d
发帖数: 357 | 24 emplace create the object inplace for you to save copy. insert is to copy
the existing one (or move)
struct Foo
{
Foo(int n, double x);
};
std::vector v;
v.emplace(someIterator, 42, 3.1416);
v.insert(someIterator, Foo(42, 3.1416)); |
|
f*******w
发帖数: 1243 | 25
还好吧？LC反正都能过
反正最后都是要输出所有的permutation，字符串长度是n的话，有n!个
直接recursion经常要往字符串中间insert，复杂度不知道怎么算，但是感觉挺高的啊
Next permutation的复杂度也就是inplace调整一下，大部分时候都不到O(n)
所以我感觉差不多…… |
|
x*******i
发帖数: 28 | 26 下午刚刚面的，面试官是个国人大哥。上来他先自我介绍了一下，然后我自我介绍，说
了下phd的研究内容。然后就开始coding。
第一题，给一个字符数组，要求将其中的'a'加倍，'b'删除，其他字符保持不变。要求
inplace，线性复杂度。这一题做的很顺利。面试官说good enough
第二题，Sum Root to Leaf Numbers。这个题平时写起来很熟练的。可这是lz人生中第
一次求职面试，有点紧张。写完以后面试官说有点问题，然后我改了一下，没改到点子
上。面试官很nice的说，你为啥不找个testcase试一试呢，然后给了我两个testcase，
我试了一下，果断发现bug，修好。
然后面试官说时间不够做第三题了，让我把第二题recursion改成iterative的方法。我
一开始就动手写iterative版本的preorder traversal，写了一半面试官说没这么复杂
。然后lz就删了重新用levelorder traversal写了一遍，写完的时候其实就超时了一分
钟左右。面试官没让lz检查，说已经good enough了，不过还是指出一个小错误，然后
自己主... 阅读全帖 |
|
a*****a
发帖数: 46 | 27 我估计得至少两倍空间存在，最惨的情况是字符串上全是a，然后又要求inplace的话。。
我的想法是把字符串先复制到数组的后面，然后再挨个拷回前面
void add_a_remove_b(char* a){
int len = strlen(a);
for(int i=0; i
int p = 0;
for(int i=0; i
if (*(a+len+i) == 'a') {
*(a+p) = 'a';
*(a+p+1) = 'a';
p = p+2;
}
else if (*(a+len+i) == 'b') continue;
else{
*(a+p) = *(a+len+i);
p++;
}
}
*(a+p) = '\0';
} |
|
s****z
发帖数: 18 | 28 你也是额外用一倍的空间么? 这样算inplace么...额 |
|
q******n
发帖数: 4479 | 29 是不是可以先traverse一遍，count the number of a, b.算出目标长度，然后inplace
from end to first copy each char to end, if it is a, double, if it is b,
skip it.
这样复杂度是O（2n）， 也是线性的。 |
|
x*********n
发帖数: 100 | 30 如果是缩小呢？就算不缩小，比如这个：btaa。会踩到自己的脚，把T弄没了。
应该先从左到右先把b的坑填了，顺便点a个数。然后从目标长度从右到左double a。
inplace |
|
g********r
发帖数: 89 | 31 上Leetcode上看了一下，发现这题还有solution。
"One simple approach is a two-pass solution: First pass to split the string
by spaces into an array of words, then second pass to extract the words in
reversed order.
We can do better in one-pass. While iterating the string in reverse order,
we keep track of a word’s begin and end position. When we are at the
beginning of a word, we append it."
我的方法就是leetcode solution说的"one-pass" solution啊。时间复杂度是O(n), 空
间复杂度也是O(n).
大牛不妨说说更好的方法？
inplace reverse两边的话，不知道怎么处理中间的space？e... 阅读全帖 |
|
d******e
发帖数: 2265 | 32 string你不可能写inplace的。
要是非要上效率的。就是两个指针，从尾部读word,从头部读sperator.
char[] char_arr = new char[len(s)];
int i = len(s) -1;
int j = 0;
// read word from end and save to char_arr
while (i > -1 && j < len(s)){
// read word from end and save to char_arr reverse
// read separtor from begin and save to char_arr
}
return new StringBuilder(char_arr).toString() |
|
k**l
发帖数: 2966 | 33 我的brutal想法是建立三个pool
pool1: singles's position
pool2: misplaced pairs a->i1, j1; b->i2, j2,不相邻
pool3: inplaced pairs
目标消灭pool2，从a开始 i1 +/-1，j1+/-1位置可以放另一个a, 这四个位置里先看有
没有singles（pool1),有就换来；如果没有，看有没有其他misplace pairs (pool2);
最后再看pool3．用pool3里的元素会导致pool3减一又加一，得弄个从左到右的固定顺
序防止死循环． |
|
d*********e
发帖数: 352 | 34 楼主面的是前端。所以面经参考价值可能不大。
求问new grad package 大约如何，以及这公司是否还能去。。。
1. 提供大量的URL，批量输出这些页面上的merchant电话到file里
2. 实现首页上的search autocomplete 功能
3. 设计groupon的merchant、deal这两个class，以及数据库
4. 算法题很简单：
1） remove duplicate in array
2） remove duplicate in linked list
3) binary search
4) [1,3, 0, 2, 1, 0, 1], 把0移到所有数字后面，要求inplace和O(n)
5. 讲自己做过的project
6. 前端题：
1） 如何clear float
2） 如何improve performance
3） 如何做到真正的responsive
4） 什么是progressive enhancement
5） 什么是closure
6） 一些CSS/JS... 阅读全帖 |
|
c******g
发帖数: 238 | 35 要求的inplace会特别说，不说的都是随便儿用。 |
|
D**********d
发帖数: 849 | 36 解决思路：(a) 由 int[] （记为A) 求逆变换 int[] （记为B), 可以 inplace. (b)
由逆变换 int[] 直接输出变换前的数组。关键在 (a), 遍历一次 A 即可得 B (存在同
一位置). 方法如下:
void GetReverseIndex(int* A, int len) {
if (len <= 0) return;
int count = 0, old = 0;
while (count < len) {
int new = A[old];
int tmp = A[new];
A[new] = old;
old = tmp;
++count;
}
} |
|
l*********w
发帖数: 472 | 37 我感觉在非亚裔的情况下，公司给的bar再低，码农都不算性价比最高的，就算狗家
product manager不招人待见，但是我看我们学校的非亚裔几乎全是去当什么manager，
consultant的，毕竟人家特长不在这里。狗家来我这个学校模拟面试，我看声明构造函
数的时候，知道要写public，不要写int的，也就那么一两个。能知道java里面string
不能直接inplace操作的一个也没有。。。 |
|
t**********g
发帖数: 3388 | 38 【 以下文字转载自 JobHunting 讨论区 】
发信人: yinyueyouge (隐约有歌), 信区: JobHunting
标 题: Google Onsite归来，发面经攒RP求祝福
发信站: BBS 未名空间站 (Wed Sep 22 19:18:26 2010, 美东)
下午刚面完Google Mountain View，趁记忆还在，把经历写下来。
因为签署了NDA，所以不方便把题目直接贴在这里。只能说个大概。若是有兴趣的筒子
，可以私下交流。
早上10点半开始。面第一位阿三哥，开始侃项目，谈跟专业相关的东西，追问的很深，
最后还有15分钟的时候要求写代码，要求inplace对一个数据结构内的元素重新排序，
昏倒啊。在白板上画了简单的结构，讨论后获得首肯，然后开始写代码。
我把笔记本电脑带了过去，所以在键盘上敲。大概一会就写出来了。（若是在白板上写
，怎么死的都不知道阿）。然后三哥问，are you done？我说跑几个测试案例试试看。
然后在纸上写了5个案例，一行一行的检查。立马发现2个bug，更正之。三哥看到快没
时间了，说你跑这个案例试试。遂发现一个新的bug， |
|
b******n
发帖数: 4509 | 39 用 inplace test，速度直接超过 70c 了 |
|
r******r
发帖数: 700 | 40 谁能写个比较简洁的 inplace 算法。试了试，好像还挺费劲的 。。。 |
|
b*********n
发帖数: 1258 | 41 这个inplace sorting我知道
我想问的是那个class Ball如何初始化
谢谢 |
|
N****p
发帖数: 1691 | 42 一个C++的设计问题：
一个Class含有一个vector h，Constructor参数可能是空，然后Elem一个一个push进来
，也有可能是一个vector（可能很长，10^9）。
后一种情况要求In-place，前一种情况就要创建一个vector。
目前是把h定义为一个Reference，如下实现的，求建议和拍砖
MyHeap() : h(*(new std::vector())), hispassedin(false) {}
MyHeap(std::vector & _h): h(_h), hispassedin(true)
{
heapify_full(h);
}
~MyHeap(){if(!hispassedin) delete &h;}
private:
std::vector & h; // Note: This is a reference!
bool hispassedin; |
|
|
|
a***n
发帖数: 538 | 45 不是inplace的，就算doc位置不变，但是整个bsonobj还是要重新serialize，那块
mmap内存就要重写了，对应的disk也要重写。 |
|
s*i
发帖数: 5025 | 46 Quick sort 的精华部分还包括inplace的空间利用。
上述实现都忽略了
[发表自未名空间手机版 - m.mitbbs.com] |
|
|
e*******o
发帖数: 4654 | 48 你看来没用过mongo
postgres 只负责存储 简单query
这个缺点就是 你要干个啥 必须先把整个JSON读出来 如果要update 要在存进去
mongo 是inplace的 不需要读出来
你这一读一写 黄花菜都凉了
另外 postgres 哪有文件这个概念？ |
|
w*s
发帖数: 7227 | 49 Ok i found this code online, works fine except i want to see date in the
xlabel.
import numpy as np
import pandas
import matplotlib.pyplot as plt
from matplotlib.finance import candlestick, candlestick2
import matplotlib.dates as mdates
from pandas.io.data import DataReader
import datetime
# get daily stock price data from yahoo finance for S&P500
start = datetime.datetime(2015, 11, 1)
end = datetime.datetime(2016, 2, 11)
SP = DataReader("spy", "yahoo", start, end)
SP.reset_index(inplace=True)... 阅读全帖 |
|
w***g
发帖数: 5958 | 50 在语言层面可以做到纯函数。各种树都能做别说哈希表了。比如哈希表插入函数，输入
为哈希表和需要插入的对象，输出为一个*新的*哈希表。因为建了一个新的表，所以不
存在inplace
更新这个操作。但是从实现上，新表和老表通过reference共享了绝大部分内容，所以
空间代价还是O(1). 有点像docker用的那个洋葱文件系统。所有更新操作都通过包洋葱
实现。
一路摊过去。gc在背后收拾没用了的东西。
纯fp和imperative有点像数学上的对偶关系，本质是同一个东西，但表面上套路完全不
一样，没法直接翻译。比如插元素，它非要说是建新表，但背地里其实还是插元素。比
如算数列的一个元素，它非给你构造出一个无穷数列，到最后其实还是只算了一个元素
。说白了就是迂。
：Out of sight, out of mind? 而且我的问题是如何实现哈希表这种常用结构。
： |
|
