Creasy's Blog

December 18, 2010

Reply: 这七个月

其实我应该好好享受最后一个人过的日子
me: 嗯，其实我也是。

参加不靠谱的活动
me: ok~

读不靠谱的书
me: of course, you can

穿不靠谱的衣服
me: 好吧……

学不靠谱的知识。
me: 没问题～

勾引可爱的小学弟
me: 不行！

然后再勾引学长
me: 不行！！

再勾引单身的男老师
me: 必然不行！！！

或者，只是一个人安静一会儿不去想你。
me: 嗯:)

嗯哼～

c/c++ input/ouput functions

int open(char * filename, int flags)
int open(char * filename, int flags, int mode)
include: fcntl.h
flags = bitwise | or of any of the following:
     O_RDONLY      Only read operations permitted
     O_WRONLY      Only write operations permitted
     O_RDWR        Read and Write operations both permitted
     O_NONBLOCK    Non-blocking, applies to open operation only
     O_APPEND      All writes go to end of file
     O_CREAT       Create file if it doesn't already exist
     O_TRUNC       Delete existing contents of file
     O_EXCL        Open fails if file already exists
     O_SHLOCK      Get a "shared lock" on the file
     O_EXLOCK      Get an "exclusive lock" on the file
     O_DIRECT      Try to avoid all caching of operations
     O_FSYNC       All writes immediately effective, no buffering
     O_NOFOLLOW    If file is symbolic link, open it, don't follow it
mode required if file is created, ignored otherwise.
mode specifies the protection bits, e.g. 0644 = rw-r--r--
returns <0 for error, or integer file descriptor.

int close(int fd)
include: unistd.h
fd = file descriptor as returned by open
returns <0 for error, 0 for success.

int read(int fd, void * ptr, int numbytes)
include: unistd.h
fd = file descriptor as returned by open
ptr = address in memory where data is to be stored;
      may be a pointer of any type.
numbytes = number of bytes to attempt to read
returns <0 for error, 0 for end-of-file,or number of bytes successfully read. (for a non-blocking interactive file, that may be zero).

int write(int fd, void * ptr, int numbytes)
include: unistd.h
fd = file descriptor as returned by open
ptr = address in memory where data already is;
      may be a pointer of any type.
numbytes = number of bytes to attempt to write
returns <=0 for error, or number of bytes successfully written. (for a non-blocking file, that may be less than the number attempted without any errors having occurred).

int lseek(int fd, int position, int startpoint)
include: unistd.h
Sets the file position effective for the next read or write operation.
fd = file descriptor as returned by open
position = position within file: number of bytes between startpoint and the desired position, may be negative.
startpoint = location in file that position is relative to, one of:
     SEEK_SET: Position is number of bytes from beginning of file
     SEEK_END: Position is number of bytes after end of file
     SEEK_CUR: Position is number of bytes after current position
returns <0 for error, or resulting file position relative to beginning of file. Moving beyond the end of the file is permitted; the file is extended in length only if a write occurs beyond the current end of file. Moveing before the beginning of a file is not permitted. A write operation after a move only overwrites the number of bytes actually written.

int stat(char * file, struct stat * info)
include: sys/types.h
include: sys/stat.h
Finds information about a file.
file = The name (or path) for the file.
info = A pointer to an uninitialised stat structure. Even in C++, the type must be "struct stat *" because of the name clash. Information about the file is stored in the info object.
returns <0 for error (including file does not exist), or 0 for success.
The useful fields of a stat object are as follows. All have types that behave like ints, although they may be 16, 32, or 64 bits long.
     st_size: size in bytes
     st_ino: inode number
     st_mode: protection or mode (see below)
     st_nlink: number of hard links
     st_uid: file's owner's identification number
     st_gid: file's group identification number
     st_birthtime: date and time of file creation (see below)
     st_mtime: date and time of last modification (see below)
     st_atime: date and time of last access (see below)
All times are stored as time_t values, as described here. Mode and Protection. st_mode is the logical-or of a number of bits each representing different properties. The named constants for these bits, and their values in octal are:
     S_ISUID 0004000 set user id on execution
     S_IRUSR 0000400 protection: readable by owner
     S_IWUSR 0000200 writable by owner
     S_IXUSR 0000100 executable by owner
     S_IRGRP 0000040 readable by group
     S_IWGRP 0000020 writable by group
     S_IXGRP 0000010 executable by group
     S_IROTH 0000004 readable by all
     S_IWOTH 0000002 writable by all
     S_IXOTH 0000001 executable by all
Four bits of the mode give the file type. The mask for type is S_IFMT = 0170000
if (mode & S_IFMT) is S_IFREG = 0100000, type = perfectly ordinary file
if (mode & S_IFMT) is S_IFDIR = 0040000, type = directory
if (mode & S_IFMT) is S_IFLNK = 0120000, type = symbolic link
if (mode & S_IFMT) is S_IFIFO = 0010000, type = named pipe
if (mode & S_IFMT) is S_IFSOCK = 0140000, type = named socket

File Mode or Protection Bits

A file's mode or protection is usually specified visually by 9 characters, for example rw-r--r-- or rwxr-x--x. Each of the letters are (nearly always) 'r' for read permitted, 'w' for write permitted, or 'x' for execute permitted.

The letters always appear in groups of three. Within a group, the order is always 'rwx'. The first group of three indicate operations permitted to the owner of the file; the second group of three indicates operations permitted to other users in the same group as the owner; the third group of three indicates operations permitted to all users who can access the file.

If the file is a directory, 'x' means that files in the directory may be accessed if referred to directly by name, but wildcard substitutions ('*') and ls operations will not be permitted.

Modes are usually represented inside programs by a sequence of three octal digits. each octal digit represents one of the groups of three characters, 4 for 'r' plus 2 for 'w' plus 1 for 'x'. In C and C++ programs remember that numbers with leading zeros are always assumed to be in octal, so the mode 0751 represents rwxr-x--x.

vim setup

The configuration should be done in the file named "vimrc".

For linux os, the directory should be: /etc/vim/vimrc. For Unix, without root privilege, just as I am..., it needs to make a new file named ".vimrc" in the $HOME/ directory. As the vim starting, it will automatically read this file for configuration. And, the punctuation quotes " is the sign for comment.

" syntax highlighting
syntax on
" automatic indentation
set autoindent
" specifically c/c++ indentation
set cindent
" to show the line number for each line
set nu

Have fun:)

December 12, 2010

为什么Lisp语言如此先进？（译文）

作者：阮一峰

日期： 2010年10月14日

上周，《黑客与画家》总算翻译完成，已经交给出版社了。

翻译完这本书，累得像生了一场大病。把书稿交出去的时候，心里空荡荡的，也不知道自己得到了什么，失去了什么。
希望这个中译本和我的努力，能得到读者认同和肯定。
下面是此书中非常棒的一篇文章，原文写于八年前，至今仍然具有启发性，作者眼光之超前令人佩服。由于我不懂Lisp语言，所以田春同学帮忙校读了一遍，纠正了一些翻译不当之处，在此表示衷心感谢。

============================

为什么Lisp语言如此先进？
作者：Paul Graham
译者：阮一峰
英文原文：Revenge of the Nerds
（节选自即将出版的《黑客与画家》中译本）

一、
如果我们把流行的编程语言，以这样的顺序排列：Java、Perl、Python、Ruby。你会发现，排在越后面的语言，越像Lisp。
Python模仿Lisp，甚至把许多Lisp黑客认为属于设计错误的功能，也一起模仿了。至于Ruby，如果回到1975年，你声称它是一种Lisp方言，没有人会反对。
编程语言现在的发展，不过刚刚赶上1958年Lisp语言的水平。

二、
1958年，John McCarthy设计了Lisp语言。我认为，当前最新潮的编程语言，只是实现了他在1958年的设想而已。
这怎么可能呢？计算机技术的发展，不是日新月异吗？1958年的技术，怎么可能超过今天的水平呢？
让我告诉你原因。
这是因为John McCarthy本来没打算把Lisp设计成编程语言，至少不是我们现在意义上的编程语言。他的原意只是想做一种理论演算，用更简洁的方式定义图灵机。
所以，为什么上个世纪50年代的编程语言，到现在还没有过时？简单说，因为这种语言本质上不是一种技术，而是数学。数学是不会过时的。你不应该把 Lisp语言与50年代的硬件联系在一起，而是应该把它与快速排序（Quicksort）算法进行类比。这种算法是1960年提出的，至今仍然是最快的通用排序方法。

三、
Fortran语言也是上个世纪50年代出现的，并且一直使用至今。它代表了语言设计的一种完全不同的方向。Lisp是无意中从纯理论发展为编程语言，而Fortran从一开始就是作为编程语言设计出来的。但是，今天我们把Lisp看成高级语言，而把Fortran看成一种相当低层次的语言。
1956年，Fortran刚诞生的时候，叫做Fortran I，与今天的Fortran语言差别极大。Fortran I实际上是汇编语言加上数学，在某些方面，还不如今天的汇编语言强大。比如，它不支持子程序，只有分支跳转结构（branch）。
Lisp和Fortran代表了编程语言发展的两大方向。前者的基础是数学，后者的基础是硬件架构。从那时起，这两大方向一直在互相靠拢。Lisp 刚设计出来的时候，就很强大，接下来的二十年，它提高了自己的运行速度。而那些所谓的主流语言，把更快的运行速度作为设计的出发点，然后再用超过四十年的时间，一步步变得更强大。
直到今天，最高级的主流语言，也只是刚刚接近Lisp的水平。虽然已经很接近了，但还是没有Lisp那样强大。

四、
Lisp语言诞生的时候，就包含了9种新思想。其中一些我们今天已经习以为常，另一些则刚刚在其他高级语言中出现，至今还有2种是Lisp独有的。按照被大众接受的程度，这9种思想依次是：

1. 条件结构（即"if-then-else"结构）。现在大家都觉得这是理所当然的，但是Fortran I就没有这个结构，它只有基于底层机器指令的goto结构。
2. 函数也是一种数据类型。在Lisp语言中，函数与整数或字符串一样，也属于数据类型的一种。它有自己的字面表示形式（literal representation），能够储存在变量中，也能当作参数传递。一种数据类型应该有的功能，它都有。
3. 递归。Lisp是第一种支持递归函数的高级语言。
4. 变量的动态类型。在Lisp语言中，所有变量实际上都是指针，所指向的值有类型之分，而变量本身没有。复制变量就相当于复制指针，而不是复制它们指向的数据。
5. 垃圾回收机制。
6. 程序由表达式（expression）组成。Lisp程序是一些表达式区块的集合，每个表达式都返回一个值。这与Fortran和大多数后来的语言都截然不同，它们的程序由表达式和语句（statement）组成。
区分表达式和语句，在Fortran I中是很自然的，因为它不支持语句嵌套。所以，如果你需要用数学式子计算一个值，那就只有用表达式返回这个值，没有其他语法结构可用，因为否则就无法处理这个值。
后来，新的编程语言支持区块结构（block），这种限制当然也就不存在了。但是为时已晚，表达式和语句的区分已经根深蒂固。它从Fortran扩散到Algol语言，接着又扩散到它们两者的后继语言。
7. 符号（symbol）类型。符号实际上是一种指针，指向储存在哈希表中的字符串。所以，比较两个符号是否相等，只要看它们的指针是否一样就行了，不用逐个字符地比较。
8. 代码使用符号和常量组成的树形表示法（notation）。
9. 无论什么时候，整个语言都是可用的。Lisp并不真正区分读取期、编译期和运行期。你可以在读取期编译或运行代码；也可以在编译期读取或运行代码；还可以在运行期读取或者编译代码。
在读取期运行代码，使得用户可以重新调整（reprogram）Lisp的语法；在编译期运行代码，则是Lisp宏的工作基础；在运行期编译代码，使得Lisp可以在Emacs这样的程序中，充当扩展语言（extension language）；在运行期读取代码，使得程序之间可以用S-表达式（S-expression）通信，近来XML格式的出现使得这个概念被重新"发明"出来了。

五、
Lisp语言刚出现的时候，它的思想与其他编程语言大相径庭。后者的设计思想主要由50年代后期的硬件决定。随着时间流逝，流行的编程语言不断更新换代，语言设计思想逐渐向Lisp靠拢。
思想1到思想5已经被广泛接受，思想6开始在主流编程语言中出现，思想7在Python语言中有所实现，不过似乎没有专用的语法。
思想8可能是最有意思的一点。它与思想9只是由于偶然原因，才成为Lisp语言的一部分，因为它们不属于John McCarthy的原始构想，是由他的学生Steve Russell自行添加的。它们从此使得Lisp看上去很古怪，但也成为了这种语言最独一无二的特点。Lisp古怪的形式，倒不是因为它的语法很古怪，而是因为它根本没有语法，程序直接以解析树（parse tree）的形式表达出来。在其他语言中，这种形式只是经过解析在后台产生，但是Lisp直接采用它作为表达形式。它由列表构成，而列表则是Lisp的基本数据结构。
用一门语言自己的数据结构来表达该语言，这被证明是非常强大的功能。思想8和思想9，意味着你可以写出一种能够自己编程的程序。这可能听起来很怪异，但是对于Lisp语言却是再普通不过。最常用的做法就是使用宏。
术语"宏"在Lisp语言中，与其他语言中的意思不一样。Lisp宏无所不包，它既可能是某样表达式的缩略形式，也可能是一种新语言的编译器。如果你想真正地理解Lisp语言，或者想拓宽你的编程视野，那么你必须学习宏。
就我所知，宏（采用Lisp语言的定义）目前仍然是Lisp独有的。一个原因是为了使用宏，你大概不得不让你的语言看上去像Lisp一样古怪。另一个可能的原因是，如果你想为自己的语言添上这种终极武器，你从此就不能声称自己发明了新语言，只能说发明了一种Lisp的新方言。
我把这件事当作笑话说出来，但是事实就是如此。如果你创造了一种新语言，其中有car、cdr、cons、quote、cond、atom、eq这样的功能，还有一种把函数写成列表的表示方法，那么在它们的基础上，你完全可以推导出Lisp语言的所有其他部分。事实上，Lisp语言就是这样定义的，John McCarthy把语言设计成这个样子，就是为了让这种推导成为可能。

六、
就算Lisp确实代表了目前主流编程语言不断靠近的一个方向，这是否意味着你就应该用它编程呢？
如果使用一种不那么强大的语言，你又会有多少损失呢？有时不采用最尖端的技术，不也是一种明智的选择吗？这么多人使用主流编程语言，这本身不也说明那些语言有可取之处吗？
另一方面，选择哪一种编程语言，许多项目是无所谓的，反正不同的语言都能完成工作。一般来说，条件越苛刻的项目，强大的编程语言就越能发挥作用。但是，无数的项目根本没有苛刻条件的限制。大多数的编程任务，可能只要写一些很小的程序，然后用胶水语言把这些小程序连起来就行了。你可以用自己熟悉的编程语言，或者用对于特定项目来说有着最强大函数库的语言，来写这些小程序。如果你只是需要在Windows应用程序之间传递数据，使用Visual Basic照样能达到目的。
那么，Lisp的编程优势体现在哪里呢？

七、
语言的编程能力越强大，写出来的程序就越短（当然不是指字符数量，而是指独立的语法单位）。
代码的数量很重要，因为开发一个程序耗费的时间，主要取决于程序的长度。如果同一个软件，一种语言写出来的代码比另一种语言长三倍，这意味着你开发它耗费的时间也会多三倍。而且即使你多雇佣人手，也无助于减少开发时间，因为当团队规模超过某个门槛时，再增加人手只会带来净损失。Fred Brooks在他的名著《人月神话》（The Mythical Man-Month）中，描述了这种现象，我的所见所闻印证了他的说法。
如果使用Lisp语言，能让程序变得多短？以Lisp和C的比较为例，我听到的大多数说法是C代码的长度是Lisp的7倍到10倍。但是最近，New Architect杂志上有一篇介绍ITA软件公司的文章，里面说"一行Lisp代码相当于20行C代码"，因为此文都是引用ITA总裁的话，所以我想这个数字来自ITA的编程实践。如果真是这样，那么我们可以相信这句话。ITA的软件，不仅使用Lisp语言，还同时大量使用C和C++，所以这是他们的经验谈。
根据上面的这个数字，如果你与ITA竞争，而且你使用C语言开发软件，那么ITA的开发速度将比你快20倍。如果你需要一年时间实现某个功能，它只需要不到三星期。反过来说，如果某个新功能，它开发了三个月，那么你需要五年才能做出来。
你知道吗？上面的对比，还只是考虑到最好的情况。当我们只比较代码数量的时候，言下之意就是假设使用功能较弱的语言，也能开发出同样的软件。但是事实上，程序员使用某种语言能做到的事情，是有极限的。如果你想用一种低层次的语言，解决一个很难的问题，那么你将会面临各种情况极其复杂、乃至想不清楚的窘境。
所以，当我说假定你与ITA竞争，你用五年时间做出的东西，ITA在Lisp语言的帮助下只用三个月就完成了，我指的五年还是一切顺利、没有犯错误、也没有遇到太大麻烦的五年。事实上，按照大多数公司的实际情况，计划中五年完成的项目，很可能永远都不会完成。
我承认，上面的例子太极端。ITA似乎有一批非常聪明的黑客，而C语言又是一种很低层次的语言。但是，在一个高度竞争的市场中，即使开发速度只相差两三倍，也足以使得你永远处在落后的位置。
附录：编程能力
为了解释我所说的语言编程能力不一样，请考虑下面的问题。我们需要写一个函数，它能够生成累加器，即这个函数接受一个参数n，然后返回另一个函数，后者接受参数i，然后返回n增加（increment）了i后的值。
Common Lisp的写法如下：

(defun foo (n)
(lambda (i) (incf n i)))

Ruby的写法几乎完全相同：

def foo (n)
lambda {|i| n += i } end

Perl 5的写法则是：

sub foo {
my ($n) = @_;
sub {$n += shift}
}

这比Lisp和Ruby的版本，有更多的语法元素，因为在Perl语言中，你不得不手工提取参数。
Smalltalk的写法稍微比Lisp和Ruby的长一点：

foo: n
|s|
s := n.
^[:i| s := s+i. ]

因为在Smalltalk中，局部变量（lexical variable）是有效的，但是你无法给一个参数赋值，因此不得不设置了一个新变量，接受累加后的值。
Javascript的写法也比Lisp和Ruby稍微长一点，因为Javascript依然区分语句和表达式，所以你需要明确指定return语句，来返回一个值：

function foo (n) {
return function (i) {
return n += i } }

（实事求是地说，Perl也保留了语句和表达式的区别，但是使用了典型的Perl方式处理，使你可以省略return。）
如果想把Lisp/Ruby/Perl/Smalltalk/Javascript的版本改成Python，你会遇到一些限制。因为Python并不完全支持局部变量，你不得不创造一种数据结构，来接受n的值。而且尽管Python确实支持函数数据类型，但是没有一种字面量的表示方式（literal representation）可以生成函数（除非函数体只有一个表达式），所以你需要创造一个命名函数，把它返回。最后的写法如下：

def foo (n):
s = [n]
def bar (i):
s[0] += i
return s[0]
return bar

Python用户完全可以合理地质疑，为什么不能写成下面这样：

def foo (n):
return lambda i: return n += i

或者：

def foo (n):
lambda i: n += i

我猜想，Python有一天会支持这样的写法。（如果你不想等到Python慢慢进化到更像Lisp，你总是可以直接......）
在面向对象编程的语言中，你能够在有限程度上模拟一个闭包（即一个函数，通过它可以引用由包含这个函数的代码所定义的变量）。你定义一个类（class），里面有一个方法和一个属性，用于替换封闭作用域（enclosing scope）中的所有变量。这有点类似于让程序员自己做代码分析，本来这应该是由支持局部作用域的编译器完成的。如果有多个函数，同时指向相同的变量，那么这种方法就会失效，但是在这个简单的例子中，它已经足够了。
Python高手看来也同意，这是解决这个问题的比较好的方法，写法如下：

def foo (n):
class acc:
def _ _init_ _ (self, s):
self.s = s
def inc (self, i):
self.s += i
return self.s
return acc (n).inc

或者

class foo:
def _ _init_ _ (self, n):
self.n = n
def _ _call_ _ (self, i):
self.n += i
return self.n

我添加这一段，原因是想避免Python爱好者说我误解这种语言。但是，在我看来，这两种写法好像都比第一个版本更复杂。你实际上就是在做同样的事，只不过划出了一个独立的区域，保存累加器函数，区别只是保存在对象的一个属性中，而不是保存在列表（list）的头（head）中。使用这些特殊的内部属性名（尤其是__call__），看上去并不像常规的解法，更像是一种破解。
在Perl和Python的较量中，Python黑客的观点似乎是认为Python比Perl更优雅，但是这个例子表明，最终来说，编程能力决定了优雅。Perl的写法更简单（包含更少的语法元素），尽管它的语法有一点丑陋。
其他语言怎么样？前文曾经提到过Fortran、C、C++、Java和Visual Basic，看上去使用它们，根本无法解决这个问题。Ken Anderson说，Java只能写出一个近似的解法：

public interface Inttoint {
public int call (int i);
}
public static Inttoint foo (final int n) {
return new Inttoint () {
int s = n;
public int call (int i) {
s = s + i;
return s;
}};
}

这种写法不符合题目要求，因为它只对整数有效。
当然，我说使用其他语言无法解决这个问题，这句话并不完全正确。所有这些语言都是图灵等价的，这意味着严格地说，你能使用它们之中的任何一种语言，写出任何一个程序。那么，怎样才能做到这一点呢？就这个小小的例子而言，你可以使用这些不那么强大的语言，写一个Lisp解释器就行了。
这样做听上去好像开玩笑，但是在大型编程项目中，却不同程度地广泛存在。因此，有人把它总结出来，起名为"格林斯潘第十定律"（Greenspun's Tenth Rule）：

"任何C或Fortran程序复杂到一定程度之后，都会包含一个临时开发的、只有一半功能的、不完全符合规格的、到处都是bug的、运行速度很慢的Common Lisp实现。"

如果你想解决一个困难的问题，关键不是你使用的语言是否强大，而是好几个因素同时发挥作用（a）使用一种强大的语言，（b）为这个难题写一个事实上的解释器，或者（c）你自己变成这个难题的人肉编译器。在Python的例子中，这样的处理方法已经开始出现了，我们实际上就是自己写代码，模拟出编译器实现局部变量的功能。
这种实践不仅很普遍，而且已经制度化了。举例来说，在面向对象编程的世界中，我们大量听到"模式"（pattern）这个词，我觉得那些"模式"就是现实中的因素（c），也就是人肉编译器。当我在自己的程序中，发现用到了模式，我觉得这就表明某个地方出错了。程序的形式，应该仅仅反映它所要解决的问题。代码中其他任何外加的形式，都是一个信号，（至少对我来说）表明我对问题的抽象还不够深，也经常提醒我，自己正在手工完成的事情，本应该写代码，通过宏的扩展自动实现。
（完）

What are the differences between a union and a structure in C?

original webpage click

Answer

A union is a way of providing an alternate way of describing the same memory area. In this way, you could have a struct that contains a union, so that the "static", or similar portion of the data is described first, and the portion that changes is described by the union. The idea of a union could be handled in a different way by having 2 different structs defined, and making a pointer to each kind of struct. The pointer to struct "a" could be assigned to the value of a buffer, and the pointer to struct "b" could be assigned to the same buffer, but now a->somefield and b->someotherfield are both located in the same buffer. That is the idea behind a union. It gives different ways to break down the same buffer area.

Answer:

The difference between structure and union in c are: 1. union allocates the memory equal to the maximum memory required by the member of the union but structure allocates the memory equal to the total memory required by the members. 2. In union, one block is used by all the member of the union but in case of structure, each member have their own memory space

Difference in their Usage:

While structure enables us treat a number of different variables stored at different in memory , a union enables us to treat the same space in memory as a number of different variables. That is a Union offers a way for a section of memory to be treated as a variable of one type on one occasion and as a different variable of a different type on another occasion.

There is frequent rwquirement while interacting with hardware to access access a byte or group of bytes simultaneously and sometimes each byte individually. Usually union is the answer.

=======Difference With example***** Lets say a structure containing an int,char and float is created and a union containing int char float are declared. struct TT{ int a; float b; char c; } Union UU{ int a; float b; char c; }

sizeof TT(struct) would be >9 bytes (compiler dependent-if int,float, char are taken as 4,4,1)

sizeof UU(Union) would be 4 bytes as supposed from above.If a variable in double exists in union then the size of union and struct would be 8 bytes and cumulative size of all variables in struct.

Detailed Example:

struct foo
{
char c;
long l;
char *p;
};

union bar
{
char c;
long l;
char *p;
};

A struct foo contains all of the elements c, l, and p. Each element is separate and distinct.

A union bar contains only one of the elements c, l, and p at any given time. Each element is stored in the same memory location (well, they all start at the same memory location), and you can only refer to the element which was last stored. (ie: after "barptr->c = 2;" you cannot reference any of the other elements, such as "barptr->p" without invoking undefined behavior.)

Try the following program. (Yes, I know it invokes the above-mentioned "undefined behavior", but most likely will give some sort of output on most computers.)

==========
#include

struct foo
{
char c;
long l;
char *p;
};

union bar
{
char c;
long l;
char *p;
};

int main(int argc,char *argv[])
{
struct foo myfoo;
union bar mybar;

myfoo.c = 1;
myfoo.l = 2L;
myfoo.p = "This is myfoo";

mybar.c = 1;
mybar.l = 2L;
mybar.p = "This is mybar";

printf("myfoo: %d %ld %s\n",myfoo.c,myfoo.l,myfoo.p);
printf("mybar: %d %ld %s\n",mybar.c,mybar.l,mybar.p);

return 0;
}

==========

On my system, I get:

myfoo: 1 2 This is myfoo
mybar: 100 4197476 This is mybar

December 4, 2010

140 Google Interview Questions

original site:click

Google Interview Questions: Product Marketing Manager

Why do you want to join Google?
What do you know about Google's product and technology?
If you are Product Manager for Google's Adwords, how do you plan to market this?
What would you say during an AdWords or AdSense product seminar?
Who are Google's competitors, and how does Google compete with them?
Have you ever used Google's products? Gmail?
What's a creative way of marketing Google's brand name and product?
If you are the product marketing manager for Google's Gmail product, how do you plan to market it so as to achieve 100 million customers in 6 months?
How much money you think Google makes daily from Gmail ads?
Name a piece of technology you've read about recently. Now tell me your own creative execution for an ad for that product.
Say an advertiser makes $0.10 every time someone clicks on their ad. Only 20% of people who visit the site click on their ad. How many people need to visit the site for the advertiser to make $20?
Estimate the number of students who are college seniors, attend four-year schools, and graduate with a job in the United States every year.

Google Interview Questions: Product Manager

How would you boost the GMail subscription base?
What is the most efficient way to sort a million integers?
How would you re-position Google's offerings to counteract competitive threats from Microsoft?
How many golf balls can fit in a school bus?
You are shrunk to the height of a nickel and your mass is proportionally reduced so as to maintain your original density. You are then thrown into an empty glass blender. The blades will start moving in 60 seconds. What do you do?
How much should you charge to wash all the windows in Seattle?
How would you find out if a machine's stack grows up or down in memory?
Explain a database in three sentences to your eight-year-old nephew.
How many times a day does a clock's hands overlap?
You have to get from point A to point B. You don't know if you can get there. What would you do?
Imagine you have a closet full of shirts. It's very hard to find a shirt. So what can you do to organize your shirts for easy retrieval?
Every man in a village of 100 married couples has cheated on his wife. Every wife in the village instantly knows when a man other than her husband has cheated, but does not know when her own husband has. The village has a law that does not allow for adultery. Any wife who can prove that her husband is unfaithful must kill him that very day. The women of the village would never disobey this law. One day, the queen of the village visits and announces that at least one husband has been unfaithful. What happens?
In a country in which people only want boys, every family continues to have children until they have a boy. If they have a girl, they have another child. If they have a boy, they stop. What is the proportion of boys to girls in the country?
If the probability of observing a car in 30 minutes on a highway is 0.95, what is the probability of observing a car in 10 minutes (assuming constant default probability)?
If you look at a clock and the time is 3:15, what is the angle between the hour and the minute hands? (The answer to this is not zero!)
Four people need to cross a rickety rope bridge to get back to their camp at night. Unfortunately, they only have one flashlight and it only has enough light left for seventeen minutes. The bridge is too dangerous to cross without a flashlight, and it's only strong enough to support two people at any given time. Each of the campers walks at a different speed. One can cross the bridge in 1 minute, another in 2 minutes, the third in 5 minutes, and the slow poke takes 10 minutes to cross. How do the campers make it across in 17 minutes?
You are at a party with a friend and 10 people are present including you and the friend. your friend makes you a wager that for every person you find that has the same birthday as you, you get $1; for every person he finds that does not have the same birthday as you, he gets $2. would you accept the wager?
How many piano tuners are there in the entire world?
You have eight balls all of the same size. 7 of them weigh the same, and one of them weighs slightly more. How can you find the ball that is heavier by using a balance and only two weighings?
You have five pirates, ranked from 5 to 1 in descending order. The top pirate has the right to propose how 100 gold coins should be divided among them. But the others get to vote on his plan, and if fewer than half agree with him, he gets killed. How should he allocate the gold in order to maximize his share but live to enjoy it? (Hint: One pirate ends up with 98 percent of the gold.)
You are given 2 eggs. You have access to a 100-story building. Eggs can be very hard or very fragile means it may break if dropped from the first floor or may not even break if dropped from 100th floor. Both eggs are identical. You need to figure out the highest floor of a 100-story building an egg can be dropped without breaking. The question is how many drops you need to make. You are allowed to break 2 eggs in the process.
Describe a technical problem you had and how you solved it.
How would you design a simple search engine?
Design an evacuation plan for San Francisco.
There's a latency problem in South Africa. Diagnose it.
What are three long term challenges facing Google?
Name three non-Google websites that you visit often and like. What do you like about the user interface and design? Choose one of the three sites and comment on what new feature or project you would work on. How would you design it?
If there is only one elevator in the building, how would you change the design? How about if there are only two elevators in the building?
How many vacuum's are made per year in USA?

Google Interview Questions: Software Engineer

Why are manhole covers round?
What is the difference between a mutex and a semaphore? Which one would you use to protect access to an increment operation?
A man pushed his car to a hotel and lost his fortune. What happened?
Explain the significance of "dead beef".
Write a C program which measures the the speed of a context switch on a UNIX/Linux system.
Given a function which produces a random integer in the range 1 to 5, write a function which produces a random integer in the range 1 to 7.
Describe the algorithm for a depth-first graph traversal.
Design a class library for writing card games.
You need to check that your friend, Bob, has your correct phone number, but you cannot ask him directly. You must write a the question on a card which and give it to Eve who will take the card to Bob and return the answer to you. What must you write on the card, besides the question, to ensure Bob can encode the message so that Eve cannot read your phone number?
How are cookies passed in the HTTP protocol?
Design the SQL database tables for a car rental database.
Write a regular expression which matches a email address.
Write a function f(a, b) which takes two character string arguments and returns a string containing only the characters found in both strings in the order of a. Write a version which is order N-squared and one which is order N.
You are given a the source to a application which is crashing when run. After running it 10 times in a debugger, you find it never crashes in the same place. The application is single threaded, and uses only the C standard library. What programming errors could be causing this crash? How would you test each one?
Explain how congestion control works in the TCP protocol.
In Java, what is the difference between final, finally, and finalize?
What is multithreaded programming? What is a deadlock?
Write a function (with helper functions if needed) called to Excel that takes an excel column value (A,B,C,D…AA,AB,AC,… AAA..) and returns a corresponding integer value (A=1,B=2,… AA=26..).
You have a stream of infinite queries (ie: real time Google search queries that people are entering). Describe how you would go about finding a good estimate of 1000 samples from this never ending set of data and then write code for it.
Tree search algorithms. Write BFS and DFS code, explain run time and space requirements. Modify the code to handle trees with weighted edges and loops with BFS and DFS, make the code print out path to goal state.
You are given a list of numbers. When you reach the end of the list you will come back to the beginning of the list (a circular list). Write the most efficient algorithm to find the minimum # in this list. Find any given # in the list. The numbers in the list are always increasing but you don't know where the circular list begins, ie: 38, 40, 55, 89, 6, 13, 20, 23, 36.
Describe the data structure that is used to manage memory. (stack)
What's the difference between local and global variables?
If you have 1 million integers, how would you sort them efficiently? (modify a specific sorting algorithm to solve this)
In Java, what is the difference between static, final, and const. (if you don't know Java they will ask something similar for C or C++).
Talk about your class projects or work projects (pick something easy)… then describe how you could make them more efficient (in terms of algorithms).
Suppose you have an NxN matrix of positive and negative integers. Write some code that finds the sub-matrix with the maximum sum of its elements.
Write some code to reverse a string.
Implement division (without using the divide operator, obviously).
Write some code to find all permutations of the letters in a particular string.
What method would you use to look up a word in a dictionary?
Imagine you have a closet full of shirts. It's very hard to find a shirt. So what can you do to organize your shirts for easy retrieval?
You have eight balls all of the same size. 7 of them weigh the same, and one of them weighs slightly more. How can you fine the ball that is heavier by using a balance and only two weighings?
What is the C-language command for opening a connection with a foreign host over the internet?
Design and describe a system/application that will most efficiently produce a report of the top 1 million Google search requests. These are the particulars: 1) You are given 12 servers to work with. They are all dual-processor machines with 4Gb of RAM, 4x400GB hard drives and networked together.(Basically, nothing more than high-end PC's) 2) The log data has already been cleaned for you. It consists of 100 Billion log lines, broken down into 12 320 GB files of 40-byte search terms per line. 3) You can use only custom written applications or available free open-source software.
There is an array A[N] of N numbers. You have to compose an array Output[N] such that Output[i] will be equal to multiplication of all the elements of A[N] except A[i]. For example Output[0] will be multiplication of A[1] to A[N-1] and Output[1] will be multiplication of A[0] and from A[2] to A[N-1]. Solve it without division operator and in O(n).
There is a linked list of numbers of length N. N is very large and you don't know N. You have to write a function that will return k random numbers from the list. Numbers should be completely random. Hint: 1. Use random function rand() (returns a number between 0 and 1) and irand() (return either 0 or 1) 2. It should be done in O(n).
Find or determine non existence of a number in a sorted list of N numbers where the numbers range over M, M>> N and N large enough to span multiple disks. Algorithm to beat O(log n) bonus points for constant time algorithm.
You are given a game of Tic Tac Toe. You have to write a function in which you pass the whole game and name of a player. The function will return whether the player has won the game or not. First you to decide which data structure you will use for the game. You need to tell the algorithm first and then need to write the code. Note: Some position may be blank in the game। So your data structure should consider this condition also.
You are given an array [a1 To an] and we have to construct another array [b1 To bn] where bi = a1*a2*...*an/ai. you are allowed to use only constant space and the time complexity is O(n). No divisions are allowed.
How do you put a Binary Search Tree in an array in a efficient manner. Hint :: If the node is stored at the ith position and its children are at 2i and 2i+1(I mean level order wise)Its not the most efficient way.
How do you find out the fifth maximum element in an Binary Search Tree in efficient manner. Note: You should not use use any extra space. i.e sorting Binary Search Tree and storing the results in an array and listing out the fifth element.
Given a Data Structure having first n integers and next n chars. A = i1 i2 i3 ... iN c1 c2 c3 ... cN.Write an in-place algorithm to rearrange the elements of the array ass A = i1 c1 i2 c2 ... in cn
Given two sequences of items, find the items whose absolute number increases or decreases the most when comparing one sequence with the other by reading the sequence only once.
Given That One of the strings is very very long , and the other one could be of various sizes. Windowing will result in O(N+M) solution but could it be better? May be NlogM or even better?
How many lines can be drawn in a 2D plane such that they are equidistant from 3 non-collinear points?
Let's say you have to construct Google maps from scratch and guide a person standing on Gateway of India (Mumbai) to India Gate(Delhi). How do you do the same?
Given that you have one string of length N and M small strings of length L. How do you efficiently find the occurrence of each small string in the larger one?
Given a binary tree, programmatically you need to prove it is a binary search tree.
You are given a small sorted list of numbers, and a very very long sorted list of numbers - so long that it had to be put on a disk in different blocks. How would you find those short list numbers in the bigger one?
Suppose you have given N companies, and we want to eventually merge them into one big company. How many ways are theres to merge?
Given a file of 4 billion 32-bit integers, how to find one that appears at least twice?
Write a program for displaying the ten most frequent words in a file such that your program should be efficient in all complexity measures.
Design a stack. We want to push, pop, and also, retrieve the minimum element in constant time.
Given a set of coin denominators, find the minimum number of coins to give a certain amount of change.
Given an array, i) find the longest continuous increasing subsequence. ii) find the longest increasing subsequence.
Suppose we have N companies, and we want to eventually merge them into one big company. How many ways are there to merge?
Write a function to find the middle node of a single link list.
Given two binary trees, write a compare function to check if they are equal or not. Being equal means that they have the same value and same structure.
Implement put/get methods of a fixed size cache with LRU replacement algorithm.
You are given with three sorted arrays ( in ascending order), you are required to find a triplet ( one element from each array) such that distance is minimum.
Distance is defined like this : If a[i], b[j] and c[k] are three elements then distance=max(abs(a[i]-b[j]),abs(a[i]-c[k]),abs(b[j]-c[k]))" Please give a solution in O(n) time complexity
How does C++ deal with constructors and deconstructors of a class and its child class?
Write a function that flips the bits inside a byte (either in C++ or Java). Write an algorithm that take a list of n words, and an integer m, and retrieves the mth most frequent word in that list.
What's 2 to the power of 64?
Given that you have one string of length N and M small strings of length L. How do you efficiently find the occurrence of each small string in the larger one?
How do you find out the fifth maximum element in an Binary Search Tree in efficient manner.
Suppose we have N companies, and we want to eventually merge them into one big company. How many ways are there to merge?
There is linked list of millions of node and you do not know the length of it. Write a function which will return a random number from the list.
You need to check that your friend, Bob, has your correct phone number, but you cannot ask him directly. You must write a the question on a card which and give it to Eve who will take the card to Bob and return the answer to you. What must you write on the card, besides the question, to ensure Bob can encode the message so that Eve cannot read your phone number?
How long it would take to sort 1 trillion numbers? Come up with a good estimate.
Order the functions in order of their asymptotic performance: 1) 2^n 2) n^100 3) n! 4) n^n
There are some data represented by(x,y,z). Now we want to find the Kth least data. We say (x1, y1, z1) > (x2, y2, z2) when value(x1, y1, z1) > value(x2, y2, z2) where value(x,y,z) = (2^x)*(3^y)*(5^z). Now we can not get it by calculating value(x,y,z) or through other indirect calculations as lg(value(x,y,z)). How to solve it?
How many degrees are there in the angle between the hour and minute hands of a clock when the time is a quarter past three?
Given an array whose elements are sorted, return the index of a the first occurrence of a specific integer. Do this in sub-linear time. I.e. do not just go through each element searching for that element.
Given two linked lists, return the intersection of the two lists: i.e. return a list containing only the elements that occur in both of the input lists.
What's the difference between a hashtable and a hashmap?
If a person dials a sequence of numbers on the telephone, what possible words/strings can be formed from the letters associated with those numbers?
How would you reverse the image on an n by n matrix where each pixel is represented by a bit?
Create a fast cached storage mechanism that, given a limitation on the amount of cache memory, will ensure that only the least recently used items are discarded when the cache memory is reached when inserting a new item. It supports 2 functions: String get(T t) and void put(String k, T t).
Create a cost model that allows Google to make purchasing decisions on to compare the cost of purchasing more RAM memory for their servers vs. buying more disk space.
Design an algorithm to play a game of Frogger and then code the solution. The object of the game is to direct a frog to avoid cars while crossing a busy road. You may represent a road lane via an array. Generalize the solution for an N-lane road.
What sort would you use if you had a large data set on disk and a small amount of ram to work with?
What sort would you use if you required tight max time bounds and wanted highly regular performance.
How would you store 1 million phone numbers?
Design a 2D dungeon crawling game. It must allow for various items in the maze - walls, objects, and computer-controlled characters. (The focus was on the class structures, and how to optimize the experience for the user as s/he travels through the dungeon.)
What is the size of the C structure below on a 32-bit system? On a 64-bit?

struct foo {

char a;

char* b;

};

Google Interview: Software Engineer in Test

Efficiently implement 3 stacks in a single array.
Given an array of integers which is circularly sorted, how do you find a given integer.
Write a program to find depth of binary search tree without using recursion.
Find the maximum rectangle (in terms of area) under a histogram in linear time.
Most phones now have full keyboards. Before there there three letters mapped to a number button. Describe how you would go about implementing spelling and word suggestions as people type.
Describe recursive mergesort and its runtime. Write an iterative version in C++/Java/Python.
How would you determine if someone has won a game of tic-tac-toe on a board of any size?
Given an array of numbers, replace each number with the product of all the numbers in the array except the number itself *without* using division.
Create a cache with fast look up that only stores the N most recently accessed items.
How to design a search engine? If each document contains a set of keywords, and is associated with a numeric attribute, how to build indices?
Given two files that has list of words (one per line), write a program to show the intersection.
What kind of data structure would you use to index annagrams of words? e.g. if there exists the word "top" in the database, the query for "pot" should list that.

Google Interview: Quantitative Compensation Analyst

What is the yearly standard deviation of a stock given the monthly standard deviation?
How many resumes does Google receive each year for software engineering?
Anywhere in the world, where would you open up a new Google office and how would you figure out compensation for all the employees at this new office?
What is the probability of breaking a stick into 3 pieces and forming a triangle?

Google Interview: Engineering Manager

You're the captain of a pirate ship, and your crew gets to vote on how the gold is divided up. If fewer than half of the pirates agree with you, you die. How do you recommend apportioning the gold in such a way that you get a good share of the booty, but still survive?

Google Interview: AdWords Associate

How would you work with an advertiser who was not seeing the benefits of the AdWords relationship due to poor conversions?
How would you deal with an angry or frustrated advertisers on the phone?

Sources

http://news.ycombinator.com/item?id=266663

http://tihomir.org/crazy-questions-at-google-job-interview/

http://www.drizzle.com/~jpaint/google.html

http://www.gamedev.net/community/forums/topic.asp?topic_id=299692

http://careers.cse.sc.edu/googleinterview

http://job-interview.blogspot.com/2005/02/google-interview-product-marketing.html

http://www.theregister.co.uk/2007/01/05/google_interview_tales/

http://money.cnn.com/2007/08/29/technology/brain_teasers.biz2/index.htm

http://blogs.lessthandot.com/index.php/ITProfessionals/EthicsIT/google-interview-questions

http://placementsindia.blogspot.com/2007/09/google-top-interview-puzzles.html

http://linkmingle.com/user/interview_questions/google_interview_questions