一起来编程

2015-07-14 09:33

关注

面试题目收集

1.google 一道面试题目：一个数列中 Q 中的每个元素至少能被 a 和 b 中的一个元素整除。现给定 a 和 b ，要求计算出 Q 的前几项。例如 a=3 ， b=5 ，则序列： 3,5,6,9,10,12....

思路：设计两个 index ，分别指向被 3 和被 5 整除的数，被 3 整除的数只能每次递增 3 ，被 5 整除的数只能每次递增 5 。判断那个小，就添加到数组中，将添加到数组中的索引指向当前的索引。

个人觉得：这个何海涛里面的丑数解法有点雷同，我也是这么悟出来的，必须要设置一个数组保存前面的值

[cpp] view plain copy print ?

#include <iostream>

#include <cstdlib>

#include <exception>

using namespace std;

void printArr(int arr[],int len)

{

if(arr==NULL || len<0)

throw new runtime_error("Invalid Input");

for(int i=0; i<len; ++i){

cout<<arr[i]<<" ";

}

cout<<endl;

}

void PrintQ(int num)

{

int *arr = NULL;

arr = new int[num];

int fiveIndex = 1;

int threeIndex = 0;

int index = 2;

arr[0] = 3;

arr[1] = 5;

while(index<num){

int addFive = arr[fiveIndex] + 5;

int addThree = arr[threeIndex] + 3;

int min = addThree<=addFive?addThree:addFive;

if(min == addThree)

threeIndex = index;

if(min == addFive)

fiveIndex = index;

arr[index++] = min;

}

printArr(arr,num);

delete[] arr;

}

int main()

{

cout<<"By lsj: http://www.nowcoder.com/discuss "<<endl;

PrintQ(10);

system("pause");

return 0;

}

2. 剑指 offer 上面的丑数：我们只把包含 2 、 3 、 5 的数称作丑数，习惯把 1 称为第一个丑数，求从小到大顺序的 num 个抽数。

呵呵：按照上面的思想重新解了一遍，换汤不换药。海涛老师给我的灵感。

[cpp] view plain copy print ?

#include <iostream>

#include <cstdlib>

#include <exception>

using namespace std;

void printArr(int arr[],int len)

{

if(arr==NULL || len<0)

throw new runtime_error("Invalid Input");

for(int i=0; i<len; ++i){

cout<<arr[i]<<" ";

}

cout<<endl;

}

int Min(int a,int b,int c)

{

int t = a<b?a:b;

return t<c?t:c;

}

void PrintUglyNum(int num)

{

int *arr = NULL;

arr = new int[num];

int twoIndex = 0;

int fiveIndex = 0;

int threeIndex = 0;

int index = 1;

arr[0] = 1;

while(index<num){

int mutTwo = arr[twoIndex] * 2;

int mutFive = arr[fiveIndex] * 5;

int mutThree = arr[threeIndex] * 3;

int mindata = Min(mutTwo,mutThree,mutFive);

if(mindata == mutTwo)

++twoIndex;

if(mindata == mutThree)

++threeIndex;

if(mindata == mutFive)

++fiveIndex;

arr[index++] = mindata;

}

printArr(arr,num);

delete[] arr;

}

int main()

{

cout<<"By lsj: http://www.nowcoder.com/discuss "<<endl;

PrintUglyNum(11);

system("pause");

return 0;

}

3.google 的一道笔试题目：一个字符串，压缩其中的连续空格为 1 个后，对其中的每个字串逆序打印出来。比如 "abc efg hij" 打印为 "cba gfe jih" 。

思路：用 string 来解还是蛮不错的，然后借助栈来翻转，省得字符串烦来烦去

[cpp] view plain copy print ?

#include <iostream>

#include <string>

#include <stack>

using namespace std;

string reverseStr(string str)

{

int len = str.size();

string ret;

stack<char> st;

bool begin = true;

for(int i=0; i<len;){

if(i<len && str[i] == ' '){

if(!begin)ret.append(1,' ');

begin = false;

while(str[i]==' ')

i++;

}

else{

while(i<len && str[i] != ' '){

st.push(str[i]);

i++;

}

while(!st.empty()){

ret.append(1,st.top());

st.pop();

}

return ret;

}

int main()

{

string str = string(" abc lsj hlj");

cout<<reverseStr(str)<<endl;

system("pause");

return 0;

}

4. 面试员宝典的一道笔试题目：一个字符串，压缩其中的连续空格为 1 个后，对其中的每个字串逆序打印出来。比如 "i am lsj" 打印为 "lsj am i" 。

思路：先整体翻转，然后单词部分翻转

[cpp] view plain copy print ?

#include <iostream>

#include <string>

#include <stack>

using namespace std;

void reverseSub(char str[],int start,int end)

{

if(!str||start<0||end<0)

throw new runtime_error("Invalid Input");

if(start>=end)

return;

for(;start<end;++start,--end){

char t = str[start];

str[start] = str[end];

str[end] = t;

}

void reverseStr(char str[])

{

int len = strlen(str);

reverseSub(str,0,len-1);

int beg = 0;

int end =0;

cout<<str<<endl;

for(int i=0; i<len;){

while(i<len && str[i] != ' ')++i;

end = i - 1;

reverseSub(str,beg,end);

while(i<len && str[i] == ' ')++i;

beg = i;

}

int main()

{

char str[] = "ss i am lsj";

reverseStr(str);

cout<<str<<endl;

system("pause");

return 0;

}

5 。描述在浏览器中敲入一个网址并按下回车后所发生的事情（尽量详细）

答：浏览器输入网址之后，首先
步骤 1 ：需要查找域名的 IP 地址， DNS 查找过程如下：

（ 1 ）浏览器缓存 – 浏览器会缓存 DNS 记录一段时间。有趣的是，操作系统没有告诉浏览器储存 DNS 记录的时间，这样不同浏览器会储存个自固定的一个时间（ 2 分钟到 30 分钟不等）。

（ 2 ）系统缓存 – 如果在浏览器缓存里没有找到需要的记录，浏览器会做一个系统调用（ windows 里是 gethostbyname ）。这样便可获得系统缓存中的记录。

（ 3 ）路由器缓存 – 接着，前面的查询请求发向路由器，它一般会有自己的 DNS 缓存。

（ 4 ） ISP DNS 缓存 – 接下来要 check 的就是 ISP 缓存 DNS 的服务器。在这一般都能找到相应的缓存记录。

（ 5 ）递归搜索 – 你的 ISP 的 DNS 服务器从跟域名服务器开始进行递归搜索，从 .com 顶级域名服务器到 Facebook 的域名服务器。一般 DNS 服务器的缓存中会有 .com 域名服务器中的域名，所以到顶级服务器的匹配过程不是那么必要了。

步骤 2 ：浏览器给 web 服务器发送一个 HTTP 请求。 请求中也包含浏览器存储的该域名的 cookies 。可能你已经知道，在不同页面请求当中， cookies 是与跟踪一个网站状态相匹配的键值。这样 cookies 会存储登录用户名，服务器分配的密码和一些用户设置等。 Cookies 会以文本文档形式存储在客户机里，每次请求时发送给服务器。