作者: admin, 讨论版: 面试求职, 发表时间: 2015-01-27 00:15:47 PST
标题: FB 面试题目
关键字:
--1---------------------------
From: http://www.mitbbs.com/article_t/JobHunting/32867879.html
1） pre-fix String search. 我写了一个TRIE class
2) String evaluation: eg. Given 3 +2x +5y -(3 +5x) = 8 -7y +2x and X value, return Y value
--2---------------------------
From: http://www.mitbbs.com/article_t/JobHunting/32872629.html
1， 给一个string，比如UAXXBAUB，给一个pattern，比如AB，返回包含pattern的最短
substring，结果是AUB,考虑pattern是有序的。
就是Minimum Window Substring的有序版，主要考虑的是找到window后shrink到
底怎么做，有好几种情况。比如"UAXSSXSXAAUB", "XXA"，找到XSSXSXA之后shrink窗口
，得把leftBound前进到第2个X。
[Similar to Distinct Subsequences. DFS is intuitive. DP needs a little more thought.]
2， 给一个int array，有正有负， 给一个target number，找出这个array里有没有连
续的几个数之和等于target number 要用O(n) time
感觉是DP，但是没什么头绪。
3, 给一个字典，可以组合任意个单词，怎么找到最长的可能的palindom
发信人: cfdream (gogogo), 信区: JobHunting
标 题: Re: 求问FB题目
发信站: BBS 未名空间站 (Thu Jan 22 13:46:25 2015, 美东)
写写自己的理解
1. DP
f(i,j)为母串s[0,...,i]匹配到子串p[0,...j]的最短substring的长度，则
f(i,j) = f(i-1,j-1)+1, if s[i]==p[j]
= f(i-1,j)+1, if s[i]!=p[j]
然后要用另外一个二维数组记录f(i,j)的前面是哪个操作，j-1或者j,i始终减1
最后查找f(i,n)哪个最小，n为子串的长度，并且回溯找到起始的index，返回值
2. 将(0,i)的和存在hashmap<int, vector<int> >，key为(0,i)的和，vector<int>记
录具有相同和的下标。然后从头开始，对于i，如果(0,i)的和为sum, 找sum-x是否在
hashmap中，如果在且vector中有小于i的下标，存在，否则i++;
3. 能想到的就是建一个trie，然后brute force
--3---------------------------
From: http://www.mitbbs.com/article_t1/JobHunting/32838067_0_1.html
1) 给个数组seq， 和一个total，找 if there is a contiguous sequence in seq
which sums to total. 都是正数.
Solution:
- If all numbers are positive, use a sliding window. O(n)
- If sequence is sorted, use a sliding window too. O(n)
- If not sorted, and not all numbers are positive, use the method below. O(n)
发信人: chaeyoung (love_cy), 信区: JobHunting
标 题: Re: FB电面面经
发信站: BBS 未名空间站 (Wed Nov 26 16:58:11 2014, 美东)
O(n) solution for unsorted array.
An example
arr=[-1 4 1 0 -2 -3 7],
sum = 2
step 1: accumulate the sums
arr -> acc = [0 -1 3 4 4 2 -1 6]. Insert 0 at the front
step 2: traverse the acc with hash table
the hash table will store the following values
ht = [0+2, -1+2, 3+2, 4+2, 4+2, ..]
It returns when finding an element of acc in the hash table (2 in this case).
In case above, when 2 is reached, it exists in ht as 0-th element. So the subsequence [ht[2]+1, indexOf(2)], which is [0+1, 5] is the subsequence to find.
--
最后修改: admin on 2015-01-27 16:21:08 PST
※ 来源: homecox.com [来自: 66.]
|
|
|
