l******e
发帖数: 76 | 1 说有一个特别大的phone book，里面有好多电话号码，有些被占用，有些没被占用
写三个function，
第一个，给定号码，检查是否被占用
第二个，给定号码，标注其已经被占用
第三个，返回一个没有被占用的号码
要求复杂度
给出了hashtable的解法，但是第三个无法保证复杂度< O(n)
估计挂了
后来想了想，其实就是把10位的电话号码分成几段搜索，111-222-3333, 先搜索111,然
后222, 然后3333
这样直接跳过
可惜当时没想到用skip list |
s******x
发帖数: 417 | |
c******n
发帖数: 4965 | 3 你这个用 hash 里面每个值除了号码， 再记前后两个邻居， 就是把双链表跟hashmap
合起来
【在 l******e 的大作中提到】
: 说有一个特别大的phone book，里面有好多电话号码，有些被占用，有些没被占用
: 写三个function，
: 第一个，给定号码，检查是否被占用
: 第二个，给定号码，标注其已经被占用
: 第三个，返回一个没有被占用的号码
: 要求复杂度 : 给出了hashtable的解法，但是第三个无法保证复杂度< O(n)
: 估计挂了
: 后来想了想，其实就是把10位的电话号码分成几段搜索，111-222-3333, 先搜索111,然
: 后222, 然后3333
|
s*****e
发帖数: 1679 | |
S***w
发帖数: 1014 | 5 这个好复杂
【在 l******e 的大作中提到】
: 说有一个特别大的phone book，里面有好多电话号码，有些被占用，有些没被占用
: 写三个function，
: 第一个，给定号码，检查是否被占用
: 第二个，给定号码，标注其已经被占用
: 第三个，返回一个没有被占用的号码
: 要求复杂度 : 给出了hashtable的解法，但是第三个无法保证复杂度< O(n)
: 估计挂了
: 后来想了想，其实就是把10位的电话号码分成几段搜索，111-222-3333, 先搜索111,然
: 后222, 然后3333
|
S***w
发帖数: 1014 | |
S***w
发帖数: 1014 | 7 用hasmap + [可用区间]
假设号码有1， 2， 3，4
开始
hashmap []
可用区间: [1-4]
mark 2
hashmap: [2]
可用区间: [1-1, 3-4]
mark 1
hashmap: [1, 2]
可用区间: [3-4]
1.check, check hashmap O(1)
2. mark, insert hashmap O(1) + 更新 可用区间, < O(N)
3. search, 访问可用区间, O(1) |
P******r
发帖数: 1342 | 8 可以用trie吗？
插入和查找都快;
对于找空格，每个节点记录自己下面有多少个已经用过了，来快速找到空格 |
r****7
发帖数: 2282 | 9 电话号码的话，都是数字，用count sort的思路，binary search干这些事，最后复杂
度 > lgn 小于 n
【在 l******e 的大作中提到】
: 说有一个特别大的phone book，里面有好多电话号码，有些被占用，有些没被占用
: 写三个function，
: 第一个，给定号码，检查是否被占用
: 第二个，给定号码，标注其已经被占用
: 第三个，返回一个没有被占用的号码
: 要求复杂度 : 给出了hashtable的解法，但是第三个无法保证复杂度< O(n)
: 估计挂了
: 后来想了想，其实就是把10位的电话号码分成几段搜索，111-222-3333, 先搜索111,然
: 后222, 然后3333
|
l******e
发帖数: 76 | 10 这道题考我这样的new grad 是不是有点难了 |
|
|
y****z
发帖数: 52 | 11 你这个方法就是用两个HASHMAP 一个记录已经存在的 一个记录未存在的
所以这三个functions都是O(1) 空间O(N)
我想了一下 用trie最好
Class TrieNode{
boolean visited;
TrieNode[] children;
public TrieNode(){
visited=false;
children=new TrieNode[10];
}
}
插入的时候把该节点标记为visited
顺便记录父节点 然后扫描父节点下的所有子节点 如果都是visited就把父节点也标记
为visited
查找不说了
第三个方法的话就变成寻找一个visited=false的叶子就好了(假设号码10位数)
如果一个节点的visited=false 那么必然存在available的子节点
static class TrieNode{
boolean visited;
TrieNode[] children;
public TrieNode(){
visited=false;
children=new TrieNode[10];
}
}
private static TrieNode root;
private static int length;
public static void init(){
length=10;
root=new TrieNode();
}
public static void insert(String input){
char[] array=input.toCharArray();
TrieNode current=root;
TrieNode parent=null;
for(int i=0;i
int index=array[i]-'0';
if(current.children[index]==null){
current.children[index]=new TrieNode();
}
parent=current;
current=current.children[index];
}
current.visited=true;
for(int i=0;i<10;i++){
if(parent.children[i]==null||parent.children[i].visited==false){
return;
}
}
parent.visited=true;
}
public static boolean search(String input){
char[] array=input.toCharArray();
TrieNode current=root;
for(int i=0;i
int index=array[i]-'0';
if(current.children[index]==null){
return false;
}
current=current.children[index];
}
return current.visited;
}
public static String getOne(){
TrieNode current=root;
StringBuilder sb=new StringBuilder();
for(int i=0;i
TrieNode[] currentChildren=current.children;
for(int j=0;j
if(currentChildren[j]==null){
sb.append(j);
currentChildren[j]=new TrieNode();
current=currentChildren[j];
break;
}else if(currentChildren[j].visited==false){
sb.append(j);
current=currentChildren[j];
break;
}
}
}
// insert(sb.toString());
return sb.toString();
}
public static void main(String []args){
//System.out.println("Hello World");
init();
insert("1234567890");
insert("0987654321");
insert("0000000002");
System.out.println(search("1234567890"));
String newNum=getOne();
System.out.println(newNum);
insert(newNum);
System.out.println();
System.out.println(getOne());
insert(getOne());
System.out.println(getOne());
}
插入查找和第三个函数的复杂度为O(k) k为号码长度 接近于常数级别。
【在 S***w 的大作中提到】
: 用hasmap + [可用区间]
: 假设号码有1， 2， 3，4
: 开始
: hashmap []
: 可用区间: [1-4]
: mark 2
: hashmap: [2]
: 可用区间: [1-1, 3-4]
: mark 1
: hashmap: [1, 2]
|
w******n
发帖数: 61 | 12 可以用两个hashtable么。一个存已经占用的一个存还没占用的。
【在 l******e 的大作中提到】
: 说有一个特别大的phone book，里面有好多电话号码，有些被占用，有些没被占用
: 写三个function，
: 第一个，给定号码，检查是否被占用
: 第二个，给定号码，标注其已经被占用
: 第三个，返回一个没有被占用的号码
: 要求复杂度 : 给出了hashtable的解法，但是第三个无法保证复杂度< O(n)
: 估计挂了
: 后来想了想，其实就是把10位的电话号码分成几段搜索，111-222-3333, 先搜索111,然
: 后222, 然后3333
|
v*****y
发帖数: 68 | 13 电话号码位数是固定的10位？
O(n)的n指的是数据库里的号码数量？ |
z*******o
发帖数: 4773 | 14 haha, all O(1)
【在 w******n 的大作中提到】
: 可以用两个hashtable么。一个存已经占用的一个存还没占用的。
|
g******d
发帖数: 152 | 15 靠，有那么复杂吗？
< O(N) 有 O(lgN)
有没有插入删除，直接就来一个sorted array 就可以了
binary search |
x*****n
发帖数: 195 | 16 讲讲记录没有占用的hashtable怎么设计，不懂。。。
我想到的比较浪费的做法是用bloom filter检查某个号码用了没。
【在 w******n 的大作中提到】
: 可以用两个hashtable么。一个存已经占用的一个存还没占用的。
|
x*****n
发帖数: 195 | 17 这个不能保证寻找一个未使用号码的效率小于O（N）吧？沿着链表扫描的效率是O（N）
啊。
hashmap
【在 c******n 的大作中提到】
: 你这个用 hash 里面每个值除了号码， 再记前后两个邻居， 就是把双链表跟hashmap
: 合起来
|
n******n
发帖数: 12088 | 18 代码狂人。我要是面试的，印象肯定不好。太长了。
【在 y****z 的大作中提到】
: 你这个方法就是用两个HASHMAP 一个记录已经存在的 一个记录未存在的
: 所以这三个functions都是O(1) 空间O(N)
: 我想了一下 用trie最好
: Class TrieNode{
: boolean visited;
: TrieNode[] children;
: public TrieNode(){
: visited=false;
: children=new TrieNode[10];
: }
|
g*****c
发帖数: 106 | 19 第三个函数的复杂度worst case是10^k吧？要把所有的都试一遍。
【在 y****z 的大作中提到】
: 你这个方法就是用两个HASHMAP 一个记录已经存在的 一个记录未存在的
: 所以这三个functions都是O(1) 空间O(N)
: 我想了一下 用trie最好
: Class TrieNode{
: boolean visited;
: TrieNode[] children;
: public TrieNode(){
: visited=false;
: children=new TrieNode[10];
: }
|
w*****1
发帖数: 6807 | 20 不知道LZ所谓的O(n)里面的n到底指什么
n=10的话，我感觉好难啊，不像是电面的题
n=所有电话号码个数的话
下面这段代码不是O(n)吗？可能我想的太简单了，我也刚开始刷题，板上大牛多多
-------------------------------------
unordered_map phone_book;
int result;
for (auto x : phone_book) {
if (x.second == false) { // number have not used
result = x.first;
break;
}
}
cout << result << endl; |
|
|
l******e
发帖数: 76 | 21 要求小于O(n)
【在 w*****1 的大作中提到】
: 不知道LZ所谓的O(n)里面的n到底指什么
: n=10的话，我感觉好难啊，不像是电面的题
: n=所有电话号码个数的话
: 下面这段代码不是O(n)吗？可能我想的太简单了，我也刚开始刷题，板上大牛多多
: -------------------------------------
: unordered_map phone_book;
: int result;
: for (auto x : phone_book) {
: if (x.second == false) { // number have not used
: result = x.first;
|
w*****1
发帖数: 6807 | 22 那还真挺难的，估计是要求log(n)的复杂度
放狗搜了下，好像真的要用trie什么的来贮存电话本，这也太难了。。。
麻烦楼主知道答案的话，把代码写写呗，解释的那些看不太懂
【在 l******e 的大作中提到】
: 要求小于O(n)
|
y****z
发帖数: 52 | 23 晕 Trie其实写起来不复杂
要简单那就用两个hashmap咯
简单容易理解
【在 n******n 的大作中提到】
: 代码狂人。我要是面试的，印象肯定不好。太长了。
|
y****z
发帖数: 52 | 24 同学 你的复杂度没学好吧
两个for循环嵌套 如果k＝10
复杂度是O（10*10）
哪来的指数级别??
【在 g*****c 的大作中提到】
: 第三个函数的复杂度worst case是10^k吧？要把所有的都试一遍。
|
J*******o
发帖数: 741 | |
g*****c
发帖数: 106 | 26 不好意思先看错了 以为是dfs那种 每一步有10个选择 一共需要k步
【在 y****z 的大作中提到】
: 同学 你的复杂度没学好吧
: 两个for循环嵌套 如果k＝10
: 复杂度是O（10*10）
: 哪来的指数级别??
|
s********l
发帖数: 998 | 27 你这个O(n)只 电话长度 还是电话本长度啊？
【在 l******e 的大作中提到】
: 说有一个特别大的phone book，里面有好多电话号码，有些被占用，有些没被占用
: 写三个function，
: 第一个，给定号码，检查是否被占用
: 第二个，给定号码，标注其已经被占用
: 第三个，返回一个没有被占用的号码
: 要求复杂度 : 给出了hashtable的解法，但是第三个无法保证复杂度< O(n)
: 估计挂了
: 后来想了想，其实就是把10位的电话号码分成几段搜索，111-222-3333, 先搜索111,然
: 后222, 然后3333
|
