|
p*****2
发帖数: 21240 | 2
可能我理解错了。我以为先进行语法检查，再remove comments
你的意思是先remove comments再进行语法检查
难道remove comments这步没有现成的代码吗？还有为什么要求只扫一遍呢？ |
|
c******t
发帖数: 391 | 3 我的想法是用一个HashMap>, 先扫一次，然后找hash
value里的max(list.tail-list.head)。复杂度应该是O(n)…… |
|
w**********6
发帖数: 800 | 4 我的结果是782。。。
回家换了台电脑，稍改了一下，只扫奇数，现在是78s。准备用版上的方法继续优化。
PS：我用的是C @ CodeBlocks |
|
b****e
发帖数: 45 | 5 嗯，输出的时候比较麻烦，每行需要跟前一行比较，并且按照column order从左到右扫
描。从第一个不一样的column开始，分层逐个输出后面的所有column。 |
|
|
|
c********t
发帖数: 5706 | 8 第一题，两个指针i,j，一个从头，一个从尾扫，但是while里面要有两个子while来跳
过标点空格，然后还要再判断越界i
问一下先用regular expression把字符串标点空格删掉（只留A-Z,a-z,0-9)如何？比如
用java replaceAll，一句就可以删掉所有标点空格。剩下就没难度了。这样的解法会
被面试官认可吗？
还有空字符串算回文吗？
多谢。 |
|
c********t
发帖数: 5706 | 9 第二题A有没有重复字符？B有没有？如果都说是set,应该没有重复。你的解正确，而且
比面试官的好。
但既然他不允许（估计他不会），只好排序，用二分查找。
还有一种，就是两个都排序以后，两个指针一起扫A,B,每次输出比较小的值，并改变那
个指针，如果等值则不输出，两个指针一起增加。也是nlgn的复杂度。
总结, 你的面试官是个面瓜。 |
|
r*****e
发帖数: 792 | 10 来自主题: JobHunting版 - bb家电面 能解释一下怎么理解hashset 1就是解吗？能给个具体点的code吗？
最后输出的那部分就够了。
unordered_set 所有的key都是count为1啊。
如何能扫一遍就直接得到解的啊？
我不会java，所以不知道是不是java里的hashset 就可以有hashset 1. |
|
j********g
发帖数: 80 | 11 第二题 是不是把s按顺序扫一遍就行了， 我没理解错吧
bool find_substr(string si, string t){
int s_len=si.size();
int t_len=t.size();
int j=0;
for(int i=0; i
while(si[i]!=t[j] && j
j++;
if(j==t_len)
return false;
j++;
}
return true;
} |
|
j********g
发帖数: 80 | 12 第二题 是不是把s按顺序扫一遍就行了， 我没理解错吧
bool find_substr(string si, string t){
int s_len=si.size();
int t_len=t.size();
int j=0;
for(int i=0; i
while(si[i]!=t[j] && j
j++;
if(j==t_len)
return false;
j++;
}
return true;
} |
|
M********5
发帖数: 715 | 13 除了用一个map的structure, 建立一个原来数组长度的bitset，在遍历原来的数组的时
候，如果发现有相同的string存在过，就把原来的那个bit set为0，把新的bit set为1
，然后最后从头到尾扫一遍bitset，就可以得到最后的结果。不过这个提法跟你的提法
可能会适用于不同的地方，如果原数组的重复的string很少，可能这个会更好，因为
sorting一般会nlogn的时间，这个是线性的；不过如果重复的多的话，sorting会更划
算，比如如果10000个数组最后可能只有100个unique的，显然遍历一遍也要花10000，
但是sorting比这个快。 |
|
p*****2
发帖数: 21240 | 14
不错呀。LinkedHashMap我前不久还扫过一下，不过从来没用过，学习了。 |
|
l**b
发帖数: 457 | 15 没有背景也一样佩服，佩服的是做题的能力，不是在什么公司工作，做什么。哪怕是扫
大街的也一样佩服。 |
|
|
l**b
发帖数: 457 | 17 只是大哥比方，就没可能是扫大街的。我看过大牛的几个帖子，都很NB的说。 |
|
e*****r
发帖数: 93 | 18 第一题在树状数组里面有用，是标准做法，用做数多少个1的话，渐进复杂度和直接扫
一遍一样的。。。数多少个1有更快的做法 |
|
d****r
发帖数: 80 | 19
穷举。N个数的话，用N位的三进制。从0扫到最大值。0,1,2对应三个组。我这个方法实
际上没什么用。 |
|
f*****e
发帖数: 2992 | 20 先扫一遍，确定范围。然后分配一个这个范围大小的数组A。
每个数组元素，结构为：
{bool, Node *} bool记载这个点occupied or not。
然后创建一个Node链表B，每个Node存放起点和终点。
struct Node {
int start;
int end;
Node* next;
}
A的每一个occupied的元素指向B的一个元素。
当插入v到A的时候，如果A[v]已经occupied了就什么事也不做，如果A[v]没有occupied
并且A[v-1]或A[v+1]有一个已经occupied，就并入那个occupied的interval:A[v]=A[v-
1]或A[v]=A[v+1], 并且更新相应的B的start & end信息。如果A[v-1]和A[v+1]两个都
occupied，就合并两个B interval。如果两边都没有occupied，就加入一个新元素到B
。好想见到过或做过。 |
|
t*********n
发帖数: 89 | 21 先找出数组范围，然后用bitmap记录出现的数字，最后扫一遍bitmap得出区间。
这个类似与hash table. 问题是双向链表到底有什么用呢？ |
|
d**********x
发帖数: 4083 | 22 其实也不是不可以
如果链表只有两个元素，分别是INT_MAX和INT_MIN的话，你只要分配一个500M的数组就
行了
然后扫一遍这个500M的数组直接出结果 |
|
w****x
发帖数: 2483 | 23 一个是hash_table两边扫了，O(n)但是需要额外空间，
一个是链表的quick sort, 不需要空间但是nlogn |
|
|
|
p*****2
发帖数: 21240 | 26
对呀。两头扫不久可以了吗？又是two pointer |
|
p*****2
发帖数: 21240 | 27 看了一下。这题你怎么做的？
感觉扫两遍就可以了吧？第一遍算乘除，第二遍算加减。 |
|
y***x
发帖数: 22 | 28 写了个JavaScript的，想法跟二爷一开始的一样，扫两遍，一遍处理+-， 一遍处理*/
function getnum(str){
var n = str.split(/[+\-]+/);
var c = str.split(/[0-9\*\/]+/);
for(var i=0; i
n[i] = getmdnum(n[i]);
}
for(var j=0; j
n[j+1] = cal(n[j], n[j+1], c[j+1]);
}
return n[j];
}
function getmdnum(str){
var n = str.split(/[\*\/]/);
var c = str.split(/[0-9]+/);
if(n.length==1) return n[0]-0;
for(var i=0; i
... 阅读全帖 |
|
p*****2
发帖数: 21240 | 29 看了一下。这题你怎么做的？
感觉扫两遍就可以了吧？第一遍算乘除，第二遍算加减。 |
|
y***x
发帖数: 22 | 30 写了个JavaScript的，想法跟二爷一开始的一样，扫两遍，一遍处理+-， 一遍处理*/
function getnum(str){
var n = str.split(/[+\-]+/);
var c = str.split(/[0-9\*\/]+/);
for(var i=0; i
n[i] = getmdnum(n[i]);
}
for(var j=0; j
n[j+1] = cal(n[j], n[j+1], c[j+1]);
}
return n[j];
}
function getmdnum(str){
var n = str.split(/[\*\/]/);
var c = str.split(/[0-9]+/);
if(n.length==1) return n[0]-0;
for(var i=0; i
... 阅读全帖 |
|
p*****p
发帖数: 379 | 31 没太看懂你题目的意思，不过感觉不需要排序，开一个list装list1的interval，然后
扫2判断
O(m+n)，排序肯定超过这个 |
|
c********t
发帖数: 5706 | 32 为什么要开一个新的list来装list1? 扫2对应list1查询，最后难道不是O(m*n)吗？
interval tree好复杂，能40分钟写出来吗？ |
|
c********t
发帖数: 5706 | 33 直接用visited矩阵扫一遍不行吗？DP怎么解？ |
|
r******3
发帖数: 221 | 34 你这个visited矩阵不也是extra memory吗？
anyways,如果是square那么这道题是经典的DP题，解法如下：
建立一个dp[row][col]矩阵，
for (int i = 0; i < array.length; ++i)
dp[i][0] = array[i][0];
for (int j = 0; j < array[0].length; ++j)
dp[0][j] = array[0][j];
for (int i = 1; i < array.length; ++i) {
for (int j = 1; j < array[0].length; ++j) {
if (array[i][j] == 0)
dp[i][j] = 0;
else {
dp[i][j] = Math.min(Math.min(dp[i-1][j-1], dp[i-1][j]), dp[i][j-1])
+ 1;
}
}
}
然后扫一遍dp矩阵找到最大值，时空复杂度都是N^2。 |
|
Y********f
发帖数: 410 | 35 如果有顺序要求，如题目的例子，要求twitter 在good前面，good在tool前面，那么建
立一个数组，数组第i个元素是包含i+1的word的最近的位置。类似于dp
如果没有顺序要求，用set，set的每个元素是最近word的位置，每个word的位置只能出
现一个（扫面过程中，如果该word在set中已经有位置，先把它从set中删除）， set中
最大位置和最小位置的差就是当前的包含所有word的字符串的长度。 |
|
n****r
发帖数: 120 | 36 空格做token切词出来，然后hash，找公共的，然后再分别扫两个string，删除公共的
word就可以了吧 |
|
r*******6
发帖数: 99 | 37 求最大的质数怎么解，就是把数组扫一遍，判断当前元素是不是prime？ |
|
|
a******e
发帖数: 710 | 39 既然是2，那这个数组{A,B,Z,C,D}就跟{A,B,C,D,Z}一样喽？
那从左到右扫一遍可以么？ |
|
y****i
发帖数: 312 | 40 应该可以直接上bitmap吧。扫两遍就可以找到重复的电话号码了。 |
|
c******a
发帖数: 789 | 41 你说的是bitset吧？电话号码有10位，int32不够, 最少要扫3个pass。
还是trie最好。 |
|
n**m
发帖数: 122 | 42 我倒觉得国女可能是在照顾lz，用tree做思路不对，及时打断免得浪费时间
这题不用dp，线性扫一遍数组就够了 |
|
g**G
发帖数: 767 | 43 同问，如果用Priority queue的话，是不是得写个wrapper，把超出大小的就边扫边丢
掉了 |
|
w********g
发帖数: 106 | 44 店面之前首先了online test，所以店面只问了简历上的内容，问得很详细，包括具体
实现某一功能时用了哪些系统调用、函数名是什么、参数怎么设置、某些用到的系统文
件的具体路径，总之就是要确定我真的做过这些project。
店面前要求的online test有三道题，共90分钟，和leetcode类似要求编译运行，但是
不提供test case，只能自己输入，所以真的考验自己是否细心，比如overflow、空输
入之类的。
第一题不难：
给一个整形数组存储的是下一跳的位置，就像指针一样。
比如A[0]=2 A[1]=3 A[2]=1 A[3]=1 A[4]=3
就这么跳：0 2 1 3 1 3...，于是找到了一个长度为2的由1、3这两个元素组成loop。
题目就是输入这样的数组，返回loop长度。
要求O(N) time，O(1) space，其中N是数组长度。
第二题极简单：
给一个表示16进制数的字符串，返回这个数的二进制表示中有几个1.
例如，输入16进制字符串“1E”，它的二进制为“11110”，所以返回4。
要求O(N) time，O(1) space，其中N是字... 阅读全帖 |
|
w********g
发帖数: 106 | 45 就出了一道千年老题，我感觉还有时间，但是对方说结束吧 -- 预感不妙。
给两个已排序数组，要求返回他们的交集和并集。
我就用两个指针分别指向两个数组，从左向右扫一遍。
我也说了hash的方法。
对方又问能不能用merge的方法，我回答能，但是不觉得复杂度更低。 |
|
l******l
发帖数: 1088 | 46 递归下？
A,m,B,n
A中比B[0]小的和比B[n-1]大的不用扫了
然后继续merge
A+k1,m-k1,B+k2,n-k2 |
|
z****e
发帖数: 54598 | 47 楼主最开始给的是什么解法？
对方居然会问merge可以不可以？
估计一开始给的不是merge吧
是m*n的那种扫法吧？ |
|
z****e
发帖数: 54598 | 48 这只是一个很简单的考多线程基础的题
所以对方后面会说用lock，线性实现就足够了
Window类添加一个hashmap
记录每一个message进来的时间
然后实现put方法，需要找一个类来记录msg
还是hashmap吧，既然已经用了hashmap
然后实现get方法
get方法里面，先找
找到后做一个判断，是否当前时间超过5分钟
超过，则返回空，否则返回找到的值
然后关键是remove超过5分钟的msg
简单啊，启动一个scheduler线程，sleep(1000*60)
然后醒来后，扫一遍记录时间的hashmap
找到超时的msg，去记录msg的hashmap删除就好了
这里会有并发的问题，hashmap不是线程安全的
上java.util.concurrent
这就是所谓的efficiency的意思 |
|
T******e
发帖数: 157 | 49 感觉像堆箱子的题
先根据开始时间排个序，这样扫的时候就会有规律些 |
|
u*****o
发帖数: 1224 | 50 这个用swap应该可以做吧。碰到0就skip,非0的就一直swap，一直到它占在应该在的位
置上。再扫一遍，0在的位置就是被换掉的数。 |
|
