2013.9.28 톈진바이두 소프트웨어 연구 개발 필기시험

7897 단어
여러분은 몇 가지 의문이 있는 문제에 대해 자신의 견해를 많이 제기해 주시기를 바랍니다. 감사합니다.
간단한 답안
1: 동적 링크 라이브러리와 정적 링크 라이브러리는 어떤 장점과 단점이 있습니까?
양자는 모두 코드를 공유하는 방식이고 프로그램의 모듈화 방식이라고도 할 수 있다.
정적 라이브러리의 구조는 비교적 간단하다. 사실은 원래의 목표 코드를 함께 놓고 링크 프로그램은 각 목표 코드의 기호표에 따라 해당하는 기호(함수와 변수의 이름)를 찾는다. 찾으면 이 함수에 있는 위치를 정하고 위치를 정한 다음에 전체 함수 코드를 실행 가능한 파일에 넣고 필요한 함수를 찾지 못하면 잘못 보고하고 종료한다.
이점:
1: 성능이 어느 정도 향상되었습니다.예를 들어exe모듈이 동적 링크 라이브러리의 내보내기 함수를 호출할 때 동적 링크 라이브러리를 먼저 불러와야 하기 때문에 일정한 성능 손실이 있다.
2: 정적 링크는 프로그램을 실행하는 시스템에 동적 라이브러리가 없어서 실행할 수 없는 상황을 피할 수 있다.예를 들어 VS2008에서 컴파일한 MFC 동적 링크 프로그램은 MFC90U가 필요합니다.Dll 이 동적 라이브러리 파일대상 시스템에 이 동적 라이브러리가 부족하면 프로그램이 불러올 수 없습니다.
단점:
1: 링크 후에 생성된 실행 가능한 파일은 호출할 함수의 모든 코드를 포함하기 때문에 디스크 공간을 많이 차지한다.
2: 여러 개의 프로세스가 메모리에서 동시에 실행되면 메모리에 같은 라이브러리 함수 코드가 여러 개 존재하기 때문에 메모리 공간을 많이 차지한다.
동적 링크는 프로그램이 메모리를 불러올 때 라이브러리 함수 코드 링크를 진정으로 그들의 주소를 확인하는 것을 의미한다.
이점:
1. 프로그램 공유에 유리하다
2, DLL의 단일 매핑을 사용하는 여러 프로그램의 메모리 공간 절약
3. 프로그램 분할을 통해 프로그램 업그레이드에 유리하다
4. 대량의 하드디스크 공간을 절약할 수 있다
단점:
1: 정적 링크보다 성능이 떨어져야 함
2: 프로그램이 동적 라이브러리가 없으면 실행할 수 없습니다
2: 폴링 작업 스케줄링과 선점식 작업 스케줄링의 차이점?
폴링 스케줄링 알고리즘의 원리는 매번 사용자의 요청을 내부에 있는 서버에 번갈아 분배하고 1부터 N(내부 서버 개수)까지 다시 순환하는 것이다.
선점식 작업 스케줄링은 스케줄러가 어떤 원칙에 따라 실행 중인 프로세스를 일시 정지시키고, 이 프로세스에 분배된 프로세서를 다른 프로세스에 재분배할 수 있도록 한다.선점 방식의 장점은 장거리 장시간 점용 프로세서를 방지하고 대부분의 프로세스에 더욱 공평한 서비스를 제공할 수 있으며 특히 응답 시간에 대해 비교적 엄격한 요구를 가진 실시간 임무에 대한 수요를 충족시킬 수 있다는 것이다.
3: 데이터베이스에서 자주 사용하는 자물쇠를 열거하고 각각 응용 장면을 보여 주시겠습니까?
자물쇠 배열 (쓰기): 사무 T가 데이터 대상 A에 X 자물쇠를 추가하면 T가 A를 읽고 수정할 수 있으며, 다른 어떤 사무도 A에 어떤 종류의 자물쇠를 추가할 수 없습니다. T가 A의 자물쇠를 풀 때까지.다른 업무는 T가 A의 자물쇠를 풀기 전에 A를 읽고 수정할 수 없습니다.
공유 자물쇠 (읽기 자물쇠): 데이터 대상 A에 사무 T가 S 자물쇠를 추가하면 사무 T는 A를 읽을 수 있지만 수정할 수 없습니다. 다른 사무는 A에 자물쇠를 추가할 수 있고, A의 자물쇠가 풀릴 때까지 X 자물쇠를 추가할 수 없습니다.다른 업무는 A를 읽을 수 있으나, T가 A의 자물쇠 S를 풀기 전에 A에 대해 어떠한 조작도 할 수 없습니다.
활성 잠금: 만약에 사무 T1이 데이터 R을 봉쇄하면 사무 T2가 R을 봉쇄할 것을 요청하여 T2가 기다린다.T3도 R의 봉쇄를 요청했다. T1이 R의 봉쇄를 풀자 시스템이 먼저 T3의 요청을 승인했고 T2는 기다렸다.그리고 T4는 R을 봉쇄해 달라고 요청했다. T3가 R의 자물쇠를 풀자 시스템이 T4의 요청을 승인했다. T2는 영원히 기다릴 수 있다. 이것이 바로 자물쇠다.
사라진 자물쇠: 만약에 업무 T1이 데이터 R1을 봉쇄하면 T2는 데이터 R2를 봉쇄하고 T1은 R2를 봉쇄할 것을 요청한다. T2가 R2를 봉쇄했기 때문에 T1은 T2가 R2의 자물쇠를 풀기를 기다린다.이어 T2가 R1 봉쇄를 신청하면서 T2도 R1의 자물쇠가 풀리기를 기다릴 수밖에 없었다.이렇게 되면 T1이 T2를 기다리고 T2가 T1을 기다리는 국면이 나타나 T1과 T2 두 가지 사무는 영원히 끝날 수 없다.이것이 바로 자물쇠다.
몇 가지 의향 자물쇠
의향 공유 자물쇠 (IS 자물쇠): 데이터 대상에 IS 자물쇠를 추가하면 후예 결점에 S 자물쇠를 추가하겠다는 뜻이다.예를 들어 사무 T1이 R1의 어떤 원조에 S 자물쇠를 넣으려면 관계 R1과 데이터베이스에 IS 자물쇠를 넣어야 한다.
의향 배타 자물쇠 (IX 자물쇠): 데이터 대상에 IX 자물쇠를 넣으면 후예 결점에 X 자물쇠를 넣으려는 것을 표시합니다.예를 들어 사무 T1이 R1의 어떤 원조에 X 자물쇠를 넣으려면 관계 R1과 데이터베이스에 IX 자물쇠를 넣어야 한다.
공유 의도 배타적 잠금(SIX 잠금): 데이터 대상에 SIX 잠금을 추가하면 S잠금을 추가하고 IX 잠금을 추가합니다. 즉, SIX=S+IX입니다.예를 들어 어떤 테이블에 SIX 자물쇠를 넣으면 이 업무가 전체 테이블을 읽어야 한다는 것을 의미한다. (이 테이블에 S 자물쇠를 넣어야 하기 때문에) 개별 원조를 업데이트할 것이다. (따라서 이 테이블에 IX 자물쇠를 넣어야 한다.)
알고리즘과 프로그램 설계 문제
1:n은 정수로 이 수보다 크고 가장 작은 불중복수를 구한다. 중복수는 서로 인접한 두 자리 숫자와 같다. 예를 들어 1101은 중복수이고 1231은 불중복수이다.
방법1:폭력해법
#include "stdafx.h"
#include <iostream>
using namespace std;

bool IsNorepeatNum(int key)
{
	int n1,n2;
	int p = 1, q = 10;
	bool flag = true;
	while ( key )
	{
		n1 = key/p%q;
		n2 = key/(p*10)%q;
		if(n1 == n2)
		{
			flag = false;
			break;
		}
		key /= 10;
	}
	return flag;
}
int FindNextNotrepeatNum(int inputNum)
{
	while ( !IsNorepeatNum(inputNum) )
		inputNum++;

	return inputNum;
}

int _tmain(int argc, _TCHAR* argv[])
{
	int a[] = {1101,1231,9901,1099,1001};
	for ( int i = 0; i < 5; i++ )
	{
		cout << FindNextNotrepeatNum(a[i]) <<endl;
	}
	
	return 0;
}

방법2: 최적화 전략
  :      1222,           。       1222,         ,    1*      1223,      ,1223,                  ,  1233,  ,              0, 1230,          ,            。
#include "stdafx.h"
#include <iostream>
using namespace std;

int FindNextNotRepeatNum1(int nNum)
{
	//     
	int nPreBitNum, nCurBitNum, nNewNum, nProcessCount, nDigitCount = 0;
	nNewNum = nNum;
	while ( nNewNum )
	{
		nNewNum /= 10;
		nDigitCount++;
	}
	int* pProcessedBitNum= new int[nDigitCount];	//      

	int p = 1, q = 10;
	nNewNum = nNum;
	nProcessCount = 0;
	while ( nProcessCount < nDigitCount-1  )
	{
		nCurBitNum = nNewNum/p%q;
		nPreBitNum = nNewNum/(p*10)%q;
		
		if ( nCurBitNum != nPreBitNum )
		{
			nProcessCount++;
			p = p*10;
		}
		else 
		{//       2     ,          1,        0,    。
			nNewNum = nNewNum + p;	
			int nTempNum = nNewNum%p;
			nNewNum = nNewNum - nTempNum;
			nProcessCount = 0;
			p = 1;
		}
	}
	return nNewNum;
}

2: 길이가 N (N) 인 문자열입니다. 이 문자열의 가장 긴 메모 문자열을 구하십시오.
해결:
 
 
 
 
3: 수축에 왼쪽에서 오른쪽으로 n개의 점 a[0], a[1],...a[n-1]가 있는데 길이가 L인 밧줄을 정해서 이 밧줄이 몇 개의 점을 덮을 수 있도록 한다.
방법1: 매거법을 이용하여 임의의 두 점 구간의 길이를 L에 비해 최대 길이를 갱신한다
#include "stdafx.h"
#include <iostream>
using namespace std;

int MaxCoverCount(int* arr, int len, int L)
{
	int maxCover = 1, nCurCount;
	for ( int i = 0; i < len; i++ )
	{
		for ( int j = i+1; j < len; j++ )
		{
			if ( (arr[j]-arr[i]) <= L )
			{
				nCurCount = j-i+1;
				maxCover = (maxCover>nCurCount)?maxCover:nCurCount;
			}
		}
	}
	return maxCover;
}

int _tmain(int argc, _TCHAR* argv[])
{
	int a[] = {1,10,90,105,150,200,203,250,300};
	int Len = 100;
	cout << MaxCoverCount(a,9,Len) <<endl;
	return 0;
}

방법2: 시간의 복잡도는 O(n)-----내 전우인 insist GoGo의 해법을 참고한다
분석: 두 개의 커서 nS와 nE를 설정하여 양쪽 점의 거리 D와 L의 길이에 따라 비교할 수 있다.
(1) L>=D이면 nE가 한 자리를 뒤로 이동하여 현재 구간을 확대합니다
(2) L코드:
#include "stdafx.h"
#include <iostream>
using namespace std;

int MaxCoverCount(int* arr, int len, int L)
{
	int maxCover = 1, nCurCount = 1;
	int nStart = 0;
	int nEnd = 1;
	while ( nEnd < len )
	{
		if ( (arr[nEnd]-arr[nStart]) <= L )	//      L     
		{
			nCurCount++;
			nEnd++;
		}
		else	//    L     
		{
			maxCover = (maxCover>nCurCount)? maxCover : nCurCount;	//          
			//          
			do 
			{
				nStart++;
				nCurCount--;
			} while (arr[nEnd]-arr[nStart] > L);
		}
	}
	//                 
	maxCover = (maxCover>nCurCount)? maxCover : nCurCount;

	return maxCover;
}

int _tmain(int argc, _TCHAR* argv[])
{
	int a[] = {1,10,90,100,100,200,203,250,300};
	int Len = 105;
	cout << MaxCoverCount(a,9,Len) <<endl;
	return 0;
}

시스템 설계 문제
현대 시스템의 설계 과정에서 요청의 압력을 줄이기 위해 보통 캐시 기술, 즉 분포식 캐시나 클라이언트의 스케줄링 모듈을 이용하여 서로 다른 내용의 사용자를 대상으로 서로 다른 캐시 서버에 할당하여 처리한다. 이 서버가 만족하도록 설계하십시오.
1) 단일 캐시 서버 장애, 전체 분산 캐시 클러스터로 서비스를 계속 제공할 수 있습니다.
2) 일정한 분배 정책을 통해 모든 캐시 서비스의 저장 공간을 충분히 활용하고 부하의 균형을 확보할 수 있다.일부 서버가 고장나거나 시스템이 확장될 때, 분배 정책을 바꾸면 비교적 작은 캐시 파일의 재분배 비용을 보장할 수 있다.
3) 서로 다른 캐시 서버의 저장 공간이 차이가 있을 때 분배 정책은 비례 분배를 충족시킬 수 있다.
해결:
이 시스템 설계 문제가 어느 부분의 지식에 속하는지 모르고, 어떻게 준비해야 하는지, 소를 바라보고, 지적해 주십시오.

좋은 웹페이지 즐겨찾기