2011年七月

推荐firefox插件vimperator (用vim方式使用Firefox)

今天在逛水木的时候,发现这篇文章:http://www.newsmth.net/bbsrecon.php?id=8017

是对vimperator进行了介绍,原来国外哥们写的firefox插件,能够像使用Vim的方式来高效地使用firefox,下来来尝试了,效果不错!

下载地址:https://addons.mozilla.org/en-US/firefox/addon/vimperator/

常用命令(不断更新):

open: 在当前tab打开新的网址  open www.baidu.com

tabopen: 在新的tab打开网址

back: 后退键

forward:前进键

gt/gT:在tab间进行移动

d: 关闭当前tab

hjkl:上下移动网页或者光标

i(insert):进入insert模式,可以移动光标

/ :搜索网页的内容

总的来说很强大哈!!!



MySQL索引背后的数据结构及算法原理【好文】

这篇文章从mysql索引的内部结构B+树来分析如何来提高索引的性能,以及索引如何进行存储等方面,

写的比较通俗易懂,推荐!

地址:http://www.cnblogs.com/leoo2sk/archive/2011/07/10/mysql-index.html



140个Google的面试题【转载】

原文地址:http://coolshell.cn/articles/3345.html

来源:http://blog.seattleinterviewcoach.com/2009/02/140-google-interview-questions.html(墙)

某猎头收集了140多个Google的面试题,都张到他的Blog中了,主要是下面这些职位的,因为被墙,且无任何敏感信息,所以,我原文搬过来了。
  • Product Marketing Manager
  • Product Manager
  • Software Engineer
  • Software Engineer in Test
  • Quantitative Compensation Analyst
  • Engineering Manager
  • AdWords Associate

这篇Blog例举了Google用来面试下面这几个职位的面试题。很多不是很容易回答,不过都比较经典与变态,是 Google,Microsoft,Amazon之类的公司的风格。对于本文,我没有翻译,因为我相信,英文问题是最好的。不过对于有些问题,我做了一些 注释,不一定对,但希望对你有帮助启发。对于一些问题,如果你百思不得其解,可以Google一下,StackOverflow或是Wikipedia上 可能会给你非常全面的答案。

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.
Product Manager
  • How would you boost the GMail subscription base?
  • What is the most efficient way to sort a million integers?  (陈皓:merge sort)
  • 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. (陈皓:用三句话向8岁的侄子解释什么是数据库,考你的表达能力了)
  • 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? (陈皓:很不错的一道题,不要以为分类查询很容易,想想图书馆图书的分类查询问题吧。另外,你处想想如何在你在你的衣柜里实现一个相当于Hash表或是一 个Tree之类的数据结构)
  • 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? (陈皓:这个问题很有限制级,哈哈,非常搞的一个问题,注意wife们的递归,这类的问题是经典的分布式通讯问题,上网搜 一搜吧。)
  • 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?(陈皓:第一反应是——这个国家是中国。一个概率问题,其实,无论你怎么生,50%的概率是永远不变的。)
  • 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. (陈皓:从3的倍数的楼层开始扔,比如3,6,9,12…..,如果鸡蛋在3n层碎了,那到在3n-1层扔第二个鸡蛋,如果没碎,则最高不碎楼层为3n- 1,否则为3n-2)
  • 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?


[编程之美]N个鸡蛋放到M个篮子的方法

今天看到一个面试题目,题目大意:将n个鸡蛋放到m个篮子,同时保证不能有空篮子,且对于任意小于等于n的数,都能保证有几个篮子的鸡蛋数等于这个数

题目分析

第一眼看到这个题目时,感觉像是整数拆分问题,但是有两个限制:1. 不能有空篮子 2.保证能够针对任意<=n的数,都可以用几个篮子的鸡蛋的和来表示,所以应该不是整数拆分问题。

首先想到是就是穷举,也就是深度搜索,但是如何判断搜索的一个结果是否满足第二个条件呢?

这里可以通过归纳的方法,假设当前的前n个数为Sn,同时任意<=Sn的数都可以用前n个数某些数的和来表示,那么第n+1个数的范围是什么呢?

这里应该可以想到,如果第n+1个数>(Sn) + 1 的话,相当于有间隔,那么(Sn) + 1这个就无法表示,所以第n+1个数应该是<= Sn + 1,这样就可以满足

任意的<=S(n+1) 的数都可以用前n+1个数来表示;

同时在搜索的过程中保证序列是非降序的,而且会有剪枝的方法,实现具体看代码

代码实现

更多 >



使用mmap实现文件的拷贝

今天看csapp看到了虚拟存储器的映射以及mmap函数的用法,作为练习,使用mmap来实现文件的拷贝操作,同时与传统的文件拷贝操作进行了性能比较。

mmap与munmap函数介绍:
#include <unistd .h>
#include <sys /mman.h>
void *mmap(void *start, size_t length, int prot, int flag, int fd, off_t offset);
//返回:若成功时则返回映射区域的指针,若出错则为MAP_FAILED(-1)
</sys></unistd>

start: 最好从start开始的一个区域,这个是hint,具体映射结果还是要看返回结果
length: 映射区域的大小
prot: 映射区域的访问权限位 PROT_EXEC PROT_READ PROT_WRITE PROT_NONE
flags: 映射对象的类型 MAP_ANON MAP_PRIVATE MAP_SHARED

munmap函数删除映射区域

#include <unistd .h>
#include <sys /mman.h>
int munmap(void *start, size_t length);
</sys></unistd>
实验

分别使用了mmap函数和普通的read write实现了文件的复制拷贝,下面是通过复制50M的文件性能分析:

[yangguang@sim124 ~]$ time ./workspace/mmapcopy linux-20101214.tar.gz ./output    
real    0m0.100s
user    0m0.034s
sys     0m0.065s
[yangguang@sim124 ~]$ time ./workspace/copy linux-20101214.tar.gz ./output
real    0m5.016s
user    0m0.000s
sys     0m0.124s

可以看到使用mmap的性能明显高于使用Read write的方式,这里主要原因是使用mmap减少了用户态和内核态间数据
的拷贝
更多 >