Hawstein's Blog

Make something people love

Cracking the coding interview--Q20.7

题目原文： Write a program to find the longest word made of other words. 译文：写一个程序，找到由其它单词组成的最长单词。解答我们从例子着手开始分析问题。假如我们有一个单词数组，如下： 1 2 3 string arr[] = {"test", "tester", "testertest", "testing...

Hawstein | March 4, 2013

Cracking the coding interview--Q20.6

题目原文： Describe an algorithm to find the largest 1 million numbers in 1 billion numbers. Assume that the computer memory can hold all one billion numbers. 译文：描述一个算法，在10亿个数中找到最大的1百万个数。假设内存可以一...

Hawstein | March 3, 2013

Cracking the coding interview--Q20.5

题目原文： You have a large text file containing words. Given any two words, find the shortest distance (in terms of number of words) between them in the file. Can you make the searching operation ...

Hawstein | March 2, 2013

动态规划之背包问题（一）

一切都要从一则故事说起。话说有一哥们去森林里玩发现了一堆宝石，他数了数，一共有n个。但他身上能装宝石的就只有一个背包，背包的容量为C。这哥们把n个宝石排成一排并编上号： 0,1,2,…,n-1。第i个宝石对应的体积和价值分别为V[i]和W[i] 。排好后这哥们开始思考：背包总共也就只能装下体积为C的东西，那我要装下哪些宝石才能让我获得最大的利益呢？ OK，如果是你，你会怎么做？你斩...

Hawstein | March 1, 2013

Cracking the coding interview--Q20.4

题目原文： Write a method to count the number of 2s between 0 and n. 译文：写一个函数，计算0到n之间2的个数。解答最简单直观的方法就是对于0到n之间的数，一个个地去统计2在它们上出现的个数，然后累加起来即可。求2在某个数上出现的次数需要O(logn)的时间，一共有n个数，所以共需要O(nlogn)的时间。 ...

Hawstein | March 1, 2013

Cracking the coding interview--Q20.3

题目原文： Write a method to randomly generate a set of m integers from an array of size n. Each element must have equal probability of being chosen. 译文：写一个函数，随机地从大小为n的数组中选取m个整数。要求每个元素被选中的概率相等。 ...

Hawstein | February 25, 2013

Cracking the coding interview--Q20.2

题目原文： Write a method to shuffle a deck of cards. It must be a perfect shuffle - in other words, each 52! permutations of the deck has to be equally likely. Assume that you are given a random n...

Hawstein | February 24, 2013

Cracking the coding interview--Q20.1

题目原文： Write a function that adds two numbers. You should not use + or any arithmetic operators. 译文：写一个Add函数求两个数的和，不能使用+号或其它算术运算符。解答为了解决这个问题，让我们来深入地思考一下，我们是如何去加两个数的。为了易于理解，我们考虑10进制的情况。比如...

Hawstein | February 24, 2013

Cracking the coding interview--Q19.11

题目原文： Design an algorithm to find all pairs of integers within an array which sum to a specified value. 译文：设计一个算法，找到数组中所有和为指定值的整数对。解答时间复杂度O(n)的解法我们可以用一个哈希表或数组或bitmap(后两者要求数组中的整数非负)来保存s...

Hawstein | February 23, 2013

Cracking the coding interview--Q19.10

题目原文： Write a method to generate a random number between 1 and 7, given a method that generates a random number between 1 and 5 (i.e., implement rand7() using rand5()). 译文：给你一个能生成1到5随机数的函数，...

Hawstein | February 23, 2013