Suning R&D Center Phone Interview 10.31

The interviewee is really a nice and friendly person .
First introduced some basic information about the new built research center.
Then came up with three coding questions.
First two were quiet easy could be done in 3 minutes which are just some basic operation on string.
The third one is a medium difficult problem which needs to find out minimum substring which contains all the characters of another string.

It sounds really noisy in the phone and the interviewee explained that the company was celebrating the Halloween.
Pleasure and positive interview.

11.4 contacted to move forward to 2nd round

Facebook On-Campus Interview 10.31

Met up with a very friendly interviewee who looks like even younger then me.

She firstly introduced herself and asked me to do a brief introduction.
Than came up with an coding question. I cannot say what it is but it is a regular one which is a medium difficulty dynamic programming problem in leetcode.

I used the iterative way to solve the problem. Then run some simple test case.
Than she asked me to solve it by recursion. So I did it.
Then she asked about the time and space complexity of my code.

Then coding phase ended. I was surprised because I thought it should be two coding questions. What's wrong with me?

Then I asked some thing about facebook and her work. I asked if you can use facebook during working hours. She said yes and actually she use it all day time and press 'like' very quickly. Thus some friends asked her if she used any script to press like. Ans she said no. She just did it.

The interviewee is really nice and friendly guy and smiling all the time. It was an positive interview and it seems my performance is not to bad. The only thing is she didn't give any hint or pointed any wrong with my code. She just asked me question and saw what I'm writing. Could anyone tell me why it could be like this?


(11.5) been told that I have passed the 1st round and let me choose a slot and move forward to the onsite interview at Seattle or Menlo Park.

Machine Zone Phone Interview 10.30

Cannot believe a phone interview with a hr officer could be so tired.
I have never think of the process of interview could be like this.

HR "Describe virtual memory"
ME "bla bla bla"
HR "Difference between array and linked list"
ME "bla bla bla"
HR "Describe Mutex"
Me "bla bla bla"
......
.....
.....
HR "Difference between thread and process"
Me "bla bla bla"

All the 30 minutes interview is all the same as what looks like above conversation. I know this is a hr interview and just ask some basic knowledge. But why don't you choose some more friendly way instead of this Q&A. We have no communication except he put out the question I give the answer. Looks like to robots are doing the conversation. lol.

At the end of interview my brain almost didn't work any more. Total about 15 to 25 questions were asked. And no response no comments to any of my answer. Only next question was following.

Efficient but unpleasant.

(11.5) received a email told me that I was rejected.  Totally makes no sense at least from my perspective.

Blizzard On-Campus Interview 10.30

For me Blizzard is not a dream company, but a dream.
It has too much intersection with my life my friends my brothers.
I believe when my friends meet up together and talking about the past time, the first thing come into mind must be Blizzard game. For us it is a whole new world paralleled with the real world.

At first I hesitated whether to summit my resume to Blizzard because I knew there is no change to be hired. But Blizzard is too close to us because we both located in Irvine. It would be regret if I didn't do that.

I can't believe I would get an interview chance. But it happened. I don't if anything wrong with their system.

The interview is ..hard to say.
First talking about my proud project. But it seems that the interviewee is not familiar with my database and just listen what I'm saying.
After that talked about a bug I have done.

Than ! GIVEN a brain test.
It was not to hard. ! but I got the wrong answer ! And I came up with the correct one just when the interview is over !!!
WHAT A PITY!!!!
HOW REGRETTABLE IT IS!!!!
OH MY !!!
And this is the only question he asked me. So I think. IT IS OVER............

UPDATED 10.31
Received email one day later. Be rejected.

On-Campus Interview: ESRI 10.30

Meet up with one leader engineer and one manager of ESRI at UCIrvine. The interview took about 40 minutes.

First talking about the database management system project. Asked some really detailed questions.
Then asked about internship experience and NoSQL databases. Asked some really detailed questions.
Ask me to explain what is multicast assuming he is a idiot with no idea of network.

No coding problems no brain test. Just ask some experience questions.
Not a very pleasure interview experience. Although the interviewee is exactly an expert in database and even showed me that he would present a paper in a database conference next month in New York, he is kind of arrogant. Sometime you can feel that he asks you questions is not aiming to access your skills but aiming to show that he is knowledgeable.

The company is quiet cool which deals with the big data in geographic and produce analysis and some cool stuff.

But after all talking with an arrogant expert is better then talking with a friendly idiot.

(11.12 rejected)

Network Basics

1. What happens after you typing an URL into your browser

1. Browser contacts with the DNS server to find out the IP address of URL
2. DNS server return the requested IP address
3. Browser builds up and connects with web server by TCP at port 80
4. Browser send the http request to the server and server return the html code to browser
5. Browser renders the display result of html code
6. Browser terminates the connection when window is closed

2. DNS 

1. Check if the URL has already been cached. If so just return the result (local Resolver)
2. Preferred DNS server will query other DNS server RECURSIVELY / ITERATIVELY

3. TCP & UDP

Transmission Control Protocol is a connection-oriented network protocol

1. Reliable: When you send a message by TCP you will know it will get there. If it or some parts of it lost on the way the server will re-request the lost part.
2. The order is guaranteed by the sequence number
3. HeavyWeighted: all the out of order parts will be re sent

User Datagram Protocol is a connectless network protocol

1. You don't know whether you message is delivered
2. You don't know the order of your sent message
3. Light Weighted: No ordering information, no tracing information. It's faster

TCP Handshake Process

1. Client sends a SYN to server with a segment sequence number
2. Server replies client a SYN-ACK with the client sequence number + 1 and its sequence number
3. Client send ACK to server with server sequence number + 1

Now both client and server receive an acknowledgement of connection. The communication is established.

Reliable Delivery 

For each TCP packet receiver must send acknowledgement to show it is delivered. If the sender doesn't receive the acknowledgement sender will resend the packet until acknowledgement received.

Flow Control (TCP sender's/Receiver's Window)

A TCP window is the number of data that sender can send before it gets the acknowledgement.

Congestion Control

congestion window

4. IPv4 & IPv6

128 bits and 256 bits ip address

5. Basics about common internet protocol suite

Like IGMP, ICMP, HTTP, FTP, BGP, DHCP etc..

https://www.princeton.edu/~achaney/tmve/wiki100k/docs/Internet_Protocol_Suite.html

C++ Qualifiers

Volatile 

Have been told in the last post "C++"

Const

const variable cannot modify the value by the program
const member function cannot modify the data in the class

Static

• variable inside a function: only it is initialized it remains in the memory until the end of program
• In the class: a static class variable or static class method. All the instances share one variable or static. It doesn't require a instance of class to exist. It can be called by class rather than instance.

Public vs Protected vs Private

• public : can be accessed by anyone
• private: can be accessed only by member functions and friends of the class
• protected: can be accessed by member functions and friends of the class and derived classes

Friend

• A non-member function can access the private and protected members of a class if it is defined as a friend of that class
• A class can access the private and protected members of a class if it is defined as a friend of that class

Multithreading C++ pthread POSIX

The difference between Process and Thread?

• A process is an instance of computer program and it has the whole running resource like memory space and it is private. Thus in order to communicate with the shared memory or Inter Process Communication(IPC) is needed.
• One process may have multiple threads which can be treat as a light weighted process. All the threads share the memory space of the process. 
• And each process has it own run time status like registers and run time stack. Thus switch threads is more efficient than switch processes. 
• The communication between threads, the synchronization is the importation part of multithreading. 

How to synchronize multiple threads?

1. Race Condition

Race Condition is that the output of program is dependent on the sequence of uncontrolled events like multiple threads. When the events does not happen as programmer intend the bug generated.

2. How to avoid race condition

Synchronize threads to avoid race condition. 

1. Mutex: mutual exclusive lock. Enforce exclusive access
2. Join: Make a thread wait until another thread terminate 
3. Condition Variable: Make a thread wait until some condition is true
4. Barrier: Make all the threads wait until all the threads called the barrier function
5. Semaphore: used to solve the consumer and producer problem (a variable used to control access to a shared resource by multiple processes)

3. Problem from CrackCode 4th Edition

Suppose we have the following code:class Foo {public:f.A(.....); f.B(.....); f.C(.....); f.A(.....); f.B(.....); f.C(.....);A(.....); /* If A is called, a new thread will be created and * the corresponding function will be executed. */B(.....); /* same as above */C(.....); /* same as above */ }Foo f; f.A(.....); f.B(.....); f.C(.....);i) Can you design a mechanism to make sure that B is executed after A, and C is ex- ecuted after B?iii) Suppose we have the following code to use class Foo. We do not know how the threads will be scheduled in the OS.Foo f;Can you design a mechanism to make sure that all the methods will be executed in sequence? 

Answer Cool

   Semaphore s_a(0); 

   Semaphore s_b(0);
   Semaphore s_c(1);
   A{
      s_c.acquire(1);
      run_some_thing;
      s_a.release(1);
    }

   B{
      s_a.acquire(1);
      run_some_thing;
      s_b.release(1);
    }
    
   C{
      s_b.acquire(1);
      run_some_thing;
      s_c.release(1);
    }

You are given a class with synchronized method A, and a normal method C. If you have two threads in one instance of a program, can they call A at the same time? Can they call A and C at the same time? 

Answer
 1. If a method is synchronized method then two instance of a program cannot be called at same time because they are mutual exclusive
2. Yes.

4.Deadlock

Because of mutex deadlock could be happened.

A deadlock is a situation that two or more actions are each waiting for other to finish, and thus neither ever does.

• Mutual exclusive 
• No preemption
• Circular wait

5. Thread Safe

Thread safe means the program can be used by multiple threads at the same time and without causing any problem.

[Leetcode Solution] Divide Two Integers

[Leetcode Solution] Sudoku Solver

On Campus Interview: Veeva System 10.24

Applied on the Career Fair and scheduled an On-Campus Interview yesterday.

I was told it is a Java interview. So I tried to warm up Java by touching some website like 'Most Common 20 Java Questions you need to know'. However it is only one morning about 2 hours for me. After figuring out what's the difference between string, stringbuffer and stringbuilder I gave up.

Because last day was Career Fair I was really tired. I got insomnia last night to 3am and got up at 8am. I was really tired during interview and responded slowly.

First question must be a warm up question asked that the difference between abstract class and interface. I thought for ten seconds and then said 'I don't know'. Of course the interviewee was shocked because that's was really a basic question. Then I said I focused on C++. After that we started to talk some others like db and C++.

The programming problem was pretty basic like a median level in Leetcode.

At last we talked about some information about company. It is a cloud computing company focused on life science. Thus of course the intuitive question is does software engineer need any life science knowledge. The answer is no. That's perfect. The reason why Veeva is now focus on life science is that on the one hand there is huge market in this area. On the other hand is because Veeva is still the growing company which would be more competitive if focuses on more detail field. Hence we know the cloud computing used in Veeva is also applied for other fields.

Although I performed pretty bad in the interview, Veeva is a pretty potential company in cloud computing.

(rejected at 11.3)

UCI 2014 Fall Career Fair 10.23

虽然和其他名校相比来UCI CF的企业相当少，不过已经很多了，而且所有活动都安排在室内进行，对于站着投简历一天的人来说还是不错的。

准备了三天时间，最后确定下来十七家感兴趣的公司，基本都是在做云计算相关的内容。虽然CF公司比较少，可以从CF开始就入场，一直投到结束，这十七家都没有投完。

整体来说这次CF我做的还不错，比上次参加要强一百倍。因为有了经验知道该做什么，并且做了充分的准备。一方面知道和别人说什么，另一方面也知道怎么说。

因为貌似又几个公司的交流就在简历后边做了记号。

FB貌似因为提前做了图表准备怎么讲project所以被问了智力题，想了十分钟终于答出来了。

MS因为说“Azure is better than AWS"也拿到了hr 的email

还有几个公司也被做了标记。

准备了很长的对话和blazzard讲，貌似人家也没甩我，不过至少我做到了自己能做的，昨天晚上还反复犹豫到底要不要去和blazzard人说，要不要把准备好的长长一段屁话说了，毕竟这种事我在中国也没有用汉语讲过。最后鼓起勇气用英语说了出来，还是挺开心的，虽然貌似一点作用也没有，但是自己没有任何遗憾，也就挺开心了。

唯一感觉很糟糕的就是salesforce，完全没有尊重，根本没有听我说了什么。而且我说话说一半就打断我。

总结的经验就是，不要把事情当故事讲，要简明扼要，没人愿意听你扯那么长的事。

另一方面不要指望别人刚好问道你想说的内容，你要自己想方法把话题引过去。

如果别人没问你的劣势（比如实习只有一个月），就不要自己最贱的说。。

Implementation of Binary Search

Found details at here

Grandstream Networks Onsite Oct. 15

An IP audio and video communication company located near LA. Overall interview took almost three hours.
The interview was quiet fine for me because all were technical problems.

The first warm up question was a variation of binary search which turned out to be a little embarrassed because I finally wrote the correct code after three times of modification.

Then given half a hour with six pages of problems, varying from C++language to algorithm and coding. All regular problems nothing hard.

After explained details about my answer, the second interviewee gave me two brain storm problems.
1. two fuse that each burn out in 1 hour. How to get 45 mins.
2. eight stones in which only one is heavier than others. Given a scale how many times can you find out that one. Generalize the problem to N stones.

Last interviewee asked C++ friend. I didn't use this before so I talked about virtual function instead.

Things needed to check out after interview:
   1. How does free() know how much memory did malloc allocated
   2. How to free this
                  Obj *p= new Obj[5]
   3. Usage of keyword Friend


Offer 12.10

[Leetcode Solution] Rotate List

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode *rotateRight(ListNode *head, int k) { if(head==NULL || k==0)return head; ListNode*p=head,*q=p->next; int len=1; while(q!=NULL){ p=p->next; q=q->next; len++; } p->next=head; p=head; for(int i=0;inext; q=p->next; p->next=NULL; return q; } };

[Leetcode Solution] Remove Duplicates from Sorted Array II

[Leetcode Solution] Gray Code

[Leetcode Solution] Find Minimum in Rotated Sorted Array I && II

It's pretty straightforward that this is a binary search problem.

The key part of binary search is how to decrease the searching scale. There are two types of scale down strategy based on the different scale down factor.

Let find(num,x,p,q) denote that find the target x in the range from num[p] to num[q]. Thus the first step we need to make sure is that whether target is located within this range. An important point needed to mind is that (p,q) denotes the target is located in range (p,q) inclusively and thus each step we decrease the range, the statement that the target is located in the range is always held.

Two things about binary search

1. Terminate condition
2. How to decrease range

Based on different types of above method, two types of implementation emerged.

1. Find out the mid element. Decrease the range (p,q) to (p,mid) or (mid,q). Thus the problem is that  the procedure might be endless because p could be always not equal to q. Hence the terminate condition is that (if p==mid) return the target which is the case that p==q or p==q-1
2. Find out the mid element. Decrease the range (p,q) to (p,mid-1) or (mid+1,q). This can make sure  that binary search procedure will sure terminate by p==q. However the thing needed to do for this method is that you must make sure if mid is the target because each time of decrease range you always eliminate the mid from next searching range.

Now let's consider the Problem "Find Minimum in Rotated Sorted Array"

1. Use first type of binary search
2. Use second type of binary search

Now let's consider the Problem  "Find Minimum in Rotated Sorted Array II"

Because duplicated elements exist. Thus it is hard to check whether mid element is the target. So we can use the first method to implement the binary search easilier.

[Leetcode Solution]Validate Binary Search Tree

[Leetcode Solution] Binary Tree Zigzag Level Order Traversal

[Leetcode Solution]Maximum Depth of Binary Tree

[Leetcode Solution] Construct Binary Tree from Inorder and Postorder Traversal

[Leetcode Solution] Binary Tree Level Order Traversal II

[Leetcode Solution] Convert Sorted Array to Binary Search Tree

[Leetcode Solution] Convert Sorted List to Binary Search Tree

[Leetcode Solution] Balanced Binary Tree

[Leetcode Solution]Minimum Depth of Binary Tree

UPDATED AT LEETCODE 2ND PASS

[Leetcode Solution] Path Sum

[Leetcode Solution] Path Sum II

[Leetcode Solution] Flatten Binary Tree to Linked List

UPDATED AT LEETCODE 2ND PASS

[Leetcode Solution] Populating Next Right Pointers in Each Node

[Leetcod Solution] Pascal's Triangle II .cpp

[Leetcode Solution] Triangle

[Leetcode Solution] Binary Tree Maximum Path Sum

[Leetcode Solution] Valid Palindrome

Computer Architecture

ISA
Instruction Set Architecture. A high level abstraction of the hardware that implemented by a set of microprocessor design techniques.
Types like RICS: x86. CICS: MIPS, ARM

RICS
Reduced Instruction Set Computing.
Reduce the amount work of a single instruction that at most a single data memory cycle.

MISP
Microprocessor without Interlocked Pipeline Stages.
Reduce the amount of job of each instruction. Make it easier to do the pipeline to speed up.
( Use more registers. Only one memory access method, reg + offset. Return address register, use coprocessor CP0 to deal with floating points and interrupt)
TODO What does WITHOUT INTERLOCK mean?

EXcpu = Number of Instructions * CPI * cycle time

PIPELINE
Five stages: Instruction Fetch, Instruction Decode, Execution, Memory Access, Write Back.
Hazard: Structural Hazard, Data Hazard (Stall, Data Forward), Branch Hazard (Static Prediction, Dynamic Prediction)

CACHE
WHY: Balance the performance difference between CPU and memory. L1 L2 L3 cache.
The reason why cache is useful is taking advantage of temporary locality and spacial locality.
ORGANISATION: Full associate, direct mapping, two way set associate.


VIRTUAL MEMORY
WHAT: Virtual memory is a memory management technique that maps a virtual address used by program into a physical address in memory.

WHY: (1. Abstraction Layer) Each program will have a independent 4G memory space provided by the system which is a middle layer between high level software program and low level hardware memory resource. Then software program no longer needs to care about which segment of memory can be used or whether a memory is 'real' memory or disk. (2. Memory Protection) Virtual memory can help programs from interfering with others programs. Because each program can access its own memory space which maps to a part of physical memory controlled by operating system. (3. Shared Memory) Also helps programs cooperate and share memory.

HOW: Use the page table to translate virtual address to physical address and use TLB (Translation Lookaside Buffer) to accelerate the speed.

PAGE FAULT: When the hardware tries to access a page that is mapped in the virtual space however not loaded into the physical memory, then a page fault will be raised by hardware. Usually the operating system will handle page fault interrupt by allocate a new page in physical memory and map it to the demanded virtual memory.

THRASHING:
When a large process or some small processes frequently access the memory and physical memory doesn't have the enough space for these processes, and the memory swapping strategy makes inefficient  swapping decision, then pages are frequently swapped between memory and disk which costs a lot time but do less help to the program.
TODO: Cache swap replacement algorithm

OUT OF ORDER PROCESSOR
TODO: Tomasulu algorithm, register renaming, reorder buffer, reservation station, instruction window
MEMORY MODEL FOR SEQUENTIAL CONSISTENCY
TODO: Review the cs 295 content

[Leetcode Solution] Gas Station

Code

Updated at LeetCode 2nd Pass

Divide array into sub arrays

How to divide a array into multiple sub arrays by given delimiter specification

[Leetcode Solution] Maximum Product Subarray

Analysis 

• First idea came in mind is dynamic programming which would be fine if it is required to calculate the maximum sum subarray. However after short thinking it's easy to find out this is a greedy algorithm 
• Assume there is no Zero in the array, we can divide the problem into two sub problems
• If the number of negative elements in the array is even, the maximum product is multiple all the elements together
• If the number of negative elements in the array is odd, we calculate the two products of elements in which the first is from left to the last negative element and the second is from the first negative element to the last element. Then return the bigger one.
• Take zero element into consideration. If we multiple zero into product, the result is always equals to zero. So the solution is divide original array into multiple subarrays delimited by the zero. Then calculate the maximum product within each sub array. Last return the biggest one.

Note

Divide an array by given delimiter and perform calculation on each sub array. Code Template can be found here 
http://fmarss.blogspot.com/2014/10/divide-array-into-sub-arrays.html 

Code