b***m
发帖数: 5987 | 1 面试题大家做着玩玩吧，其实也没什么，估计早就有人贴过了：
1、给定内存buffer的指针void *buffer以及size，实现malloc()和free()，对内存的
管理不允许使用动态数据块（任何长度未知、可扩展的数据类型）；
2、实现double pow(double x, int y)即x^y（或x**y）。 |
g*********e
发帖数: 14401 | 2 要考虑溢出吗
double pow(x,y){
if(y<0)
return 1.0/pow(x,-y);
if(y==0)
return x;
if(y==1)
return x;
double half=pow(x,y/2);
return half*half*(odd(y)?x:1);
} |
b***m
发帖数: 5987 | 3
没说考虑不考虑溢出，但是这个暂时不重要。
【在 g*********e 的大作中提到】
: 要考虑溢出吗
: double pow(x,y){
: if(y<0)
: return 1.0/pow(x,-y);
: if(y==0)
: return x;
: if(y==1)
: return x;
: double half=pow(x,y/2);
: return half*half*(odd(y)?x:1);
|
c***r
发帖数: 35 | 4 能不能再仔细说下第一题malloca & free？没看明白啊 |
q****m
发帖数: 177 | 5 这个malloc 和 free 怎么搞阿，感觉是底层的东西，我们能搞？ 就相当于能搞个
write, read, open 来？
【在 b***m 的大作中提到】
: 面试题大家做着玩玩吧，其实也没什么，估计早就有人贴过了：
: 1、给定内存buffer的指针void *buffer以及size，实现malloc()和free()，对内存的
: 管理不允许使用动态数据块（任何长度未知、可扩展的数据类型）；
: 2、实现double pow(double x, int y)即x^y（或x**y）。
|
b***m
发帖数: 5987 | 6 就是让你做内存管理，怎么合理分配那块buffer，碎片管理，等等。
【在 c***r 的大作中提到】
: 能不能再仔细说下第一题malloca & free？没看明白啊
|
b***m
发帖数: 5987 | 7 不能算底层吧，其实也是很算法的一个东西。大家看看算法书关于内存管理的章节就知
道了，核心问题是分配策略。
【在 q****m 的大作中提到】
: 这个malloc 和 free 怎么搞阿，感觉是底层的东西，我们能搞？ 就相当于能搞个
: write, read, open 来？
|
S********t
发帖数: 3431 | 8 就是freelist first fit best fit那些，话说这个是我当年onsite第一个面试的第一
道题目，做的还有些紧张。没想到这好几年后，这个题还没有被ban
【在 b***m 的大作中提到】
: 不能算底层吧，其实也是很算法的一个东西。大家看看算法书关于内存管理的章节就知
: 道了，核心问题是分配策略。
|
A****e
发帖数: 310 | 9 这个没看明白，能展开讲讲吗，谢谢：）
【在 S********t 的大作中提到】
: 就是freelist first fit best fit那些，话说这个是我当年onsite第一个面试的第一
: 道题目，做的还有些紧张。没想到这好几年后，这个题还没有被ban
|
s********k
发帖数: 6180 | 10 这个内存分配允许segmentation之类的吗？
【在 b***m 的大作中提到】
: 面试题大家做着玩玩吧，其实也没什么，估计早就有人贴过了：
: 1、给定内存buffer的指针void *buffer以及size，实现malloc()和free()，对内存的
: 管理不允许使用动态数据块（任何长度未知、可扩展的数据类型）；
: 2、实现double pow(double x, int y)即x^y（或x**y）。
|
|
|
e***s
发帖数: 799 | 11 写C#的人对内存管理一窍不通的说，楼主能不能提供一些资料看看啊？ |
b***m
发帖数: 5987 | 12 有一本书，Algorithm in C++，其中一章大概讲了一下。
【在 e***s 的大作中提到】
: 写C#的人对内存管理一窍不通的说，楼主能不能提供一些资料看看啊？
|
p*****2
发帖数: 21240 | 13 对内存的
管理不允许使用动态数据块（任何长度未知、可扩展的数据类型）
这时啥意思？ |
b***m
发帖数: 5987 | 14
就是说，你程序本身的内存使用也需要在buffer的范围呢，不能另开一个链表什么的来
管理内存信息。如果需要单开链表，必须在buffer中。
【在 p*****2 的大作中提到】
: 对内存的
: 管理不允许使用动态数据块（任何长度未知、可扩展的数据类型）
: 这时啥意思？
|
s********k
发帖数: 6180 | 15 我觉得意思就是不能调用其他内存分配API，完全自己做，不知道自己理解对不对。
实际主要功能就是alloc,split,free,merge,不知道这个算不算内存分配了
【在 p*****2 的大作中提到】
: 对内存的
: 管理不允许使用动态数据块（任何长度未知、可扩展的数据类型）
: 这时啥意思？
|
b***m
发帖数: 5987 | 16
基本就是这个意思，其实核心问题就是free block的管理和再分配，其它的都好说。
【在 s********k 的大作中提到】
: 我觉得意思就是不能调用其他内存分配API，完全自己做，不知道自己理解对不对。
: 实际主要功能就是alloc,split,free,merge,不知道这个算不算内存分配了
|
s********k
发帖数: 6180 | 17 O(n)还是要做到O(1)啊
【在 b***m 的大作中提到】
:
: 基本就是这个意思，其实核心问题就是free block的管理和再分配，其它的都好说。
|
p*****2
发帖数: 21240 | 18 感觉最简单就是double linkedlist吧。 |
b***m
发帖数: 5987 | 19 O(1)不太容易吧？
【在 s********k 的大作中提到】
: O(n)还是要做到O(1)啊
|
b***m
发帖数: 5987 | 20 嗯。但是大内存下怎么提高效率。
【在 p*****2 的大作中提到】
: 感觉最简单就是double linkedlist吧。
|
|
|
s********k
发帖数: 6180 | 21 分配可以做O(1),keep 一个free list。free要free那块直接addr到header，然后把
header里面的标志位改为free，然后把addr加到free list？不过这个办法的
fragementation很厉害,也没有merge的功能
【在 b***m 的大作中提到】
: O(1)不太容易吧？
|
C***U
发帖数: 2406 | 22 第一题可以用linked list么? node里面放block的内存首地址和大小。然后空闲的地址
用大小排好顺序。然后分配的时候binary search找最接近的?
【在 b***m 的大作中提到】
: 面试题大家做着玩玩吧，其实也没什么，估计早就有人贴过了：
: 1、给定内存buffer的指针void *buffer以及size，实现malloc()和free()，对内存的
: 管理不允许使用动态数据块（任何长度未知、可扩展的数据类型）；
: 2、实现double pow(double x, int y)即x^y（或x**y）。
|
s********k
发帖数: 6180 | 23 linked list 怎么做Binary search？
【在 C***U 的大作中提到】
: 第一题可以用linked list么? node里面放block的内存首地址和大小。然后空闲的地址
: 用大小排好顺序。然后分配的时候binary search找最接近的?
|
K*****k
发帖数: 430 | 24 第二题应该是用二进制来实现log(N)的乘方解法，可以扩展到log(N)求Fibnacci数列的
第N项(利用矩阵乘方)？
【在 b***m 的大作中提到】
: 面试题大家做着玩玩吧，其实也没什么，估计早就有人贴过了：
: 1、给定内存buffer的指针void *buffer以及size，实现malloc()和free()，对内存的
: 管理不允许使用动态数据块（任何长度未知、可扩展的数据类型）；
: 2、实现double pow(double x, int y)即x^y（或x**y）。
|
p*****2
发帖数: 21240 | 25
复杂度要求多高呀？这题应该Landy Wang来作
【在 b***m 的大作中提到】
: 嗯。但是大内存下怎么提高效率。
|
s********k
发帖数: 6180 | 26 double linkedlist是怎么做？一个linklist指向不同的块，然后其中每个节点有链接
这个块大小下的free 内存？类似linux buddy system?
【在 b***m 的大作中提到】
: 嗯。但是大内存下怎么提高效率。
|
