고전 면접 문제 (3) 부 답 알고리즘 + 데이터 구조 + 코드 마이크로소프트, 구 글 구 글, 바 이 두, 텐 센트
<pre name="code" class="cpp">1. ， （2011 MTK）
？
？
。
1. 。 。 1， 2， 。 ， ， 。
2. 。 ， ， 。 ， 1 。
3. 。 ， ， 。 ， ， 1。 。
， 。
， a ， b ， x 。
S( i ) i ， 。
， S( a )， a 。
：
x a S( a ), S( x + a ) = S( a )
， a = tb ( t = 1, 2, …. )， S( x + a ) = S( a )
a = tb？
， ， S( x ) = S( 2x )
， 2x = x + bt, x = tb.
[cpp] view plaincopy
struct Node
{
int data;
Node* next;
Node( int value ): data(value), next(NULL) {};
};
//
bool IsCircle( Node *pHead )
{
// next ，
if( pHead == NULL || pHead->next == NULL ) return false;
Node *pSlow = pHead;
Node *pFast = pHead;
while( ( pFast != NULL ) && ( pFast->next != NULL ) )
{
// 1、2
pSlow = pSlow->next;
pFast = pFast->next->next;
if( pSlow == pFast ) break;
}
if( ( pFast == NULL ) || ( pFast->next == NULL ) )
return false;
else
return true;
}
//
int GetLen( Node *pHead )
{
if( pHead == NULL || pHead->next == NULL ) return false;
Node *pSlow = pHead;
Node *pFast = pHead;
//
while( ( pFast != NULL ) && ( pFast->next != NULL ) )
{
pSlow = pSlow->next;
pFast = pFast->next->next;
if( pSlow == pFast ) break;
}
//
int cnt = 0;
while( ( pFast != NULL ) && ( pFast->next != NULL ) )
{
pSlow = pSlow->next;
pFast = pFast->next->next;
cnt++;
// ，
if( pSlow == pFast ) break;
}
return cnt;
}
//
Node* GetEntrance( Node* pHead )
{
if( pHead == NULL || pHead->next == NULL ) return false;
Node *pSlow = pHead;
Node *pFast = pHead;
//
while( ( pFast != NULL ) && ( pFast->next != NULL ) )
{
pSlow = pSlow->next;
pFast = pFast->next->next;
if( pSlow == pFast ) break;
}
pSlow = pHead;
while( pSlow != pFast )
{
//
pSlow = pSlow->next;
pFast = pFast->next;
}
return pSlow;
}
2. （2011 MTK）
， 。
： 。
：？？
[cpp] view plaincopy
//
Node* merge( Node* pHeadA, Node* pHeadB )
{
//
if( pHeadA == NULL || pHeadB == NULL )
{
return ( pHeadA == NULL ) ? pHeadB : pHeadA;
}
//
Node *px, *py;
if( pHeadA->data <= pHeadB->data )
{
px = pHeadA; py = pHeadB;
}
else
{
px = pHeadB; py = pHeadA;
}
Node *pResult = px;
// py px
Node *pre = px;
px = px->next;
while( py != NULL && px != NULL )
{
// px py
while( py != NULL && px != NULL && py->data > px->data )
{
py = py->next;
px = px->next;
pre = pre->next;
}
//py pre px
if( py != NULL && px != NULL )
{
//py
Node* tmp = py;
py = py->next;
//pre
Node* tmpPre = pre;
pre = pre->next;
//
tmp->next = px;
tmpPre->next = tmp;
//px
px = px->next;
}
else
break;
}
if( px == NULL ) pre->next = py;
return pResult;
}
4 ： (long ) ， printf
。 ， 。 ， ： 。 ， 。 ， 。
[cpp] view plaincopy
void LongFormat( long value )
{
//
long mask = 0x1 << ( 8 * sizeof(long) - 1 );
if( value & mask ) cout << "1";
else cout << "0";
//
mask = 0x1 << ( 8 * sizeof(long) - 2 );
for( int i=1; i<8*sizeof(long); i++ )
{
if( value & mask ) cout << "1";
else cout << "0";
mask >>= 1;
}
cout << endl;
//
cout << "0x";
mask = 0xF << ( 8 * sizeof(long) - 4 );
long tmp = ( value & mask ) >> ( 8 * sizeof(long) - 4 );
if( tmp < 10 )
cout << tmp;
else
cout << (char)( 'a' + ( tmp - 10 ) );
//
mask = 0xF << ( 8 * sizeof(long) - 8 );
for( int i=1; i<2*sizeof(long); i++ )
{
tmp = ( value & mask ) >> ( 8 * sizeof(long) - 4 * i - 4 );
if( tmp < 10 )
cout << tmp;
else
cout << (char)( 'a' + ( tmp - 10 ) );
mask >>= 4;
}
}
5. ： , "abccade","dgcadde" "cad"
： KMP。 KMP ， 。
： ， 、 ， 。 1， 0。 1 ， 。 0( m*n )， O( m*n )
， O( m*n )。 ， A ， B 。 ， ， ， 。
[cpp] view plaincopy
void GetSubStr( char *strA, char *strB, char *ans )
{
int max = 0;
char *pAns = NULL;
// A
for( int i=0; *(strA+i) != '\0'; i++ )
{
// strB ， strB
char *pb = strB;
while( *pb != '\0' )
{
// strA
char *pa = strA + i;
int cnt = 0;
char *pBegin = pb;
//
if( *pb == *pa )
{
while( *pb == *pa && *pb != '\0' )
{
pa++;
pb++;
cnt++;
}
if( cnt > max )
{
max = cnt;
pAns = pBegin;
}
if( *pb == '\0' ) break;
}
else
pb++;
}
}
//
memcpy( ans, pAns, max );
*(ans+max) = '\0';
}
6. ：
struct node
{
int data;
struct node *front,*next;
};
A，B， ：pHeadA,pHeadB， data 。
NB 。 A， A ， B 。 B ， ， A 。
， 。 ， 。 ？p->next == pHead.
：
[cpp] view plaincopy
struct Node
{
int data;
struct Node *front,*next;
Node( int value ): data( value ), front( NULL ), next( NULL ) { };
void SetPointer( Node *pPre, Node *pNext ) { front = pPre; next = pNext; };
};
// 。 ， 。
bool DeleteValue( Node *&pHead, int target )
{
if( pHead == NULL ) return false;
//
bool flag = false;
Node* ph = pHead;
while( ph->next != pHead )
{
Node *pPre = ph->front;
Node *pNext = ph->next;
if( ph->data == target )
{
//
if( ph == pHead ) pHead = ph->next;
pPre->next = pNext;
pNext->front = pPre;
Node *tmp = ph;
delete tmp;
//
flag = true;
}
ph = pNext;
}
//
if( ph->next == pHead )
{
if( ph->data == target )
{
//
if( ph->front != ph )
{
Node *pPre = ph->front;
Node *pNext = ph->next;
pPre->next = pNext;
pNext->front = pPre;
Node *tmp = ph;
delete tmp;
}
else
{
delete pHead;
pHead = NULL;
}
flag = true;
}
}
return flag;
}
void DeleteSame( Node *&pHeadA, Node *&pHeadB )
{
if( pHeadA != NULL && pHeadB != NULL )
{
Node *pa = pHeadA;
while( pa->next != pHeadA )
{
// B pa->data，
if( DeleteValue( pHeadB, pa->data ) )
{
// A pa->data
Node *tmp = pa->next;
DeleteValue( pHeadA, pa->data );
pa = tmp;
}
else
pa = pa->next;
}
//
if( DeleteValue( pHeadB, pa->data ) )
{
DeleteValue( pHeadA, pa->data );
}
}
}
7. int atoi(char *s)。
int i=(j=4,k=8,l=16,m=32); printf(“%d”, i); ？
、 。
。
。
1. ， ， 。
2. 。 ， i=(m=32)
3. ： 。 ： 。
： 。 ： 。
：static ， 。 ， 。 ， 。 ： ， 。
4. ： new ， ， ， 。
： 、 ， 。
8.
： ， 。
： ：
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5, 6, 7, 11, 10。
： Autodesk、EMC
， 。 ， 2， 。 ， 0、1 。 ， 。 。 ， ， 。
[cpp] view plaincopy
const int MAX_ROW = 100;
const int MAX_COL = 100;
void PrintMatrix( int data[][MAX_COL], int row, int col )
{
int top = 0;
int bottom = row-1;
int left = 0;
int right = col-1;
int cnt = 0;
int total = row * col;
while( cnt < total )
{
// ，
int j;
for( j=left; j<=right && cnt<total; j++ )
{
cout << data[top][j] <<" ";
cnt++;
}
top++;
// ，
for( j=top; j<=bottom && cnt<total; j++ )
{
cout << data[j][right] << " ";
cnt++;
}
right--;
// ，
for( j=right; j>=left && cnt<total; j-- )
{
cout << data[bottom][j] << " ";
cnt++;
}
bottom--;
// ，
for( j=bottom; j>=top && cnt<total; j-- )
{
cout << data[j][left] << " ";
cnt++;
}
left++;
}
}
9.
： ， 。
“google”， “goog”， 。
： ，
10. 1、2、3、4、5、6 ， main ， ， ：512234、412345 ， ："4" ，"3" "5" .
， （ ， ， ）。 ， ， ， ， 。
[cpp] view plaincopy
bool IsValid( char *str )
{
for( int i=1; *(str+i) != '\0'; i++ )
{
if( i == 2 && *(str+i) == '4' ) return false;
if( *(str+i) == '3' && *(str+i-1) == '5' || *(str+i) == '5' && *(str+i-1) == '3' )
return false;
}
return true;
}
void PrintStr( char *str, char *start )
{
if( str == NULL ) return;
if( *start == '\0' )
{
if( IsValid( str ) ) cout << str << endl;
}
for( char *ptmp = start; *ptmp != '\0'; ptmp++ )
{
char tmp = *start;
*start = *ptmp;
*ptmp = tmp;
PrintStr( str, start+1 );
tmp = *start;
*start = *ptmp;
*ptmp = tmp;
}
}
11。
， 2 3 5 ，1 。 1500 ？
2、3、5 30。[ 1, 30] 22 。 [ 31, 60] 22 ， 。 ， ， 30.
1500 ：1500/22=68 1500%68=4。 ： 1500 68 ， 4 。 4 ：2,3,4,5。
， 68*30=2040+5=2045
12.
： ， 。 ：
struct ListNode
{
int m_nKey;
ListNode* m_pNext;
};
： 。 、 。
。 ： ， 3 ， 。 ， 。 ， ， 。
[cpp] view plaincopy
struct ListNode
{
int m_nKey;
ListNode* m_pNext;
};
void PrintReverse( ListNode* pHead )
{
ListNode* ph = pHead;
if( ph != NULL )
{
PrintReverse( ph->m_pNext );
cout << ph->m_nKey << " ";
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
