title: 面試題總結(jié)
date: 2016-03-8 14:05:32
tags:
前言：整理下面試遇到的題，都是個(gè)人整理。不確定對(duì)錯(cuò)煞肾，僅供參考。
1 block在調(diào)用時(shí)嗓袱，變量的生命周期有哪幾種籍救？分別是什么樣的？
_NSConcreteStackBlock 保存在棧中的block渠抹，出棧時(shí)會(huì)被銷毀
_NSConcreteGlobalBlock 全局的靜態(tài)block蝙昙，不會(huì)訪問任何外部變量
_NSConcreteMallocBlock 保存在堆中的block，當(dāng)引用計(jì)數(shù)為0時(shí)會(huì)被銷毀
局部變量block塊被創(chuàng)建時(shí)梧却，block被保存到棧中（_NSConcreteStackBlock）奇颠。當(dāng)block作用域結(jié)束時(shí)，block會(huì)被釋放掉放航。
全局靜態(tài)變量blcok塊被創(chuàng)建時(shí)烈拒，blcok被保存到全局靜態(tài)block(_NSConcreteGlobalBlock)。
全局變量block塊被創(chuàng)建時(shí)，會(huì)被從棧上copy到堆上（_NSConcreteMallocBlock）荆几。包括__blcok修飾的對(duì)象吓妆。
感謝此博客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("一共計(jì)算%d次 \n", (len - 1) * 10 / 2);
for (int m = 0; m < (sizeof(a) / 4); m++) {
printf("%d \n", a[m]);
}
3 鏈表
1 單向鏈表
// 結(jié)構(gòu)體定義
struct ListNote
{
int m_nValue;
struct ListNote* m_pNext;
};
/**
* 添加一個(gè)節(jié)點(diǎn)
*
* @param pHead 結(jié)構(gòu)體 指針的指針
* @param value 結(jié)構(gòu)體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;
}
}
/**
* 刪除一個(gè)節(jié)點(diǎn)
*
* @param pHead 結(jié)構(gòu)體指針的指針
* @param value 結(jié)構(gòu)體value刪除的值
*/
void removeNode(ListNote **pHead, int value)
{
if (pHead == NULL || *pHead == NULL) {
return;
}
ListNote *deleteNote;
// 第一個(gè)結(jié)點(diǎn)m_nValue == value,deleteNote保留要?jiǎng)h除的指針*pHead诞吱，并將子結(jié)點(diǎn)指針賦值給要?jiǎng)h除的指針*pHead
if ((*pHead)->m_nValue == value) {
deleteNote = *pHead;
*pHead = (*pHead)->m_pNext;
} else {
ListNote *pNode = *pHead;
// 1 遍歷鏈表舟奠，判斷當(dāng)前結(jié)點(diǎn)的下個(gè)結(jié)點(diǎn)的m_nValue不等于value，等于就跳出循環(huán)房维。
while (pNode->m_pNext != NULL && pNode->m_pNext->m_nValue != value) {
pNode = pNode->m_pNext;
}
// 1 pNode有可能是中間的結(jié)點(diǎn)
// 2 pNode有可能是倒數(shù)第二個(gè)結(jié)點(diǎn)沼瘫。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;
}
}
/**
* 從尾到頭打印結(jié)點(diǎn)
*
* @param pHead 結(jié)構(gòu)體 指針的指針
*/
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?
// 插入節(jié)點(diǎn)到頭部
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
}
}
// 根據(jù)key獲取節(jié)點(diǎn)
func getNode(noteKey noteKey:String) -> FWLinkedMapNode? {
if let value = dic[noteKey] {
return value
}
return nil;
}
// 移動(dòng)節(jié)點(diǎn)到頭部
func bringNodeToHead(node node:FWLinkedMapNode) -> Void {
if node == firstNode {
return
}
if node == lastNode {
// 保留最后一個(gè)節(jié)點(diǎn)
lastNode = node.head
lastNode?.next = nil;
// 新node下個(gè)節(jié)點(diǎn)
node.next = firstNode;
// 第一個(gè)node上個(gè)節(jié)點(diǎn)（新節(jié)點(diǎn)）
firstNode?.head = node;
// 第一個(gè)新節(jié)點(diǎn)無上個(gè)節(jié)點(diǎn)
node.head = nil
// 保留第一個(gè)
firstNode = node;
} else {
node.head!.next = node.next
node.next!.head = node.head
// 第一個(gè)node上個(gè)節(jié)點(diǎn)（新節(jié)點(diǎn)）
firstNode!.head = node;
// 第一個(gè)新節(jié)點(diǎn)無上個(gè)節(jié)點(diǎn)
node.head = nil;
// 新node下個(gè)節(jié)點(diǎn)
node.next = firstNode;
// 保留第一個(gè)
firstNode = node
}
}
// 移除尾節(jié)點(diǎn)
func removeTailNode() -> Void {
dic[lastNode!.key!] = nil
lastNode = lastNode?.head;
}
// 移除所有節(jié)點(diǎn)
func removeAll() -> Void {
firstNode = nil;
lastNode = nil;
dic.removeAll()
}
}
4 二分查找算法
一次面試被問到如何從數(shù)組里快速找到某個(gè)值。傻呼呼的說for循環(huán)握巢，??晕鹊。
二分查找對(duì)數(shù)組要求是有序的排列松却，思路摘錄下此博客 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 查找的有序數(shù)組
* @param len 數(shù)組長(zhǎng)度
* @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用到了什么數(shù)據(jù)結(jié)構(gòu)和算法
據(jù)我所知 數(shù)據(jù)結(jié)構(gòu)：哈希表 算法：哈希算法暴浦。哈希算法是哈希算法的統(tǒng)稱，其中包括除于算法什么的晓锻。
6 快速排序
快速排序是對(duì)冒泡法排序的一種改進(jìn)歌焦。思想就是將數(shù)組看成左右2部分。以一個(gè)基準(zhǔn)數(shù)砚哆，一般是數(shù)組索引下標(biāo)為0的數(shù)独撇。如將小的扔到左邊，大的扔到右邊躁锁。并且移動(dòng)最大和最小索引變量纷铣，然后在重復(fù)排序數(shù)組左邊，右邊战转。最終得到有序數(shù)組搜立，就理解這么多，上代碼槐秧。
int partition(int arr[], int low, int high){
int key;
// 變量key
key = arr[low];
while(low<high){
// 數(shù)組右側(cè)與key比較啄踊，大于的話，左移high索引
while(low <high && arr[high]>= key ) {
high--;
}
// 右邊某值小于key刁标，賦值給key颠通。并low++
if(low<high)
arr[low++] = arr[high];
// 數(shù)組左側(cè)與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){
// 分割數(shù)組左右2部分硼控。
pos = partition(arr, start, end);
// 分割處理數(shù)組左部分
quick_sort(arr,start,pos-1);
// 分割處理數(shù)組右部分
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;
}
