w**h
发帖数: 34 | 1 老印
自我介绍；
Coding: Integer数组，先升序后降序，例如：1,3,5,9,15,10,9,7,5，找出最大元素；
设计Least Recently Used Cache；
什么是abstract class;
什么是singleton pattern, 如何实现；
什么是Model-View-Controller pattern. |
s******n
发帖数: 3946 | 2 第一题，2分法查找
第二题，DoubleLinkedList + Hashtable |
p*****2
发帖数: 21240 | |
l*****a
发帖数: 14598 | 4 假定你访问过一些item,设计数据结构使得每次新读入一个item，
你可以判断是否已经访问过，已经访问过的话，更新他的访问顺序
新则插入
只能保存一定数目的item,如果到上限了
删掉访问时间距离现在最久的
【在 p*****2 的大作中提到】
: 第二题什么意思呀？
|
m**q
发帖数: 189 | 5 第一题大概是:
int find_max(int a[], int n)
{
ASSERT(n>0);
int i = 0, j = n-1;
while (i < j) {
int mid = i + (j - i + 1)/2;
if (mid == 0 || a[mid] >= a[mid-1])
i = mid;
else
j = mid-1;
}
return j;
}
【在 s******n 的大作中提到】
: 第一题，2分法查找
: 第二题，DoubleLinkedList + Hashtable
|
p*****2
发帖数: 21240 | 6
多谢。这样的话，用个数组代替双向链表应该也够用了。
【在 l*****a 的大作中提到】
: 假定你访问过一些item,设计数据结构使得每次新读入一个item，
: 你可以判断是否已经访问过，已经访问过的话，更新他的访问顺序
: 新则插入
: 只能保存一定数目的item,如果到上限了
: 删掉访问时间距离现在最久的
|
l*****a
发帖数: 14598 | 7 数组的插入删除比较麻烦吧
【在 p*****2 的大作中提到】
:
: 多谢。这样的话，用个数组代替双向链表应该也够用了。
|
s******n
发帖数: 3946 | 8 看不懂if (mid==0 || ...)什么意思，这样是不是更清楚？
int find_max(int a[], int n)
{
ASSERT(n>0);
int i = 0, j = n-1;
while (i < j-1) {
int mid = (i + j)/2;
ASSERT(mid>i && mid
if (a[mid-1] < a[mid] && a[mid]
i = mid;
} else if (a[mid-1] > a[mid] && a[mid]>a[mid+1]) {
j = mid;
} else if (a[mid-1] < a[mid] && a[mid]>a[mid+1]) {
return mid;
} else {
//如果a[mid]==a[mid-1], etc.则输入数据不对
return -1;
}
}
return -1;
}
【在 m**q 的大作中提到】
: 第一题大概是:
: int find_max(int a[], int n)
: {
: ASSERT(n>0);
: int i = 0, j = n-1;
:
: while (i < j) {
: int mid = i + (j - i + 1)/2;
: if (mid == 0 || a[mid] >= a[mid-1])
: i = mid;
|
p*****2
发帖数: 21240 | 9
可以simulate 双向链表。满了之后把新的element copy 到 last element, 然后改改
指针。
【在 l*****a 的大作中提到】
: 数组的插入删除比较麻烦吧
|
s******n
发帖数: 3946 | 10 有个小问题mid == 0 是多余的检查，因为0<=i
这个效率比我前面写的那个高，跳过了不少validation
【在 m**q 的大作中提到】
: 第一题大概是:
: int find_max(int a[], int n)
: {
: ASSERT(n>0);
: int i = 0, j = n-1;
:
: while (i < j) {
: int mid = i + (j - i + 1)/2;
: if (mid == 0 || a[mid] >= a[mid-1])
: i = mid;
|
|
|
n*******w
发帖数: 687 | 11 还是选双向链表好。
有几个好处：
动态大小。空间紧张的时候特别需要这一点，用多少申请多少空间；
插入删除快；
配合hashtable，查找也快。
【在 p*****2 的大作中提到】
:
: 可以simulate 双向链表。满了之后把新的element copy 到 last element, 然后改改
: 指针。
|
p*****2
发帖数: 21240 | 12
看这个问题保存最近的element, 那应该空间不会太大吧？而且一般都处于满的状态吧
？（当然如果不是这样那用链表没话说）
插入删除的话，数组也可以一样是O(1）呀
用数组也要配合hashtable
数组有一个好处就是不用反复new和delete。heap 操作也是很耗时的。
【在 n*******w 的大作中提到】
: 还是选双向链表好。
: 有几个好处：
: 动态大小。空间紧张的时候特别需要这一点，用多少申请多少空间；
: 插入删除快；
: 配合hashtable，查找也快。
|
m**q
发帖数: 189 | 13 我写完了看了看也觉得是多余的，但总觉得还是写上放心点;)
【在 s******n 的大作中提到】
: 有个小问题mid == 0 是多余的检查，因为0<=i: 这个效率比我前面写的那个高，跳过了不少validation
|
s******n
发帖数: 3946 | 14 双向表不需要反复new/delete，在置换的时候把新value复制到老value所在的
LinkListNode上。
【在 p*****2 的大作中提到】
:
: 看这个问题保存最近的element, 那应该空间不会太大吧？而且一般都处于满的状态吧
: ？（当然如果不是这样那用链表没话说）
: 插入删除的话，数组也可以一样是O(1）呀
: 用数组也要配合hashtable
: 数组有一个好处就是不用反复new和delete。heap 操作也是很耗时的。
|
z******t
发帖数: 59 | 15 Coding: Integer数组，先升序后降序，例如：1,3,5,9,15,10,9,7,5，找出最大元素；
这题的详细解答见博客：
http://codercareer.blogspot.com/2011/11/no-22-turning-number-in |
j********x
发帖数: 2330 | |
