没有合适的资源?快使用搜索试试~ 我知道了~
首页MITBBS 面试题整理
MITBBS 面试题整理
5星 · 超过95%的资源 需积分: 9 12 下载量 30 浏览量
更新于2023-03-16
评论
收藏 1.71MB PDF 举报
MITBBS 面试题 整理,内容比较新,大家可以和国内的试题比较一下,还是有一定的难度的
资源详情
资源评论
资源推荐
知识类问题
1. 一个系统里面有多个线程, 其中一个线程想终止另外一个线程, 该怎么实现.
2. 为什么要用 virtual destructor
3. 什么是 heap corruption
4. Semaphore VS Mutex
5. C++中的 static, 怎么用,内存在哪里分配,等等
6. sizeof 一个指针和 sizeof 一个指针指向的空间有什么不同?
7. char* 和 char[]有什么区别?
8. 操作系统的 Page 是怎么做的?
9. 什么是 Thrashing
10. 什么是 volatileu 关键字? 在什么情况下需要使用?http://drdobbs.com/cpp/184403766
11. 什么是 critical section?
12. C++里面的 dynamic_cast 如何实现,为什么 dynamic_cast 要求被 cast 的指针指向的类
至少要有一个 virtual method?
13. virtual inheritance 为什么能够避免导出类中有多于一个的 virtual base class
的 copy?
14. deadlock's four condition
15. 关于 C++ 处理异常的方法
16. static 变量最大的问题是什么(考虑多线程)?
17. state Machine 的几种实现方法, 各自的优缺点是什么
18. 多线程程序里,你最喜欢哪种同步操作? Mutex 是大家用得最多的, 为什么?Mutex 有什么不好?
(overhead,serialize,deadlock), 给例子。如何避免这些坏处?(lock-free 算法, 比如 lock-free
的 queue,stack,hashtable)一般用什么办法来写 lock-free 算法?(用 CAS 等原子操作,等等), 如
何实现一个 lock-free 的 queue? (coding ?)
19. strlen(“hello”)=? , sizeof(“hello”)=?
20. 如果 main 函数只有如下结构
int main(…)
{
Try{…}
catch(){…}
}
并且这个 catch 语句 catch 了所有的 exception,但是这个程序还是 coredump 了,问可能是什么问题引
起的。
21. singleton, 多线程, 如何做 double check?
22. Command Pattern
23. 同步/异步 IO 和阻塞/非阻塞 IO 的区别?
24. 写一个 thread safe lazy initialization 的 singleton
25. Map Reduce 和 Multi-thread 的 trade-off
编程,数据结构,算法
1. 在 linked list 中找倒数第 N 个结点
Node* get_last_nth(Node* head, int n)
{
if (n < 1) return NULL;
Node* p1 = head;
Node* p2 = head;
while (p1 && n-- > 0) p1 = p1->next;
if (n > 0) return NULL;
while (p1)
{
p1 = p1->next;
p2 = p2->next;
}
return p2;
}
2. 倒转 linked list
void reverse_list(Node*& head)
{
Node* remain = head->next;
head->next = NULL;
while (remain)
{
Node* tmp = remain;
remain = remain->next;
tmp->next = head;
head = tmp;
}
}
3. 二叉树的结点有指向 parent 的指针,求最近公共祖先
TreeNode* search_tree_node_with_ancestors(TreeNode* root, int value, vector<TreeNode*>& ancestors)
{
if (root == NULL) return NULL;
if (root->value == value)
{
ancestors.push_back(root);
return root;
}
else
{
ancestors.push_back(root);
TreeNode* tn = search_tree_node_with_ancestors(root->left, value, ancestors);
if (tn != NULL) return tn;
tn = search_tree_node_with_ancestors(root->right, value, ancestors);
if (tn != NULL) return tn;
ancestors.pop_back();
return NULL;
}
}
TreeNode* find_lowest_common_ancestor(TreeNode* root, int val1, int val2)
{
vector<TreeNode*> ancestor1;
TreeNode* n1 = search_tree_node_with_ancestors(root, val1, ancestor1);
vector<TreeNode*> ancestor2;
TreeNode* n2 = search_tree_node_with_ancestors(root, val2, ancestor2);
int minLen = min(ancestor1.size(), ancestor2.size());
for (int i = 1; i < minLen; ++i)
{
if (ancestor1[i] != ancestor2[i])
return ancestor1[i-1];
}
return ancestor1.size() > ancestor2.size() ? ancestor2[minLen - 1] : ancestor2[minLen - 1];
}
int _tmain(int argc, _TCHAR* argv[])
{
int in_order[] = {6,2,7,1,5,3,4,8,9,10};
int pre_order[] = {5,2,6,1,7,4,3,9,8,10};
TreeNode* tree = create_tree(pre_order, in_order, 10);
TreeNode *tn = find_lowest_common_ancestor(tree, 7, 8);
tn = find_lowest_common_ancestor(tree, 7, 6);
tn = find_lowest_common_ancestor(tree, 7, 1);
tn = find_lowest_common_ancestor(tree, 4, 8);
tn = find_lowest_common_ancestor(tree, 3, 10);
return 0;
}
4. 给一个数组,如何打印该数组成员构成集合的全部子集合.
void _print_all_subset(const vector<int>& col, int i, vector<int>& output)
{
if (i >= col.size())
print_vector(output);
else
{
output.push_back(col[i]);
_print_all_subset(col, i+1, output);
output.pop_back();
_print_all_subset(col, i+1, output);
}
}
void print_all_subset(const vector<int>& col)
{
vector<int> output;
_print_all_subset(col, 0, output);
}
5. 有两个字符串,一个是 text,一个是 command, Command 有四种:
'+': 在 text 中前进一位
'-': 在 text 中后退一位
'a': 在当前位置插入一个字符,字符由 command 中的后一位决定
'd': 删除当前字符
实现函数 Process(string& text, string& command, string& result);
Coding 题,大致要点:
1. 扫描一遍 command,看看有多少加字符的 command,再建一个满足大小要求的临时数组,copy
text
2. 在临时数组上进行操作,注意插入和删除的复杂度都是 O(N)
6. 实现一个 LRU 的 cache
数据结构:
/// Typedef for URL/Entry pair
typedef std::pair< std::string, Entry > EntryPair;
/// Typedef for Cache list
typedef std::list< EntryPair > CacheList;
/// Typedef for URL-indexed map into the CacheList
typedef boost::unordered_map< std::string, CacheList::iterator > CacheMap;
/// Cache LRU list
CacheList mCacheList;
/// Cache map into the list
CacheMap mCacheMap;
插入新 cache 的算法:
3.
// create new entry
Entry iEntry( ... );
// push it to the front;
mCacheList.push_front( std::make_pair( aURL, iEntry ) );
// add it to the cache map
mCacheMap[ aURL ] = mCacheList.begin();
// increase count of entries
mEntries++;
// check if it's time to remove the last element
if ( mEntries > mMaxEntries )
{
// erease from the map the last cache list element
mCacheMap.erase( mCacheList.back().first );
// erase it from the list
mCacheList.pop_back();
// decrease count
mEntries--;
}
如果找到了,用 splice 函数将刚刚被访问的 CacheEntry 移到队首。
关于多线程,一般来说 reader/writer lock 不适用,因为 reader 也会更改 LRU cache. 一种解
决的办法是让每个线程拥有自己的 cache.
更多内容参考 http://www.bottlenose.demon.co.uk/article/lru.htm
7. 两个排序的数组,求它们的交集
vector<int> find_intersect(const vector<int>& v1, const vector<int>& v2)
{
int i = 0;
int j = 0;
vector<int> ret;
while (i < v1.size() && j < v2.size())
{
if (v1[i] == v2[j])
{
ret.push_back(v1[i]);
++i;++j;
}
else if (v1[i] > v2[j]) ++j;
else ++i;
}
return ret;
}
8. 在二叉树中添加额外的两个指针(树可能非满),遍历整棵树并将同一层的结点用这两个额外指针
连接起来
剩余74页未读,继续阅读
wowohei
- 粉丝: 0
- 资源: 5
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- c++校园超市商品信息管理系统课程设计说明书(含源代码) (2).pdf
- 建筑供配电系统相关课件.pptx
- 企业管理规章制度及管理模式.doc
- vb打开摄像头.doc
- 云计算-可信计算中认证协议改进方案.pdf
- [详细完整版]单片机编程4.ppt
- c语言常用算法.pdf
- c++经典程序代码大全.pdf
- 单片机数字时钟资料.doc
- 11项目管理前沿1.0.pptx
- 基于ssm的“魅力”繁峙宣传网站的设计与实现论文.doc
- 智慧交通综合解决方案.pptx
- 建筑防潮设计-PowerPointPresentati.pptx
- SPC统计过程控制程序.pptx
- SPC统计方法基础知识.pptx
- MW全能培训汽轮机调节保安系统PPT教学课件.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论3