goood solutions for tree traversal

TracyJanuary 26, 2011 at 7:20 pm

@1337c0d3r:
I'm quite sure that my code of using one stack for post-order traversal works. You can use the same example above to go through it. I made iterative in-order, pre-order and post-order traversal as similar as possible:

void postorderNoR(const Node *root)
{
stack s;
const Node *itr = root;

while (itr || !s.empty()) {
if (!itr) {
while (!s.empty() &&
itr == s.top()->right) {
itr = s.top();
s.pop();
printf("%d ",itr->value);
}
itr = s.empty() ? NULL : s.top()->right;
}
else
{
s.push(itr);
itr = itr->left;
}
}
}

// *********************

void inorderNoR(const Node *root)
{
stack s;
const Node *itr = root;

while (itr || !s.empty()){
if (!itr){
itr = s.top();
s.pop();
printf("%d ",itr->value);
itr = itr->right;
}
else{
s.push(itr);
itr = itr->left;
}
}
}

// *********************

void preorderNoR(const Node *root)
{
stack s;
const Node *itr = root;

while (itr || !s.empty()){
if (!itr){
itr = s.top();
s.pop();
itr = itr->right;
}
else{
printf("%d ",itr->value);
s.push(itr);
itr = itr->left;
}
}
}

0

Pay Attention!!

Graph

directed graph or undirected graph?
The methods of graph traversal?
http://articles.leetcode.com/2012/05/clone-graph-part-i.html

Number
always consider if the algorithm will over flow!!!!!!
if negative or zero number will impact the final result!!!!!!
http://articles.leetcode.com/2012/01/palindrome-number.html

String
'a' to 'z'? Digits? Upper case letter? Does it contain ASCII characters only? Or even unicode character sets?
http://articles.leetcode.com/2011/05/longest-substring-without-repeating-characters.html

Tree
duplications? 
http://articles.leetcode.com/2011/04/construct-binary-tree-from-inorder-and-preorder-postorder-traversal.html

Longest Palindromic Substring

Longest Palindromic Substring

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

--------------------- thinking -----------------------------

https://leetcode.com/discuss/32204/simple-c-solution-8ms-13-lines
http://articles.leetcode.com/2011/11/longest-palindromic-substring-part-i.html
http://articles.leetcode.com/2011/11/longest-palindromic-substring-part-ii.html
http://www.felix021.com/blog/read.php?2040

word ladder

Word Ladder

 Given two words (beginWord and endWord), and a dictionary, find the length of shortest transformation sequence from beginWord to endWord, such that:

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

For example,

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

As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

Note:

• Return 0 if there is no such transformation sequence.
• All words have the same length.
• All words contain only lowercase alphabetic characters.

--------------- thinking -----------------------
A lot of optimizations are discussed in this post!!!! And why my codes is memory limit exceed!!!
http://www.cnblogs.com/linyx/p/3706688.html

Detect Cycle in a Directed Graph

Detect Cycle in a Directed Graph

Given a directed graph, check whether the graph contains a cycle or not. Your function should return true if the given graph contains at least one cycle, else return false. For example, the following graph contains three cycles 0->2->0, 0->1->2->0 and 3->3, so your function must return true.
Solution
Depth First Traversal can be used to detect cycle in a Graph. DFS for a connected graph produces a tree. There is a cycle in a graph only if there is a back edge present in the graph. A back edge is an edge that is from a node to itself (selfloop) or one of its ancestor in the tree produced by DFS. In the following graph, there are 3 back edges, marked with cross sign. We can observe that these 3 back edges indicate 3 cycles present in the graph.

For a disconnected graph, we get the DFS forrest as output. To detect cycle, we can check for cycle in individual trees by checking back edges.

----------------------- thinking ----------------------------------

rotate array

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

Uber

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)