title: 面试题总结
date: 2016-03-8 14:05:32
tags:
前言：整理下面试遇到的题，都是个人整理。不确定对错，仅供参考。
1 block在调用时，变量的生命周期有哪几种？分别是什么样的？
_NSConcreteStackBlock 保存在栈中的block，出栈时会被销毁
_NSConcreteGlobalBlock 全局的静态block，不会访问任何外部变量
_NSConcreteMallocBlock 保存在堆中的block，当引用计数为0时会被销毁
局部变量block块被创建时，block被保存到栈中（_NSConcreteStackBlock）。当block作用域结束时，block会被释放掉。
全局静态变量blcok块被创建时，blcok被保存到全局静态block(_NSConcreteGlobalBlock)。
全局变量block块被创建时，会被从栈上copy到堆上（_NSConcreteMallocBlock）。包括__blcok修饰的对象。
感谢此博客http://www.cocoachina.com/ios/20150106/10850.html
2 冒泡排序
上次面试被问到冒泡排序。工作中涉及到算法比较少，都忘记了。重新写下。
int a[]={2,7,5,100,200, 4, 50, 23, 9, 10};
int len = sizeof(a) / 4;
for (int i = 0; i < len; i++) {
for (int j = i + 1; j < len; j++) {
if (a[i] > a[j]) {
int tem = a[i];
a[i] = a[j];
a[j] = tem;
}
}
}
printf("一共计算%d次 \n", (len - 1) * 10 / 2);
for (int m = 0; m < (sizeof(a) / 4); m++) {
printf("%d \n", a[m]);
}
3 链表
1 单向链表
// 结构体定义
struct ListNote
{
int m_nValue;
struct ListNote* m_pNext;
};
/**
* 添加一个节点
*
* @param pHead 结构体 指针的指针
* @param value 结构体value值
*/
void addToTail(struct ListNote **pHead, int value)
{
struct ListNote *pNew = new ListNote();
pNew->m_nValue = value;
pNew->m_pNext = NULL;
if (*pHead == NULL) {
*pHead = pNew;
} else {
ListNote *pNode = *pHead;
while (pNode->m_pNext != NULL) {
pNode = pNode->m_pNext;
}
pNode->m_pNext = pNew;
}
}
/**
* 删除一个节点
*
* @param pHead 结构体指针的指针
* @param value 结构体value删除的值
*/
void removeNode(ListNote **pHead, int value)
{
if (pHead == NULL || *pHead == NULL) {
return;
}
ListNote *deleteNote;
// 第一个结点m_nValue == value,deleteNote保留要删除的指针*pHead，并将子结点指针赋值给要删除的指针*pHead
if ((*pHead)->m_nValue == value) {
deleteNote = *pHead;
*pHead = (*pHead)->m_pNext;
} else {
ListNote *pNode = *pHead;
// 1 遍历链表，判断当前结点的下个结点的m_nValue不等于value，等于就跳出循环。
while (pNode->m_pNext != NULL && pNode->m_pNext->m_nValue != value) {
pNode = pNode->m_pNext;
}
// 1 pNode有可能是中间的结点
// 2 pNode有可能是倒数第二个结点。pNode->m_pNext->m_pNext为NULL,赋值给pNode->m_pNext
if (pNode->m_pNext != NULL && pNode->m_pNext->m_nValue == value) {
deleteNote = pNode->m_pNext;
pNode->m_pNext = pNode->m_pNext->m_pNext;
}
}
// 销毁
if (deleteNote != NULL) {
delete(deleteNote);
deleteNote = NULL;
}
}
/**
* 从尾到头打印结点
*
* @param pHead 结构体 指针的指针
*/
void fromTailToHeadPrintf(ListNote *pHead)
{
if (pHead != NULL) {
if (pHead->m_pNext != NULL) {
fromTailToHeadPrintf(pHead->m_pNext);
}
}
printf("%i \n", pHead->m_nValue);
}
struct ListNote *noteList = new ListNote();
struct ListNote **noteList2 = ¬eList;
addToTail(noteList2, 5);
addToTail(noteList2, 6);
// printf("%i %i", noteList->m_nValue, noteList->m_pNext->m_nValue);
// removeNode(noteList2, 6);
fromTailToHeadPrintf(noteList);
// printf("%i %i", noteList->m_nValue, noteList->m_pNext->m_nValue);
2 双向链表
class FWLinkedMapNode: NSObject {
var key: String?
var value: String?
var head: FWLinkedMapNode?
var next: FWLinkedMapNode?
init(key:String, value:String) {
self.key = key;
self.value = value;
}
}
class FWLinkedMap: NSObject {
var dic = Dictionary<String, FWLinkedMapNode>()
var firstNode: FWLinkedMapNode?
var lastNode: FWLinkedMapNode?
// 插入节点到头部
func insertNoteAtHead(note note:FWLinkedMapNode) -> Void {
if let akey = note.key {
dic[akey] = note
}
if firstNode == nil {
firstNode = note
lastNode = note
} else {
firstNode?.head = note;
note.next = firstNode;
note.head = nil
firstNode = note
}
}
// 根据key获取节点
func getNode(noteKey noteKey:String) -> FWLinkedMapNode? {
if let value = dic[noteKey] {
return value
}
return nil;
}
// 移动节点到头部
func bringNodeToHead(node node:FWLinkedMapNode) -> Void {
if node == firstNode {
return
}
if node == lastNode {
// 保留最后一个节点
lastNode = node.head
lastNode?.next = nil;
// 新node下个节点
node.next = firstNode;
// 第一个node上个节点（新节点）
firstNode?.head = node;
// 第一个新节点无上个节点
node.head = nil
// 保留第一个
firstNode = node;
} else {
node.head!.next = node.next
node.next!.head = node.head
// 第一个node上个节点（新节点）
firstNode!.head = node;
// 第一个新节点无上个节点
node.head = nil;
// 新node下个节点
node.next = firstNode;
// 保留第一个
firstNode = node
}
}
// 移除尾节点
func removeTailNode() -> Void {
dic[lastNode!.key!] = nil
lastNode = lastNode?.head;
}
// 移除所有节点
func removeAll() -> Void {
firstNode = nil;
lastNode = nil;
dic.removeAll()
}
}
4 二分查找算法
一次面试被问到如何从数组里快速找到某个值。傻呼呼的说for循环，😄。
二分查找对数组要求是有序的排列，思路摘录下此博客 http://www.cnblogs.com/shuaiwhu/archive/2011/04/15/2065062.html
int main(int argc, const char * argv[]) {
int lists[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
int value = 9;
int result = binarySearch(lists, 10, value);
printf("result:%d", result);
return 0;
}
/**
* 二分查找算法
*
* @param lists 查找的有序数组
* @param len 数组长度
* @param value 查找的值
*
* @return 找到后的值
*/
int binarySearch(int *lists, int len , int value)
{
int low = 0;
int high = len - 1;
while (low <= high) {
int middle = (high - low) / 2 + low;
if (lists[middle] == value) {
return lists[middle];
}
// 左边
if (lists[middle] > value) {
high = middle - 1;
}
// 右边
else {
low = middle + 1;
}
}
return -1;
}
5 NSDictionary用到了什么数据结构和算法
据我所知 数据结构：哈希表 算法：哈希算法。哈希算法是哈希算法的统称，其中包括除于算法什么的。
6 快速排序
快速排序是对冒泡法排序的一种改进。思想就是将数组看成左右2部分。以一个基准数，一般是数组索引下标为0的数。如将小的扔到左边，大的扔到右边。并且移动最大和最小索引变量，然后在重复排序数组左边，右边。最终得到有序数组，就理解这么多，上代码。
int partition(int arr[], int low, int high){
int key;
// 变量key
key = arr[low];
while(low<high){
// 数组右侧与key比较，大于的话，左移high索引
while(low <high && arr[high]>= key ) {
high--;
}
// 右边某值小于key，赋值给key。并low++
if(low<high)
arr[low++] = arr[high];
// 数组左侧与key比较，小于的话，右移low索引
while( low<high && arr[low]<=key ) {
low++;
}
// 左边某值大于key,赋值给high索引。并且high左移索引
if(low<high)
arr[high--] = arr[low];
}
// low high索引相等，也是变量key的索引。
// 将key赋值给low
arr[low] = key;
return low;
}
void quick_sort(int arr[], int start, int end){
int pos;
if (start<end){
// 分割数组左右2部分。
pos = partition(arr, start, end);
// 分割处理数组左部分
quick_sort(arr,start,pos-1);
// 分割处理数组右部分
quick_sort(arr,pos+1,end);
}
return;
}
int main(int argc, char * argv[]) {
int i;
int arr[]={32,12,7, 78, 23,45};
int len = sizeof(arr) / 4;
printf("排序前 \n");
for(i=0;i<len;i++)
printf("%d\t",arr[i]);
printf ("\n");
quick_sort(arr,0,len-1);
printf("\n 排序后 \n");
for(i=0; i<len; i++)
printf("%d\t", arr[i]);
printf ("\n");
return 0;
}
