工程师面试题目

1，反转二叉树

BiTree ReversedBiTree(BiTree root)
{
if (root == null) {
return null;
}
root->left = ReversedTree(root->left);
root->right = ReversedTree(root->right);

BiTree tmp = root->left;
root->left = root->right;
root->right = tmp;
return root;
}

 

2，从一个字符串中找出出现频率最高的字符

int[] x = new int[26];
char[] ca = str.toCharArray();
for(int i=0;i <ca.length;i++){
x[ca[i]-'a']++;
}
for(int i=0;i <ca.length;i++){
System.out.println("字符"+(char)('a'+i)+"出现了"+ca[i]+"次");
}

3，快速排序

快速排序选择基准的三种方法：

• 1，选第一个；
• 2，随机选
• 3，选择1，n 和 n/2 的平均数

四种优化方法：

• 优化1：当待排序序列的长度分割到一定大小后，使用插入排序（对于小规模部分有序的数组，快排不如插排好）
• 优化2：在一次分割结束后，可以把与Key相等的元素聚在一起，继续下次分割时，不用再对与key相等元素分割
• 优化3：优化递归操作，使用为递归进行优化
• 优化4：使用并行或多线程处理子序列

void quicksort(int arr[],int left,int right)
{
int i,j,t,temp;
if(left>=right)
return;
temp=a[left]; //temp中存的就是基准数
i=left;
j=right;
while(i!=j)
{
while(a[j]>=temp && i<j) //顺序很重要，要先从右边开始找
j--;
while(a[i]<=temp && i<j) //再找右边的
i++;
if(i<j) //交换两个数在数组中的位置
{
t=a[i];
a[i]=a[j];
a[j]=t;
}
}
a[left]=a[i]; //最终将基准数归位
a[i]=temp;
quicksort(arr,left,i-1);//继续处理左边的，这里是一个递归的过程
quicksort(arr,i+1,right);//继续处理右边的 ，这里是一个递归的过程

4，二分查找

int BinSearch(int arr[],int low,int high,int num)
{
while(low<=high)
{
int mid=(low+high)/2;
if(num==arr[mid]) return mid;
else if(num < arr[mid]) high=mid-1;
else low=mid+1；
}
return -1；
}

5，希尔排序

void shellsort2(int a[], int n)
{
int j, gap;

for (gap = n / 2; gap > 0; gap /= 2)
for (j = gap; j < n; j++)//从数组第gap个元素开始
if (a[j] < a[j - gap])//每个元素与自己组内的数据进行直接插入排序
{
int temp = a[j];
int k = j - gap;
while (k >= 0 && a[k] > temp)
{
a[k + gap] = a[k];
k -= gap;
}
a[k + gap] = temp;
}
}

6，冒泡排序(在某趟冒泡排序过程中，若没有发现一个逆序对，就可以直接结束整个排序过程)

void bubble_sort(int arr[],int n)
{
int flag=1;
for(int i=0;i<n && flag;i++)
{
flag=0;
for(int j=0;j<n-i;j++)
if(a[j]>a[j+1])
{
int tmp=a[j];
a[j]=a[j+1];
a[j+1]=tmp;
flag=1;
}
}
}

7,选择排序

void select_sort(int arr[],int n)
{
for(int i=0;i<n;i++)
{
int k=i;
for(int j=i+1;j<n;j++)
if(a[j]<a[k])
k=j;
if(k!=i)
{
int tmp=a[i];
a[i]=a[k];
a[k]=tmp;
}
}
}

8，插入排序

void insert_sort(int arr[],int n)
{
for(int i=2;i<n;i++)
{
if(a[i]<a[i-1])
{
a[0]=a[i];
for(int j=i;a[0]<a[j];j--)
a[j+1]=a[j]; //记录后移
a[j+1]=a[0]; //插入到正确的位置
}
}
}

9，木桶排序

#include <stdio.h>
int main()
{
int a[11],i,j,t;
for(i=0;i<=10;i++)
a[i]=0; //初始化为0

for(i=1;i<=5;i++) //循环读入5个数
{
scanf("%d",&t); //把每一个数读到变量t中
a[t]++; //进行计数
}

for(i=0;i<=10;i++) //依次判断a[0]~a[10]
for(j=1;j<=a[i];j++) //出现了几次就打印几次
printf("%d ",i);
}

10，实现一个逆转函数

#!/usr/bin/env python
# coding=utf-8

 

string_reversed = lambda x:x[::-1]

if __name__ == '__main__':
s = 'abcde'
print string_reversed(s)