两个面试题，求解答,该怎么处理

2012-03-14

两个面试题，求解答1.Describe an algorithm that would: return the 5th element from the end in a singl

两个面试题，求解答
1.Describe an algorithm that would: return the 5th element from the end in a singly linked list of integers, in one pass, and how about to find the middle element? Write the prototype of the function and then provide a set of test cases against that function.

2.Suppose you have an array of 1001 integers. The integers are in random order, but you know each of the integers is between 1 and 1000 (inclusive). In addition, each number appears only once in the array, except for one number, which occurs twice. Assume that you can access each element of the array only once. Describe an algorithm to find the repeated number. If you used auxiliary storage in your algorithm, can you find an algorithm that does not require it?

[解决办法]
第一个，随机算法，基于快速排序的思想，O（N）的算法，寻找数组中第K小的元素

C/C++ code

#include <stdio.h>#include <math.h>#include <stdlib.h>#define LEN 1024 using namespace std;int RANDOM(int p,int r){    return rand()*(r-p)/32767+p;    }int PARTITION(int arr[LEN],int p,int r){     int x = arr[r];     int i = p-1;     for(int j = p;j<r;j++)     {         if(arr[j]<=x)          {            ++i;            int t = arr[i];            arr[i] = arr[j];            arr[j] = t;            }     }     int t = arr[i+1];     arr[i+1] = arr[r];     arr[r] = t;     return i+1;     }int RANDOMIZED_PARTITION(int arr[LEN],int p,int r){     int i = RANDOM(p,r);     int t = arr[i];     arr[i] = arr[r];     arr[r] = t;     return PARTITION(arr,p,r);}int RANDOMIZED_SELECT(int arr[LEN],int p,int r,int i)  //找到arr中第i小的数，数组下标从1开始 {     if(p==r) return arr[p];     int q = RANDOMIZED_PARTITION(arr,p,r);     int k = q-p+1;     if(i==k) return arr[q];     else if(i<k)     return RANDOMIZED_SELECT(arr,p,q-1,i);     else return RANDOMIZED_SELECT(arr,q+1,r,i-k);      }int main(){    int n,arr[]={45,67,32,78,4,23,567,78,34,0,78};    while(scanf("%d",&n)==1)    {         printf("%d\n",RANDOMIZED_SELECT(arr,0,10,n));                       }    return 0;}
[解决办法]
对于找最中间的元素，我只能想到用两指针，一个一步走一步，一个一步走两步；
不过这样严格来讲，应该也算是遍历了两遍；
[解决办法]
1.1
int *p[5] = {NULL, NULL, NULL, NULL, NULL};
int i = 0, j;

p[0] = head;
while(p[i]->next != NULL)
{
j = i;
i = (i + 1) % 5;
p[i] = p[j]->next;
}
i = (i + 1) % 5;

如果p[i]不为空,即为倒数第5个结点.否则说明链表长度小于5.

算法虽然用了五个指针,但是只对链表遍历了一次.

不知道有没有更好的办法.
[解决办法]
1. 第一题是找出单向链表的倒数第五个元素。算法可以这样，准备两个指针p和q，p指向第一个元素，q前进到第5个，然后同时移动p和q，当q到达终点时，p就到了倒数第五个。后面半个问题的解决方式，p和q都指向第一个元素，p每前进一个元素，q前进2个元素，到q达到终点时，p就在中点附近。一些边界条件要考虑。

2. 第二题解法如C1053710211说的一样。如果要求不用辅助存储空间，可以试着这样，
a[1]=a[1]+a[0] -> 把前两个元素和放在第2个元素，
a[2]=a[2]+a[1] -> 把前三个元素和放在第3个元素（这里的a[1]已经是第一个和第二个元素的和）
依次类推，最后一个元素就是所有元素的和，然后减去500500就是那个重复的数字。

这里我没有用到辅助存储空间（假设常量500500不算辅助存储空间）
[解决办法]
第一个大家都是O（N）的算法，只能比较N的系数大小。
9楼的看似对链表遍历了一次，遍历了一次时，循环内加了不少操作如[]、i=j;i=(i+1)%5;
还有前进走两步，也必然多加一个判断做安全检查，这些都要算。
C/C++ code  int s, k;  ListNode *p,*ps,*pn;  s = k = 1;         // 2*(2*Tfetch + Tstore)     ps = head;         // 2*Tfetch + Tstore  pn = p = ps->next; // 2*(2*Tfetch + Tstore) + T->  for( ; ; )  {      p = p->next;   // n*(2*Tfetch + Tstore + T->)      if(p)          // (n+1)*(2*Tfetch + T<)          break;      else if(--s)   // n*(4*Tfetch + Tstore + T- + T<)      {              // logn *(9*Tfetch + 4*Tstore + T+)          ps = pn;             pn = p;          k += k;            s = k;      }   }  if(s)    for(k = (k-s)/2, p = ps; --k; )  // ... (n-2^k)/2*(...)        p = p->next;  else      p = pn; p为所求； s为奇数，p、p->next为所求

热点排行

软件架构设计

两个面试题，求解答,该怎么处理