zhgw01

2009年4月16日 #

腾讯面试中一道题

题目:1分钟内用户上线的数目是60万,如果用户在5分钟内重复上线,就给他发警告,问如何设计?

考虑:要判断用户是否在5分内重复上线,那么至少要(也只需要)保存距当前时刻5分钟内的登录用户的信息(只要简单的ID)
           从这个开始出发,需要考虑的问题为2个:
           1.如何在迅速判断用户是否在保存的数据中 (这个理所当然想道用hash)
           2. 如果把过期的数据删掉  (这个就想到维护一个时间链表,把到期的通过链表来删除)


这个是半年前腾讯面试的时候碰到的题目,当时觉得很难,今天走在路上突然想起,想了想,突然想到这种方法,也许不是最好,但至少解决了,也了解了一件事

posted @ 2009-04-16 20:39 apacs 阅读(1738) | 评论 (10)编辑 收藏

2008年10月27日 #

内存对齐,little endian 和big endian

在笔试中考到,虽然认识到是内存对齐的问题,最后还是做错了,另外下面采用了big endian,一般的都是采用little endian

class Test
{
public
 
short int a;
 
int b;
 
char c[5];
public:
 Test():b(0x
1234),a(b){
  c[
0]='h';
  c[
1]='e';
  c[
2]='l';
  c[
3]='l';
  c[
4]='o'//我是绝对这里应该赋值为'\0'
}

}


int main()
{
  Test t;
  cout
<<a<<endl;
  cout
<<b<<endl;
  cout
<<sizeof(t)<<endl;
  
char* p=(char*)&t;
  cout
<<*(p+8)<<endl;
}

sizeof 那里考的就是内存对齐的问题,short int 的变量必须从模2为0的开始,int必须从模4为0 的开始,char必须从模1为0的开始,而整个Test依照它的成员中最大的,这里就是int,也就是Test的必须从模4为0的开始,而且它必须占4的倍数。
为了满足int的条件,short int后要填充(padding)两个字节,为了满足Test的条件,char[5]后必须填充3个字节,所以总共是2+2+4+5+3=16个字节
具体的内存对齐可以参考如下
英文:http://www.chinaitpower.com/2005September/2005-09-13/206312.html
中文:http://blog.ednchina.com/jasony/92132/Message.aspx
这样*(p+8)也就很容易了解了,跳过前面8个字节,即short int 的2个,填充的2个,以及int的4个,最后跳到了c[0]

little endian 和 big endian

当一个变量占多个字节时,如何排列这些字节就产生出了little endian和big endian的区别
little endian: 把低字节放在内存的低位 (The most significant byte is on the right end of a word)
big endian: 把低字节放在内存的高位 (The most significant byte is on the left end of a word)
举个例子:
     假设从地址0x00000000开始的一个字中保存有数据0x1234abcd,那么在两种不同的内存顺序的机器上从字节的角度去看的话分别表示为:
       1)little endian:在内存中的存放顺序是0x00000000-0xcd,0x00000001-0xab,0x00000002-0x34,0x00000003-0x12
       2)big  endian:在内存中的存放顺序是0x00000000-0x12,0x00000001-0x34,0x00000002-0xab,0x00000003-0xcd


在构造函数中的Test():b(0x1234),a(b)看起来有问题,本来想这应该涉及到little endian和big endian的问题,不过在vs2005里调试了一下,发现由于a比b先声明,所以实际上时a先初始化,也就是a(b)这个语句先运行,由于这时候b还没初始化,a的值就是一个随机数(相对于不同的运行来说),接着b再初始化为正确值,但是这时候已经无法改变a的值了

posted @ 2008-10-27 17:17 apacs 阅读(339) | 评论 (0)编辑 收藏

2008年10月20日 #

static 和 extern


static的作用有2个,一个是控制名字的可见性,一个是控制生存期

1.控制名字的可见性
这时候是跟extern相对应的,作用与文件作用域(file scope)内的所有名字(变量名或函数名),其它定义在函数内或类内的变量名或函数名都不具有文件作用域。
一般情况下,当你定义了一个全局范围内变量或函数名的时候,默认的是extern,如在下面的file1.cpp
//file1.cpp
int a=1;  //完整的应该是extern int a=1;但extern是缺省的

void f() //同上一样,这里也是定义
{

}

那么在file2.cpp中你不能再声明a跟f,否则会引起名字冲突,当你想要使用file1.cpp中的a跟f时,可以如下
extern int a; //不运行赋值,这里只是声明,不可以省去extern,否则编译器会认为是重定义

void f(); //同样是声明,而且对函数而言,可以省去extern

   extern int b=1;//这里是定义
这样就可以在file2.cpp中使用a跟f了

反过来,你在文件作用域范围内定义了一个名字,你不希望被其它文件引用,这时候就要在前面加上static,此时这个变量具有internal linkage,它不能被其它文件引用,同时在其它文件中声明同名变量不会认为有冲突(因为static 使得名字只在本文件内可见)。

2.控制生存期

static 变量同global 变量一样,放在static存储区,只有当程序运行结束时,这些变量才会消失

当static变量定义在函数中时,它仅在该函数内可见,当每次函数调用完,这个变量的值都会保留下来

当static变量定义在类当中时,这个变量就同类的对象无关,真个类只有一个该变量的副本,不过它定义了多少个对象,而且对改变量的改变可以只通过类来改变,该变量的变化对所有同类的对象是可见的


posted @ 2008-10-20 15:42 apacs 阅读(481) | 评论 (0)编辑 收藏

Handle Class 和 Interface Class

这两者都是为了降低文件间的编译依存

1.编译依存
#include"file1.h"
#include
"file2.h"

class class_name
{
 member1 m_m1;
 member2 m_m2;
public:
 member1 get_member_1()
const{};
 member2 get_member_2()
const{};
}
;
假设上面的头文件为file.h,当file1.h或者file2.h发生变化,或者file中的class_name的实现发生变化时,所有包含file.h的文件都得重新编译,当file.h被很多文件包含时,即使只是对class_name做了小小的改动,也要花费大量的编译时间。

2. Handle class (句柄类)
handle classs 只是提高了所有的接口,同时包含了一个指向真正实现类的指针。真正的实现类包含在另外一个文件中,当要修改这个类时,只有file.h会引起重编译,而包含file.h的其它文件不会引起重编译
#include"file1.h" //contain member1
#include
"file2.h" //contain member2
   #include"implement.h"

class class_name
{
  class_impl
* implement; //一般会用shared pointer

public:
 member1 get_member_1()
const
 
{
   
return implement->get_member_1();
 }


 member2 get_member_2() 
const
 
{
   
return implement->get_member_2();
 }

}
;

下面的是implement.h的实现

class class_impl
{
  member1 m_1;
  member2 m_2;
public;
  member1 get_member_1()
const {}
  member2 get_member_2()
const {}
}
;

2.Interface class
这是制作handle class的另外一种方法
首先声明的class是抽象类,一般里面的接口都是纯虚函数,就像Java的Interface
然后提高一个static的create函数(就是工厂方法),这个函数返回改抽象类的某个具体子类的对象,函数声明中的返回值仍然是该抽象类的指针或引用。

具体子类在另外一个文件中声明。

posted @ 2008-10-20 15:02 apacs 阅读(1280) | 评论 (0)编辑 收藏

2008年10月17日 #

C++的重载与虚函数

     摘要: 其实真正要说的是虚函数,不过其中要扯倒重载,所以顺便也说了下重载1. 重载1.1 简单重载      在C++中,是允许同名函数的存在 int add(int i,int j);float add(float i,float);     ...  阅读全文

posted @ 2008-10-17 14:45 apacs 阅读(4903) | 评论 (1)编辑 收藏

2008年10月7日 #

ADL关联名字查找

如果给定一个函数名,那么c++编译器如何去查找这个函数呢?
1.普通的名字查找 
   对变量的调用,一般是按scope的大小来的

#include<iostream>
#include
<string>
using namespace std;

namespace NS
{
        
string x="namespace NS";
}


string x="global scope";

class A
{
        
string x;
public:
        A():x(
"class scope"){};

        
void f(){
                
string x="local scope";
                cout
<<x<<endl;
        }

        
void g(){
                cout
<<x<<endl;
 }

}
;

class B
{
        
public:
                
void f()
                
{
                        cout
<<x<<endl;
                }

                
void g()
                
{
                        cout
<<NS::x<<endl;
                }

}
;

int main()
{
        A a;
        B b;
        a.f();a.g();
        b.f();b.g();
}

 

  • 首先调用local scope的
  • 接着调用class scope的
  • 最后才调用global scope的
  • 如果直接有用限定符,则调用限定符的,无论是namespace 限定符还是class限定符

函数名字的查找,除了local scope的,基本同上,有一点例外的是,则在下面ADL中说明

2.关联名字查找 (Argument Dependent Lookup)
在说明前要明确2个概念

  • 关联(dependent name):不能解析的名字就叫关联名,这个一般同模版有关,比如template<class T> A{T t;}; 中,t就是关联名,它在模版编译的第一阶段是无法解析的,只有到第二阶段,用实际参数来实例化的时候才知道 
  • 限定名(qualified name): 指变量名或函数名前有类名前缀,或者被对象,指针修饰: Class::f() //类名前缀  x.f() //对象修饰 p->f() //指针修饰

而ADL要解决的问题是对非限定名的查找问题(限定名可以根据相应的限定来查找): 当出现了对某个非限定函数的调用,而该非限定函数却没有在一个(标准)作用域内进行声明时(简单的讲,该函数只声明在某个namespace,而你又没有引入这个namespace),编译器就会寻找它的每一个参数的名字空间来进行匹配。ADL是为了简化函数调用,不过事实上它有点破坏了namespace的封装。
比如以下函数调用
   std::string s("hello");
   std::cout<<s<<std::endl;
程序中没有指定使用哪一个operator<<函数,程序员当然不想输入
  std::operator<<(std::operator(std::cout,s),std::endl);
这时,ADL根据s查找s的namespace,并查找相应的operator<<

posted @ 2008-10-07 20:29 apacs 阅读(579) | 评论 (0)编辑 收藏

2008年9月23日 #

悲惨,被微软bs了一轮就回来

第一题,17分钟过河,大家估计都知道了
第二题,写代码判断回文
第三题,写测试案例,就是在输入框输入字符串,然后下面回显这个字符串
第四题,写时针跟分针所夹的角度,好几年没带表了,竟然以为只要是8点,时针就永远指在8。太蠢了,因这道题直接出局,到大厅的时候立刻想到了解法:(hour*5+minute/60*5)-minute如果是负的,反一下负号,最后乘以360/60=6

posted @ 2008-09-23 14:04 apacs 阅读(139) | 评论 (0)编辑 收藏

2008年6月19日 #

extern "C"

简单讲的话,
就是c++由于支持函数重载,生成的函数名与c生成的不一样。

为了能让c调用c++函数,就要使用extern "c" {}使得c++按c那样生成函数名

posted @ 2008-06-19 16:57 apacs 阅读(110) | 评论 (0)编辑 收藏

const 探究(转)

1. const常量,如const int max = 100;
优点:const常量有数据类型,而宏常量没有数据类型。编译器可以对前者进行类型安全检查,而对后者只进行字符替换,没有类型安全检查,并且在字符替换时可能会产生意料不到的错误(边际效应)



2. const 修饰类的数据成员。如:
class A

{

const int size;



}

const数据成员只在某个对象生存期内是常量,而对于整个类而言却是可变的。因为类可以创建多个对象,不同的对象其const数据成员的值可以不同。所以不能在类声明中初始化const数据成员,因为类的对象未被创建时,编译器不知道const 数据成员的值是什么。如

class A

{

const int size = 100; //错误

int array[size]; //错误,未知的size

}

const数据成员的初始化只能在类的构造函数的初始化表中进行。要想建立在整个类中都恒定的常量,应该用类中的枚举常量来实现。如

class A

{…

enum {size1=100, size2 = 200 };

int array1[size1];

int array2[size2];

}

枚举常量不会占用对象的存储空间,他们在编译时被全部求值。但是枚举常量的隐含数据类型是整数,其最大值有限,且不能表示浮点数。



3. const修饰指针的情况,见下式:

int b = 500;
const int* a = & [1]
int const *a = & [2]
int* const a = & [3]
const int* const a = & [4]

如果你能区分出上述四种情况,那么,恭喜你,你已经迈出了可喜的一步。不知道,也没关系,我们可以参考《Effective c++》Item21上的做法,如果const位于星号的左侧,则const就是用来修饰指针所指向的变量,即指针指向为常量;如果const位于星号的右侧,const就是修饰指针本身,即指针本身是常量。因此,[1]和[2]的情况相同,都是指针所指向的内容为常量(const放在变量声明符的位置无关),这种情况下不允许对内容进行更改操作,如不能*a = 3 ;[3]为指针本身是常量,而指针所指向的内容不是常量,这种情况下不能对指针本身进行更改操作,如a++是错误的;[4]为指针本身和指向的内容均为常量。




4. const的初始化

先看一下const变量初始化的情况
1) 非指针const常量初始化的情况:A b;
const A a = b;

2) 指针const常量初始化的情况:

A* d = new A();
const A* c = d;
或者:const A* c = new A();
3)引用const常量初始化的情况:
A f;
const A& e = f; // 这样作e只能访问声明为const的函数,而不能访问一

般的成员函数;

[思考1]: 以下的这种赋值方法正确吗?
const A* c=new A();
A* e = c;
[思考2]: 以下的这种赋值方法正确吗?
A* const c = new A();
A* b = c;









5. 另外const 的一些强大的功能在于它在函数声明中的应用。在一个函数声明中,const 可以修饰函数的返回值,或某个参数;对于成员函数,还可以修饰是整个函数。有如下几种情况,以下会逐渐的说明用法:A& operator=(const A& a);
void fun0(const A* a );
void fun1( ) const; // fun1( ) 为类成员函数
const A fun2( );

1) 修饰参数的const,如 void fun0(const A* a ); void fun1(const A& a);
调用函数的时候,用相应的变量初始化const常量,则在函数体中,按照const所修饰的部分进行常量化,如形参为const A* a,则不能对传递进来的指针的内容进行改变,保护了原指针所指向的内容;如形参为const A& a,则不能对传递进来的引用对象进行改变,保护了原对象的属性。
[注意]:参数const通常用于参数为指针或引用的情况,且只能修饰输入参数;若输入参数采用“值传递”方式,由于函数将自动产生临时变量用于复制该参数,该参数本就不需要保护,所以不用const修饰。

[总结]对于非内部数据类型的输入参数,因该将“值传递”的方式改为“const引用传递”,目的是为了提高效率。例如,将void Func(A a)改为void Func(const A &a)

对于内部数据类型的输入参数,不要将“值传递”的方式改为“const引用传递”。否则既达不到提高效率的目的,又降低了函数的可理解性。例如void Func(int x)不应该改为void Func(const int &x)

2) 修饰返回值的const,如const A fun2( ); const A* fun3( );
这样声明了返回值后,const按照"修饰原则"进行修饰,起到相应的保护作用。const Rational operator*(const Rational& lhs, const Rational& rhs)
{
return Rational(lhs.numerator() * rhs.numerator(),
lhs.denominator() * rhs.denominator());
}

返回值用const修饰可以防止允许这样的操作发生:Rational a,b;
Radional c;
(a*B) = c;

一般用const修饰返回值为对象本身(非引用和指针)的情况多用于二目操作符重载函数并产生新对象的时候。
[总结]

1. 一般情况下,函数的返回值为某个对象时,如果将其声明为const时,多用于操作符的重载。通常,不建议用const修饰函数的返回值类型为某个对象或对某个对象引用的情况。原因如下:如果返回值为某个对象为const(const A test = A 实例)或某个对象的引用为const(const A& test = A实例) ,则返回值具有const属性,则返回实例只能访问类A中的公有(保护)数据成员和const成员函数,并且不允许对其进行赋值操作,这在一般情况下很少用到。

2. 如果给采用“指针传递”方式的函数返回值加const修饰,那么函数返回值(即指针)的内容不能被修改,该返回值只能被赋给加const 修饰的同类型指针。如:

const char * GetString(void);

如下语句将出现编译错误:

char *str=GetString();

正确的用法是:

const char *str=GetString();

3. 函数返回值采用“引用传递”的场合不多,这种方式一般只出现在类的赙值函数中,目的是为了实现链式表达。如:

class A

{…

A &operate = (const A &other); //赋值函数

}
A a,b,c; //a,b,c为A的对象



a=b=c; //正常

(a=B)=c; //不正常,但是合法

若负值函数的返回值加const修饰,那么该返回值的内容不允许修改,上例中a=b=c依然正确。(a=B)=c就不正确了。
[思考3]: 这样定义赋值操作符重载函数可以吗?
const A& operator=(const A& a);

6. 类成员函数中const的使用
一般放在函数体后,形如:void fun() const;
任何不会修改数据成员的函数都因该声明为const类型。如果在编写const成员函数时,不慎修改了数据成员,或者调用了其他非const成员函数,编译器将报错,这大大提高了程序的健壮性。如:

class Stack

{

public:

void Push(int elem);

int Pop(void);

int GetCount(void) const; //const 成员函数

private:

int m_num;

int m_data[100];

};

int Stack::GetCount(void) const

{

++m_num; //编译错误,企图修改数据成员m_num

Pop(); //编译错误,企图调用非const函数

Return m_num;

}

7. 使用const的一些建议

1 要大胆的使用const,这将给你带来无尽的益处,但前提是你必须搞清楚原委;
2 要避免最一般的赋值操作错误,如将const变量赋值,具体可见思考题;
3 在参数中使用const应该使用引用或指针,而不是一般的对象实例,原因同上;
4 const在成员函数中的三种用法(参数、返回值、函数)要很好的使用;
5 不要轻易的将函数的返回值类型定为const;
6除了重载操作符外一般不要将返回值类型定为对某个对象的const引用;

[思考题答案]
1 这种方法不正确,因为声明指针的目的是为了对其指向的内容进行改变,而声明的指针e指向的是一个常量,所以不正确;
2 这种方法正确,因为声明指针所指向的内容可变;
3 这种做法不正确;
在const A::operator=(const A& a)中,参数列表中的const的用法正确,而当这样连续赋值的时侯,问题就出现了:
A a,b,c:
(a=B)=c;
因为a.operator=(B)的返回值是对a的const引用,不能再将c赋值给const常量。

posted @ 2008-06-19 16:55 apacs 阅读(154) | 评论 (0)编辑 收藏

2008年6月5日 #

括号数和catalan数

给定 P=a1×a2×a3×……×an,依据乘法结合律,不改变其顺序,只用括号表示成对的乘积,试问有几种括号化的方案

n=4的例子如下
((ab)c)d \quad (a(bc))d \quad(ab)(cd) \quad a((bc)d) \quad a(b(cd))

假设这个数是h(n-1), (这里之所以是n-1,是因为实际上n指的是元素个数,每2个元素乘一次,只要n-1次就可以乘完)
那么显然h(n-1)=h(0)h(n-2)+h(1)h(n-3)+...+h(n-2)h(0) 
对应的例子则是
a(b(cd)) a((bc)d)    h(0)h(n-2)  (只要先对右边的n-2个元素进行乘积,接着再跟最左边的元素相乘,h(0)=1)
(ab)(cd)                  h(1)h(n-3)  (先乘最左边的2个元素,再乘最右边的n-3个元素,之后再把这2个元素相乘)
(a(bc))d ((ab)c)d    h(n-2)h(0) 


从括号化展开的应用
1. 进出栈
   对括号进行进出栈的模拟,左括号代表进栈,右括号代表进行出栈,那么进出栈的顺序就相当于括号化的方案
2.三角剖分
   三角剖分就是从距阵乘法类比过来的,而距阵乘法就是括号化的问题

posted @ 2008-06-05 23:03 apacs 阅读(493) | 评论 (0)编辑 收藏

仅列出标题  下一页

My Links

Blog Stats

常用链接

留言簿(1)

随笔分类

随笔档案

搜索

最新评论

阅读排行榜

评论排行榜