code: 一月 2015

2015年1月11日星期日

Longest Substring Without Repeating Characters -- LeetCode

Longest Substring Without Repeating Characters -- LeetCode

维护一个窗口，[walker ,runner]
abcbdef
迭代1： walker =0=a，runner = 0 =a
runner 一直向右走，直到发现重复的字符。
当runner遇到重复的字符，walker走，
比如当runner到b，发现重复了。 walker需要右移到c，
并且set中的a被删除，
abcbdef

迭代2： walker =c， runner = b， set=(b,c)

edit distance

http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/MIT6_006F11_lec21_orig.pdf

nlp video

Multiply Strings

One Easy solution with C++

2015年1月4日星期日

Word Ladder

Word Ladder -- LeetCode

public int ladderLength(String start, String end, HashSet dict) {
    if(start==null || end==null || start.length()==0 || end.length()==0 || start.length()!=end.length())
        return 0;
    LinkedList queue = new LinkedList();
    HashSet visited = new HashSet();
    int level= 1;
    int lastNum = 1; // 当前level还需要check的节点
    int curNum = 0; // next level 需要check的节点
    queue.offer(start);
    visited.add(start);

    while(!queue.isEmpty())
    {
        String cur = queue.poll(); //从queue拿出一个进行visit
        lastNum--;
        for(int i=0;i<cur.length();i++)
        {
            char[] charCur = cur.toCharArray();
            for(char c='a';c<='z';c++)
            {
                charCur[i] = c;
                String temp = new String(charCur);
                if(temp.equals(end))
                    return level+1;
                if(dict.contains(temp) && !visited.contains(temp))
                {
                    curNum++;//新的未visit的节点，
                    queue.offer(temp); // 加到下次check的行列
                    visited.add(temp); //标记为visited
                }
            }
        }
       //当前level已经check完成，进行下一个level
        if(lastNum==0)
        {
            lastNum = curNum;
            curNum = 0;
            level++;
        }
    }
    return 0;
}

2015年1月3日星期六

树的求和

树的题目在LeetCode中还是有比较大的比例的，不过除了基本的递归和非递归的遍历之外，其他大部分题目都是用递归方式来求解特定量，

判断是否存在从根到叶子的路径和跟给定sum相同的


Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.
For example:
Given the below binary tree and sum = 22,              5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1


return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

public boolean hasPathSum(TreeNode root, int sum) {
    if(root == null)
        return false;
    if(root.left == null && root.right==null && root.val==sum)
        return true;
    return hasPathSum(root.left, sum-root.val) || hasPathSum(root.right, sum-root.val);
}

算法的时间复杂度是一次遍历O(n)，空间复杂度是栈的大小O(logn)。


Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.
For example:
Given the below binary tree and sum = 22,              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1


return
[
   [5,4,11,2],
   [5,8,4,5]
]

Sum Root to Leaf Numbers这道题多了两个变化，一个是每一个结点相当于位上的值，而不是本身有权重，不过其实没有太大变化，每一层乘以10加上自己的值就可以了。另一个变化就是要把所有路径累加起来，这个其实就是递归条件要进行调整，Path Sum中是判断左右子树有一个找到满足要求的路径即可，而这里则是把左右子树的结果相加返回作为当前节点的累加结果即可。


Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path 1->2->3 which represents the number 123.

Find the total sum of all root-to-leaf numbers.

For example,
    1
   / \
  2   3




The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.

Return the sum = 12 + 13 = 25.

Binary Tree Maximum Path Sum

Given a binary tree, find the maximum path sum.

The path may start and end at any node in the tree.

For example:
Given the below binary tree,
       1
      / \
     2   3



Return 6.

job-Uber

softeare engine-machine learning

Strong engineering background - it’s an engineering job
Experience around machine learning, pattern recognition, etc.
Skills in statistical analysis, feature engineering
A naturally curious nature and are a driven self-starter – we’ve got a problem to solve and need you to figure out how to solve it
Skills in Python, MySQL, etc.
Experience in any statistics tools or framework, such as R, Matlab, Scikit-learn, etc.
Experience in the fraud space is a plus, but not required. Either way, you should be passionate about tackling the problem and the impact you can have on the company.

Our team is responsible for Uber’s core business logic, which includes maintaining our product configuration in 200+ cities around the world, handling and storing thousands of payment transactions per second, developing intelligent fraud prevention strategies that scale, and ensuring that push and SMS notifications are sent in a timely manner.

backend:

build financial systems

Building highly scalable, robust, and fault-tolerant services that support our unique rate or growth. Redis, Kafka, ElasticSearch - we seriously nerd out on these.

support cities financial operations of 100,000 and 10 million people alike

As a member of our back-end application team, you'll have a direct impact on handling city financials.

You have advanced knowledge of at least one scripting language (e.g. Python or JavaScript) and knowledge of or eagerness to learn: ORACLE, MySQL, PostgreSQL, Redis, Kafka, and ElasticSearch.

Redis是一个开源、支持网络、基于内存、键值对存储数据库
Apache Kafka是由Apache软件基金会开发的一个开源消息系统项目，由Scala写成。Kafka最初是由LinkedIn开发，并于2011年初开源。2012年10月从Apache Incubator毕业。该项目的目标是为处理实时数据提供一个统一、高通量、低等待的平台。
Elasticsearch是一个建立在全文搜索引擎Apache Lucene(TM)基础上的搜索引擎，可以说Lucene是当今最先进，最高效的全功能开源搜索引擎框架。

当然Elasticsearch并不仅仅是Lucene这么简单，它不但包括了全文搜索功能，还可以进行以下工作:

分布式实时文件存储，并将每一个字段都编入索引，使其可以被搜索。
实时分析的分布式搜索引擎。
可以扩展到上百台服务器，处理PB级别的结构化或非结构化数据。

Dispatch 调度，调遣-Node.js,
Experience building large-scale distributed systems
Familiarity with asynchronous event-based programming frameworks (Node.js, Twisted, Go)

Node.js不是JS应用、而是JS运行平台

Node.js采用C++语言编写而成，是一个Javascript的运行环境。为什么采用C++语言呢？据Node.js创始人Ryan Dahl回忆，他最初希望采用Ruby来写Node.js，但是后来发现Ruby虚拟机的性能不能满足他的要求，后来他尝试采用V8引擎，所以选择了C++语言。

作为Web前端最重要的语言之一，Javascript一直是前端工程师的专利。不过，Node.js是一个后端的Javascript运行环境（支持的系统包括*nux、Windows），这意味着你可以编写系统级或者服务器端的Javascript代码，交给Node.js来解释执行

Designing and building API's to support a seamless mobile experience and evolving the systems that match supply and demand to power millions of trips a week - Dispatch is killing it with distributed computing, networking programming, machine learning, and more.

The Realtime Engineering team is looking for a talented Node.js developer to build, scale, and support our mission critical infrastructure. Our small team of engineers is responsible for the most complex systems at Uber with the most stringent uptime requirements.You’ll be expected to write software to solve challenging problems, relentlessly focus on impact, and create an enduring platform. We ship aggressively and constantly push the operational boundaries of what it means to run an always-on worldwide marketplace. You should be comfortable working in a fast-paced, growing, and dynamic environment.·

HERE ARE THE KINDS OF SKILLS WE'RE LOOKING FOR:

Curiosity to explore new ideas and passion to make them happen
Experience building large-scale distributed systems
Familiarity with asynchronous event-based programming frameworks (Node.js, Twisted, Go)
Understanding of key Node.js modules such as Express, Async, etc. is a definite plus
Working knowledge of relational and NoSQL datastores like MySQL, Postgres, Redis, Riak and core infrastructure components like nginx, HAProxy and Varnish.
Practitioner of iterative programming - coding to quickly test the waters, writing smaller, reusable, well-tested modules and following API-based development
Active involvement in the open source community (GitHub, StackOverflow, Google groups)

WHAT YOU'LL BE DOING:

Design and build APIs to support a seamless mobile experience
Evolve the core dispatching infrastructure that matches supply and demand and powers millions of trips a week
Innovate in the areas of distributed computing, network programming, machine learning, and more
Contribute to a realtime platform that is flexible, robust, performant, and scalable
Become an expert of the Node.js ecosystem
Work with various open source projects

Infrastructure
Providing a steady foundation for our worldwide platform. Building things that allow us to build more things better, faster and stronger, using SQL, Hadoop, Postgres, Riak, Node, and Storm.

analytics infrastrucre:

We’re looking for all levels of software engineers to help build Uber's realtime analytics platform and make Uber the smartest billion dollar company in the world. It’s an ambitious mission, are you up to being a part of it?
You will have a strong interest in building distributed systems to analyze all realtime and historical data. You will be moving all of the bits and pieces of a very exciting urban data set across multiple systems and making it available for a hungry customer base that is working hard to make our products better. You will work within a team of solid engineering talent to build the platform itself as well as collaborate with every other team in our organization to build generalized, scalable, accessible and fault tolerant solutions to Uber’s most pressing analytical needs.

TO REALLY GET OUR ATTENTION:

Complete our coding challenge: https://www.dropbox.com/s/r53xv9mu75xm7bj/realtime-coding-challenge.tar.gz?dl=0. Info on the challenge and submission are in the README.

二分查找

Search Insert Position
Search for a Range
Sqrt(x)
Search a 2D Matrix
Search in Rotated Sorted Array
Search in Rotated Sorted Array II
二分查找是面试中出现频率不低的问题，但是很少直接考二分查找，会考一些变体。

Search Insert Position和Search for a Range是考察二分查找的基本用法

Search Insert Position

Search for a Range

Search in Rotated Sorted Array :

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

依靠中间和边缘元素的大小关系，来判断哪一半是不受rotate影响，仍然有序的.
假设数组是A，每次左边缘为l，右边缘为r，还有中间位置是m。在每次迭代中，分三种情况：
（1）如果target==A[m]，那么m就是我们要的结果，直接返回；
（2）如果A[m]<A[r]，说明 从m到r一定是有序的（没有受到rotate的影响），那么我们只需要判断target是不是在m到r之间，如果是则把左边缘移到m+1;
If (A[m]< target<A[r] ) l=m+1;
else r=m-1; // target在left，即把右边缘移到m-1。
（3）如果A[m]>=A[r]，那么说明从l到m一定是有序的，
If A[l] < target<A[m], r = m-1;
else l= m+1;

根据以上方法，每次我们都可以切掉一半的数据，所以算法的时间复杂度是O(logn)，空间复杂度是O(1)。

Search in Rotated Sorted Array II

Follow up for "Search in Rotated Sorted Array":
What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

Write a function to determine if a given target is in the array.

因为重复的出现，如果我们遇到中间和边缘相等的情况，我们就丢失了哪边有序的信息，因为哪边都有可能是有序的结果。假设原数组是{1,2,3,3,3,3,3}，那么旋转之后有可能是{3,3,3,3,3,1,2}，或者{3,1,2,3,3,3,3}，这样的我们判断左边缘和中心的时候都是3，如果我们要寻找1或者2，我们并不知道应该跳向哪一半。

解决的办法只能是对边缘移动一步，直到边缘和中间不在相等或者相遇，这就导致了会有不能切去一半的可能。所以最坏情况（比如全部都是一个元素，或者只有一个元素不同于其他元素，而他就在最后一个）就会出现每次移动一步，总共是n步，算法的时间复杂度变成O(n)。代码如下：

333 3 332

Search a 2D Matrix

m*n matrix

[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]

Given target = 3, return true.

2015年1月2日星期五

Minstack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

push(x) -- Push element x onto stack.
pop() -- Removes the element on top of the stack.
top() -- Get the top element.
getMin() -- Retrieve the minimum element in the stack.

combination

Simplify Path

Given an absolute path for a file (Unix-style), simplify it.

For example,
path = "/home/", => "/home"
path = "/a/./b/../../c/", => "/c"

click to show corner cases.

Corner Cases:

Did you consider the case where path = "/../"?
In this case, you should return "/".
Another corner case is the path might contain multiple slashes '/' together, such as "/home//foo/".
In this case, you should ignore redundant slashes and return "/home/foo".

这道题目是Linux内核中比较常见的一个操作，就是对一个输入的文件路径进行简化。思路比较明确，就是维护一个栈，对于每一个块（以‘/’作为分界）进行分析，如果遇到‘../’则表示要上一层，那么就是进行出栈操作，如果遇到‘./’则是停留当前，直接跳过，其他文件路径则直接进栈即可。最后根据栈中的内容转换成路径即可（这里是把栈转成数组，然后依次添加）。时间上不会超过两次扫描（一次是进栈得到简化路径，一次是出栈获得最后结果），所以时间复杂度是O(n)，空间上是栈的大小，也是O(n)。