腾讯面试题2

1、首先给一个地址http://pay.qq.com/include/login_box.html?url=http://pay.qq.com/
有工具 比如 firefox 、 google chrome 等网页代码查看工具。要求用一段 js 实现下列功能已知 用户名 和 明文密码，实现 提交的过程，如果中间出现校验码，捕获校验码的图片。

答：首先找出iframe的src是
http://ui.ptlogin2.qq.com/cgi-bin/login?appid=11000101&f_url=loginerroralert&hide_title_bar=1&link_target=blank&ep=http://pay.qq.com/cgi-bin/login/qqacctlogin.cgi&s_url=http://pay.qq.com/&qlogin_jumpname=payjump&qlogin_param=url%3Dhttp://pay.qq.com/
通过这个页面能查到js具体功能由这个实现，加载图片的函数οnlοad='imgLoadReport()'就在这里
http://imgcache.qq.com/ptlogin/ac/v9/js/comm.js?v=1.2.5

校验函数ptui_onLogin

JScript code

function ptui_onLogin(A){

try{if(parent.ptlogin2_onLogin){

if(!parent.ptlogin2_onLogin()) 

{return false}}

if(parent.ptlogin2_onLoginEx){

var D=A.u.value;var B=A.verifycode.value;

if(str_uintip==D) {D=""}if(!parent.ptlogin2_onLoginEx(D,B)){return false}} 

}catch(C){}

return ptui_checkValidate(A) 

}
通过这个函数，貌似图片的信息会赋值给A.u这个label，然后校验你输入的A.verifycode.value和它是不是相同
解决的思路是
调用imgLoadReport，取到A.u即image里的值
调用submit
具体细节大家感兴趣再研究下吧

输入QQ号或者是QQ绑定的邮箱，当输入框失去焦点后，会进行验证以确定是否需要验证码（验证码的形式分两种，一种是生成一个图片，需要用户输入指定的字符，一种是程序返回时自带验证码，不用用户输入；有一种情况是不会触发请求的：清空输入框后，重新输入相同的字符串）

输入密码

如果需要，输入验证码

提交表单（这一过程中会将密码和验证码合并加密）

整个过程中的请求都是用<script>来完成的

验证图片的获取：

在整个登录过程中，没有发现一全局的状态变量可以用来判断是否生成了验证图片，但是程序中会有这样一个过程：当帐号输入框失去焦点后，如果本次输入的帐号与上次的不同，则会发送一个验证码请求，图片路径生成以后会使验证码输入框可见，并使密码输入框获取到焦点。所以可以从这里想办法获取到当前有的并且正确的图片路径。

以下是提交代码，没有写在生成了验证图片时获取并输入验证码的过程(只是猜测不会让你可以通过分析代码获取到的,如果有人分析出来了，那就爽了!!!):

JScript code

function loginIt(u, p) {var ubox= document.getElementById('u');var pbox= document.getElementById('p');var img= document.getElementById('imgVerify');var vf= document.getElementById("verifyinput");var s= ""; ubox.focus(); ubox.value= u;if(g_uin== u){ up(); }else { addEvent(pbox,'focus', up); ubox.blur(); }function addEvent(o, t, f) {if(o.att) { o.attachEvent('on' + t, f); }else if(o.addEventListener) { o.addEventListener(t, f,false); } }function up() {if(img.src&& vf.style.display== '') { s= img.src; alert(s); } pbox.value= p; document.getElementById('loginform').submit(); } }

2、QQ怎么实现多用户登录

    为每一个QQ用户创建一个以QQ号码命名的文件夹，将其信息都存放在这个文件夹里面!

3、如何迅速的告知用户资料之类

    根据QQ号码查询！

4、假设电信每分钟登录次数是60w次，现在要提醒5分钟内重复登录的用户，如何设计程序缓存和查找算法？

用内存数据库（IMDB）可以解决，如eXtremeDB或者Oracle的TimesTen，在稍好点的机器上可以每秒钟可以插入或者更新30w+条记录。也就是说每分钟可以处理1800w+个插入或者更新。所以这样性能完全可以满足第1个问题的要求。
     或者是：

对IP 段进行排序从小到大，后进来的进行插入排序，然后每个节点带一个时间戳，如果是少于5分钟，就提示，数据结构可以考虑链表
    

5、QQ数据库的用户信息表现在有5亿多条记录，现在请给出怎么样设计，使通过QQ号码查询QQ用户信息的速度更快。。用怎么样的算法算出查询大概需要多少的系统开销。

    用到了下面全部或者部分方法(或许腾讯他们还有更好的方法吧)：
  a. 数据存放在磁盘阵列上，磁盘阵列可以大幅度提高IO能力
  b. 数据库文件存放在raw设备上，这样也是速度最快的
  c. 数据库系统参数优化
  d. 数据表分区。大表分区会提高查询新能
  e. 用QQ号作为主键(即唯一+非空，速度本身就非常非常快的)

6、到商店里买200的商品返还100优惠券（可以在本商店代替现金）。请问实际上折扣是多少？

答：用200元买了300元的东西，折扣就是=300-200/300=1/3  打折就是2/3 但是如果消费者不用的话，相当于没有打折扣！

第三道题目的答案是不确定的！
  真正的答案是有商家自己确定的，这在营销学里面是个很简单的问题 !
  通常在商家进行促销的时候，都会提高商品的价格，然后通过商品的折扣形式，来吸引顾客。以返还为例。原本商品是100，现在提高到200在返还100其实结果还是100.呵呵！
  腾讯处这个题目的出发点是考察考生对市场营销的一些基本知识的了解！
  楼主加油！
7、 有无序的实数列V[N]，要求求里面大小相邻的实数的差的最大值，关键是要求线性空间和线性时间 

8、 25匹赛马，5个跑道，也就是说每次有5匹马可以同时比赛。问最少比赛多少次可以知道跑得最快的5匹马 

9、 有一个函数int getNum()，每运行一次可以从一个数组V[N]里面取出一个数，N未知，当数取完的时候，函数返回NULL。现在要求写一个函数int get()，这个函数运行一次可以从V[N]里随机取出一个数，而这个数必须是符合1/N平均分布的，也就是说V[N]里面任意一个数都有1/N的机会被取出，要求空间复杂度为O（1）

10、史密斯夫妇晚上开了个party，他们一共邀请了另外4对夫妇。晚会结束后，史密斯先生问其他的所有人跟其他人握手的次数。结果得到的结果各不相同。已知每个人不能跟他的配偶握手，也不能跟同一个人握多次手。请问：史密斯太太一共握了多少次手？
   答：首先握手8次和握手0次的人必然是配偶（握手8次的人同余下人都握过一次手了，其中一个已经和8个人都握过手了，那么他的配偶就不可以和其他人握手了！）
   8，0-7，1-6，2-5，3-4，4 -----因为最后得到的结果各不相同，则只有史密斯夫人是4次
11、static 变量概念，举例子；

Static变量是静态变量，存放在全局数据区，如果没有初始化会自动初始化为0，不会因为函数的退出而释放空间，不能被外部文件所调用，也就是你定义了一个static变量，在其作用域内，你可以对其值进行操作，但是不会释放其所占的空间。

1、静态全局变量 　　

在全局变量前，加上关键字static，该变量就被定义成为一个静态全局变量。我们先举一个静态全局变量的例子，如下： 　　

//Example 1 　　

#include <iostream.h> 　　

void fn(); 　　

static int n; //定义静态全局变量 　　

oid main() 　　

{ n=20; 　　

cout<<n<<endl; 　

fn(); 　

　} 　　

void fn() 　　

{ n++; 　　

cout<<n<<endl; 　

　} 　　

静态全局变量有以下特点： 　　

该变量在全局数据区分配内存； 　　

未经初始化的静态全局变量会被程序自动初始化为0（ 在函数体内声明的自动变量的值是随机的，除非它被显式初始化，而在函数体外被声明的自动变量也会被初始化为0）； 　　静态全局变量在声明它的整个文件都是可见的，而在文件之外是不可见的； 　　

静态变量都在全局数据区分配内存，包括后面将要提到的静态局部变量。对于一个完整的程序，在内存中的分布情况如下图： 　　

代码区 //low address 　　

全局数据区 　　

堆区 　　

栈区 //high address 　　

一般程序把新产生的动态数据存放在堆区，函数内部的自动变量存放在栈区。自动变量一般会随着函数的退出而释放空间，静态数据（即使是函数内部的静态局部变量）也存放在全局数据区。全局数据区的数据并不会因为函数的退出而释放空间。细心的读者可能会发现，Example 1中的代码中将 　　

static int n; //定义静态全局变量 　　

改为 　　int n; //定义全局变量 　　

程序照样正常运行。 　　

的确，定义全局变量就可以实现变量在文件中的共享，但定义静态全局变量还有以下好处： 　　

静态全局变量不能被其它文件所用； 　　

其它文件中可以定义相同名字的变量，不会发生冲突； 　　

您可以将上述示例代码改为如下： 　　

//Example 2//File1 　　

#include <iostream.h> 　　

void fn(); 　　

static int n; //定义静态全局变量 　　

void main() 　　

{ n=20; 　　

cout<<n<<endl; 　　

fn(); 　　

} 　　//File2 　　

#include <iostream.h> 　　

extern int n; 　　

void fn() 　　

{

 n++; 　　

cout<<n<<endl; 　　

} 　　

编译并运行Example 2，您就会发现上述代码可以分别通过编译，但运行时出现错误。 试着将 　　

static int n; //定义静态全局变量 　　改为 　　int n; //定义全局变量 　　

再次编译运行程序，细心体会全局变量和静态全局变量的区别。 　　

注意：全局变量和全局静态变量的区别 　　

1）全局变量是不显式用static修饰的全局变量，但全局变量默认是动态的，作用域是整个工程，在一个文件内定义的全局变量，在另一个文件中，通过extern 全局变量名的声明，就可以使用全局变量。 　　

2）全局静态变量是显式用static修饰的全局变量，作用域是所在的文件，其他的文件即使用extern声明也不能使用。 　　

2、静态局部变量 　　

     在局部变量前，加上关键字static，该变量就被定义成为一个静态局部变量。 　　

我们先举一个静态局部变量的例子，如下： 　　

//Example 3 　　

#include <iostream.h> 　　

void fn(); 　　

void main() 　　

{ fn(); 　　fn(); 　　fn(); 　　} 　　

void fn() 　　{ static int n=10; 　　cout<<n<<endl; 　　n++; 　　} 　　

通常，在函数体内定义了一个变量，每当程序运行到该语句时都会给该局部变量分配栈内存。但随着程序退出函数体，系统就会收回栈内存，局部变量也相应失效。 　　

但有时候我们需要在两次调用之间对变量的值进行保存。通常的想法是定义一个全局变量来实现。但这样一来，变量已经不再属于函数本身了，不再仅受函数的控制，给程序的维护带来不便。 　　

静态局部变量正好可以解决这个问题。静态局部变量保存在全局数据区，而不是保存在栈中，每次的值保持到下一次调用，直到下次赋新值。 　　

静态局部变量有以下特点： 　　

该变量在全局数据区分配内存； 　　

静态局部变量在程序执行到该对象的声明处时被首次初始化，即以后的函数调用不再进行初始化； 　　

静态局部变量一般在声明处初始化，如果没有显式初始化，会被程序自动初始化为0； 　　它始终驻留在全局数据区，直到程序运行结束。但其作用域为局部作用域，当定义它的函数或语句块结束时，其作用域随之结束； 

   

12、虚函数概念，举例子；

定义：在某基类中声明为 virtual 并在一个或多个派生类中被重新定 义的成员函数 [1] 　　 语法：virtual 函数返回类型 函数名（参数表） { 函数体 } 　　

用途：实现多态性，通过指向派生类的基类指针，访问派生类中同名覆盖成员函数 　　 虚函数必须是基类的非静态成员函数，其访问权限可以是protected或public，在基类的类定义中定义虚函数的一般形式：

虚函数的作用是实现动态联编，也就是在程序的运行阶段动态地选择合适的成员函数，在定义了虚函数后，可以在基类的派生类中对虚函数重新定义，在派生类中重新定义的函数应与虚函数具有相同的形参个数和形参类型。以实现统一的接口，不同定义过程。如果在派生类中没有对虚函数重新定义，则它继承其基类的虚函数。 　　

当程序发现虚函数名前的关键字virtual后，会自动将其作为动态联编处理，即在程序运行时动态地选择合适的成员函数。虚函数是C++多态的一种表现。 

   　定义虚函数的限制：

（1）非类的成员函数不能定义为虚函数，类的成员函数中静态成员函数和构造函数也不能定义为虚函数，但可以将析构函数定义为虚函数。实际上，优秀的程序员常常把基类的析构函数定义为虚函数。因为，将基类的析构函数定义为虚函数后，当利用delete删除一个指向派生类定义的对象指针时，系统会调用相应的类的析构函数。而不将析构函数定义为虚函数时，只调用基类的析构函数。 　　

（2）只需要在声明函数的类体中使用关键字“virtual”将函数声明为虚函数，而定义函数时不需要使用关键字“virtual”。 　　

（3）当将基类中的某一成员函数声明为虚函数后，派生类中的同名函数自动成为虚函数。 　　（4）如果声明了某个成员函数为虚函数，则在该类中不能出现和这个成员函数同名并且返回值、参数个数、类型都相同的非虚函数。在以该类为基类的派生类中，也不能出现这种同名函数。 　　

虚函数联系到多态，多态联系到继承。所以本文中都是在继承层次上做文章。没了继承，什么都没得谈。

class A{ 　　

public: 　　

virtual void print(){ cout<<"This is A"<<endl;} //现在成了虚函数了 　　}; 　　

class B:public A{ 　

　public: 　　

void print(){ cout<<"This is B"<<endl;} //这里需要在前面加上关键字virtual吗？ 　　}; 　　毫无疑问，class A的成员函数print（）已经成了虚函数，那么class B的print（）成了虚函数了吗？回答是Yes，我们只需在把基类的成员函数设为virtual，其派生类的相应的函数也会自动变为虚函数。所以，class B的print()也成了虚函数。那么对于在派生类的相应函数前是否需要用virtual关键字修饰，那就是你自己的问题了。

class A{ //虚函数示例代码 　　

public: 　　

virtual void fun(){cout<<1<<endl;} 　　

virtual void fun2(){cout<<2<<endl;} 　　}; 　　

class B:public A{ 　　

public: 　　

void fun(){cout<<3<<endl;} 　　

void fun2(){cout<<4<<endl;} 　　}; 

13、拷贝构造函数的概念，举例子、

拷贝构造函数，是一种特殊的构造函数，它由编译器调用来完成一些基于同一类的其他对象的构建及初始化。其唯一的参数（对象的引用）是不可变的（const类型）。此函数经常用在函数调用时用户定义类型的值传递及返回。拷贝构造函数要调用基类的拷贝构造函数和成员函数。如果可以的话，它将用常量方式调用，另外，也可以用非常量方式调用。

在C++中，下面三种对象需要调用拷贝构造函数（有时也称“复制构造函数”）： 　　

1) 一个对象作为函数参数，以值传递的方式传入函数体； 　　

2) 一个对象作为函数返回值，以值传递的方式从函数返回； 　　

3) 一个对象用于给另外一个对象进行初始化（常称为复制初始化）； 　　

如果在前两种情况不使用拷贝构造函数的时候，就会导致一个指针指向已经被删除的内存空间。对于第三种情况来说，初始化和赋值的不同含义是拷贝构造函数调用的原因。事实上，拷贝构造函数是由普通构造函数和赋值操作符共同实现的。描述拷贝构造函数和赋值运算符的异同的参考资料有很多。 　　

通常的原则是：①对于凡是包含动态分配成员或包含指针成员的类都应该提供拷贝构造函数；②在提供拷贝构造函数的同时，还应该考虑重载"="赋值操作符号。原因详见后文。 　　拷贝构造函数必须以引用的形式传递(参数为引用值)。

其原因如下：当一个对象以传递值的方式传一个函数的时候，拷贝构造函数自动的被调用来生成函数中的对象。如果一个对象是被传入自己的拷贝构造函数，它的拷贝构造函数将会被调用来拷贝这个对象这样复制才可以传入它自己的拷贝构造函数，这会导致无限循环直至栈溢出（Stack Overflow）。除了当对象传入函数的时候被隐式调用以外，拷贝构造函数在对象被函数返回的时候也同样的被调用。

     拷贝构造函数的格式

拷贝构造函数的声明： 　　

class 类名 　　{ 　　

public： 　　

类名（形参参数）//构造函数的声明/原型 　　

类名（类名&对象名）//拷贝构造函数的声明/原型 　　

... 　　

}; 　　

拷贝构造函数的实现： 　　

类名::类名（类名&对象名）//拷贝构造函数的实现/定义 　　{函数体} 

拷贝构造函数的示例

Class Point 　　

{ Public: 　　

Point(int xx=0,int yy=m)(X=xx;Y=yy;) 　　

Point(Point& p); 　　

Int getX() {return X；} 　　

Int getY(){ return Y;} 　　

Private : 　　

Int X,Y; 　　} 　　

Point::Point(Point& p) 　　

{ 　　X=p.X; 　　Y=p.Y; 　　Cout<<"拷贝构造函数调用"<<endl; 　　}
14、哈希表

散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

15、1.03的250次方。

先说一下实际数据，windows自带的计算器的结果是：1619.2211813680911019159005748703 
1.03^5 = 1 + 0.03*5 + 0.0009*10 = 1.159 ~= 1.16 
1.16^5 = 1 + 0.16*5 + 0.0256*10 + 0.004096*10 = 1.8 + 0.256 + 0.04096 ~=2.1 
2.1^5 = 32 + 0.1*5*16 + 0.01*10*8 + 0.001*10*4 = 32 + 8 + 0.8 + 0.04 = 40.84 
40.84^2 = 1600 + 2*40*0.84 = 1600 + 8*8.4 ~= 1600

注明：1.03^5 =（1+0.03）^5=C(5,0)1^5*0.03^0+C(5,1)1^4*0.03^1+C(5,2)1^3*0.03^2....

下面的以此类推

#include <iostream>
#include <math.h>

int main()
{
  double a = 1.03;
  std::cout<<pow(a,250)<<std::endl;

  return 0;
}

不知道这样有问题吗？
结果是1619.22
16、 n!后面有多少个相邻的零。    

      当0 < n < 5时，f(n!) = 0;

     当n >= 5时，f(n!) = k + f(k!), 其中 k = n / 5（取整）。

(1)当n < 5时, 结论显然成立。

    (2)当n >= 5时，令n！= [5k * 5(k-1) * ... * 10 * 5] * a，其中 n = 5k + r (0 <= r <= 4)，a是一个不含因子“5”的整数。

    对于序列5k, 5(k-1), ..., 10, 5中每一个数5i(1 <= i <= k)，都含有因子“5”，并且在区间(5(i-1),5i)(1 <= i <= k)内存在偶数，也就是说，a中存在一个因子“2”与5i相对应。即，这里的k个因子“5”与n！末尾的k个“0”一一对应。

我们进一步把n！表示为：n！= 5^k * k! * a（公式1），其中5^k表示5的k次方。很容易利用(1)和迭代法，得出结论1。

答：当0 < n < 5时，有0个相邻的零;

    当n >= 5时，相邻的零的个数=f（n/5）+f（n/25）+f（n/125）+（n/625）+。。。直到n<5,f()就是向下取整。

17、你设计个算法：从×××××酒店到×××××机场假如坐出租车需要一个小时的话，请问怎么让时间缩短到30分钟或者40分钟、
（我所想到的就是最短路径问题，不知道正确否？）

答：A、搬到离机场更近的酒店。B、使用更快的交通工具C、闯红灯D、调自己的表，将自己的表调快！

我不知道，呵呵，感觉出租车都已经需要一个小时了，那么就只能搬到离机场近的酒店住了！