Saturday, May 21, 2005

 

Google Interview Questions - 1

1.
From http://www.cnblogs.com/joycsharp/archive/2006/10/20/534439.html

已知T(0)=1; T(1)=1; T(2)=2; T(n)=T(n-1)+T(n-2)+T(n-3);
请用最优方式求T(n);

int T(int n)
{
}

可以用最熟悉的语言写,不考虑溢出情况,大家有什么更优的算法拿出来讨论下。

# re: google面试题目 回复
2006-10-20 16:03 by flycbn

public static long T1(int t)
{
long temp = 0, a = 1, b = 1, c = 2;
for (int i = 3; i < t + 1; i++)
{
temp = a + b + c;
a = b; b = c; c = temp;
}
return temp;
}

public static long T2(int t)
{
long[] buffer = { 1, 1, 2 };
for (int i = 3; i < t + 1; i++)
{
buffer[i % 3] += buffer[(i - 2) % 3] + buffer[(i - 1) % 3];
}
return buffer[t % 3];
}

public static long T3(int t)
{
long[] buffer ={ 1, 1, 2 };
int temp = 0;
int up = t + 1;
for (int i = 3; i < up; i++)
{
temp = i % 3;
buffer[temp] += buffer[(temp + 1) % 3] + buffer[(temp + 2) % 3];
}
return buffer[temp];
}

两轮测试成绩如下:

方法T1循环100000000次,结果为1370210800226364673,耗时8612384微秒。
方法T2循环100000000次,结果为1370210800226364673,耗时74707424微秒。
方法T3循环100000000次,结果为1370210800226364673,耗时71803248微秒。
方法T1循环100000000次,结果为1370210800226364673,耗时8612384微秒。
方法T2循环100000000次,结果为1370210800226364673,耗时73906272微秒。
方法T3循环100000000次,结果为1370210800226364673,耗时71602960微秒。

(按:不难看出程序编译器优化或,直接使用寄存器的威力)

2.
发信人: wlter (fdsfsdf), 信区: Programming
标 题: google昨天晚上笔试题
发信站: 水木社区 (Wed Oct 18 01:03:20 2006), 站内

一个n个顶点的连通图.

写一个算法,求任意两个点之间是否存在长度为k的通路,通路上可以有重复的点.

写时间和空间复杂度

--

※ 来源:·水木社区 newsmth.net·[FROM: 221.221.248.*]

发信人: Macsy (真心), 信区: Programming
标 题: Re: google昨天晚上笔试题
发信站: 水木社区 (Wed Oct 18 01:15:12 2006), 站内

用matrix multiple, 复杂度是O(N^3logK)

(按:如果用矩阵相乘快速算法,如FFT等,比这个更快。其实本题用标准的Node Labeling算法即可搞定,也就是Floyd算法稍微变形一下,无趣,到底是第一轮的题目)

3.

(按:有的说是MS的题,有的说是Google的题,不管了,就放在这里)

Anyway, I guess I have already drifted too far. Here are the brain teasers:

1. Given an integer array (positive #, negative #, or 0), find a subarray with the maximum sum.

(A subarray is a consecutive subsequence of the original array. The sum of an array is just the sum of its individual elements.)

2. Suppose you have a M-by-N matrix (i.e. M rows and N columns), whose entries are all integers. We want to set all the elements on the i-th row and j-th column to 0 if matrix entry (i, j) is 0. Write a routine that does this and we want to find a solution with the minimum amount of memory consumption and fastest speed (i.e. the less memory you use to store some intermediate result, the better). Highlight the next sentence for a quick hint: you can actually find a solution that only scans the matrix once and use O(1) memory (i.e. constant amount of memory).

For instance, if the matrix is:

1 0 2

3 1 1

then, the result should be:

0 0 0

3 0 1

(since the (1, 2) entry is 0, we set all elements on the 1st row and 2nd column to 0)

From http://blog.joycode.com/demonfox/archive/2006/12/14/89009.aspx

两题的解答

1. 最大子数列 (Kadane算法)

static void FindMaxSumSubarray(int[] array, out int start, out int end)
{
int tmp, max, cur;
start = end = 0;
tmp = 0;
max = int.MinValue;
cur = 0;
for (int i=0; i {
tmp += array[i];
if (tmp > max)
{
start = cur; end = i; max = tmp;
}
if (tmp < 0)
{
tmp = 0; cur = i + 1;
}
}
}


顺便说一句:这个问题在2维数列的情况下是一个蛮有名的machine learning的问题。google一下maximum subarray machine learning可以查到不少文献。

2. 矩阵设零 (特殊的1x1矩阵我就偷懒掉了,: ) )

static void ZeroThemOut(ref int[,] matrix)
{
int rows = matrix.GetLength(0);
int cols = matrix.GetLength(1);
int oneExtraFlagForCol0 = 1;

for (int r = 0; r < rows; r++)
{
for (int c = 0; c < cols; c++)
{
if (0 == matrix[r, c])
{
matrix[r, 0] = 0;
if (0 == c)
oneExtraFlagForCol0 = 0;
else
matrix[0, c] = 0;
}
}
}

for (int r = 1; r < rows; r++)
{
if (0 == matrix[r, 0])
{
for (int c = 0; c < cols; c++)
matrix[r, c] = 0;
}
}
for (int c = 1; c < cols; c++)
{
if (0 == matrix[0, c])
{
for (int r = 0; r < rows; r++)
matrix[r, c] = 0;
}
}
if (0 == matrix[0, 0])
{
for (int c = 0; c < cols; c++)
matrix[0, c] = 0;
}
if (0 == oneExtraFlagForCol0)
{
for (int r = 0; r < rows; r++)
matrix[r, 0] = 0;
}
}

仓促写就,如果有错误的话,麻烦告诉我一下,多谢多谢。

# 回复: 两题的解答
2006-12-14 19:03 by Qinghu
matrix[0, c] = 0;
if (0 == c)
oneExtraFlagForCol0 = 0;
是否应改为

if (0 == c)
oneExtraFlagForCol0 = 0;
else
matrix[0, c] = 0;
# 回复: 两题的解答
2006-12-14 19:39 by demonfox
嗯,对的,呵呵,多谢多谢。



<< Home

This page is powered by Blogger. Isn't yours?