两道TB面试题
1：有一个数列，它由3个数列复合而成，并升序排列。三个数列分别是2的n次，3的n次，5的n次，0 <= n < 无穷大
给出前几项：1,2,3,4,5,8,9,16,25,27………………即2^0(3^0, 5^0) , 2^1, 3^1, 2^2, 5^1, 2^3, 3^2, 4^2, 5^2, 3^3 。 。 。
问你如何快速得到第1000个数的值。。。。
2：用C语言写一个函数，将字符串按空格拆分。比如 Hello, Welcome to forget-wind's blog. 拆分成"Hello," , "Welcome", "to", "forget-wind's", "blog."5个串。
第一题:
我的思路如下：
首先，考虑到数列的指数表现形式，第1000个数必定是一个大数，做大数运算的龟速必然不能快速求得结果，所以必须避开大数运算。
然后，要求的是数列的第1000个数，如果避开大数运算，则O(1000)的复杂度也是满足题目要求的。
考虑到这两点，问题就可以转换为：如何比较以指数形式表示的两个数的大小？（如2^i 与 3^j 比较大小）。
(⊙_⊙)既然不可以直接比较，那就只能想法去掉指数次幂，所以. . .两边同时取对数就可以了。。。
化简一下：2^i 与 3^j 的比较 -------- i 与 log2 (3) * j 的比较 （以2为底3的对数）-------- i 与 lg 3 / lg 2 * j -------- i * lg2 与 j * lg3。
用C++代码实现了一下，如下：
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
struct Node {
int base;
int exp;
Node (int base, int exp) {
this->base = base;
this->exp = exp;
}
};
Node* Min(Node *a, Node *b) {
if (a->exp * log(a->base) > b->exp * log(b->base)) {
return b;
}
return a;
}
Node* Min(Node *a, Node *b, Node *c) {
Node *min = Min(a, b);
return Min(min, c);
}
int main() {
Node *a = new Node(2, 0);
Node *b = new Node(3, 1);
Node *c = new Node(5, 1);
Node *min = NULL;
for (int t = 1; t <= 1000; t++) {
min = Min(a, b, c);
min->exp++;
}
cout << "The 1000th number is : " << endl; cout << "base: " << min->base << endl;
cout << "exp" << " : " << min->exp - 1 << endl << endl;
delete a; a = 0 ;
delete b; b = 0;
delete c; c = 0;
return 0;
}
问题一扩充：假设面试官要你求的不是数列的第1000个，而是... ... 第1000,000,000个数呢？
那么O（n）的复杂度则显得有点力不从心了。
还好，某龙大神说了一句：
二分枚举2的倍数,然后去找3,5的比枚举小的(这里是O(log(n)) --------- log(n)*log(n)的复杂度
有想法了么？
龙神一句话，顿悟了。
1: 问题求的是数列中的第len个数。
因为数列是有2^n, 3^n, 5^n 符合而成， 所以第len个数必然可以以2^n, 3^n, 5^n 其中之一的形式表示。
我们可以转换为 求 2^i <= 第len个数，求满足条件的最大的 i 。
同理：也可以求 3^j <= 第len个数， 求满足条件的最大的 j， 同理最大的k 。
（因为数列的构造性质，上诉必然有一个可以取得 等于号，即确定了第len个数的值。）
------------问题转换为怎样求这个 i 的最大值。
2：假设一直数列中某个数为2^i 次方，那么它是数列中的第几个数呢？ 正因为有序性，我们可以在log（n）内确定这个值。
即求满足 3^j < 2^i （此时 i 值确定）时 j 的最大值。----- 二分 j 就可以了。
同理， 二分 k 求得满足条件的k的最大值。 此时就求得 2^i 是数列的第 i + j + k +１个数（1是因为 0 次方）。
然后 1 中要求2^i <= 第len个数时 i 的最值，因为数列是复合有序的，所以 i 增大时，j 增大（3^j < 2^i ），k 增大，
i + j + k + 1的值也随之增大。
则有 2^i <= 第len个数时 i 的最值 等价于 i + j + k + 1 <= len时 i 的最值。 也因此可以通过二分 i 求解。
下面是log(n) * log(n)算法-我的C++实现：
#include <iostream>
#include <cstdlib>
#include <cmath>
using namespace std;
struct Node { //指数形式存贮一个数
int base; //基数域
int exp; //指数域
Node () : base(2), exp(0) {}
Node (int base, int exp) {
this->base = base;
this->exp = exp;
}
};
Node *Min(Node *a, Node *b) {
/*返回用指数表示的两个数中较小的那个数的指针*/
if (a->exp * log(a->base) > b->exp * log(b->base)) {
return b;
}
return a;
}
Node *Min(Node *a, Node *b, Node *c) {
/*返回用指数表示的三个数中最小的那个数的指针*/
Node *min = Min(a, b);
return Min(min, c);
}
int Binary_Search(int base, int len, Node *a, Node *b) {
int low = 1, high = len;/*
/*b值确定的情况下，求一个用指数形式表示的数a，
满足(a->base)^(a->exp) < b，使得a最大，返回数a的指数域（a->exp）*/
while (low <= high) {
int mid = (low + high) >> 1;
a->base = base;
a->exp = mid;
Node *min = Min(a, b);
if (min->base == a->base) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return low - 1;
}
int Binary_Solve(int base0, int base1, int base2, int len, int &ans) {
//求满足条件“base0^t <= 第len个数”下, t的最大值，t值用引用值ans返回。
int low = 0, high = len;
Node *p = new Node;
Node *q = new Node(base0, 0);
int mid = 0, m = 0, n = 0;
int ret = 0;
while (low <= high) {
mid = (low + high) >> 1;
q->exp = mid;
m = Binary_Search(base1, len, p, q);
n = Binary_Search(base2, len, p, q);
if (mid + m + n + 1 <= len) {
low = mid + 1;
ret = low + m + n;
} else {
high = mid - 1;
}
}
ans = low - 1;
delete p; p = 0;
delete q; q = 0;
//ret表示base0^t次是数列中的第ret个数
return ret;
}
int main() {
int n, ans;
cout << "Enter the index of the number: ";
while (cin >> n) {
cout << "The " << n << "th number is : " << endl;
if (Binary_Solve(2, 3, 5, n, ans) == n) {
cout << "base: " << 2 << endl;
} else if (Binary_Solve(3, 5, 2, n, ans) == n) {
cout << "base: " << 3 << endl;
} else if (Binary_Solve(5, 2, 3, n, ans) == n) {
cout << "base: " << 5 << endl;
}
cout << "exp" << " : " << ans << endl << endl << endl;
system("pause");
system("cls");
cout << "Enter the index of the number: ";
}
return 0;
}
第二题：
不在于考察你实现的速度和功能，而在于考察代码质量。
空格拆分？=。= 这个简单。 -------- 我传一个二维数组进去，把字符串拆分后依次保存在这个二维数组中不就行了么？
/*--------------------------------------------------------------------------------------------------------*/
=_=|| 很快敲完，到面试官问问题了，这个二维数组该怎么开，你怎么确定数组的大小呢？
上面两道是前天淘宝实习生杭州站我认为比较好的两道面试题（没机会参加面试，也就差不多只知道这么两道. . .）。
以上是我一些同学第一次参见面试时的一些经历，两个同学就死在了这看似简单的第二题上。
---- Pass： 我更惨 . . . 笔试直接被刷掉了，没机会被鄙视，囧。
回来听他们讲诉面试经历，于是自己思考和实现了下他们遇到的其中两道面试题。
/*--------------------------------------------------------------------------------------------------------*/
我的想法是：
既然二维数组的大小不好控制，那么，动态分配空间是可以解决这个问题的。
（由于以前做acm不常用指针，甚至是避免用指针 ---- 因为在有限的时间里，侧重于追求代码的高效性和稳定性(指针用的不熟很容易造成程序崩溃)。
--- 这样分析一下，这大概也就是我去面试的同学挂在这道题的内因吧。）
我的具体做法：
建立存储结构如下，用链表实现：
struct Node {
char *ch; //指向字符串按' '拆分的各首字符指针
struct Node *next; //下一个结点
};
则函数传参时只需要传递链表的头结点。
if (str[i] 为拆分后单词的首字符) {
在表尾建立新结点，并让其ch域指向单词首字符的地址;
让指针指向表尾结点。
}
这样就避免了如，二维数组大小是多少那样的不确定性问题。
以下是我的C语言实现：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct Node {
char *ch;
struct Node *next;
}Node, *PNode;
void calWord(PNode head, char str[], int lstr) {
PNode p = head;
int i;
if (lstr > 0 && str[0] != ' ') {
p->next = (PNode)malloc(sizeof(Node));
p = p->next;
p->ch = &str[0];
p->next = NULL;
}
for (i = 0; i < lstr; i++) {
if (' ' == str[i])
str[i] = 0;
}
for (i = 1; i < lstr; i++) {
if (0 == str[i-1] && str[i] != 0) {
p->next = (PNode)malloc(sizeof(Node));
p = p->next;
p->ch = &str[i];
p->next = NULL;
}
}
p = head;
}
void del(PNode p) {
while (p->next != NULL) {
PNode q = p;
p = p->next;
free(q);
}
free(p);
}
int main() {
char str[] = "Hello, Welcome to forget-wind's blog.";
PNode p = (PNode)malloc(sizeof(Node));
int len = strlen(str);
p->next = NULL;
calWord(p, str, len);
while (p->next != NULL) {
p = p->next;
printf("%s\n", p->ch);
}
del(p);
return 0;
}
虽然没去面试，但总结一下前人的经验还是有好处的吧。。。
原创文章如转载请注明：转自￥忘%风 {http://www.cnblogs.com/slave_wc}
本文地址: 两道TB面试题