Tags » Interview Questions

Google两道题

1.给你一个two dimensional array, array的元素是0 或者1。问能不能找到一个矩形
,矩形的4个角都是1.

leetcode里面有类似的题,我给了类似的答案,复杂度是O(n^3),感觉面试官不是很满
意。不知道有没有复杂度更少的算法。

One Thing I noticed when trying to implement the solution is that

Java does not support array of collections! 163 more words

Algorithm

How To: Get Your Dream Job

We spend four years (for many, often more) in college, soaking up knowledge in preparation for a thriving career.

Often, graduation day comes and then reality sets in. 611 more words

Topological Sort

The Topological sort algorithm is fairly simple. First we need to find the starting point, which is the nodes with 0 in-degrees. Then we remove them and the out edges, and putting them into the result array. 135 more words

Algorithm

G家题讨论: harry potter 走矩阵

假设你是harry potter,在grid的左上角,你现在要走到右下角,grid中有
正数也有负数,遇到正数表示你的strength增加那么多,遇到负数表示strength减少那
么多,在任何时刻如果你的strength小于等于0,那么你就挂了。在一开始你有一定的
初始的strength,现在问这个初始的strength最少是多少,才能保证你能够找到一条路
走到右下角。每一步只能向右或者向下。

This is a typical DP problem.
We need to have a dp matrix that is the same size as the matrix. 84 more words

Interview Questions

Ebay onsite question

前些天面的EBay, onsite。 有几个问题感觉回答的不是很好,在这求教:

1. 两个输入,一个是description(String), 另一个是Negative Words(List).

description 是一个非常长的String, 例如一段话。 要求其中不能有negative
words。如果有 则输出哪里negative word。 没有则输出good。

回答 把description分成每一个word,然后比对 negative words (this is what I thought of in the first place) 113 more words

Algorithm

某大公司两道题

1. 求一个字符串,只包含0-9的digit, 并且所有的四位数字的组合都是这个字符串的
sub-string.

第一道题没有很好的想法。唯一能想到的就是从0000到9999遍历一遍,然后从空串开始,如果字符串已经有包括当前这个数,则跳过,如果没有,进一步看开头结尾有公共子串,就接上,如果没有,则append,最后得出的结果就是我们想要的字符串了。

2. 一个m*n float矩阵A,在每个格子可以向上下左右四个方向移动。 求左上角到右下
角的一条路径,使得路径上所有数字的乘积最大(路径上不能有重复的格子)。

第二道题只能想到用DFS把所有可能的结果都算出来,用一个visited的Hashset来存已经访问过的位置。

Algorithm