存档在 2013年7月

常见面试题目

2013年7月19日

1. memcpy memmove strcpy strncpy写代码实现,这里主要就是注意边界控制等细节。

2. 写代码实现String类,包括构造函数,拷贝构造函数,赋值函数,析构函数等。还有实现strreplace方法,用给定的replace串替换其中的pattern串;实现trim方法,就是删除字符串左右两边的空白字符。
3. 写代码实现单链表反转,递归以及非递归方法。
4. 写代码实现单例模式实现,如何让一个类不能被继承等。
5. 写代码实现去掉一个串中给定的所有字符;写代码实现判断给定的串haystack是否包括串pattern,这里包括的意思是,haystack中包括pattern中的所有字符,并且每个字符数量上也要大于等于pattern中的每个字符,字符顺序没有要求。
6. 给你行程编码算法的思想, 主要思想是一个字符连续出现多次,那么前面加个数字表示其次数,如aaaa, 可以编码为4a,当然在编码的时候还要加上控制字符,用来标识这里的4到底是后面a出现的次数还是本来就是一个4. 所以编码后的格式是:控制字符+次数+字符。写代码实现 。
7. 写代码实现快速排序、归并排序等,归并排序可能有多路归并实现。
8. 写代码实现求数组中最长递增子序列,连续子数组最大和等问题。
9. 写代码实现简单的内存池。
10. tcp/ip协议相关问题,IO多路复用问题,select, poll, epoll等。
11. 如何实现key-value的存储,100G内存,1T硬盘,支持快速的增、删、查操作,这里主要问题在如何快速支持硬盘上的删除操作,并将删除后的文件漏洞补上。
12. tail命令如何实现,tail -f 如何实现。
13. mmap相关,read, fread, mmap性能相关。
14. hashmap和树形map性能差异。
15. 如何快速找到某点附近的点,lbs相关。
16. 20个杯子,5个朝上,15个朝下,每次翻动且只能翻动4个杯子,最少几次能将所有杯子全部翻向上。
17. 1~100个数丢失了2个数,怎么找到2个丢失的数。
18. 向量a,b,每一维要么是0,要么是1. 如何快速求余弦cos(a, b) = <a, b>/ (||a|| * ||b||)
19. c++多态,虚函数机制等。

20. 多线程、多进程差异,性能等。多线程、多进程的通信与同步等。

21. 拓扑排序
22. 写代码实现字符串转整数,这里注意考虑符号问题。

23. 从不知道大小的很输入流中随机取n行,讲清具体的原理。

pyqtQQ[Linux平台下QQ][WebQQ桌面化][Linux下安装QQ]使用帮助

2013年7月14日

(腾讯公司已经修改了登陆界面,pyqtQQ暂时未更新)

引言:

该软件是基于pyQt4编写,感谢pwwang.com的pyWebQQ提供的思路,由于一些系统已经不支持gtkmozembed,在fedora下独立安装gtkmozembed会有很多依赖,另外很多人并不是使用Ubuntu,安装一些相关库比较麻烦。所以我用pyqt写了该软件,目的就是让更多的Linux系统可以使用。另外python的语法和C++比较相似,比较容易上手,也为后续维护提供了可能性。(大爱Python)

下载

tar.gz压缩包下载链接:点击这pyqtQQ-1.3.tar.gz
tar.bz2压缩包下载链接:点击这(暂无)
zip压缩包下载链接:点击这pyqtQQ-1.3

测试系统:

Fedora 17, Fedora 9, Fedora 12

功能:

桌面化Q+ Web
新消息桌面与任务栏提示
支持软件最小化到系统托盘
其他Q+Web所有功能
(点击关闭时会隐藏窗口,如果想退出QQ,在任务栏图标上点击右键->退出)
最爱的是可以使用QQ音乐听歌!

安装

第一步:安装SIP(下载地址1下载地址2)

tar xvzf sip-4.17.7.tar.gz
cd xvzf sip-4.17.7
python configure.py
make
make install

第二步:安装QT(下载地址1,下载地址2)

如果你安装过QT源码包或者QT SDK,则可以跳过该步骤。
以下两种方式任选一种(第一中安装大概在5分钟左右,第二种安装在两个小时左右,自己衡量下)
懒人安装(直接安装二进制包):

./qt-sdk-linux-x86-opensource-2010.05.1.bin

或者

/你放置的目录/qt-sdk-linux-x86-opensource-2010.05.1.bin

直到安装结束
想体验QT手动编译安装过程(安装源码包)

tar xvzf qt-everywhere-opensource-src-4.8.5.tar.gz
./configure
make
make install

第三步:安装PyQt4(下载链接1下载链接2)

python configure-ng.py --qmake /opt/qtsdk-2010.05/qt/bin/qmake
make
make install

PyQt4安装,编译过程稍稍较长。

第四步:安装pyqtQQ

python configure.py
make
make install

至此,你就可以在桌面或者开始菜单应用里找到pyqtQQ了。
Enjoying!!!

可能需要的库或软件

1.PyQt4 下载链接:http://www.riverbankcomputing.co.uk/software/pyqt/download
2.python下载链接:http://www.python.org/download/
3.pynotify下载链接:http://www.galago-project.org/downloads.php
4.Sip下载链接:http://www.riverbankcomputing.co.uk/software/sip/download/
5.Pygtk下载链接:http://ftp.gnome.org/pub/GNOME/sources/pygtk/2.24/

其他

访问我的其他小软件:其他windows下小软件
没事的时候喜欢写点小东西玩玩,希望喜欢!

问题

如果在使用QQ音乐的时候不能加载,请安装flash player,Adobe Flash Player的安装比较容易,只要将对应的文档复制到正确的的位置即可,具体的操作
如下:
(1) 将libflashplayer.so拷贝到Firefox的Plugin目录:

cp libflashplayer.so /usr/lib/mozilla/plugins/

(2) 将usr目录下的所有文档拷贝到系统的/usr目录下:

cp -r ./usr/* /usr/

重新打开即可。

为fedora添加RPMFusion源

2013年7月10日

RPMFusion你可以认为是Fedora的强化软件中心,在其中提供了大量的第三方软件支持,包括我们需要的各种编解码器和显卡驱动程序。添加RPMFusion源其实很简单,访问http://rpmfusion.org/,下载Fedora的Free和Nonfree的源安装程序即可,如果你需要的话,可以去更新管理器里把Testing分支也勾上。

添加源之后要记得先
sudo yum makecache
更新最新源的信息。
2013-07-10 10:16:15的屏幕截图

这时候你应该可以尝试使用yum来安装你的显卡驱动和各类编解码器了,也可以等你遇到需要的文件后由系统自动安装,我推荐使用Fedora的添加删除程序来搜索安装你需要的包.

公用体在格式化中的应用

2013年7月9日

公用体在格式化中或许有着很高效而又简洁的效果。可以来看个例子:

关于4个字节转换为浮点数

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <string.h>
using namespace std;


int main()
{
	union {
			struct {
				unsigned char b1;
				unsigned char b2;
				unsigned char b3;
				unsigned char b4;
			} a;
			float l;
		} u;
	u.a.b1 = 0x38;
	u.a.b2 = 0x3c;
	u.a.b3 = 0xbe;
	u.a.b4 = 0x62;
	/*
	u.a.b1 = 0x62;
	u.a.b2 = 0xbe;
	u.a.b3 = 0x3c;
	u.a.b4 = 0x38;
	*/
	printf("%f\n", u.l);
}

但是有个问题就是必须得区分是大端或在小端处理器模式!

SGI STL关于sort的优化[2]

2013年7月8日

1中说了插入排序实现方法与思想,插入排序可能算是所有排序算法中思想最简单的一种了。

接下来关注下快排,因为这是在数据量较大时采用的排序方法。
通常的快排算法是将一个大区间分成两个区间,左边区间的数都小于关键字key,右边区间的数都大于关键字key。
再分别对左边和右边区间递归执行上过程,知道每个区间只有一个元素,排序完毕。
但是区间较小时,也进行如此递归是得不偿失,所以STL中的sort里的快排是当区间的长度小于等于16时结束Quick Sort.

另外在快排时,需要找一个关键字key作为观测值,这个值的决定也影响分区,因为普通的分区存在以下的情况:可能存在一个区为空白,也即是没有值大于该值,或者没有值小于该值。为了弥补这个缺陷,STL采用的是median-of-three partitioning.

template <class T>
inline const T& __median(const T& a, const T& b, const T& c) {
  if (a < b)
    if (b < c)
      return b;
    else if (a < c)
      return c;
    else
      return a;
  else if (a < c)
    return a;
  else if (b < c)
    return c;
  else
    return b;
}

即是找3个数中的中位数。

区间分割时,还是老套路,first向尾部移动,last向头部移动,直到first越过last时停止。

template <class RandomAccessIterator, class T>
RandomAccessIterator __unguarded_partition(RandomAccessIterator first,
                                           RandomAccessIterator last,
                                           T pivot) {
  while (true) {
    while (*first < pivot) ++first;
    --last;
    while (pivot < *last) --last;
    if (!(first < last)) return first;
    iter_swap(first, last);
    ++first;
  }
} 

该函数返回分区后右边区间的头迭代器。
来看看sort的核心部分

template <class RandomAccessIterator, class T, class Size>
void __introsort_loop(RandomAccessIterator first,
                      RandomAccessIterator last, T*,
                      Size depth_limit) {
  while (last - first > __stl_threshold) {
    if (depth_limit == 0) {
      partial_sort(first, last, last);
      return;
    }
    --depth_limit;
    RandomAccessIterator cut = __unguarded_partition
      (first, last, T(__median(*first, *(first + (last - first)/2),
                               *(last - 1))));
    __introsort_loop(cut, last, value_type(first), depth_limit);
    last = cut;
  }
} 

上边采用last =cut来控制左右递归。当区间长度<=16时快排结束,进入插入排序。下面的代码就可以看出。

template <class RandomAccessIterator>
inline void sort(RandomAccessIterator first, RandomAccessIterator last) {
  if (first != last) {
    __introsort_loop(first, last, value_type(first), __lg(last – first) * 2);
    __final_insertion_sort(first, last);
  }
}    

__final_insertion_sort内部总体来说就是插入排序了,代码很简单,可以找来看看。

SGI STL关于sort的优化[1]

2013年7月8日

STL里的sort算法,并不是一成不变的使用快排(qsort),而是综合各方面因素来优化得到的一种综合算法。

1.当数据量较大时(STL中定为16),使用快排(Quick Sort)进行区间递归排序;
2.当数据量较大,而且递归层次较深(__lg() *2),则采用堆排序(Heap Sort),因为区间太小的递归的栈消耗与参数入栈出栈效率并没有那么的理想;
3.当数据量较小时,则直接使用插入排序(Insert Sort).
以默认的重载了operator<的类对象为例,当然使用函数对象来作为排序规则的原理一样。

先看插入排序:

template <class RandomAccessIterator>
void __insertion_sort(RandomAccessIterator first, RandomAccessIterator last) {
  if (first == last) return; 
  for (RandomAccessIterator i = first + 1; i != last; ++i)
    __linear_insert(first, i, value_type(first));
}

其中的

for (RandomAccessIterator i = first + 1; i != last; ++i)

作为外层循环来决定__linear_insert的处理区间,区间为[first,i)。

再来看看__linear_insert

template <class RandomAccessIterator, class T>
inline void __linear_insert(RandomAccessIterator first, 
                            RandomAccessIterator last, T*) {
  T value = *last;
  if (value < *first) {
    copy_backward(first, last, last + 1);
    *first = value;
  }
  else
    __unguarded_linear_insert(last, value);
}

注意这里的区间并不是半开半闭,而是[first, last],而且[first, last)已经是有序,观测值为value=*last.
既然[first, last)已经是有序,如果value小于*first,则使用copy_backward将[first,last)整体右移。
否则使用__unguarded_linear_insert来找到合适的位置插入,顾名思义,为线性查找插入。

template <class RandomAccessIterator, class T>
void __unguarded_linear_insert(RandomAccessIterator last, T value) {
  RandomAccessIterator next = last;
  --next;
  while (value < *next) {
    *last = *next;
    last = next;
    --next;
  }
  *last = value;
}

很简单,就是倒序线性找位置。其中next为前一个迭代器,last为后一个迭代器。

APP API

2013年7月7日

通过用户名请求用户信息

/api/members/show.json?username=creater
{
    "status" : "found",
    "id" : 124227,
    "url" : "http://www.v2ex.com/member/creater",
    "username" : "creater",
    "website" : "unix8.net",
    "twitter" : "",
    "psn" : "",
    "github" : "",
    "btc" : "",
    "location" : "",
    "tagline" : "",
    "bio" : "",
    "avatar_mini" : "//cdn.v2ex.co/gravatar/66103e121af7a4496eff575016a1e294?s=24&d=retro",
    "avatar_normal" : "//cdn.v2ex.co/gravatar/66103e121af7a4496eff575016a1e294?s=48&d=retro",
    "avatar_large" : "//cdn.v2ex.co/gravatar/66103e121af7a4496eff575016a1e294?s=73&d=retro",
    "created" : 1435286217
}

通过用户名请求

/topics/show.json?username=creater
[{
    
    "id" : 204050,
    "title" : "如何找领导办一件私事?",
    "url" : "http://www.v2ex.com/t/204050",
    "content" : "该怎么开口呢?",
    "content_rendered" : "\u003Cp\u003E该怎么开口呢?\u003C/p\u003E\u000A",
    "replies" : 3,
    "member" : {
        "id" : 124227,
        "username" : "creater",
        "tagline" : "",
        "avatar_mini" : "//cdn.v2ex.co/gravatar/66103e121af7a4496eff575016a1e294?s=24&d=retro",
        "avatar_normal" : "//cdn.v2ex.co/gravatar/66103e121af7a4496eff575016a1e294?s=48&d=retro",
        "avatar_large" : "//cdn.v2ex.co/gravatar/66103e121af7a4496eff575016a1e294?s=73&d=retro"
    },
    "node" : {
        "id" : 12,
        "name" : "qna",
        "title" : "问与答",
        "url" : "http://www.v2ex.com/go/qna",
        "topics" : 52413,
        "avatar_mini" : "//cdn.v2ex.co/navatar/c20a/d4d7/12_mini.png?m=1434537173",
        "avatar_normal" : "//cdn.v2ex.co/navatar/c20a/d4d7/12_normal.png?m=1434537173",
        "avatar_large" : "//cdn.v2ex.co/navatar/c20a/d4d7/12_large.png?m=1434537173"
    },
    "created" : 1436276707,
    "last_modified" : 1436276707,
    "last_touched" : 1436279480
    
}]

关于4个字节转换为浮点数

2013年7月7日

昨天一师妹在进行项目代码编写时,需要将4个字节的数据转换为浮点型数,她使用了非常冗繁的方法来对对数据解析,结果有很多问题。
其实这看起是一个很小的问题,而是考验对基础熟悉程度,如果没理解计算机中数的存储.这可不是小问题。

附上正确的代码。

#include <iostream>
#include <string>
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
using namespace std;

int main()
{
	unsigned char byte1 = 0x38, byte2 = 0x3c, byte3 = 0xbe ,byte4 = 0x62;
	unsigned short shortHigh = (byte1 << 8 | byte2);
	unsigned short shortLow = (byte3 << 8 | byte4);
	int intValue = (shortHigh << 16) | shortLow;
	float doubleValue;
	memcpy(&doubleValue,&intValue,4 );
	//bcopy(&intValue, &doubleValue, 4);
	cout<<doubleValue<<endl;
	system("pause");
}