一亩三分地 面经 数据分析 (1)

前言：
最近爬了一亩三分地面经版所有的帖子，截止至 1/20/2018。 一共大约2W4个页面。

正文：
待续。

High Frequent

这种东西要做梦都梦到 min/max heap
bucket sort
topological sort
binary tree preorder/inorder/postorder traversal
binary tree level traversal BFS
binary tree vertical order traversal
combination/permutation

最终我觉得像下面的，这种题要达到闭眼秒杀的程度One shot
word search 1
word search 2
word break 1
word break 2
word ladder 1
word ladder 2
LIS
LRU
sort color
insert & delete in O1
rob house 1
rob house 2
rob house 3
2 sum
3 sum
4 sum

Truffle

Development

How to bootstrap a contract:
truffle init
truffle create contract NewContract
truffle create migration NewContract

truffle create test NewContract

truffle migrate --reset

Console:

How to get into console:

truffle console

How to call a contract's function in Truffle Terminal:
FlipCoin.deployed().then(function(instance){app = instance})
app.adopt(23) . //call method on contract class

How to check balance of an address in Truffle Terminal:
web3.eth.getBalance("0x627306090abaB3A6e1400e9345bC60c78a8BEf57")
web3.eth contains lots of methods

[Leetcode]Moving Average from Data Stream

LC link
Maintain a deque to
1. line 23, convert to float and make sure divisor is not zero
1. line 1 import collections
2. line 5 declare deque with maxlen by collections.deque(maxlen = size)

[Leetcode] Meeting Rooms I and II

LC link1
Sort based on start time and check conflicts
1. Line 7,8 old drill, valid inputs
2. Line 10, sort element in place based on object's attribute  python programming sugar
3. Line 12, how to handle the case where len(intervals) == 1
                   Use for i in xrange( 1, len(intervals)) It will ignore the case where len(intervals) == 1

LC link
Create sorted start/end list, use rooms/end_pointer trick to iterate through

1. Line 20, should be smaller, cuz start time == end time, it means a room is released
2. Line 20, don't forget to use end_pointer
3. Line 22, 23,   it means a new room is release, don't need a new room, but move end_pointer

[Leetcode]Binary Tree Level Order Traversal (AKA BFS)

LC link
Push root to queue then traverse level by level
1. Line 7, 8, old drill, validate input and ask what they want if input is not valid
2. Line 13,   use for loop to simulate level by level visiting
3. line 12, 15, 20,  know what they want for output,
4. Line 14,  queue, FIFO pop(0)   stack FILO pop()

[Leetcode]Number of Islands

LC link
Summary:
Ignore boundaries, sink method handles all logic and sink up/down left/right
1. Line 14, old drill, when I wrote line 14, i and j could not be negative, but in line 17,18, we access i - 1, j - 1, we need to check whether i and j are negative. Always check validness of objects or index.
 Test case ["1011011"]
2. Line 17, 18 Whenever create or change method signature, check signatures!
3.

# 000
# 010
# 000 is a valid island

4.  0 == '0' returns False

5. Line 14, 17, 18 our approach ignores values on edges. So we need to sink up, down, left ,right whenever we find a island
["111","010","111"]  for example, case like that

6. let sink method takes care of input check and most of logics

[Leetcode]Add Two Numbers

LC Link 1. line 11, use while loop controls on 11, l2 and carry
2. line 13,16, take care of l1 and l2 separately.  Cuz you always want to check Nullness before you access its attributes.
3. line 21, use carry, curr_val = divmod(raw_num, 10) to speed up process
4. line 9,22, be clear on the requirement. output as problems wanted

[Leetcode]Excel Sheet Column Number

LC Link 1. Line 11, make sure they are all upper case cuz that's our assumption that we will process upper case
2. Line 12, whenever deal with problem to convert bla bla to another number. just use same template
    res = res * (10 or 8 or 26 or whatever) + value on current digit value
    You don't need to consider most right digit value cuz res equals zero at very beginning

Python programming sugar

1. how to sort list of objects, based on attribute of the objects
2. compare Unicode difference between B and A ord('B') - ord('A')
3. carry, curr = divmod(val1 + val2 + carry, 10)

What happens when you press Google.com in your browser?

1. Parse The line gets parsed and the protocol, server, port, query gets retrieved 2. Resolve to IP Address Browser connects to server at the default/specified port 2.1. If it is in local DNS cache, fetch it 2.2. Else, recursively check IPS's DNS servers 3. Send Request Browser sends a GET request followed a crlf sequence then by the headers all followed by respective crlf-s 3.1 If this server has already cached cookies, the browser sends them as cookie headers 3.2 If the browser supports compression it tells the server what compression is using (via headers) as well as what compression it could accept in return 3.3 Sends a content-length header set to value "0" 3.4. Sends a header instructing the server how to denote the end of its transmission stream. Connection: Close would be the most common 3.5 Sends a crlf sequence to mark the end of the headers (after eventual other headers are sent) 4. Handle Response 4.1. Parses the response code / status 4.2. If this response starts with 2 it caches cookies, decompresses (if header is mentioning compression) parses and displays the html content of message body (executing eventual scripts hooked to different DOM elements/events) 4.3 If the response code starts with 3 redirects t the server mentioned in the response (goto 11) 4.4 If the response code starts with 4 or 5 parses the response and displays it to the user

[Leetcode]Balanced Binary Tree

0. Line 8, 10, Use root as method signature, cuz if you use left and right, it would be tricky to implement line 11,12
1. Line 22, handle normal case by making sure left and right values are inbound and then return the bigger height
2. Line 23, cuz the current root also has height of 1, so should return 1

Tree Related knowledge

1. What is a balanced binary tree?
Absolution difference between left sub-tree and right sub-tree is bigger than 1
 

A good video can be found here  https://www.youtube.com/watch?v=TWDigbwxuB4

2. What is BFS:

scan level by level

3. What is DFS:

go down first then go back.

we have preorder, inorder and postorder. pre/in/post describe where is the root node.

      1

  2     3

4  5  6   7

preorder:    1, 2, 4, 5, 3, 6, 7

inorder:       4, 2, 5, 1, 6, 3, 7

postorder:   4, 5, 2, 6, 7, 3, 1

[Leetcode] How to practice Leetcode

BUG FREE / CODING STYLE

Blog them.
Whenever you submit a solution, document what is the mistake and try to remember common mistakes
When you do a new problem, see if you make same mistake again. Document old and new mistakes until bug free
Summarize your approach with one sentence

Always check Nullness/Length/IndexOutOfBounds

Use memory curve

Practice by tags

Use lintCode to test coding style

[Leetcode] Construct Binary Tree from Preorder and Inorder Traversal / Construct Binary Tree from Inorder and Postorder Traversal

https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal 

1. Line 9, definitely check null of inputs
2. Line 12, pop() pops last element, pop(0) pops from beginning
3. Line 12, you want to create a root. cuz preorder and inorder only contains int
4. Line 15,16, build left subtree then right subtree. For constructing b-tree from postorder and inorder, build right sub tree first then left subtree
1. line 8, old drill, check inputs
2. line 11, we are using postorder to build b-tree. root node locates at the end of postorder
3. line 14/15, build right sub tree first, then left sub tree.

Scala 101

Why Scala:

    Scala is good for process distributed data over cluster.

    In the very end, compile all code to bytecode and run. You can use all Java library

    Spark is built on Scala

       

What's the difference of JVM on Scala or Java

Best Practice

parameterized

Don't check too much

It would be better to separate the concerns of Access Control from the concerns of Task, Action or Command.
I stopped using this pattern a long time ago, for a very simple reason; maintenance cost. Several times I found that I had some function say frobnicate(something, forwards_flag) which was called many times in my code, and needed to locate all the places in the code where the value false was passed as the value of forwards_flag. You can't easily search for those, so this becomes a maintenance headache. And if you need to make a bugfix at each of those sites, you may have an unfortunate problem if you miss one.

System Design

1. How to design Shazam phone app

2. How to speed a bank transaction order processing system. All orders need to be processed sequentially.
    a. Use lazy Load for DB
    b. Java Profiler to analyze
    c. Try to parallel orders which can be paralleled
    d. prepare/load order to different machine to cut waiting time

SQL/DB/Nosql question

1. What is NoSQL
    A DB which has key-value paired and document based.
    Doesn't use string based queries to fetch data
    Cassandra is a distributed NoSQL DB

2. Difference between NoSQL and RDMBS
    NoSQL is unstructured, high availability, cannot be queried by  SQL, K-V parir, document base
    RDMBS is structured, low availability, can use SQL QUERY,  Data/Relational stored in dif tables

Java what's new in Java 1.8?

1. forEach() method in Iterable interface
default and static methods in Interfaces
Functional Interfaces and Lambda Expressions
Java Stream API for Bulk Data Operations on Collections
Java Time API
Collection API improvements
Concurrency API improvements
Java IO improvements

Hadoop ecosystem questions

Pig
UDF
Map Reduce
When you do join in Hive, what's going on behind the scene.
Redis

1. What is Kafka:
    Scala based distributed messaging system .

2. What is Cassandra:
    A distributed NOSQL database(Key-Value Document-based), it doesn't support MapReduce

3. What is Redis:
    In memory data structure store. Let's say you have 400TB data and you want to access them very fast
    in a local variable. you want to use Redis.

news source

https://www.bloomberg.com/markets
http://www.cnbc.com/investing/
http://www.reuters.com/news/archive/marketsNews?view=page&page=1&pageSize=100
http://www.marketwatch.com/
https://www.google.com/finance/market_news?ei=QDonWfmzNc6amAHqpLGQDQ

Java Spring/Hibernate Questions

1.  Pros and Cons about Sping
    Cons:
         Huge, I wouldn't put 3000 jars in my hobby project
         Slower than other DI, like juice
         getting more and more complex in annotation and XML
     Pros:
         decoupling
         readable

2. What are the common types of Dependency Injection:
    Constructor-based:
        Use for mandatory injection

    Setter-based:
        invoking a no-argument constructor or no-argument static factory method to instantiate your bean.
        Use for optional injection
    1. Inject differently
    2. Constructor guarantees injection while setter injection can be failed
    3. Setter injection can detect circular dependency by throwing ObjectCurrentlyInCreationException
 

http://javarevisited.blogspot.com/2012/11/difference-between-setter-injection-vs-constructor-injection-spring-framework.html

3. What is the scope of Java Spring bean?
singleton: one object/ container     prototype/request: one object/ bean is requested or HTTP requested

Java GC/Memory Model Questions

GC
1. What are the six reachability states in Java?
    Strongly reachable objects
    Softly reachable objects
    Weakly reachable objects
    (Weak Refer: a reference that doesn't protect the referenced object from collection)
    Resurrect-able reachable objects
    Phantomly reachable objects
    Unreachable reachable objects

    https://stackoverflow.com/questions/299659/what-is-the-difference-between-a-soft-reference-and-a-weak-reference-in-java

2. How does GC work and when do JVM perform GC


What is Eden: newly created objects will be putted here
What is survivor: objects which survived Eden GC
Why there are two survivors: Only put things to old generation if objects survives many GC

What are the major GCs:
Minor GC:  Clean eden, move Eden to survivors

Full GC:     Clean entire heap space

When to collet:
Minor  When don't have enough space to allocate new space in Eden
Major:  New candidate for Old generation is bigger than free space in Old generation

What to collect:
    Go through GC roots. Any unreachable objects will be marked as OK to collect

What happened:
    stop some threads and finalize some objects

Java Multithread Questions

1. What is the difference between Callable and Runnable?
    Runnable is Old and has been there for a while.
    People knows how to run at the beginning. Once she runs away, you don't get back from her.
    Callable can return a result and cannot throw a checked exception

2. How to detect deadlock in Java?
    Use ThreadMXBean class. It has a method called findDeadlockedThreads.

3. Difference between static variable and volatile variable in Multithread java
    Declaring a static variable in Java, means that there will be only one copy, no matter how many objects of the class are created. However, threads may have locally cached values of it.
    When a variable is volatile and not static, there will be one variable for each Object.

Java OOP/Core Java Questions

1. What is JVM and is it platform independent:
    JVM is Java Virtual Machine and is responsible for converting byte code into machine readable code.

2. Difference between JVM and JDK and JRE:
    JVM is used to execute bytecode            JDK is for dev          
    JRE  = JVM  +  java binary libraries
    If u wanna run Java program, u need JR

3. Which class is the superclass of all classes?
    java.lang.Object is the root class for all the java classes and we don’t need to extend it.

3.5 Difference between Extends / Implements
    Implements is for implementing an interface (can implement multiple interfaces)
    Extends is for extending a class(can only extends one )
    Interface method generally doesn't have implementation.

4.Why Java doesn’t support multiple inheritance(extends a class )?
    Because of Diamond Problem
    Diamond Problem:
     
    Let's say we have a method in A.    B and C both override that method.   Should D take B's implementation or C's implementation

 5. What is path and classpath:
    path is sys environment
    classpath is used for Java to locate class files

6. What is overload and overriding:
    Overload means same method signature with different parameter
    Override, one in parent class and another in child class. Use to override method in parent class

7. Can we overload main method:
    yes, we can have multiple method named with main, but only public static void main(String args[])
    will be treated as main method

8. Can we have more than one public class in one java source file
    no, only one public Java class is allowed in one java file

9. What is final/finally/finalize keyword:
    For class: to make sure no other class can extend it, String class is final and can't be extended
    For method: child class cannot override parent's method
    For variable: make sure variable can only be assigned once, however, the state of the variable can
    be changed. For example, we can assign a final variable to an object only once, but the object  
    variable can be changed later on
     Java interface variables are by default final and static
 
    Finally block: put the code which will always be executed even if any exception thrown by the try
                            catch block.
    Finalize: Tell JVM it is good to do GC

10. What is static keyword:
    For method: A static method can only access that class' static variable and invoke
    For variable: can be used within class level to make it global. all objects will share the same variable

10.5 What is super keyword:
    Access super class method you have overridden in child class
    Invoke superclass's consturctor

11. What is Interface:
    Provide a way to achieve abstraction in java and used to define the contract for the subclasses to implement. Interface method doesn't have implementation

12. What is an abstract class:
    Abstract classes have some default method implementations for subclasses.
    An abstract class can have abstract method(no body) and real method(with body)
    Abstract class cannot be instantiated

13. Abstract class VS Interface:
    Abstract class can have method implementation while Interfaces can't
    A class can implements >1 interfaces while can only extends one abstract class
    Abstract uses abstract to define abstract class while interface uses interface to define interface

14. Can Interface implement/extend another interface:
    Interface can implement >2 interfaces

15. Four elements of OOP
    EA has a good IP

    Encapsulation:    hide data and implementation from outside by using setter/getter
    Abstraction:        It is a concept. One class should not know detail of another to use it.

    Inheritance:         Extends/Implement. Classes can be derived from other classes.
    Polymorphism:   Overload/Override. One name can have multiple implementation

16. What is default constructor?
    Compiler automatically creates default no-args constructor for classes. If there are other constructors defined, the compiler won't create default constructor.

17. Can we have try (possible with finally)without catch block:
    Yes.

18 What is GC?
   Look through heap memory and delete objects not in use.

19 What is mock object?
    Mocking or mock objects is a unit testing strategy.  Replace code chunk with dummy codes. For example, if you want to test a method in class A. Class A depends on class B/C/D, you can create some dummy objects b,c,d to testing class A instead of implementing class B/C/D

20. How to create immutable objects?

1. Don’t provide any methods that modify the object’s state (known as mutators).
2. Ensure that the class can’t be extended.
3. Make all fields final.
4. Make all fields private. This prevents clients from obtaining access to mutable objects referred to by fields and modifying these objects directly.
5. Make defensive copies. Ensure exclusive access to any mutable components.

21. How sets avoid duplicates internally ?

It roughly works like this

if (!collection.contains(element))

    collection.add(element);

And the contains method, would use equals/hashcode.

In TreeSet, the elements are stored in a Red-Black Tree, 

In HashSet, uses a HashMap to traverse buckets and use equals() to check equality

22. What is TreeMap

The TreeMap class implements the Map interface by using a tree. A TreeMap provides an efficient means of storing key/value pairs in sorted order, and allows rapid retrieval.

A tree map guarantees that its elements will be sorted in an ascending key order

Dairy

今天Lockheed Martin来电话了,说因为身份问题，把offer要收回去。HR真的太不专业了,浪费了我和公司的时间。还好我提前问了，要不然我真的drop了two week然后他再和我说这个，我就傻眼了。看来F35花400多亿美金还造不出来。是有原因的。 今天早上电面了彭博。题目本身不难但也不简单。考了两个题目。 1. Sliding Windows 变种 2. LRU 拿到题目有点紧张是真的。

[Leetcode]Best Time to Buy and Sell Stock 1

https://leetcode.com/problems/best-time-to-buy-and-sell-stock/#/description
The idea here is keep a currMin and iterate through whole prices list. Through each iteration, we update currMin and currMaxProfit

Flatten a multi-level linked list Depth

http://www.geeksforgeeks.org/flatten-a-multi-level-linked-list-set-2-depth-wise/

Fibonacci Recursion and Iterative

First 9 Fibonacci number 

1 1 2 3 5 8 13 21 34

[Leetcode]Largest Number

https://leetcode.com/problems/largest-number/#/description

Given a list of non negative integers, arrange them such that they form the largest number.
For example, given [3, 30, 34, 5, 9], the largest formed number is 9534330.

1. A naive approach would be put 9 in front of 5, 4, 3. but that would be way too complex for the case when we have 5656 and 56. The right approach is to compare numbers like that. Let’s say we have [3, 34]. We combine them to 343 and 334. 343 is larger than 334 so our list will be sorted to [34, 3]
2. define your own comparator, 1 if a > b, -1 if a < b 3. Syntax for using customized comparator in sorted() sorted(list, cmp = self.methodName)

[Leetcode]Swap Nodes in Pairs

https://leetcode.com/problems/largest-number/

  1. in Line 17 , you need to have a clear mind what is the new value for curr. curr = one will do the work but might be confusing. curr = curr.next.next is sound and safe

AUV Study

Found Cambridge is doing a project named blackghost. That image might be useful.

So that AUV designed in a shape of torpedo and uses four vector thrusters to move AUV.
The hull was separated in five modular sections.
It is mainly controlled by a 100W motor and rear  propeller to drive AUV to move forwardly.
There are four internal vector thruster for maneuvering.  They are arranged in two sets with one vertical and one horizontal thruster at the front and at end.

That AUV gives me a brief summary of how AUV works

Navigation: Accelerometer(a), Gyros(comparable XYZ) and pressure sensros(Z axis)
Propulsion: main propeller with two sets of horizontal/vertical vector thruster to achieve

Brushless Motor

Brushless DC electric motor (BLDC motors, BL motors) also known as electronically commutated motors(ECMs, EC motors) are synchronous motors that are powered by a DC electric source via an integratedinverter/switching power supply, which produces an AC electric signal to drive the motor.

So we need use separate microchip to drive our motor. Microchip,TI have bunch good 

lynx

I am playing with Hadoop these days and setting x2go or NoMachine server take forever. So I found that text-based web browser and attached some shortcuts

enter jump to current link
left   back to last page
Ctrl+A    go to front of current website
Ctrl+E  got to bottom of current website
Ctrl+W refresh current page
g       go to the URL u typed in


Hope I can optimize my Hadoop Server ASAP



12.22.2014