r*****e
发帖数: 792 | 1 来自主题: JobHunting版 - bb家电面 能解释一下怎么理解hashset 1就是解吗？能给个具体点的code吗？
最后输出的那部分就够了。
unordered_set 所有的key都是count为1啊。
如何能扫一遍就直接得到解的啊？
我不会java，所以不知道是不是java里的hashset 就可以有hashset 1. |
|
j********g
发帖数: 80 | 2 第二题 是不是把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 | 3 第二题 是不是把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 | 4 除了用一个map的structure, 建立一个原来数组长度的bitset，在遍历原来的数组的时
候，如果发现有相同的string存在过，就把原来的那个bit set为0，把新的bit set为1
，然后最后从头到尾扫一遍bitset，就可以得到最后的结果。不过这个提法跟你的提法
可能会适用于不同的地方，如果原数组的重复的string很少，可能这个会更好，因为
sorting一般会nlogn的时间，这个是线性的；不过如果重复的多的话，sorting会更划
算，比如如果10000个数组最后可能只有100个unique的，显然遍历一遍也要花10000，
但是sorting比这个快。 |
|
p*****2
发帖数: 21240 | 5
不错呀。LinkedHashMap我前不久还扫过一下，不过从来没用过，学习了。 |
|
l**b
发帖数: 457 | 6 没有背景也一样佩服，佩服的是做题的能力，不是在什么公司工作，做什么。哪怕是扫
大街的也一样佩服。 |
|
|
l**b
发帖数: 457 | 8 只是大哥比方，就没可能是扫大街的。我看过大牛的几个帖子，都很NB的说。 |
|
e*****r
发帖数: 93 | 9 第一题在树状数组里面有用，是标准做法，用做数多少个1的话，渐进复杂度和直接扫
一遍一样的。。。数多少个1有更快的做法 |
|
d****r
发帖数: 80 | 10
穷举。N个数的话，用N位的三进制。从0扫到最大值。0,1,2对应三个组。我这个方法实
际上没什么用。 |
|
f*****e
发帖数: 2992 | 11 先扫一遍，确定范围。然后分配一个这个范围大小的数组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 | 12 先找出数组范围，然后用bitmap记录出现的数字，最后扫一遍bitmap得出区间。
这个类似与hash table. 问题是双向链表到底有什么用呢？ |
|
d**********x
发帖数: 4083 | 13 其实也不是不可以
如果链表只有两个元素，分别是INT_MAX和INT_MIN的话，你只要分配一个500M的数组就
行了
然后扫一遍这个500M的数组直接出结果 |
|
w****x
发帖数: 2483 | 14 一个是hash_table两边扫了，O(n)但是需要额外空间，
一个是链表的quick sort, 不需要空间但是nlogn |
|
|
|
p*****2
发帖数: 21240 | 17
对呀。两头扫不久可以了吗？又是two pointer |
|
p*****2
发帖数: 21240 | 18 看了一下。这题你怎么做的？
感觉扫两遍就可以了吧？第一遍算乘除，第二遍算加减。 |
|
y***x
发帖数: 22 | 19 写了个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 | 20 看了一下。这题你怎么做的？
感觉扫两遍就可以了吧？第一遍算乘除，第二遍算加减。 |
|
y***x
发帖数: 22 | 21 写了个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 | 22 没太看懂你题目的意思，不过感觉不需要排序，开一个list装list1的interval，然后
扫2判断
O(m+n)，排序肯定超过这个 |
|
c********t
发帖数: 5706 | 23 为什么要开一个新的list来装list1? 扫2对应list1查询，最后难道不是O(m*n)吗？
interval tree好复杂，能40分钟写出来吗？ |
|
c********t
发帖数: 5706 | 24 直接用visited矩阵扫一遍不行吗？DP怎么解？ |
|
r******3
发帖数: 221 | 25 你这个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。 |
|
n****r
发帖数: 120 | 26 空格做token切词出来，然后hash，找公共的，然后再分别扫两个string，删除公共的
word就可以了吧 |
|
r*******6
发帖数: 99 | 27 求最大的质数怎么解，就是把数组扫一遍，判断当前元素是不是prime？ |
|
|
a******e
发帖数: 710 | 29 既然是2，那这个数组{A,B,Z,C,D}就跟{A,B,C,D,Z}一样喽？
那从左到右扫一遍可以么？ |
|
y****i
发帖数: 312 | 30 应该可以直接上bitmap吧。扫两遍就可以找到重复的电话号码了。 |
|
c******a
发帖数: 789 | 31 你说的是bitset吧？电话号码有10位，int32不够, 最少要扫3个pass。
还是trie最好。 |
|
n**m
发帖数: 122 | 32 我倒觉得国女可能是在照顾lz，用tree做思路不对，及时打断免得浪费时间
这题不用dp，线性扫一遍数组就够了 |
|
g**G
发帖数: 767 | 33 同问，如果用Priority queue的话，是不是得写个wrapper，把超出大小的就边扫边丢
掉了 |
|
w********g
发帖数: 106 | 34 店面之前首先了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 | 35 就出了一道千年老题，我感觉还有时间，但是对方说结束吧 -- 预感不妙。
给两个已排序数组，要求返回他们的交集和并集。
我就用两个指针分别指向两个数组，从左向右扫一遍。
我也说了hash的方法。
对方又问能不能用merge的方法，我回答能，但是不觉得复杂度更低。 |
|
l******l
发帖数: 1088 | 36 递归下？
A,m,B,n
A中比B[0]小的和比B[n-1]大的不用扫了
然后继续merge
A+k1,m-k1,B+k2,n-k2 |
|
z****e
发帖数: 54598 | 37 楼主最开始给的是什么解法？
对方居然会问merge可以不可以？
估计一开始给的不是merge吧
是m*n的那种扫法吧？ |
|
z****e
发帖数: 54598 | 38 这只是一个很简单的考多线程基础的题
所以对方后面会说用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 | 39 感觉像堆箱子的题
先根据开始时间排个序，这样扫的时候就会有规律些 |
|
u*****o
发帖数: 1224 | 40 这个用swap应该可以做吧。碰到0就skip,非0的就一直swap，一直到它占在应该在的位
置上。再扫一遍，0在的位置就是被换掉的数。 |
|
u*****o
发帖数: 1224 | 41 扫两遍吧，第一遍swap，第二遍找0.。
的确说清楚不容易啊。。 |
|
u*****o
发帖数: 1224 | 42 那不是0的话是不是就是雷呢？ 可是它还是会打开自己。我的意思是说，它并没有说明
如果扫到了雷怎么办。他这样不是打开自己，就打开周围，最后肯定会全部打开的啊。 |
|
|
d*****d
发帖数: 180 | 44 第一个我得初步想法是先扫一遍T，把每个字母的位置记录下来，存到一个List array,
List [] x=List[26];
x[i]是个List, i是字母-'a'得到的0-25，List里是i代表的字母出现在T中的
所有坐标，扫描完应该是排好序的，从小到大。
然后依次在X查询Sj中每个字母，如果x[Sj-'a']存在，选最小的，但要大于前一次选的
位置，依次类推。。
for(s:S)
{
int start=-1;
boolean valid=true;
for(int j=0;j
{
int idx=s.charAt(i)-'a';
List list=x.get[idx];
if (list==null) {valid=false;break;}
int idx=getMin(list, start);
if (idx<0) {valid=false;break;}
start=idx;
}
}
---
int g... 阅读全帖 |
|
s*w
发帖数: 729 | 45 这个第二题解的很棒，我记得在哪里看过一个差点的解法：先 merge 同时加一个标签
，然后再扫一遍，看相邻标签是否不一样
一个表很长，另一个很短的情况下，似乎该用 hash table（或者 bloom filter , 如
果能容忍少量错误） 存短表，扫描长表。有没有更好的办法？
第三题估计不是要求查表，是手动找规律 |
|
l*****n
发帖数: 199 | 46 我是以精确到秒的思想解题的，用size 300的array存次数和上次的hit 时间，然后用
时间time%300来找到对应的index,如果发现上次时间超过了一秒就重新计数0，然后
getHits()就把array 扫一遍加起来。 面试官蛮满意的，但是followup 没答很好，先
让我写unit test测试,然后再讨论如何concurrent. |
|
l*****n
发帖数: 199 | 47 我是以精确到秒的思想解题的，用size 300的array存次数和上次的hit 时间，然后用
时间time%300来找到对应的index,如果发现上次时间超过了一秒就重新计数0，然后
getHits()就把array 扫一遍加起来。 面试官蛮满意的，但是followup 没答很好，先
让我写unit test测试,然后再讨论如何concurrent. |
|
b*********n
发帖数: 1258 | 48 可以在300个counter的同时，再用300个timestamp，把counter and timestamp它们放
到同一个slot
getHit 的时候，把这300个slot加一遍，就可以了
300个slot扫一边，应该很快。
我觉得这个逻辑比较简单。
不知道是否忽略了什么问题。
import java.util.Date;
class Solution {
public static void main(String[] args) throws InterruptedException {
Answer ans = new Answer();
ans.hit();
ans.hit();
ans.hit();
Thread.sleep(1000);
ans.hit();
ans.hit();
System.out.println(ans.getHit());
}
}
class Answer {
Item[] buffer;
... 阅读全帖 |
|
c*******i
发帖数: 160 | 49 unicode不能直接brute force 扫吗？ |
|
c*******i
发帖数: 160 | 50 unicode不能直接brute force 扫吗？ |
|
