面试总结三

, interview and 考题

面试题目和思路总结

面试总结三

1、

int i;
if (!!i)

(!!i) 表示什么意思，即 (i)，这种表示方法是正确的。

2、

char* (*a)[2][3]，求 sizeof(a)

a 就是一个指向数组的指针，所以大小就是指针大小，32位机器就是4字节。面试官让我对这个数组初始化随便给几个元素赋值，我居然脑残式的直接写了

a[0][0][0] = "hello world";

然后问我，这个程序能跑起来吗，我实在不知道哪里出问题了，然后写了一个，说还可以写成这样

(*a)[0][0] = "hello world";

现在想想，其实面试官最想看到的是我对这个数组的动态申请内存的过程(抽风了)

a = malloc (sizeof(char*) * (2 * 3 * 2)); // 假设为 a[2][2][3]

这个时候上面那几个赋值都是可以的，还是自己理解能力不行。

3、 将一句英语翻转，但是单词不翻转。单词使用空格隔开，标点符号作为字符处理。比如

I am a student.
翻转后
student. a am I

现场做题量比较大，时间只有一个小时，我都是想到哪种方法，直接就写了，基本上没想怎么去优化的或者更好的办法。

第一时间想到的方法，就是先整个翻转句子，然后对每一个单词单个翻转一次。比如

I am a student.
翻转整个句子
.tneduts a ma I
然后对每一个单词翻转
students. a am I

4、 使用 binary search 搜索有序数组中的某个元素，如果元素不存在，那么返回元素中的大于该元素的最小值。

二分搜索，将数组整个分成了一个二叉树的结构，查找元素，如果找到就返回，如果找不到，那么大于该待查元素的最小元素应该位于所查找的分支的右边第一个节点。这是一个思路。

我当时的做法，没有这么复杂，直接使用二分搜索查找，但是每次对于 a[mid] 大于待查元素的时候，我就记录下这个 mid，即在数组中的下标索引位置，因为这样做，最终如果没有找到待查元素的时候，至少能获取一个比待查元素大且相对比较近的元素位置。

然后通过对这个位置的在有序数组中，往前搜索，与待查元素比较，直到找到一个比待查元素小的元素，那么下一个元素就是比待查元素大的最小的元素。

int bsearch (int a[], int n, int key) {
	int left = 0;
	int right = n-1;
	int greater = 0;	// 记录当 a[mid] > key 时的 mid

	while (left < right) {
		int mid = (left + right) >> 1;
		if (a[mid] == key) {
			return mid;
		} else if (a[mid] > key) {
			greater = mid;
			right = mid - 1;
		} else if (a[mid] < key) {
			left = mid + 1;
		}
	}
	// 未找到
	while (greater >= 0) {
		if (a[greater] > key) {
			greater--;
		} else if (a[greater] < key) {
			break;
		}
	}

	if (greater<0) { // 说明全部都比 key 大
		return a[0];
	} else {
		return a[greater + 1];
	}
}

应该还有比这个更有的方法。

5、 随机打印 1-100 以内的所有整数，每一个整数只能打印一次

这个题目，我的思路当时是每次打印，都将之前打印的比较一遍，如果是重复的，那么就重新生成一个随机数，但是这种思路，时间复杂度比较高，每次都需要对之前已经生成的所有数字进行比较，有没有更好的办法呢，想到了用数组下标作为生成的随机数，用数组对应的元素作为打印的值的办法，这个办法确实解决每次对之前所有已打印的值的比较去重的问题。比如

随机打印 1-10 之间的所有整数，创建一个数组，初始化为

a[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

如果随机生成一个数 random()%10 为 8，那么打印 a[8] 位数字 9，此时，9 这个数字需要从数组中删除，才能下一次随机生成的时候，不会重复。

这里，将 a[8] 即数字 9 与 a[9] 即数组最后一个元素交换，那么此时，数组为

a[10] = {1, 2, 3, 4, 5, 6, 7, 8, 10, 9};

下一次，计算随机数的时候，使用 random()%9 来生成随机数，生成的随机数的范围为 0-8，把随机数作为数组下标，那么此时，得到的数组中的值，就不会取到之前打印的 9 了。

void printNum (int n) {		// 随机打印 1 - n 个整数
	if (n <= 0) {
		return;
	}
	int *a = malloc (sizeof(int) * n);
	if (NULL == a) {
		exit (EXIT_FAILURE);
	}

	int i;
	for (i=0; i<n; i++) {
		a[i] = i + 1;
	}

	while (n >= 1) {
		int idx = random() % n;
		printf ("%d, ", a[idx]);

		swap (a[idx], a[n-1]);
		n--;
	}
}