笔试面试题目1

骑猪看日落 2022-09-17 05:26 239阅读 0赞

1. 求重合段的长度  
  
 size\_t foo(unsigned int \*a1, size\_t al1, unsigned int\* a2, size\_t al2)  
  
 其中a1和a2都为无符号数组，al1和al2为数组的长度，数组的长度为偶数。  
  
 无符号数组由一对数字区间组成。如下例：  
 a1 为 0,1,3,6,10,20  
 a2 为 0,1,20,50,4,5  
 则 a1表示以下区间\[0,1\] \[3,6\] \[10,20\]  
  a2表示以下区间\[0,1\] \[20,50\] \[4,5\]  
  
 则a1,a2的重叠部分为\[0,1\] \[4,5\]，其长度为2，函数foo要求返回重叠区间的长度。上例中为2。  
  
 要求：  
 详细说明自己的解题思路，说明自己实现的一些关键点。  
 写出函数foo原代码，另外效率尽量高，并给出代码的复杂性分析。  
  
 限制：  
 al1和al2的长度不超过100万。而且同一个数组的区间可能出现重重叠。  
 如a1可能为 0,5, 4,8, 9,100, 70,80

使用的存储空间尽量小。

#include <iostream>
    #include <algorithm>
    using namespace std;
    
    class data
    {
    public:
        unsigned int first;
        unsigned int second;
        friend bool operator<( const data & d1, const data& d2);
    };
    
    inline bool operator<( const data & d1, const data& d2)
    {
        return d1.first < d2.first;
    }
    
    int foo(unsigned int *a1, int al1, unsigned int* a2, int al2)
    {
        data * d1 = (data*) a1;
        data * d2 = (data*) a2;
    
        sort(d1, d1+al1/2, less<data>());
        sort(d2, d2+al2/2, less<data>());
    
        int len = 0;
        for( int i =0, j = 0; (i < al1/2 && j < al2/2);)
        {
            if(d1[i].second <= d2[j].first)
            {
                i++;
            }
            else if(d1[i].first >= d2[j].second)
            {
                j++;
            }
            else
            {
                if(d1[i].first <= d2[j].first && d2[j].second <= d1[i].second)
                {
                    len += d2[j].second - d2[j].first;
                    j++;
                }
                else if(d2[j].first <= d1[i].first && d2[j].second >= d1[i].second)
                {
                    len += d1[i].second - d1[i].first;
                    i++;
                }
                else if( d1[i].first >= d2[j].first && d1[i].first < d2[j].second && d1[i].second >= d2[j].second)
                {
                    len += d2[j].second - d1[i].first;
                    j++;
                }
                else if( d2[j].first >= d1[i].first && d2[j].first < d1[i].second && d2[j].second >= d1[i].second)
                {
                    len += d1[i].second - d2[j].first;
                    i++;
                }
            }
        }
    
        return len;
    }
    
    int main()
    {
        unsigned int a1[] = { 0, 1, 3, 6, 10, 20};
        unsigned int a2[] = { 0, 1, 20,50, 4, 5};
        int len = foo( a1, 6, a2, 6);
        cout << "len: " << len << endl;
        return 0;
    }

2. 多人排成一个队列,我们认为从低到高是正确的序列,但是总有部分人不遵守秩序。如果说,前面的人比后面的人高(两人身高一样认为是合适的)

那么我们就认为这两个人是一对“捣乱分子”,  
比如说,现在存在一个序列:  
176, 178, 180, 170, 171  
这些捣乱分子对为 <176, 170>，<176, 171>，<178, 170>，<178, 171>，<180, 170>，<180, 171>  
那么，现在给出一个整型序列,请找出这些捣乱分子对的个数（仅给出捣乱分子对的数目即可,不用具体的对）  
  
要求：  
输入：  
为一个文件(in)，文件的每一行为一个序列。序列全为数字，数字间用”,”分隔。  
输出：  
为一个文件(out)，每行为一个数字，表示捣乱分子的对数。  
  
详细说明自己的解题思路，说明自己实现的一些关键点。并给出实现的代码 ，并分析时间复杂度。  
  
限制：  
输入每行的最大数字个数为100000个，数字最长为6位。程序无内存使用限制。  
  
归并的方法求数组的逆序数。

#include <iostream>
    using namespace std ;
    
    void merge(int * a, int *p, int start, int mid, int end, int & count)
    {
    	int i = 0, j = 0;
    	for(i = start; i <= mid; i++)   // 将数据复制到辅助空间
    		p[i] = a[i] ;
    	for(j = mid + 1; j <= end; j++)
    		p[j] = a[j];
    
    	i = start;
    	j = mid + 1;
    	int w = start;
    	while( i <= mid && j <= end)
    	{
    		if(p[i] <= p[j])
    		{
    			a[w++] = p[i++];
    		}
    		else
    		{
    			count +=  mid - i + 1;     //注意此处的处理
    			a[w++] = p[j++];
    		}
    	}
    
    	while(i <= mid)
    	{
    		a[w++] = p[i++];
    	}
    
    	while(j <= end)
    	{
    		a[w++] = p[j++];
    	}
    }
    
    void mergeSort(int *a, int *p, int start, int end, int &count)
    {
    	if(start < end)
    	{
    		int mid = ( start + end) / 2;
    		mergeSort( a, p, start, mid, count);
    		mergeSort( a, p, mid + 1, end, count);
    		merge( a, p, start, mid, end, count);
    	}
    }
    
    int main()
    {
    	int a[5];
        int n = 5;
        int * p = new int[5];
    	if(n > 0)
    	{
    		int count = 0;
    		for(int i = 0; i < n; i++)
    		{
                a[i] = rand();
                cout << a[i] << " ";
            }
            cout << endl;
    
    		mergeSort( a, p, 0, n - 1, count);
    		cout << count << endl;
        }
    
        delete [] p;
    	return 0;
    }

3. 合并有序数组的前后段  
  
 数组al\[0,mid-1\] 和 al\[mid,num-1\]，都分别有序。将其merge成有序数组al\[0,num-1\]，要求空间复杂度O(1)

思路：就是将前半段比后半段大的元素，在后半段进行插入排序（从前向后插入，而不是从后往前），此处注意一个问题，在拿前面元素向后半段插入时，后半段肯定有空间可用，因为已经将它的一个元素放入了前半段有序数组中。

#include <iostream>
    using namespace std ;
    
    void merge(int a[], int len)
    {
        int mid = len / 2;
    
        for( int i = 0, j = mid; i < mid; )
        {
            if( a[i] <= a[j])    // 前半部分的大
            {
                i++;
            }
            else
            {
                int tmp = a[i];
                a[i] = a[j];
                i++;
                int index = j + 1;
                if( tmp <= a[index])
                {
                    a[j] = tmp;
                }
                else
                {
                    while(tmp > a[index] && index < len)
                    {
                        a[index - 1] = a[index];
                        index ++;
                    }
                    a[index-1] = tmp;
                }
            }// end of else
        }// end of for
    }
    
    int main()
    {
        int a[10] = {1, 3, 5, 9, 13, 4, 7, 11, 12, 19};
        for( int i = 0; i < 10; i++)
        {
            cout << a[i] << " ";
        }
        cout << endl;
        merge(a, 10);
        for( int i = 0; i < 10; i++)
        {
            cout << a[i] << " ";
        }
        cout << endl;
    
    	return 0;
    }

4. 随机输入一个数，判断它是不是对称数（回文数）（如3，121，12321，45254）。不能用字符串库函数

思路： 首先将数字转化为字符串（由于只是判断是否是回文数，因此转化为字符串之后的正序逆序并不重要），然后判断字符串是否是对称的。

#include <iostream>
    using namespace std ;
    
    bool IsSymmetry(char * str)
    {
        int len = strlen(str);
        char * p = str, *q = str+len-1;
        while(p < q)
        {
            if( *p == *q)
            {
                p++;
                q--;
            }
            else
            {
                return false;
            }
        }
    
        return true;
    }
    
    void int2str(int n, char * str)
    {
        if(n <= 0 || str == NULL)
        {
            return ;
        }
    
        int index = 0;
        while(n > 0)
        {
            str[index++] = '0' + n % 10;
            n /= 10;
        }
    
        return ;
    }
    
    int main()
    {
        int input;
        cout << "Input a number:";
        cin >> input;
        cout << endl;
    
        char str[256]; memset(str, 0, sizeof(str));
        int2str(input, str);
        if(IsSymmetry(str))
        {
            cout << "回文数" << endl;
        }
        else
        {
            cout << "非回文数" << endl;
        }
    	return 0;
    }

5. A，B，C，D 四个进程，A 向 buf 里面写数据，B，C，D 向 buf 里面读数据，当 A 写完，且B ，C ，D都读一次后，A 才能再写。用PV操作实现。

解答：  
一个生产者，三个消费者，公用 1 个缓冲区  
在这个问题中，不仅生产者与消费者之间要同步，同时每生产一个产品，三个消费者必须并且只能消费一次。

定义四个信号量：  
mutexB—— 消费者 B 和生产者之间的互斥信号量，初值为 1 。  
mutexC—— 消费者 C 和生产者之间的互斥信号量，初值为 1 。  
mutexD—— 消费者 D 和生产者之间的互斥信号量，初值为 1 。

// 生产者进程
    while(TRUE)
    {
         生产一个产品 ;
          // 因为这里需要确认三个消费者都已经消费了      P(mutexB);      P(mutexC);      P(mutexD);       产品送往 buffer();       // 三个消费者可以消费了      V(mutexB);      V(mutexC);      V(mutexD); }// 消费者进程 B ，每个产品，该消费者只能消费一次while(TRUE){        P(mutexB);        从 buffer() 中取出产品 ;        V(mutexB);        消费该产品 ;}// 消费者进程 C ，每个产品，该消费者只能消费一次while(TRUE){        P(mutexC);        从 buffer() 中取出产品 ;        V(mutexC);        消费该产品 ;}// 消费者进程 D, 每个产品，该消费者只能消费一次while(TRUE){        P(mutexD);        从 buffer() 中取出产品 ;        V(mutexD);        消费该产品 ;}

By Andy @ 2013-9-28