My notes on leetcode

Thursday, January 29, 2015

未名空间十大: 长年潜水，回馈FLG面经

未名空间十大: 长年潜水，回馈FLG面经: 发信人: ynlmk (oh~我拿什么来拯救你啊~我的黑眼圈~!), 信区: JobHunting 标题: 长年潜水，回馈FLG面经发信站: BBS 未名空间站 (Sun Jan 25 08:03:43 2015, 美东) 概略：从本科到PhD一直念的EE。PhD...

Wednesday, January 28, 2015

class Solution {
public:
        string largestNumber(vector<int> &num) {

            int n = num.size();
            vector<string> numstrs(n);

            for(int i = 0; i < n; i++)
            {
                numstrs[i] = to_string(num[i]); // to_string() is standard lib func
            }

            sort(numstrs.begin(), numstrs.end(), myCompare);

            if (numstrs[n-1] == "0")
            {
                return "0";
            }

            string res;
            for(int i = n-1; i >= 0; i--)
            {
                res += numstrs[i];
            }

            return res;
        }

        static bool myCompare (string str1, string str2)
        {
            return (str1 + str2) < (str2 + str1);
        }
};

Factorial Trailing Zeroes

from leetcode discussion

Because all trailing 0 is from factors 5 * 2.
But sometimes one number may have several 5 factors, for example, 25 have two 5 factors, 125 have three 5 factors. In the n! operation, factors 2 is always ample. So we just count how many 5 factors in all number from 1 to n.

n!=2 * 3 * ...* 5 ... *10 ... 15* ... * 25 ... * 50 ... * 125 ... * 250...
  =2 * 3 * ...* 5 ... * (5^1*2)...(5^1*3)...*(5^2*1)...*(5^2*2)...*(5^3*1)...*(5^3*2)... (Equation 1)

We just count the number of 5 in Equation 1.
Multiple of 5 provides one 5, multiple of 25 provides two 5 and so on.
Note the duplication: multiple of 25 is also multiple of 5, so multiple of 25 only provides one extra 5.
Here is the basic solution:

return n/5 + n/25 + n/125 + n/625 + n/3125+...;

code:

    int trailingZeroes(int n) {
        return n == 0 ? 0 : n / 5 + trailingZeroes(n / 5);
    }

iterative:

    int trailingZeroes(int n) {
        int cnt=0;
        while(n>0){
            cnt+=n/5;
            n/=5;
        }
        return cnt;
    }

Tuesday, January 20, 2015

google onsite

发信人: icetortoise (icetortoise), 信区: JobHunting
标题: 发一道G家的onsite题及教训
发信站: BBS 未名空间站 (Sat Jan 17 20:47:56 2015, 美东)

去年的onsite，挂在这题上了。其实不难，之前也有人发过，但好像没详细讨论过。

一组字符串，求所有彼此之间无公共字符的两两组合中，两字符串长度乘积的最大值。

上来就是暴力解O(n^2).问有没有更快的。我问:better than O(n^2)? 对方没正面回答
。结果我以为他是默认了。于是挖空心思的找O(nlogn)的解法，建字符索引，后缀树都
想过。最后没办法，问他有没有hint。结果他提了剪枝。当时我就崩溃了，剪枝早想到
了，但剪枝的话worst case还是O(n^2)啊！我立刻说了按长度排序再剪枝的方法。但是
时间已经不够写代码了。

想问问这题究竟有没有优于O(n^2)的解法。当然，假定比较两字符串的时间设为常数。

我的感觉是没有的。当然，我可能是错的。

教训就是面试是交流的过程，想到什么improvement就说出来讨论讨论，就算他不认可
，至少也知道你想到了一个方法。最忌讳闷头苦想，而面试官根本不知道你在想啥。

review: from here
1
Here's one take at it:

1 - Take each word and convert each into a bitmap by iterating over the characters and flipping a bit to 1 at an offset that corresponds to the position of the letter in the alphabet (e.g. abba = 11, a = 1, bdf = 101010, etc).

2 - perform a binary AND for each bitmap permutation. If ANDing the two bitmaps results in zero, and this match has the largest sum of word lengths so far, keep the word pair.

I believe this is O(n^2)-ish?

2 a more interesting method:

Use $n$ to denote the number of words and $a$ to denote the size of the alphabet. I will also use $\ell$ to denote maximum word length. Thus, the size of input is $O(\ell n)$ and this is also the time complexity of reading it.

The speedup for the naive quadratic-time solution is explained well in other answers. Here, I will explain a better algorithm for the case when the alphabet is small enough. Here, "small enough" will mean "we are able to spend $O(a2^a)$ time and $O(2^a)$ memory". Note that for lowercase English letters we have $a=26$ which makes this algorithm perfectly reasonable.

But first, a curiosity. I used the algorithm described below on the 62887 lowercase words in /usr/share/dict/words on my machine. Here's the best output: individualizing phototypesetter.

Here's the algorithm:

As in the other answers, we will use bitmasks to represent sets of letters. Thus, the integers from 0 to $2^a-1$ will represent all possible subsets of our alphabet, 0 being the empty set.

Our algorithm will consist of three steps:

For each set S of letters, find the longest word that consists of exactly those letters.
For each set S of letters, find the longest word that consists of at most those letters (i.e., some letters may be unused, but you cannot use a letter that does not belong to S).
For each word w, compute length(w) + length(longest word out of letters not in w) and pick the maximum.

Step 1 is easy: just take an array of size $2^a$ , then read the input, and for each word update the corresponding cell. This can be done in $O(\ell n)$ .

Step 2 can be done using dynamic programming. We process the subsets of our alphabet in the order 0, 1, ..., $2^a -1$ . (Note that this order that has the property that for any set S, all subsets of S are processed before S.) For each set of letters S, the best word for S is either the best word made out of exactly these letters (this we computed in phase 1), or at least one letter is unused. We try all possibilities for the unused letter and pick the best one. All of this takes $O(a2^a)$ time.

Step 3 is again easy. If we stored the set of letters for each word in step 1, step 3 can now be done in $O(n)$ time. Hence the overall time complexity is $O(\ell n + a2^a)$ .

Tuesday, December 23, 2014

FGTP Internship 的面经

发信人: hahadaxiong (hahadaxiong), 信区: JobHunting
标题: 分享几个FGTP Internship 的面经，顺便求FG收留
发信站: BBS 未名空间站 (Sun Dec 21 01:45:28 2014, 美东)

PhD summer intern，都是11月面的

F第一轮
Q1：两个string s1, s2, 比较前n个的字符的大小，n可能比s1, s2的长度长
Q2：每个user都有很多email联系人,<user, list of email contacts>,把这些user分
组，一个组内的user 可以通过一些共同的Email account连起来，还有一些改进

F第二轮
聊了很多的research和以前的project
Q1：一个文件里存着代码和注释，注释在/××/中间，要求print所有line除了注释

G家
Interview 1
有一些set of names, 比如first name, middle name, last name,写个iterator打印
名字的组合
Interview 2
Longest Consecutive Sequence
Simplify path 变型。。具体要求不太记得了
Interview 3 （是国人大哥）
聊了以前的project，题目是Interleaving String的一个变种，也是用DP做

T
Q1:设计数据结构快速查找一个栈里是否有某个元素
Q2： Inverted index 的一个题目，具体什么要求不太记得了

P：
Q1：给一个Amazon s3Key.next() 这个api, 可以读取一块定长字符串，要求实现常见
的nextLine()函数，即打印下一行。

TP面完都是一个小时内受到据信，这效率。。。。

G，F现在都在pool里等match, F家效率很低啊，好不容易安排了个面试，还被临时取消
了。。求哪位大侠收留。多谢！

Thursday, December 18, 2014

google题

发信人: xiaoyouyi (yy), 信区: JobHunting
标题: G家题讨论： harry potter 走矩阵
发信站: BBS 未名空间站 (Sun Jan 19 04:06:43 2014, 美东)

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

发信人: blaze (狂且), 信区: JobHunting
标题: Re: G家题讨论： harry potter 走矩阵
发信站: BBS 未名空间站 (Sun Jan 19 14:12:05 2014, 美东)

Just dp:
f是dp函数的值，表示从当前的点走到目标最少需要多少能量。

w是当前点上的权重，可以是正的或者负的。

f(m, n) = 0

f(i, j) = min(
max(f(i+1, j) - w(i+1,j), 0),
max(f(i, j+1) - w(i, j+1), 0)
)

每个点计算当前点到目标的最小能量要求。当前点只能走到下面或右面的点。如果走下面的点，那么最小要求是下面点的最小要求减去下面那个点的值。如果发现小于0则是0。右面的点同理。然后两种情况取最小作为当前点的最小能量要求即可。

发信人: CodeSwim (CodeSwim), 信区: JobHunting
标题: GG面经
发信站: BBS 未名空间站 (Tue Jan 20 12:55:43 2015, 美东)

前两天面了GG, 刚收到feedback说通过. 下面是面经:
白人小伙, 一上来什么都没说,直接开题.

第一题: 实现搜索框的提示功能, 用户输入一个或者一部分字符后, 算法输出所有
match的字符串.
给了三种方案, 一种是简单的直接brute force; 第二种是trie; 第三种是类似正则表
达式的做法; 面试官说用trie来实现吧. 先构建trie, 然后把搜索函数写出来. 没什么
好说的从头开始写. 完成后写了个简单的test case, 和他一起过了一遍;

第二题, deep copy linked list. 给了两种方案, 一是hashmap based Time O(n) +
Space O(n); 一是直接对List拆分deep拷贝然后再恢复原list Time O(n) + Space O(
1)。
面试官让分析了下两种方法的优劣. 然后说实现下第二种吧. 我刚把思路说完正打算写
代码, 然后考官打断说时间不太够了,实现第一种吧. 于是一口气写完. 给了个test
case过了一遍. 最后考官问代码里有没有问题, 我又从头仔细和他过了一遍,没发现.
问他给点提示, 他说他也没发现... 于是让问问题. 结束.

Wednesday, December 17, 2014

Missing Ranges

from here

Given a sorted integer array where the range of elements are [0, 99] inclusive, return its missing ranges.
For example, given [0, 1, 3, 50, 75], return [“2”, “4->49”, “51->74”, “76->99”]
[分析]
一遍线性扫描即可。
[注意事项]
1）针对一些特殊情况，询问面试官，比如说如果array是个空的，或者array包含区间内的所有元素，相应的返回值是什么
2）可以给出一些有意思的test case，另外就是不需要限制给出的范围是[0, 99]，用start和end表示就行。在面试的时候可以先提一下，写出[0, 99]的代码，然后在稍作修改，变成start和end的版本。

public class Solution {
    public List<String> findMissingRanges(int[] vals, int start, int end) {
        List<String> ranges = new ArrayList<String>();
        int prev = start - 1;
        for (int i=0; i<=vals.length; ++i) {
            int curr = (i==vals.length) ? end + 1 : vals[i];
            if ( cur-prev>=2 ) {
                ranges.add(getRange(prev+1, curr-1));
            }
            rev = curr;
        }
        return ranges;
    }
 
    private String getRange(int from, int to) {
        return (from==to) ? String.valueOf(from) : from + "->" to;
    }
}