いくつかの面接問題、ソースコードを添付(続き)


前に実習を探して、面接官がくれたいくつかの面接問題を探して、私の具体的なやり方を分かち合います.
1.一連の数を与えて、その中の余分なスペースを取り除いて、例えば“I am leader”、出力の結果は“I am leader”で、メモリを占有するのが最小で、速度が最も速いことを要求します.
分析:
メモリの消費量が最小で、必ずサイクル数が最小で、コピー文字列の回数が最小で、サイクル数については、私たちは1回だけサイクルしたいのですが、どうすればいいのでしょうか.スペースの後ろにスペースがあるかどうかを判断することができます.もしあるなら、ここでマークmarkを作って、別のマークkを利用してどれだけの余分なスペースを記録して、スペースではない文字に出会うまで、ここの鍵はどのように連続するスペースを判断して、どのように越えるかです.肝心な問題はこの条件をどのように書くかです.もし1つのスペースに出会ったら、彼の下のマークがiだと仮定して、私たちはwhileサイクルで次にどれだけのスペースがあるかを判断して、累計してkつのスペースを計算して、どのようにこれらのスペースを前にコピーしますか?
ソース実装:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int pickout(char *data, int length) {
	int mark = 0;
	int spaces = 0;
	int i;
	for (i = 0; i < length; i++) {
		if (data[i] == ' ') {
			spaces++;
		} else {
			spaces = 0;
		}
		if (spaces < 2) {
			if (mark != i) {
				data[mark] = data[i];
			}
			mark++;
		}
	}
	data[mark] = '\0';
	return mark;
}

int main(void) {
	char data[] = "I am        leader   h! as   ASD";
	int length = strlen(data);
	pickout(data, length);
	printf("%s
", data); return 0; }

もう1つの実装:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int pickout(char*data, int length) {
	int i, k;
	int mark;
	for (i = 0, mark = 0; i < length; i++) {
		if (data[i] == ' ') {
			k = 0;
			while (data[i + k + 1] == ' ') {
				k++;
			}
			if (k > 0) {
				i = i + k;
			}
		}
		if (i > mark) {
			data[mark] = data[i];
		}
		mark++;
	}
	data[mark] = '\0';
	return 0;

}

int main(void) {
	char data[] = "I am        leader   h! as   ASD";
	int length = strlen(data);
	pickout(data, length);
	printf("%s
", data); return 0; }

出力結果は
I am leader h! as ASD

1回だけループするので計算の複雑さはnである.
2.昇順で並べ替えられた2つの列に、1つのサイクルだけで同じ数を見つけることが要求され、メモリの消費量が最小で、アルゴリズムの複雑さが最小であることが要求されます.
ソース実装:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int CalSameNum(int *data1, int length1, int *data2, int length2) {
	int i = 0, j = 0;
	int count = 0;
	if (data1[0] > data2[length2 - 1] || data1[length1 - 1] < data2[0]) {
		return count;
	}
	while (i < length1 && j < length2) {
		while (data1[i] > data2[j]) {
			j++;
		}
		if (data1[i] == data2[j]) {
			count++;
			j++;
		}
		i++;
	}
	return count;
}
int main(void) {
	int data1[] = { 1, 3, 5, 6, 9, 10, 12, 24, 45, 46 };
	int data2[] = { 1, 4, 6, 7, 9, 12, 32, 45, 46, 50, 102, 345 };
	int length1 = sizeof(data1) / sizeof(int);
	int length2 = sizeof(data2) / sizeof(int);
	int num = 0;
	num = CalSameNum(data1, length1, data2, length2);
	printf("%d
", num); return 0; }

出力結果は次のとおりです.
6

1回だけループするので計算の複雑さはnである.
3.一連の数を4で割って余剰を取り、10,3,32,45,65,12などの余剰の大きさで並べます.余剰は2,3,0,1,1,0...,そのソートの結果は32,12,45,65,10,3...,アルゴリズムの複雑さが最も低いことが要求される.彼の複雑さはnlg(n)ですか.まだ向上できますか?
4.ソースコードのコメントを削除するように要求します.例えば、'/*/'、および"//".
ほぼ文字列マッチングです.
ソースコードは次のとおりです(linuxプラットフォーム):
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <fcntl.h>
#include <unistd.h>
#include <sys/stat.h>
#include <sys/types.h>
#include <assert.h>
#include <sys/mman.h>

int EraseNotes(char *path){
	int fdin;
	int size = 0, i = 0, mark = 0, p = 0;

	char *str = NULL;
	struct stat statbuf;
	if ((fdin = open(path, O_RDWR)) == -1) {
		printf("no such file!
"); return 1; } assert(fstat(fdin, &statbuf) == 0); // size = statbuf.st_size; // c map 。 str = (char *) mmap(0, size, PROT_READ | PROT_WRITE, MAP_SHARED, fdin, 0); if (str == MAP_FAILED ) { printf("map failed!
"); return 1; } // printf("%s
", str); for (i = 0; i < size; i++) { if (str[i] == '/' && str[i + 1] == '*') { mark = 1; p = i; } else if (str[i] == '/' && str[i + 1] == '/') { mark = 2; p = i; } if (mark == 1) { if ((str[i] == '*' && str[i + 1] == '/')) { memset(str + p, ' ', i - p + 2); mark = 0; } } else if (mark == 2) { if (str[i] == 0xa) { memset(str + p, ' ', i - p + 1); mark = 0; } } } printf("%s
", str); //call of mmap munmap(str, size); close(fdin); return 0; } int main(void) { char *path = "123"; EraseNotes(path); return 0; }

123ファイルの内容は
//as/
/*
 *
 *
 * as
 */
main()
as
12
//as
//asddasd
/*
 *
 */

出力結果は
                        
main()
as
12