LC 29, 31, 41, 67, 69, 168, 274, 275, LC 30, 43, 68, 273 error: Dot product
let 29
class Solution { public: int divide(int dividend, int divisor) { long long a= dividend >= 0 ? dividend : -(long long)dividend; long long b = divisor >= 0 ? divisor : -(long long)divisor; long long result = 0; long long shift = 31; while (shift >= 0) { if (a >= b << shift) { a -= b << shift; result += 1LL << shift; } shift--; } result = ((dividend ^ divisor) >> 31) ? -result : result; if (result > INT32_MAX) { return INT32_MAX; } return result; } };
Let31 Next Permutation
class Solution {
public:
void nextPermutation(vector
Let43 mul string
class Solution {
public:
string multiply(string num1, string num2) {
int len1 = num1.size();
int len2 = num2.size();
vector
for (int i = len1 - 1; i >= 0; --i) {
for (int j = len2 - 1; j >= 0; --j) {
// form the number of mul
int mul = (num1[i] - '0') * (num2[j] - '0');
// the second last pos
int p1 = i + j;
// the last pos
int p2 = i + j + 1;
int sum = mul + values[p2];
//
values[p1] += sum / 10;
values[p2] = sum % 10;
}
}
string result;
for (int value : values) {
if (!(result.size() == 0 && value == 0)) {
result.push_back(value + '0');
}
}
return result.empty() ? "0" : result;
}
};
Let 69 sort(x)
class Solution {
public:
int mySqrt(int x) {
if (x <= 0) {
return 0;
}
int start = 0;
int end = x;
while (start + 1 < end) {
int mid = start + (end-start)/2;
if(mid == x/mid){
return mid;
} else if (mid > x/mid) {
end = mid;
} else {
start = mid;
}
}
return end > x/end ? start: end;
}
};
let 168
class Solution { public: // string convertToTitle(int n) { // string result; // if (n < 1) { // return result; // } // int div = 26; // int rest = n; // while (rest) { // // status : 1->A, ... 25->Y, 0->Z // // to 1->A.. 26->Z // int index = rest % div == 0 ? div : rest % div; // // put the letter in the front // result.insert(result.begin(), index + 'A' - 1); // // minus status we have used // rest = (rest - index) / div; // } // return result; // }
string convertToTitle(int n) {
string result;
if (n < 1) {
return result;
}
int div = 26;
int rest = n;
while (rest) {
int index = (rest-1) % div;
result.insert(result.begin(), index + 'A');
rest = (rest - 1) / div;
}
return result;
}
};
加法运算不用加法
class Solution { public: int getSum(int a, int b) { if (b == 0) { return a; } // add all without carry over int bit_sum = a ^ b; // get the current carry_over, and push it to the next bit int carry_over = (a&b) << 1; // we combine the sum without carry over and current carry_over // to find whether the carry_over is needed. return getSum(bit_sum, carry_over); } };
倒叙输出单链表，有两种方法，问了下tradeoff。然后完成单链表反转
/**
- Definition for singly-linked list.
- public class ListNode {
- public var val: Int
- public var next: ListNode?
- public init(_ val: Int) {
- self.val = val
- self.next = nil
- }
- }
*/
class Solution {
func reverseList(_ head: ListNode?) -> ListNode? {
} }if head == nil { return nil } var root: ListNode? = head var cur: ListNode? = nil while root != nil { let tmp = root?.next root?.next = cur cur = root root = tmp } return cur
1 大数据的follow up
- first bad fllow up 这个题没让写代码，就说了一下思路，我回答的大概就是把区间分成k+1份，然后这样就要K个分割点让K台机器并行的调用isBad()函数，然后遍历得到的结果，会有一个点i和其相邻点(i+1)的结果不一样，这样就把区间范围缩小到(i, i+1)，重复之前的过程知道找到为止。小哥说ok也没再继续问
3. Dot Product
Leetcode 311 July,2016 Facebook 分析 Jan, 2016 http://www.1point3acres.com/bbs/thread-117371-1-1.html 最后一轮coding也是地里出现过的面经，sparse vector dot multiplication， 这道题我当时并没有准备到，但是正因为如此，我认为我跟面试官的交流给我加分了不少。
－ 面试官首先问我每个vector很大，并不能在内存中存下，该怎么办， 我说只需要存下非零的元素和他们的下标就行，然后询问面试官是否可以用预处理后的这两个vector非零元素的index和value作为输入，面试官同意后快速写完O(M*N)的代码，M和N分别是两个vector的长度。
－ 面试官说这两个输入如果是根据下标排序好的话应该怎么办， 我说可以遍历长度较短的那一个，然后用二分搜索的方法在另一个vector中找index相同的元素，相乘加入到结果中，这样的话复杂度就是O(M*logN)。这时，
－ 面试官又问是否可以同时利用两个输入都是排序好这一个特性， 我在这个地方有点卡住，但是在白板上写出一个test case，试着用可视化的方法帮助我来进行思考，同时面试官给了一些提醒，最后写出了O(M + N)的双指针方法，成功结束最后一轮面试。
include
include
include
include
include
using namespace std;
class Solution {
public:
int sparseDotProduct(vector
int sparseDotProduct2(vector<int>& num1, vector<int>& num2) {
if (num1.size() != num2.size() || num1.empty() || num2.empty()) {
return 0;
}
vector<pair<int, int>> nums1 = helper(num1);
vector<pair<int, int>> nums2 = helper(num2);
int res = 0;
int i = 0, j = 0;
int m = nums1.size();
int n = nums2.size();
while (i < m && j < n) {
int index1 = nums1[i].first;
int index2 = nums2[j].first;
if (index1 == index2) {
res += (nums1[i++].second)*(nums2[j++].second);
} else if (index1 < index2) {
i++;
} else if (index1 > index2) {
j++;
}
}
return res;
}
private:
int searchValueByIndex(vector<pair<int, int>>& nums, int index) {
int start = 0;
int end = nums.size()-1;
while (start + 1 < end) {
int mid = start + (end-start)/2;
if (nums[mid].first < index) {
start = mid;
} else if (nums[mid].first > index) {
end = mid;
} else {
return nums[mid].second;
}
}
if (nums[start].first == index) {
return nums[start].second;
}
if (nums[end].first == index) {
return nums[end].second;
}
return 0;
}
vector<pair<int, int>> helper(vector<int>& nums) {
vector<pair<int, int>> res;
for (int i = 0; i < nums.size(); i++) {
if (nums[i] != 0) {
res.push_back(make_pair(i, nums[i]));
}
}
return res;
}
};
int main(int argc, const char * argv[]) {
// insert code here...
Solution s;
vector
4 k closest to giving point
facebook 2016-2-20 facebook 2016-2-12 heap: O(nlogk) 查询O(k) quick sort: O(2n) worst case是O(n^2) http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=204200 如果用quickselect算法先找出离原点距离第k近的点和距离，然后再把原数组扫一遍和这个距离比较，如果小于该距离则放入结果数组，等于该距离则放入另一个数组最后从里面选出一些补满k个，这样的空间复杂度和时间复杂度都是O(n)。不知道这种解法有没有什么问题？
如果找kth point， quick sort 好。 K closest points to a given point (x, y). N is in millions and K is few hundreds. max Heap -> O(nlogk)
struct Point { double x; double y; Point(double i, double j): x(i), y(j){} bool operator < (const Point &p) { return xx + yy < p.xp.x + p.yp.y; } };
class Solution {
vector
//得到res
while (!pq.empty()) {
res.push_back(pq.top());
pq.pop();
}
return res;
} quick sort O(kn)
include // std::cout
include // std::priority_queue
include
using namespace std; class Point { public: int x, y; Point(int a, int b) : x(a), y(b) {} }; bool operator<=(const Point& p, const Point& q) { return ((p.x p.x + p.y p.y) <= (q.x q.x + q.y q.y)); } bool operator>=(const Point& p, const Point& q) { return ((p.x p.x + p.y p.y) >= (q.x q.x + q.y q.y)); }
//1. quick sort find kth point /O(n)
//2. traverse points array again, find all point less than kth point O(n)
5 find peak
http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=156077 不用binary啊，充分利用相邻只相差1 设结果的的index是x，value是y，nums的长度是len，解二元一次方程 x - 0 = y - nums[0] x - (len - 1) = - (y - nums[len - 1]) (这种情况默认的是peak 反正之前判断一下是peak还是valey就行 然后有不同的方程） 这样就是O(1)
6 Stock
stock with transation fee http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=137447&page=1#pid2358423 我觉得对于stock的follow-up，可以先找出多次transaction的区间，买的价钱用start表示，卖用end，like intervals，然后进行合并。因为每次买卖都有fee，所以要选择性合并，合并的依据是 intervals[i].end <= intervals[i+1].end. && 0 < interval[i].end-interval[i].start <= fee, 合并。 stock2 可以随便交易很多次，可以同时买很多股票，但是一旦卖就要把手里的股票全部卖了，问怎样最大化收益。比如[1, 2,3], 前2天都买，第三天全部卖，收益就是(3-1)+(3-2). 从右向左便利
int max = 0;
int rst = 0;
for (int i = stock.length-1; i >= 0; i--) {
if (max > stock[i]) {
rst += max - stock[i];
// i 天买入 max卖出
}else {
max = stock[i];
//再i天卖出全部股票
}
}
return rst;
Best Time to Buy and Sell Stock followup: 返回买入和卖出时间的Index
stockII 记录买卖时间
class Solution {
public:
int maxProfit(vector
7 就是lc next permutation
的反着来的previous permutation，做法一样，中间出了两个小bug，一个我子函数传参数有笔误（应该传index这个变量，我写成 了i），还有一个循环我忘记递减了，我自己发现的 Cache Line可以简单的理解为CPU Cache中的最小缓存单位。目前主流的CPU Cache的Cache Line大小都是64Bytes。
next permutation
- find first pair from end, s[i] < s[i+1]
- swap first element s[j] > s[i] from end, swap(s[i], s[j])
- reverse range s[i+1] to s[len-1] 3+, if from end to start is decreasing order, reverse range(s[0), s[len-1])
previous permutation
- Find largest index i such that str[i – 1] > str[i].
- Find largest index j such that j >= i and str[j] < str[i - 1].
- Swap str[j] and str[i - 1].
- Reverse the sub-array starting at str[i].
8 数字转单词
https://leetcode.com/problems/integer-to-english-words/
9 binary number 1's count
求1的个数
int BitCount(unsigned int n) { unsigned int c =0 ; // 计数器 while (n >0) { if((n &1) ==1) // 当前位是1 ++c ; // 计数器加1 n >>=1 ; // 移位 } return c ; }
int BitCount2(unsigned int n) { unsigned int c =0 ; while (n) { n &= (n -1) ; // 清除最低位的1 } return c ; }
int BitCount7(unsigned int n) { unsigned int table[256] = { 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8, };
return table[n &0xff] +
table[(n >>8) &0xff] +
table[(n >>16) &0xff] +
table[(n >>24) &0xff] ;
}
10 Task Time
Facebook 2016-06-17 Facebook 2016-04-28 Facebook 2015-04-03 字符串版
another follow up follow up 2 //用一个hashmap保存每个task可以开始执行的最早时间。
include
include
include
include
using namespace std;
class Solution {
public:
string cooldown(string s, int k) {
unordered_map
int main(void) { Solution s; cout<<s.cooldown("1121", 3)<<endl; }
follow up: 正确的做法应该是统计每个task的frequency，然后每次选frequency最高并且可以执行的task执行。
用multiset>提到unordered_map
一组一组来，每组k个。更新set
class Solution {
public:
string rearrangeString(string s, int k) {
string res;
if (s.empty() || k == 0) {
return s;
}
unordered_map
int n = (int)s.size();
while (n > 0) {
vector<pair<int, char>> tmp;
for (int i = 0; i <= k; i++) {
if (set.empty()) {
res += "_";
} else {
auto cur = *(set.rbegin());
int freq = cur.first;
int c = cur.second;
set.erase(set.find(cur));
res.push_back(cur.second);
if (--n == 0) {
return res;
}
if (--freq != 0) {
tmp.push_back(make_pair(freq, c));
}
}
}
for (auto t : tmp) {
set.insert(t);
}
}
return res;
}
};
let 275 index ii
Just binary search, each time check citations[mid] case 1: citations[mid] == len-mid, then it means there are citations[mid] papers that have at least citations[mid] citations. case 2: citations[mid] > len-mid, then it means there are citations[mid] papers that have moret than citations[mid] citations, so we should continue searching in the left half case 3: citations[mid] < len-mid, we should continue searching in the right side After iteration, it is guaranteed that right+1 is the one we need to find (i.e. len-(right+1) papars have at least len-(righ+1) citations)
class Solution {
public:
int hIndex(vector
let 275
class Solution { public: static string numberToWords(int n) { if(n == 0) return "Zero"; else return int_string(n).substr(1); } private: static const char const below_20[]; static const char const below_100[]; static string int_string(int n) { if(n >= 1000000000) return int_string(n / 1000000000) + " Billion" + int_string(n - 1000000000 (n / 1000000000)); else if(n >= 1000000) return int_string(n / 1000000) + " Million" + int_string(n - 1000000 (n / 1000000)); else if(n >= 1000) return int_string(n / 1000) + " Thousand" + int_string(n - 1000 (n / 1000)); else if(n >= 100) return int_string(n / 100) + " Hundred" + int_string(n - 100 (n / 100)); else if(n >= 20) return string(" ") + below_100[n / 10 - 2] + int_string(n - 10 * (n / 10)); else if(n >= 1) return string(" ") + below_20[n - 1]; else return ""; } } };
const char const Solution::below_20[] = {"One", "Two", "Three", "Four","Five","Six","Seven","Eight","Nine","Ten", "Eleven","Twelve","Thirteen","Fourteen","Fifteen","Sixteen","Seventeen","Eighteen","Nineteen"}; const char const Solution::below_100[] = {"Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};