面试题目大赏

1. 虚拟内存

虚拟内存是计算机系统内存管理的一种技术。它使得应用程序认为它拥有连续可用的内存（一个连续完整的地址空间），而实际上，它通常是被分隔成多个物理内存碎片，还有部分暂时存储在外部磁盘存储器上，在需要时进行数据交换。

2. MFC消息机制

//.h文件
#pragma once

#include <windows.h>
#include <atltypes.h>
#include <tchar.h>

//资源ID
#define ID_BUTTON_DRAW      1000
#define ID_BUTTON_SWEEP     1001

// 注册窗口类
ATOM AppRegisterClass(HINSTANCE hInstance);
// 初始化窗口
BOOL InitInstance(HINSTANCE, int);
// 消息处理函数(又叫窗口过程)
LRESULT CALLBACK    WndProc(HWND, UINT, WPARAM, LPARAM);
// (白色背景)按钮事件
void OnButtonWhite();
// (灰色背景)按钮事件
void OnButtonGray();
// 绘制事件
void OnDraw(HDC hdc);

//.cpp文件
#include "stdafx.h"
#include "Win32Test.h"


//字符数组长度
#define MAX_LOADSTRING 100

//全局变量
HINSTANCE hInst;                                            // 当前实例
TCHAR g_szTitle[MAX_LOADSTRING] = TEXT("Message process");  // 窗口标题
TCHAR g_szWindowClass[MAX_LOADSTRING] = TEXT("AppTest");    // 窗口类的名称
HWND g_hWnd;                                                // 窗口句柄
bool g_bWhite = false;                                      // 是否为白色背景

//WinMain入口函数
int APIENTRY _tWinMain(HINSTANCE hInstance, HINSTANCE hPrevInstance, LPTSTR lpCmdLine, int nCmdShow)
{
    UNREFERENCED_PARAMETER(hPrevInstance);
    UNREFERENCED_PARAMETER(lpCmdLine);
    // 注册窗口类
    if(!AppRegisterClass(hInstance))
    {
         return (FALSE);
    }
    // 初始化应用程序窗口
    if (!InitInstance (hInstance, nCmdShow))
    {
        return FALSE;
    }

    // 消息循环
    MSG msg;
    while (GetMessage(&msg, NULL, 0, 0))
    {
        TranslateMessage(&msg);
        DispatchMessage(&msg);
    }
    return (int) msg.wParam;
}



// 注册窗口类
ATOM AppRegisterClass(HINSTANCE hInstance)
{
    WNDCLASSEX wcex;
    wcex.cbSize = sizeof(WNDCLASSEX);
    wcex.style          = CS_HREDRAW | CS_VREDRAW;
    wcex.lpfnWndProc    = WndProc;
    wcex.cbClsExtra     = 0;
    wcex.cbWndExtra     = 0;
    wcex.hInstance      = hInstance;
    wcex.hIcon          = LoadIcon(NULL, IDI_APPLICATION);
    wcex.hCursor        = LoadCursor(NULL, IDC_ARROW);
    wcex.hbrBackground  = (HBRUSH)(COLOR_WINDOW+1);
    wcex.lpszMenuName   = NULL;
    wcex.lpszClassName  = g_szWindowClass;
    wcex.hIconSm        = NULL;

    return RegisterClassEx(&wcex);
}



// 保存实例化句柄并创建主窗口
BOOL InitInstance(HINSTANCE hInstance, int nCmdShow)
{  
   hInst = hInstance; // 保存handle到全局变量
   g_hWnd = CreateWindow(g_szWindowClass, g_szTitle, WS_OVERLAPPEDWINDOW, 0, 0, 400, 300, NULL, NULL, hInstance, NULL);
   // 创建按钮
   HWND hBtWhite = CreateWindowEx(0, L"Button", L"白色", WS_CHILD | WS_VISIBLE | BS_TEXT, 100, 100, 50, 20, g_hWnd, (HMENU)ID_BUTTON_DRAW, hInst, NULL);
   HWND hBtGray = CreateWindowEx(0, L"Button", L"灰色", WS_CHILD | WS_VISIBLE | BS_CENTER, 250, 100, 50, 20, g_hWnd, (HMENU)ID_BUTTON_SWEEP, hInst, NULL);

   if (!g_hWnd)
   {
      return FALSE;
   }
   ShowWindow(g_hWnd, nCmdShow);
   UpdateWindow(g_hWnd);

   return TRUE;
}



// (窗口)消息处理
LRESULT CALLBACK WndProc(HWND hWnd, UINT message, WPARAM wParam, LPARAM lParam)
{
    int wmId, wmEvent;
    PAINTSTRUCT ps;
    HDC hdc;

    switch (message)
    {
    case WM_COMMAND:
        wmId    = LOWORD(wParam);
        //wmEvent = HIWORD(wParam);

        switch (wmId)
        {
        case ID_BUTTON_DRAW:
            OnButtonWhite();
            break;
        case ID_BUTTON_SWEEP:
            OnButtonGray();
            break;
        default:
            return DefWindowProc(hWnd, message, wParam, lParam);
        }
        break;
    case WM_PAINT:
        hdc = BeginPaint(hWnd, &ps);
        OnDraw(hdc);
        EndPaint(hWnd, &ps);
        break;
    case WM_DESTROY:
        PostQuitMessage(0);
        break;
    default:
        return DefWindowProc(hWnd, message, wParam, lParam);
    }
    return 0;
}



//事件处理

//按下hBtWhite时的事件
void OnButtonWhite()
{
    g_bWhite = true;
    InvalidateRect(g_hWnd, NULL, FALSE);    //刷新窗口
}

//按下hBtGray时的事件
void OnButtonGray()
{
    g_bWhite = false;
    InvalidateRect(g_hWnd, NULL, FALSE);    //刷新窗口
}

//绘制事件(每次刷新时重新绘制图像)
void OnDraw(HDC hdc)
{   
    POINT oldPoint;
    SetViewportOrgEx(hdc, 0, 0, &oldPoint);
    RECT rcView;
    GetWindowRect(g_hWnd, &rcView); // 获得句柄的画布大小
    HBRUSH hbrWhite = (HBRUSH)GetStockObject(WHITE_BRUSH);
    HBRUSH hbrGray = (HBRUSH)GetStockObject(GRAY_BRUSH);
    if (g_bWhite)
    {
        FillRect(hdc, &rcView, hbrWhite);
    } else
    {
        FillRect(hdc, &rcView, hbrGray);
    }
    SetViewportOrgEx(hdc, oldPoint.x, oldPoint.y, NULL);
}

RegisterClassEx的作用是注册一个窗口，在调用CreateWindow创建一个窗口前必须向windows系统注册获惟一的标识。

TranslateMessage函数

函数功能描述:将虚拟键消息转换为字符消息。字符消息被送到调用线程的消息队列中，在下一次线程调用函数GetMessage或PeekMessage时被读出。

DispatchMessage函数

函数功能：该函数调度一个消息给窗口程序。通常调度从GetMessage取得的消息。消息被调度到的窗口程序即是MainProc()函数。

这个while循环就是消息循环，不断地从消息队列中获取消息，并通过DispatchMessage(&msg)将消息分发出去。消息队列是在Windows操作系统中定义的(我们无法看到对应定义的代码)，对于每一个正在执行的Windows应用程序,系统为其建立一个“消息队列”，即应用程序队列，用来存放该程序可能创建的各种窗口的消息。DispatchMessage会将消息传给窗口函数(即消息处理函数)去处理，也就是WndProc函数。WndProc是一个回调函数，在注册窗口时通过wcex.lpfnWndProc将其传给了操作系统，所以DispatchMessage分发消息后，操作系统会调用窗口函数(WndProc)去处理消息。
每一个窗口都应该有一个函数负责消息处理，程序员必须负责设计这个所谓的窗口函数WndProc。LRESULT CALLBACK WndProc(HWND hWnd, UINT message, WPARAM wParam, LPARAM lParam) 中的四个参数就是消息的相关信息(消息来自的句柄、消息类型等)，函数中通过switch/case根据不同的消息类型分别进行不同的处理。在收到相应类型的消息之后，可调用相应的函数去处理，如OnButtonWhite、OnButtonGray、OnDraw，这就是事件处理的雏形。 在default中调用了DefWindowProc，DefWindowProc是操作系统定义的默认消息处理函数，这是因为所有的消息都必须被处理，应用程序不处理的消息需要交给操作系统处理。

PostMessage与SendMessage的区别

PostMessage发送的消息是队列消息，它会把消息Post到消息队列中； SendMessage发送的消息是非队列消息， 被直接送到窗口过程处理，等消息被处理后才返回。

 

区别：

PeekMessage：有消息时返回TRUE，没有消息返回FALSE   

GetMessage：有消息时且消息不为WM_QUIT时返回TRUE，如果有消息且为WM_QUIT则返回FALSE，没有消息时不返回。

GetMessage：取得消息后，删除除WM_PAINT消息以外的消息。

PeekMessage：取得消息后，根据wRemoveMsg参数判断是否删除消息。PM_REMOVE则删除，PM_NOREMOVE不删除。

Invalidate和UpdateWindow函数

1.Invalidate()是强制系统进行重画，但是不一定就马上进行重画。因为Invalidate()只是通知系统，此 时的窗口已经变为无效。强制系统调用WM_PAINT，而这个消息只是Post就是将该消息放入消息队列。当执行到WM_PAINT消息时才会对敞口进行重绘;
UpdateWindow只向窗体发送WM_PAINT消息，在发送之前判断GetUpdateRect(hWnd,NULL,TRUE)看有无可绘制的客户区域，如果没有，则不发送WM_PAINT;
当调用Invalidate之后，屏幕不一定马上更新，因为WM_PAINT消息不一定在队列头部，而调用UpdateWindow会使WM_PAINT消息马上执行的，绕过了消息队列;
如果调用Invalidate之后想马上更新屏幕，那就加上UpdateWindow()这条语句

2.Invalidate()使窗口客户区无效，并向消息队列中寄送一个WM_PAINT消息，假如此时消息队列中没有要处理的其他消息，则此时窗口立即会重绘（因为WM_PAINT会立即得到处理），如果消息队列中有其他消息，那么WM_PAINT就排队等呗。。。。这样就可能会存在一个不能即时刷新窗口的问题；
UpdateWindow（）绕过消息队列（不进队），直接向窗口客户区发送WM_PAINT消息，使得窗口立即更新。

3.单独的Invalidate(); 在窗口要重绘时用
和Invalidate();UpdateWindow();通常在程序开始时用

4.要注意UpdateWindow()和 UpdateData()的区别

UpdateData()一般是更新编辑框中的数据，

而UpdateWindow()是更新整个窗口。

3. 回调函数

1. 既然是函数的参数，就具备了扩展性和代码重用的作用，因为形参不变，实参是可变的。所以调用时，可以A(x,y,B)，也可以A(x,y,C)，这里B和C都是回调函数，有点像虚函数。（B和C可以实现不同的功能，或以不同的方式实现）

----场景：代码重用。A(x, y, isGreater), A(x, y , isSmaller)

2. 在定义A()时，甚至不需要知道实际的被调函数的名字，只要知道这个接口的格式，即参数，返回值，实现功能。所以甚至在确定被调函数如何实现之前，只要约定好接口和功能，就可以进行A()的定义工作。（实现相同的功能）

----场景：框架编程，并行工作。业务流程步骤编排（不管具体实现）。

A(bool * f())

假设一个场景：

老师给学生布置了作业，学生收到作业后开始写作业，写完之后通知老师查看，老师查看之后就可以回家。

回调的概念，在这里面就体现的淋漓尽致，在这里面有两个角色，一个是老师，一个是学生。老师有两个动作，第一个是布置作业，第二个是查看作业。而学生有一个动作是做作业， 那么问题来了，老师并不知道学生何时才能做完作业，所以比较优雅的解决办法是等学生的通知，也就是学生做完之后告诉老师就可以。这就是典型的回调理念。

那么在编程中，该如何体现？ 从上面的分析中，可以得出来回调模式是双方互通的，老师给学生布置作业，学生做完通知老师查看作业。 关于回调，这里面还分同步回调和异步回调两种模式：

同步模式：

如果老师在放学后，给学生布置作业，然后一直等待学生完成后，才能回家，那么这种方法就是同步模式。

异步模式：

如果老师在放学后，给学生布置作业，这个时候老师并不想等待学生完成，而是直接就回家了，但告诉学生，如果完成之后发短信通知自己查看。这种方式就是异步的回调模式。

回调模式为了不影响主任务执行，一般会设计成异步任务。下面我们看下在Java中，模拟上面举的例子实现一个简单的回调，包括同步和异步两种模式：

首先，回调的方法我们最好定义成一个接口，这样便于扩展：

/***
 *通过接口定义回调函数
 */
public interface CallBack {
    //检查作业属于老师的功能，但由学生触发，故称回调
    public void checkWork();
}

然后，我们定义老师的角色：

package design_pattern.callback.demo2;
public class Teacher implements CallBack {
    private Student student;
    public Teacher(Student student) {
        this.student = student;
    }
    /***
     *  给学生分配作业
     * @param isSync true=同步回调 false=异步回调
     * @throws InterruptedException
     */
    public void assignWork(boolean isSync) throws InterruptedException {
        System.out.println("老师分配作业完成....");
        if(isSync){
            student.doWrok(this);//同步通知做作业
        }else{
            student.asynDoWrok(this);//异步通知做作业
        }
        System.out.println("老师回家了....");
    }
    @Override
    public void checkWork() {
        System.out.println("老师收到通知并查看了学生的作业!");
    }
}

上面定义的是老师角色，有两个行为，一个是布置作业，一个是检查作业，布置作业里面，在布置作业里面，老师可以选择同步回调还是异步回调。

接着我们看下学生角色如何定义：

public class Student  {
    public void doWrok(CallBack callBack) throws InterruptedException {
        System.out.println("学生开始做作业.....");
        TimeUnit.SECONDS.sleep(3);
        System.out.println("学生完成作业了，通知老师查看");
        callBack.checkWork(); //通知老师查看作业
    }
    public void asynDoWrok(CallBack callBack) throws InterruptedException {
     //通过一个线程来异步的执行任务
     Runnable runnable= new Runnable(){
            @Override
            public void run() {
                System.out.println("学生开始做作业.....");
                try {
                    TimeUnit.SECONDS.sleep(3);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
                System.out.println("学生完成作业了，通知老师查看");
                callBack.checkWork();
            }
        };
     Thread thread=new Thread(runnable);
     thread.start();
    }
}

学生角色里面只有一个行为做作业，但这里我提供了两种模式，一个是同步，一个是异步。

最后，我们来测试下：

public class AppMain {
    public static void main(String[] args) throws InterruptedException {
        Student student=new Student();//学生角色
        System.out.println("\n===============同步模式================");
        Teacher teacher=new Teacher(student);//老师角色
        //同步回调模式，老师给学生布置作业，老师等学生完成之后才能回家
        teacher.assignWork(true);
        System.out.println("\n===============异步模式================");
        //异步回调模式，老师给学生布置作业，布置完成之后就可以回家，学生完成之后会通知老师查看。
        teacher.assignWork(false);
    }
}

执行结果如下：

===============同步模式================
老师分配作业完成....
学生开始做作业.....
学生完成作业了，通知老师查看
老师收到通知并查看了学生的作业!
老师回家了....
===============异步模式================
老师分配作业完成....
老师回家了....
学生开始做作业.....
学生完成作业了，通知老师查看
老师收到通知并查看了学生的作业!

对于同步和异步两种模式的结果，在上面的输出内容里面可以非常清晰的看出来区别，也体现回调的双通模式。老师角色持有了学生对象的引用，并告诉学生做作业，而同时学生角色，也持有老师角色的引用，可以在自己完成作业后，告诉老师查看作业。

3. 甚至被调函数f()到底实现什么功能，也是可以不定义的。只是在A里面规定好条件触发，将具体做什么的决定权交给用户。

 ----场景：事件，通知。

我猜OnTimer()应当就是一个回调函数，开放给用户自定义动作。整个定时器的机制已经是预定义好的。

main函数其实也是。都是事件机制。

4. 结合多线程异步使用。

----场景：工作继续进行，主函数先结束。

void  A(url, call)
{
      开启url线程,传入call
      函数本身返回.
}

 5.结合延迟函数。

void  A(call)
{
      setTimeout(call, 10000)
      函数本身返回.
}

4. 输出中位数(和快排一个思路)

以原数组中位于中间位置k的元素作为基准值pivot，对原数组进行划分，分别为元素值< pivot、= pivot和> pivot的三部分，将这三部分的元素值分别赋给数组SL、SV、SR，并计算出SL、SV、SR中有效元素的个数sl、sv、sr。将k和sl、sv+sl、sl+sv+sr比较，如果k < sl，说明该数组的中项在SL数组中；如果k < sl+sv，说明该数组的中项在SV中；如果k < sl+sv+sr，说明该数组的中项在SR中。

/*
对于长度为n的整型数组A，随机生成其数组元素值，然后实现一个线性时间的算法，在该数组中查找其中项。
*/
 
#include <iostream>
#include <stdlib.h>
 
using namespace std;
 
int selection(int data[], int n, int k);
 
int main()
{
	int data[9];
	int n = 9;
 
	//随机生成数组元素值
	for (int i = 0; i < n; ++i)
	{
		data[i] = rand();
		cout << data[i] << ' ';
	}
	cout << endl;
 
    int temp = n % 2;
	if (temp)	//如果有奇数个元素
	{
		cout << selection(data, n, n / 2) << endl;
	}
	else    //如果有偶数个元素
	{
		cout << (double(selection(data, n, n / 2) + selection(data, n, n / 2 - 1)) / 2) << endl;
	}
 
	return 0;
}
 
int selection(int data[], int n, int k)		//data是要查找的数组，n是数组的大小，k是中位数应该在的位置
{
	//基准值
	int pivot = data[k];
 
	//对小于基准值、等于基准值、大于基准值的元素进行划分
	int sl = 0, sv = 0, sr = 0;
	int SL[10], SV[10], SR[10];
	for (int i = 0; i < n; ++i)
	{
		if (data[i] < pivot)
		{
			SL[sl] = data[i];
			++sl;
		}
		else if (data[i] == pivot)
		{
			SV[sv] = data[i];
			++sv;
		}
		else
		{
			SR[sr] = data[i];
			++sr;
		}
	}
 
	//比较k与子集所含元素大小的关系
	if (k < sl)
	{
		selection(SL, sl, k);
	}
	else if (k < sv+sl)
	{
		return data[k];
	}
	else
	{
		selection(SR, sr, k - sl - sv);
	}
}