Ying's Hunting Journal

Tuesday, April 14, 2015

rotate array

-------------------- thinking ----------------------
https://leetcode.com/discuss/30527/three-way-solve-this-problem-the-first-way-interesting-java

Saturday, April 11, 2015

1，在Uber做工程师体验如何？
Glassdoor上我们写的review非常详细，个人来说非常满意，技术规范前沿，代码多开
会少官僚无，impact大
http://www.glassdoor.com/GD/Reviews/Uber-San-Francisco-Reviews-

2，Bar有多高？
面试难度不同组差别可能较大，现在难进主要还是因为来面的太多。
喜欢招资深的，技术背景匹配的，要求马上能上手

3，待遇如何？
http://h1bdata.info/index.php?em=uber&job=
看2014年6月后数据

股票价值可观，大部分人拿到offer时的价值在四年10万(new grad)到80万(senior)间
现在已经是发RSU而不是option.另外进行过1:10和1:4两次拆股，当前股价32.5刀，所
以和以前offer对比
要注意

4，工作压力？
较大，但并不疯狂。大部分人，大部分时候都能在5天8小时内做完，偶尔加班
压力主要体现在所有project都有deadline
工程师相对于要做的事来说还是较少，我们组是1.5人负责一个service

5，发展前景如何？
简单说，很好。现在400亿估值，近3年还有2-5倍成长空间
团队执行力非常强

想理解业务模式，可以读读这两篇文章,简单说就是低价和更好的服务创造了更大的市
场，并且形成network effects不断强化竞争优势
https://hbr.org/2014/12/making-sense-of-ubers-40-billion-valuation
http://abovethecrowd.com/2014/07/11/how-to-miss-by-a-mile-an-al

至于我为什么选择uber，这篇文章有我的分析方法
http://www.mitbbs.com/article_t0/JobHunting/32722713.html

6，从国内直接招吗？H1b政策？
凡是需要直接办H1B的现在都不招
美国毕业的学生办H1b，不过一般先从OPT开始
问过HR,主要因为需要h1b的话最早要2015年十月才能入职，拿到Offer时和入职时间差
太远，估值可能变化太多；
另外Uber的速度非常快，所以要尽快入职

7，绿卡政策？
没有明文的绿卡政策，无论是第一次申请还是transfer
据我知道拿到offer的时候多半承诺6个月办绿卡。
实际有多快取决于老板，我入职一个月就开始办，进展顺利

8, 福利如何？管三餐吗？
管午餐和晚餐；吃的是catering的，没有自己厨房；晚餐坑爹的是8:15开饭；早餐虽
然没有正式的，不过牛奶,面包,黄油，奶酪,麦片都有

没有401K Match

每月400刀Uber Credits,不过要交税的，用完了还有17%的折扣。用不完作废，不能累
积到下月

各种保险齐全

9，休假政策？
官方假期9天，此外的假期只要manager批准，不限时间

比较好玩的是有个Workation, 自愿参与；在圣诞后自己想点子组队，边度假边
hackthon, 公司补贴1000刀每人

#include <iostream>
#include <string>
using namespace std;

// To execute C++, please define "int main()"
string encode(string input) {
string result;
if (input.size() == 0) {
return result;
}
unsigned int start = 0;
unsigned int next = 0;
int count = 0;
while (next < input.size()) {
if (input[next] == input[start]) {
count++;
} else {
result += string(1, input[start]);
if (count > 1) {
result += string(1, 'z' + count);
count = 1;
}
start = next;
}
next++;
}
result += string(1, input[start]);
if (start + 1 != next) {
result += string(1, 'z' + count);
}
return result;
}
int main() {
for (int i = 0; i < 5; i++) {
cout << "Hello, World\n";
}
string input("adcaadbdde");
string result = encode(input);
cout << result << endl;
return 0;
}

// 9000886209
// 00000000 11 000 11 0 111 00 1
// 8 zeros, 2 ones, 3 zeros, ..

// 0812031200130210
// 01010101010101
// 0//1010101010101

// aaaaabbbbccc11113335
// 5 a, 4 b, 3 c, 4 1, ...

// abc123 -> abc123
// aabbcc112233 -> a2b2c212232
// -> abc123222222

// abaabdddc
// abc123

// a(z+2)b(z+2)c(z+2)

转载！熬过那三厘米！

学会厚积薄发：多少人，没熬过那三厘米！

(2014-08-10 21:24:21)

转载▼

标签：

杂谈

学会厚积薄发：多少人，没熬过那三厘米！

竹子用了4年的时间，

仅仅长了3cm，

在第五年开始，

以每天30cm的速度疯狂的生长，

仅仅用了六周的时间就长到了15米。

其实，在前面的四年，

竹子将根在土壤里延伸了数百平米。

做人做事亦是如此，

不要担心你此时此刻的付出得不到回报，

因为这些付出都是为了扎根。

人生需要储备！多少人，没熬过那三厘米！

国平点评：什么叫厚积薄发，这就是，我们在资本市场，很多时候也是如此，平时的储备和提升，就为了未来行情展开时的茁壮成长。朋友们，已经悄然来临了……

k Sum

Given n distinct positive integers, integer k (k <= n) and a number target.

Find k numbers where sum is target. Calculate how many solutions there are?

Example

Given [1,2,3,4], k=2, target=5. There are 2 solutions:

[1,4] and [2,3], return 2.

------------------------ thinking -----------------------
there are two situation for each integer, either count it or not in the dp
http://tech-wonderland.net/blog/summary-of-ksum-problems.html
https://richdalgo.wordpress.com/2015/01/31/lintcode-k-sum/
----------------------- codes ----------------------------
class Solution {
public:
/**
* @param A: an integer array.
* @param k: a positive integer (k <= length(A))
* @param target: a integer
* @return an integer
*/
int kSum(vector<int> A, int k, int target) {
// wirte your code here
int dp[A.size()][k+1][target+1];
for (int i = 0; i < A.size(); i++) {
for (int j = 0; j <= k; j++) {
for (int val = 0; val <= target; val++) {
dp[i][j][val] = 0;
}
}
}
for (int i = 0; i < A.size(); i++) {
for (int j = 1; j <= k; j++) {
for (int val = 1; val <= target; val++) {
if (j == 1 && A[i] == val) {
dp[i][1][val] = 1;
} else if (i > 0) {
if (A[i] <= val) {
dp[i][j][val] += dp[i-1][j-1][val-A[i]];
}
dp[i][j][val] += dp[i-1][j][val];
}
}
}
}
return dp[A.size() - 1][k][target];
}
};

Word Ladder II

Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start toend, such that:

Only one letter can be changed at a time
Each intermediate word must exist in the dictionary

Note

All words have the same length.
All words contain only lowercase alphabetic characters.

Example

Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]

Return

  [
    ["hit","hot","dot","dog","cog"],
    ["hit","hot","lot","log","cog"]
  ]

--------------------------- thinking ----------------------------
Since we need to print all pathes, we cannot simply check if a node is visited or not to return
Instead, we need to check if a node is on the same depth of the shorted path.
--------------------------- codes -------------------------------
class Solution {
public:
/**
* @param start, a string
* @param end, a string
* @param dict, a set of string
* @return a list of lists of string
*/
vector<vector<string>> findLadders(string start, string end, unordered_set<string> &dict) {
// write your code here
unordered_map<string, int> visited;
unordered_map<string, vector<string>> parent;
queue<string> que;
que.push(start);
visited[start] = 1;
//BSF
int min_depth = INT_MAX;
while (!que.empty()) {
string cur = que.front();
que.pop();
if (visited[cur] == min_depth) {
break;
} else {
for (int i = 0; i < cur.size(); i++) {
for (char chr = 'a'; chr <= 'z'; chr++) {
if (chr != cur[i]) {
string str(cur);
str[i] = chr;
if (dict.find(str) == dict.end()) {
continue;
}
if (str.compare(end) == 0) {
min_depth = visited[cur] + 1;
}
if (visited.find(str) == visited.end() || visited[str] == visited[cur]+1) {
if (visited.find(str) == visited.end()) {
//dont' push node several times, which will cause duplications
que.push(str);
visited[str] = visited[cur]+1;
}
if (parent.find(str) == parent.end()) {
vector<string> par(1, cur);
parent[str] = par;
} else {
parent[str].push_back(cur);
}
}
}
}
}
}
}
return buildResult(parent, start, end);
}
vector<vector<string>> buildResult(unordered_map<string, vector<string>> &parent, string &start, string &end) {
vector<vector<string>> result;
if (end.compare(start) == 0) {
result.push_back(vector<string>(1, end));
return result;
}
for (int i = 0; i < parent[end].size(); i++) {
vector<vector<string>> tmp_result = buildResult(parent, start, parent[end][i]);
for (int j = 0; j < tmp_result.size(); j++) {
vector<string> ele = tmp_result[j];
ele.push_back(end);
result.push_back(ele);
}
}
return result;
}
};

Friday, April 10, 2015

Print a Binary Tree in Vertical Order

Print a Binary Tree in Vertical Order | Set 1

Given a binary tree, print it vertically. The following example illustrates vertical order traversal.

           1
        /    \
       2      3
      / \    / \
     4   5  6   7
             \   \
              8   9 
               
     
The output of print this tree vertically will be:
4
2
1 5 6
3 8
7
9

-------------------------- thinking --------------------------
http://www.geeksforgeeks.org/print-binary-tree-vertical-order/
------------------------ codes --------------------------

struct my_pair{

    TreeNode *node;

    int       hd;

    my_pair(TreeNode *n, int d): node(n), hd(d){}

};

class Solution {

public:

    vector<vector<int>> printVirtical(TreeNode *root){

        // write your code here

        int start = 0;

        int end = 0;

        findMinMax(root, 0, start, end);

        vector<vector<int>> result(end-start+1, vector<int>());

        queue<my_pair> que;

        if (root == NULL) return result;

        my_pair pair(root, 0);

        que.push(pair);

        while (!que.empty()) {

            my_pair cur = que.front();

            que.pop();

            result[cur.hd - start].push_back(cur.node->val);

            if (cur.node->left) {

                my_pair pair(cur.node->left, cur.hd-1);

                que.push(pair);

            if (cur.node->right) {

                my_pair pair(cur.node->right, cur.hd+1);

                que.push(pair);

        return result;

    void findMinMax(TreeNode *root, int hd, int &start, int &end) {

        if (root->left) {

            if (start > hd - 1) {

                start = hd - 1;

            findMinMax(root->left, hd - 1, start, end);

        if (root->right) {

            if (end < hd + 1) {

                end = hd + 1;

            findMinMax(root->right, hd + 1, start, end);

};

Binary Representation

Given a (decimal - e g 3.72) number that is passed in as a string,return the binary representation that is passed in as a string.If the number can not be represented accurately in binary, print “ERROR”

Example

n = 3.72, return ERROR

n = 3.5, return 11.1

----------------- thinking --------------------------------
http://www.cnblogs.com/EdwardLiu/p/4273813.html
------------------ codes ---------------------------------
class Solution {
public:
/**
*@param n: Given a decimal number that is passed in as a string
*@return: A string
*/
string binaryRepresentation(string n) {
// wirte your code here
//split integer and decimal
size_t npoint = n.find('.');
int integer = 0;
double decimal = 0.0;
if (npoint != string::npos) {
decimal = strtod(n.substr(npoint, n.size()).c_str(), NULL);
integer = atoi(n.substr(0, npoint).c_str());
} else {
integer = atoi(n.c_str());
}
// convert integer part
string intbuf;
if (integer > 0) {
while (integer > 0) {
intbuf.append(integer%2==1?"1":"0");
integer /= 2;
}
reverse(intbuf.begin(), intbuf.end());
} else {
intbuf.append("0");
}
// convert decimal part
string decbuf;
if (decimal > 0.0) {
while (decimal > 0.0) {
if (decbuf.size() > 32) {
return "ERROR";
}
decimal *= 2;
if (decimal >= 1.0) {
decbuf.append("1");
decimal -= 1.0;
} else {
decbuf.append("0");
}
}
}
//combine and return
return decbuf.size() > 0 ? intbuf + "." + decbuf : intbuf;
}
};