在blogspot上看到一个十分有趣的字符串算法题目，原文在这里。作者讲述了自己面试google的一次经历。本文不理会这个故事，只来讨论一下里面着个有趣的算法。
算法题目：有两个字符串由不同的字母组成，一长一短，长的为A短的为B。设计一个算法，如果所有在B中出现的字符都在A中出现，则返回true，否则返回false。
例子：
如下字符串：
字符串A: abddfdioegdddffsfagj
字符串B: dofsjadg
字符串B中每个字符都在A中出现，返回true。
如下字符串：
字符串A: aaaabbbbbbdddddd
字符串B: acc
字符串B中有字符没在A中出现，返回false。
1、在安装openoffice过程中出现大致如下的错误
ERROR: Error 65280 occurred while making /var/tmp/portage/app-office/openoffice-3.2.1-r1/work/ooo/build/OOO320_m19/desktop/zipintro rmdir /var/tmp/portage/app-office/openoffice-3.2.1-r1/temp/yERj5YXC9A make: *** [stamp/build] Error 1 * ERROR: app-office/openoffice-3.2.1-r1 failed: * Build failed * * Call stack: * ebuild.sh, line 54: Called src_compile * environment, line 8141: Called die * The specific snippet of code: * make || die "Build failed" * * If you need support, post the output of 'emerge --info =app-office/openoffice-3.2.1-r1', * the complete build log and the output of 'emerge -pqv =app-office/openoffice-3.2.1-r1'. !!! When you file a bug report, please include the following information: GENTOO_VM=sun-jdk-1.6 CLASSPATH="" JAVA_HOME="/opt/sun-jdk-1.6.0.22" JAVACFLAGS="-source 1.5 -target 1.5" COMPILER="" and of course, the output of emerge --info * The complete build log is located at '/var/log/portage/app-office:openoffice-3.2.1-r1:20101120-141010.log'. * The ebuild environment file is located at '/var/tmp/portage/app-office/openoffice-3.2.1-r1/temp/environment'. * S: '/var/tmp/portage/app-office/openoffice-3.2.1-r1/work/ooo' >>> Failed to emerge app-office/openoffice-3.2.1-r1, Log file: >>> '/var/log/portage/app-office:openoffice-3.2.1-r1:20101120-141010.log'
问题原因：openoffice依赖一个包imagemagick，该包编译时需要png。具体机制不详
解决方法： USE="png" emerge -av imagemagick openoffice
对于结构体和空类大小是1这个问题，首先这是一个C++问题，在C语言下空结构体大小为0(当然这是编译器相关的)。这里的空类和空结构体是指类或结构体中没有任何成员。
在C++下，空类和空结构体的大小是1（编译器相关），这是为什么呢？为什么不是0？
这是因为，C++标准中规定，“no object shall have the same address in memory as any other variable” ，就是任何不同的对象不能拥有相同的内存地址。 如果空类大小为0，若我们声明一个这个类的对象数组，那么数组中的每个对象都拥有了相同的地址，这显然是违背标准的。
但是，也许你还有一个疑问，为什么C++标准中会有这么无聊的规定呢？
熟悉c的人都知道，sizeof是一个关键字而不是一个宏或者库函数什么的，他的值是在编译时确定的，如果这个不了解，可以现看看这篇文章和这篇文章。
既然如此，让我们先看下面几个小例子：
sizeof(int); sizeof(char); sizeof(double);
上面三行sizeof的值是多少呢？这里我们假定在32位的x86系统下。我们会得到答案：4，1，8。这个没什么吧，大多数人都应该知道。那么，下面这个：
sizeof(int); sizeof(long);
在32位x86下，这两个是多少呢？4，8？实际上，答案是4，4。我们需要注意，long类型在32位系统下是32位的。那么，64位下结果又如何呢？8，8？其实答案是4，8。另一个需要注意的是，64位下的int是32位的。
还是面某M的时候，面试官问我：“用过gdb么？” 答：“用过，调了两年bug了”。“那好，给我解释下gdb是怎么工作的？或者说跟内核什么地方有关系？”。
是阿，gdb凭什么可以调试一个程序？凭什么能够接管一个程序的运行？我以前也想过这样的问题，但是后来居然忘记去查看了。我想到了我们的二进制翻译器，想到了intel的pin，Dynamo。这些都是将翻译后的代码放到codecache中去运行，然后接管整个程序的执行。gdb是不是也一样呢？
如果真是这样，为什么我记得用gdb跑一个程序，这个程序会有一个单独的进程？gdb的attach功能又是怎么实现的？
想了想，我还是没有答上来。面试就是由这么一个又一个细节的小杯具最后汇集成一个大杯具。
那么，gdb到底是凭什么接管的一个进程的执行呢？其实，很简单，通过一个系统调用：ptrace。ptrace系统调用的原型如下：
最近感冒，昨天流着鼻涕去一直很想去的某M面试，居然还迟到了，一紧张，鼻涕不流了－ －#
问的问题不难，都是基础，可是自己不争气，答的不怎么样，一直自诩C语言用的很不错，可是还是在基础上被鄙视－ －！都是那些个关键字们阿～今天，让我挨个把C的关键字给详细的整一整，加深一下印象～
首先，C语言中到底有多少个关键字呢？木有错，ANSI C规定是32个！ 他们分别是：auto double int struct break else long switch case enum register typedef char extern return union const float short unsigned continue for signed void default goto sizeof volatile do if while static。
别看那一堆了字母了，直接看下面的分类介绍：
第一类：数据类型关键字
当你看到“内存屏障”四个字的时候，你的第一反应是什么？寄存器里取出了错误的值？ifence,sfence之类的指令？还是诸如volatile之类的关键字？好吧，我第一次看到这四个字的时候，脑子里浮现出的是魔兽争霸里绿油油的铺满苔藓的岩石屏障－ －#，并且，当我搞明白内存屏障具体是什么，而且自认为对其很熟悉之后，我的第一反应依然是那几块绿油油的石头，而且很想上去A一把！
言归正传，先解释下什么是内存屏障。内存屏障是指“由于编译器的优化和缓存的使用，导致对内存的写入操作不能及时的反应出来，也就是说当完成对内存的写入操作之后，读取出来的可能是旧的内容”（摘自《独辟蹊径品内核》）。
概念就是概念，生硬的东西，懂的人能从中悟出点什么，不懂的人还是一头雾水。不要着急，我们先给内存屏障分下类，然后挨个来研究一番，等看完这篇文章，再回来读读概念，你就懂了！
内存屏障的分类：
- 编译器引起的内存屏障
- 缓存引起的内存屏障
- 乱序执行引起的内存屏障
之所以说是一个解法，是因为这是我暂时能想到的线性时间复杂度的算法，需要遍历约2m遍，这里把算法列出来，仅供参考。
题目：
有一串首尾相连的珠子，共有m个，每一个珠子有一种颜色，并且颜色的总数不超过n(n<=10)，求连续的珠子的颜色总数为n时，长度最小的区间。可简述思路或者给出伪代码，并且给出时间和空间复杂度分析。（baidu 2011校园招聘笔试题目）
拿到这个题目，我首先想到的是暴力搜索。即对每个珠子，都搜索以该珠子为结尾的最短符合题意的序列。但是这样比较的时间复杂度特别高，应该是m的指数，显然是不可取的，通过简单的分析我们能够发现，在搜索过程中，我们进行了许多冗余的比较。本着空间换时间的想法，我们有没有办法把这些比较记录下来，然后去掉这些冗余呢？答案是肯定的。
文章开始，先看一个结构体的代码： //爱立信2011笔试 360 2011笔试均涉及
struct node{ int a; int b; };
问：sizeof(Node)是多少？ 答案很简单，在32位机器上，一个int是4个字节，两个int就是8个字节，sizeof(Node)就是8。
好的，上面那个答案确实是8，那么再看下面这个结构体：
struct node{ char a; int b; };
问：这个时候sizeof(Node)又是多少呢？ int是4个字节，char是1个字节，答案是5？
题目：给定6个数字，1，2，2，3，4，5，打印所有的排列
要求：
- 所有的4均不会出现在排列的第4个位置
- 数字3和数字5不能相邻
- 排列不能重复。
实现思想：
采用回朔的方法便利所有可能的排列，其中把不符合题目要求的去除。需要额外注意的是，数字中出现了两个2，如果单纯的遍历，会打印两次2在某个位置的排列，要注意把这个重复给去除。
最新回复评论