Cracking The Coding Interview

• Microsoft wants smart people Geeks. People who are passionate about technology.
• You'll have a short interview with a recruiter where he or she will give you a sample question. Your recruiter is usually there to prep you, and not to grill you on techni- cal questions. Be nice to your recruiter. Your recruiter can be your biggest advocate, even pushing to re-interview you if you stumbled on your first interview. They can fight for you to be hired - or not!
• During the day, you'll do four or five interviews, often with two different teams. Unlike many companies, where you meet your interviewers in a conference room, you'll meet with your Microsoft interviewers in their once. This is a great time to look around and get a feel for the team.
• Depending on the team, interviewers may or may not share their feedback on you with the rest of the interview loop.
• When you complete your interviews with a team, you might speak with a hiring manager. If so, that’s a great sign! It likely means that you passed the interviews with a particular team. It’s now down to the hiring manager’s decision.
• You might get a decision that day, or it might be a week. After one week of no word from HR, send them a friendly email asking for a status update.

Definitely Prepare: “Why do you want to work for Microsoft?”

In this question, Microsoft wants to see that you’re passionate about technology. A great answer might be, “I’ve been using Microsoft software as long as I can remember, and I'm really impressed at how Microsoft manages to create a product that is universally excellent. For example, I’ve been using Visual Studio recently to learn game programming, and it’s APIs are excellent.” Note how this shows a passion for technology!

• Amazon’s recruiting process usually begins with one or two phone screens in which you in- terview with a specific team. The engineer who interviews you will usually ask you to write simple code and read it aloud on the phone They will ask a broad set of questions to explore what areas of technology you’re familiar with.
• Next, you fly to Seattle for four or five interviews with one or two teams which have selected you based on your resume and phone interviews. You will have to code on a whiteboard, and some interviewers will stress other skills. Interviewers are each assigned a specific area to probe and may seem very different from each other.
• They can not see other feedback until they have submitted their own and they are discouraged from discussing it until the hiring meeting.
• Amazon’s “bar raiser” interviewer is charged with keeping the interview bar high. If one interview seems significantly harder and different, that’s most likely the bar raiser This person has both significant experience with interviews and veto power in the hiring decision.
• While Amazon’s recruiters are excellent at following up with candidates, occasionally there are delays. If you haven’t heard from Amazon within a week, we recommend a friendly email.

Definitely Prepare:

• Amazon is a web-based company, and that means they care about scale. Make sure you prepare for questions in “Large Scale.” You don’t need a background in distributed systems to answer these questions. See our recommendations in the System Design and Memory Limits Chapter.
• Additionally, Amazon tends to ask a lot of questions about object oriented design. Check out the Object Oriented Design chapter for sample questions and suggestions.

• However, because Google HR can be a little disorganized, we recommend being proactive in communication.
• A Google engineer performs the first phone screen, so expect tough technical questions.
• On your on-site interview, you'll interview with four to six people, one of whom will be a lunch interviewer. Interviewer feedback is kept confidential from the other interviewers, so you can be assured that you enter each interview with blank slate. Your lunch interviewer doesn’t submit feedback, so this is a great opportunity to ask honest questions.
• Written feedback is submitted to a hiring committee of engineers to make a hire/no-hire recommendation. Feedback is typically broken down into four categories (Analytical Ability, Coding, Experience and Communication) and you are given a score from 1.0 to 4.0 overall.
• The hiring committee understands that you can’t be expected to excel in every interview, but if multiple people raise the same red flag (arrogance, poor coding skills, etc), that can disqualify you. A hiring committee typically wants to see one interviewer who is an “enthusiastic endorser”. In other words, a packet with scores of 3.6, 3.1, 3.1 and 2.6 is better than all 3.1s. Your phone screen is usually not a strong factor in the final decision.
• The Google hiring process can be slow. If you don’t hear back within one week, politely ask your recruiter for an update. A lack of response says nothing about your performance.

Definitely Prepare:

• As a web-based company, Google cares about how to design a scalable system. So, make sure you prepare for questions from “System Design and Memory Limits”
• Additionally, many Google interviewers will ask questions involving Bit Manipulation, so please brush up on these questions.

• Much like the company itself, Apple’s interview process has minimal beaucracy.
• The inter- viewers will be looking for excellent technical skills, but a passion for the position and company is also very important. While it’s not a prerequisite to be a Mac user, you should at least be familiar with the system.
• The interview process typically begins with a recruiter phone screen to get a basic sense of your skills, followed up by a series of technical phone screens with team members.
• Once you’re invited on campus, you'll typically be greeted by the recruiter who provides an overview of the process. You will then have 6-8 interviews with members of the team for which you’re interviewing, as well as key people with whom your team works.
• You can expect a mix of 1-on-1 and 2-on-1 interviews. Be ready to code on a whiteboard and make sure all of your thoughts are clearly communicated. Lunch is with your potential future manager and appears more casual, but is still an interview. Each interviewer is usually focused on a different area and is discouraged from sharing feedback unless there’s something they want subsequent interviewers to drill into.
• Towards the end of the day, your interviewers will compare notes and if everyone still feels you’re a viable candidate, you'll interview with the director and then VP of the organization you’re applying to. While this decision is rather informal, it’s a very good sign if you make it. This decision also happens behind the scenes and if you don’t pass, you'll simply be escorted out of the building without ever having been the wiser (until now)
• If you made it to the director and VP interviews, all of your interviewers will gather in a conference room to give an official thumbs up or thumbs down The VP typically won’t be present, but can still veto the hire if they weren’t impressed.
• Your recruiter will usually follow up a few days later, but feel free to ping your recruiter for updates.

Definitely Prepare:

• If you know what team you’re interviewing with, make sure you read up on that product. What do you like about it? What would you improve? Offering specific recommendations can show your passion for the job.
• Also, Apple employees are huge Apple fans. You should show this same passion in your interview.

• While Yahoo tends to only recruit at the top 10 – 20 schools, other candidates can still get interviewed through Yahoo’s job board (or – better yet – if they can get an internal referral). If you’re one of the lucky ones selected, your interview process will start off with a phone screen. Your phone screen will be with a senior employee (tech lead, manager, etc)
• You will typically interview with 6 – 7 people on the same team for 45 minutes each. Each interviewer will have an area of focus(Database, Archiecture etc). Interviews will often be composed as follows:
  • 5 minutes: General conversation Tell me about yourself, your projects, etc
  • 20 minutes: Coding question For example, implement merge sort
  • 20 minutes: System design For example, design a large distributed cache These questions will often focus on an area from your past experience or on something your interviewer is cur-rently working on
• At the end of the day, you will likely meet with a Program Manag- er or someone else for a general conversation (product demos, concerns about the company, your competing offers, etc). Meanwhile, your interviewers will discuss your performance and attempt to come to a decision The hiring manager has the ultimate say and will weigh the positive feedback against the negative.
• If you have done well, you will often get a decision that day, but this is not always the case. There can be many reasons that you might not be told for several days – for example, the team may feel it needs to interview several other people.

Definitely Prepare:

• Yahoo, almost as a rule, asks questions about system design, so make sure you prepare for that. They want to know that you can not only write code, but that you can design software. Don’t worry if you don’t have a background in this - you can still reason your way through it!

Resume screeners look for the same things that interviewers do:

• Are you smart?
• Can you code?

That means that you should present your resume to show those two things. Your love of tennis, traveling, or magic cards won’t do much to show that, so it’s likely just wasting space.Keep in mind that recruiters only spend a fixed amount of time (about 20 seconds) looking at your resume. If you limit the content to the best, most impressive, most relevant items, they’ll jump out at the recruiter Weak items only dilute your resume and distract the recruiter from what you’d like them to see.

Writing Strong Bullets:

• For each role, try to discuss your accomplishments with the following approach: “Accom- plished X by implementing Y which led to Z” Here’s an example:
• “Reduced object rendering time by 75% by applying Floyd’s algo- rithm, leading to a 10% reduction in system boot time”
• “Increased average match accu- racy from 1.2 to 1.5 by implementing a new comparison algorithm based on windiff”

Not everything you did will fit into this approach, but the principle is the same: show what you did, how you did it, and what the results were Ideally, you should try to make the results “measurable” somehow.

Advice for Non-Native English Speakers and Internationals:

• Proofreading: Some companies will throw out your resume just because of a typo. Please get at least one native English speaker to proofread your resume.
• Personal Information: For US positions, do not include age, marital status, or nationality. This sort of personal information is not appreciated by companies, as it creates a legal liabil- ity for them However, you may want to include your current work authorization / visa status, particularly when applying to smaller companies who may be unable to sponsor candidates.

Behavioral questions are asked for a variety of reasons

• They can be asked either to get to know your personality,
• to more deeply understand your resume,
• or just to ease you into an interview Either way,

these questions are important and can be prepared for.

Behavioral questions are usually of the form “tell me about a time when you ”, and may ask for an example from a specific project or position. I recommend filling in the following “preparation grid” as shown below:

In each cell, put the corresponding story. We recommend reducing each story to just a couple keywords that you can write in each cell This will make the grid easier to study

行为型问题:

• So tell me about yourself.
• What is your greatest weakness?
• Have you ever had a conflict with a co-worker? How did you solve it?
• What is your most challenging/interesting project?
• Where do you see yourself in five years?

What questions should you ask the interviewer?

• Genuine Questions: These are the questions you actually want to know ideas of questions that are valuable to many candidates:
  • “How much of your day do you spend coding?”
  • “How many meetings do you have every week?”
  • “What is the ratio of testers to developers to product managers? What is the interac- tion like? How does project planning happen on the team?”
• Insightful Questions: These questions are designed to demonstrate your deep knowledge of programming or technologies.
  • “I noticed that you use technology X How do you handle problem Y?”
  • “Why did the product choose to use the X protocol over the Y protocol? I know it has benefits like A, B, C, but many companies choose not to use it because of issue D”
• Passion Questions: These questions are designed to demonstrate your passion for technology.
  • “I’m very interested in scalability Did you come in with a background in this, or what opportunities are there to learn about it?”
  • “I’m not familiar with technology X, but it sounds like a very interesting solution Could you tell me a bit more about how it works?”

• Memorizing or trying to learn specific questions won’t help you!
• Try to solve the problem on your own.
• Write the code for the algorithm on paper.
• Type your paper code as-is into a computer.

• Do a mock interview. CareerCup offers a mock interview

  Data Structures	Algorithms	Concepts
  Linked Lists	Breadth First Search	Bit Manipulation
  Binary Trees	Depth First Search	Singleton Design Pattern
  Tries	Binary Search	Factory Design Pattern
  Stacks	Merge Sort	Memory (Stack vs Heap)
  Queues	Quick Sort	Recursion
  Vectors / ArrayLists	Tree Insert / Find / etc	Big-O Time
  Hash Tables

• Be Specific, Not Arrogant # 将问题说的具体一些就不会显得傲慢
• Limit Details # 同样也不要说的太多具体，限制细节，否则有可能会把面试官搞晕
• Ask Good Questions
• Structure Answers Using S.A.R(Situation, Action, Response) # 当时情况，如何分析的，如何行动的，以及最后的结果。其中如何分析的这点没有办法放在简历上，其他几点在简历上也比较简略，所以这些都可以在面试中体现出来

Arrogance is a redflag, but you still want to make yourself sound impressive. So how do you make yourself sound good without being arrogant? By being specific! Specificity means giving just the facts and letting the interviewer derive an interpretation. Consider an example:

• Candidate #1: “I basically did all the hard work for the team.”
• Candidate #2: “I implemented the file system, which was considered one of the most challenging components because …”

Candidate #2 not only sounds more impressive, but she also appears less arrogant.

A technical interview question can be solved utilizing a five step approach:

1. Ask your interviewer questions to resolve ambiguity
2. Design an Algorithm
3. Write pseudo-code first, but make sure to tell your interviewer that you’re writing pseudo-code! Otherwise, he/she may think that you’re never planning to write “real” code, and many interviewers will hold that against you
4. Write your code, not too slow and not too fast
5. Test your code and carefully fix any mistakes

• Negotiating. It’s Always Negotiable! Ok, maybe not always, but usually an offer is negotiable even if a recruiter tells you otherwise. It helps if you have a competing offer But, don’t lie – Microsoft knows what Google offers, so it just won’t be realistic if you make up numbers. Also, technol- ogy is a small world, and people talk. Be honest.
• What’s the money like, really? Think about the full offer package Many companies will have impressive salaries, but small annual bonuses Other companies will have huge annual bonuses, but lower salaries Make sure you look at the full package (salary, signing bonus, health care benefits, raises, annual bonus, relocation, stock, promotions, etc) It’s very confusing, and it’s often not clear which company is offering more
• What about your career options? I can’t give you some magical formula to compute which offer to accept, but here’s what I’d recommend thinking about (in no particular order):
  • Career Path: Make a plan for your career What do you want to do 5, 10 and 15 years out? What skills will you need to develop? Which company or position will help you get there?
  • Promotion Opportunity: Do you prefer to move into management, or would you prefer to become an increasingly senior developer?
  • Money and Benefits: Of course, the money matters (but if you’re early in your career, it probably doesn’t matter much). As mentioned above, make sure you look at the full package.
  • Happiness: Did you like the people? The products? The location? It’s hard to tell, of course, before you work there. What are the options to change teams if you’re unhappy?
  • Brand Name: The company’s brand name can mean a lot for your future career. Some company names will open doors, while others will not as much.
  • What about company stability? Personally, I think it matters much less than most people think. There are so many software companies out there. If you get laid off and need to find a new job, will it be difficult to find a new one? Only you can answer that.

• Practicing on a Computer
• Not Rehearsing Behavioral Questions
• Not Doing a Mock Interview
• Trying to Memorize Solutions
• Talking Too Much
• Talking Too Little
• Rushing
• Not Debugging
• Sloppy Coding
• Giving Up

Should I tell my interviewer if I know a question?

Yes! You should definitely tell your interviewer if you’ve previously heard the question This seems silly to some people - if you already know the question (and answer), you could ace the question, right? Not quite

Here’s why we strongly recommend that you tell your interviewer that you’ve heard the question:

1. Big honesty points. This shows a lot of integrity That’s huge. Remember that the interviewer is evaluating you as a potential teammate I don’t know about you, but I personally prefer to work with honest people!
2. The question might have changed ever-so-slightly. You don’t want to risk repeating the wrong answer
3. If you easily belt out the right answer, it’s obvious to the interviewer. They know how hard a problem is supposed to be. It’s very hard to “pretend” to struggle through a question, because you just can’t approach it the same way other candidates do.

• 1.1 Implement an algorithm to determine if a string has all unique characters. What if you can not use additional data structures?
• 1.2 Write code to reverse a C-Style String. (C-String means that “abcd” is represented as five characters, including the null character.)
• 1.3 Design an algorithm and write code to remove the duplicate characters in a string without using any additional buffer.
• 1.4 Write a method to decide if two strings are anagrams or not.
• 1.5 Write a method to replace all spaces in a string with ‘%20’.
• (x) 1.6 Given an image represented by an NxN matrix, where each pixel in the image is 4 bytes, write a method to rotate the image by 90 degrees. Can you do this in place?
  • https://leetcode.com/problems/rotate-image
• 1.7 Write an algorithm such that if an element in an MxN matrix is 0, its entire row and column is set to 0.
  • https://leetcode.com/problems/set-matrix-zeroes/description/
• (x) 1.8 Assume you have a method isSubstring which checks if one word is a substring of another. Given two strings, s1 and s2, write code to check if s2 is a rotation of s1 using only one call to isSubstring (i e , “waterbottle” is a rotation of “erbottlewat”).

1.6 clockwise

#include <vector>
using namespace std;

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        vector<vector<int>>& m = matrix;
        int N = matrix.size();
        for(int r = 0; r < N/2; r++) {
            int end = N - 1 - r;
            for(int c = r; c < end; c++) {
                int tmp = m[r][c];
                m[r][c] = m[N-1-c][r];
                m[N-1-c][r] = m[N-1-r][N-1-c];
                m[N-1-r][N-1-c] = m[c][N-1-r];
                m[c][N-1-r] = tmp;
            }
        }
    }
};

1.7

#include <cstdio>
#include <vector>
using namespace std;

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int odd = 78392356;
        for(int r = 0; r < matrix.size(); r++) {
            for (int c = 0; c < matrix[r].size(); c++) {
                if (matrix[r][c] == 0) {
                    for(int k = 0; k < matrix.size(); k++) {
                        if(matrix[k][c] != 0) {
                            matrix[k][c] = odd;
                        }
                    }
                    for(int k = 0; k < matrix[0].size();k++) {
                        if (matrix[r][k] != 0) {
                            matrix[r][k] = odd;
                        }
                    }
                }
            }
        }
        for(int r =0; r < matrix.size(); r++) {
            for(int c = 0; c < matrix[r].size();c ++) {
                if(matrix[r][c] == odd) {
                    matrix[r][c] = 0;
                }
            }
        }
    }
};

Questions:

• 2.1 Write code to remove duplicates from an unsorted linked list. How would you solve this problem if a temporary buffer is not allowed?
• 2.2 Implement an algorithm to find the nth to last element of a singly linked list.
• 2.3 Implement an algorithm to delete a node in the middle of a single linked list, given only access to that node.
• 2.4 You have two numbers represented by a linked list, where each node contains a single digit. The digits are stored in reverse order, such that the 1’s digit is at the head of the list. Write a function that adds the two numbers and returns the sum as a linked list.
• (x) 2.5 Given a circular linked list, implement an algorithm which returns node at the beginning of the loop.
  • Assume P,Q at head. P proceeds 1 step, and Q proceed 2 step. There is k nodes before entry node of the circular list. And they takes u step to meet each other at p in the circular list. So we have following equations.
    1. k + xn + p= 2u # Q position.
    2. k + yn + p = u # P position.
    3. u = zn # using 1 and 2.
    4. (k + p) = z'n # using 2 and 3.
    5. k % n = (n-p) # done. 这个时候从开头以及当前位置分别追踪直到相遇，相遇点就是loop的起始点
• https://oj.leetcode.com/problems/linked-list-cycle/
• https://oj.leetcode.com/problems/linked-list-cycle-ii/

2.5

#include <cstdio>
struct ListNode {
    ListNode* next;
};

class Solution {
public:
    ListNode* detectCycle(ListNode* head) {
        ListNode* p0 = head, *p1 = head;
        bool cycle = false;
        while(p0 != NULL && p1 != NULL) {
            p0 = p0->next;
            p1 = p1->next;
            if (p1 == NULL) {
                return NULL;
            }
            p1 = p1->next;
            if (p0 == p1) {
                cycle = true;
                break;
            }
        }
        if(!cycle) {
            return NULL;
        }
        p0 = head;
        while(p0 != p1) {
            p0 = p0->next;
            p1 = p1->next;
        }
        return p1; // or p0
    }
};

Questions:

• 3.1 Describe how you could use a single array to implement three stacks.
• (x) 3.2 How would you design a stack which, in addition to push and pop, also has a function min which returns the minimum element? Push, pop and min should all operate in O(1) time.
  • https://leetcode.com/problems/min-stack/description/
• 3.3 Imagine a (literal) stack of plates. If the stack gets too high, it might topple. Therefore, in real life, we would likely start a new stack when the previous stack exceeds some threshold. Implement a data structure SetOfStacks that mimics this. SetOfStacks should be composed of several stacks, and should create a new stack once the previous one exceeds capacity. SetOfStacks.push() and SetOfStacks.pop() should behave identically to a single stack (that is, pop() should return the same values as it would if there were just a single stack).
  • FOLLOW UP. Implement a function popAt(int index) which performs a pop operation on a specific sub-stack.
• 3.4 In the classic problem of the Towers of Hanoi, you have 3 rods and N disks of different sizes which can slide onto any tower. The puzzle starts with disks sorted in ascending order of size from top to bottom (e.g., each disk sits on top of an even larger one). You have the following constraints: (A) Only one disk can be moved at a time (B) A disk is slid off the top of one rod onto the next rod. (C) A disk can only be placed on top of a larger disk. Write a program to move the disks from the first rod to the last using Stacks.
• 3.5 Implement a MyQueue class which implements a queue using two stacks.
  • https://leetcode.com/problems/implement-queue-using-stacks/description/
  • https://www.hackerrank.com/challenges/ctci-queue-using-two-stacks
• (x) 3.6 Write a program to sort a stack in ascending order. You should not make any assumptions about how the stack is implemented.

3.4 这个问题可以做个扩展，就是如何存在R根柱子的话，应该是什么样的解法？我觉得可以先把头部几个plates先放到(R-3)根柱子上，然后按照Hanoi的方法移动下面几个plates, 最后把头部plates放回到目的地。 R=3的时候，最少步数是 2**N - 1. R>3的时候

• 先移动R-3个盘子，
• 剩余的plates需要 2^(N-R+3)-1
• 然后将开始R-3盘子移动到目的地
• 所以总数是2*(R-3) + 2^(N-R+3) - 1

#!/usr/bin/env python
# coding:utf-8
# Copyright (C) dirlt

def find_solution(N):
    steps = []
    def move(n, r0, r1):
        if (n == 0):
            return
        r2 = 3 - r0 - r1
        move(n-1, r0, r2)
        steps.append((n, r0, r1))
        move(n-1, r2, r1)
    move(N, 0, 2)
    return steps

steps = find_solution(5)
print(steps)
print(len(steps))

利用BUD(Bottlenecks, Unnecessary work, Duplicated work) 来优化算法

• Trees
  • Not all binary trees are binary search trees
  • In-Order: Traverse left node, current node, then right
  • Pre-Order: Traverse current node, then left node, then right node
  • Post-Order: Traverse left node, then right node, then current node
  • AVL Tree, RB Tree, Splay Tree
  • Construct Tree by using Orders
• Graphs
  • Depth First Search
  • Breadth First Search
  • Dijkstra, Floyd, Bellman-Ford, A*
    • https://leetcode.com/problems/network-delay-time/description/
    • https://www.geeksforgeeks.org/dijkstras-shortest-path-algorithm-using-priority_queue-stl/ Dijkstra in O(ELogE) = O(ELogV)
    • https://www.geeksforgeeks.org/dynamic-programming-set-23-bellman-ford-algorithm/ negative weight graph.
  • Prim, Kruskal

Questions:

• 4.1 Implement a function to check if a tree is balanced. For the purposes of this question, a balanced tree is defined to be a tree such that no two leaf nodes differ in distance from the root by more than one.
• 4.2 Given a directed graph, design an algorithm to find out whether there is a route between two nodes.
• 4.3 Given a sorted (increasing order) array, write an algorithm to create a binary tree with minimal height.
• 4.4 Given a binary search tree, design an algorithm which creates a linked list of all the nodes at each depth (eg, if you have a tree with depth D, you’ll have D linked lists).
• 4.5 Write an algorithm to find the ‘next’ node (e.g., in-order successor) of a given node in a binary search tree where each node has a link to its parent.
• (x) 4.6 Design an algorithm and write code to find the first common ancestor of two nodes in a binary tree. Avoid storing additional nodes in a data structure.
  • https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/
  • https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/
• 4.7 You have two very large binary trees: T1, with millions of nodes, and T2, with hundreds of nodes. Create an algorithm to decide if T2 is a subtree of T1.
  • https://leetcode.com/problems/subtree-of-another-tree/description/
• (x) 4.8 You are given a binary tree in which each node contains a value. Design an algorithm to print all paths which sum up to that value. Note that it can be any path in the tree - it does not have to start at the root.
  • https://leetcode.com/problems/path-sum/description/
  • https://leetcode.com/problems/path-sum-ii/description/
  • https://leetcode.com/problems/path-sum-iii/description/
  • https://leetcode.com/problems/binary-tree-maximum-path-sum/description/

https://www.hackerrank.com/challenges/ctci-is-binary-search-tree/problem

检查一棵树是否为BST. 我一开始写错的版本是，只拿root和left/right的值做比较，而不是和两边子树的最大和最小值做比较。

""" Node is defined as
class node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
"""

def checkBST(root):
    def f(root):
        if root is None: return True, None, None
        data = root.data
        min_value, max_value = data, data

        if root.left:
            lr, lmin, lmax = f(root.left)
            if not lr or data <= lmax:
                return False, None, None
            min_value = min(min_value, lmin)
            max_value = max(max_value, lmax)

        if root.right:
            rr, rmin, rmax = f(root.right)
            if not rr or data >= rmin:
                return False, None, None
            min_value = min(min_value, rmin)
            max_value = max(max_value, rmax)

        return True, min_value, max_value
    res, _, _ = f(root)
    return res

我觉得上面这个写起来还是太丑了，下面是更加简洁的写法

boolean isValid(Node root) {
    return isValidHelper(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
}
boolean isValidHelper(Node curr, int min, int max) {
    if (curr.left != null) {
        if (curr.left.value < min || !isValidHelper(curr.left, min, curr.value))
        return false;
    }
    if (curr.right != null) {
        if (curr.right.value > max || !isValidHelper(curr.right, curr.value, max))
        return false;
    }
    return true;
}

4.6

#include <cstdio>
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
};

class Solution {
public:
    TreeNode* find(TreeNode *root, TreeNode *p, TreeNode *q, int* covers) {
        if (root == NULL) return NULL;

        int c = 0;
        if((root == p) || (root == q))
            c += 1;

        int c0 = 0, c1 = 0;
        TreeNode *t0 = find(root->left, p, q, &c0);
        if (c0 == 2) {
            *covers = 2;
            return t0;
        }
        TreeNode *t1 = find(root->right, p, q, &c1);
        if (c1 == 2) {
            *covers = 2;
            return t1;
        }
        c += (c0 + c1);
        *covers = c;
        return root;
    }

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        int covers = 0;
        TreeNode *t = find(root, p, q, &covers);
        return t;
    }
};

Questions:

• 5.1 You are given two 32-bit numbers, N and M, and two bit positions, i and j Write a method to set all bits between i and j in N equal to M. Input: N = 10000000000, M = 10101, i = 2, j = 6. Output: N = 10001010100
• 5.2 Given a (decimal - e.g. 3.72) number that is passed in as a string, print the binary representation If the number can not be represented accurately in binary, print “ERROR”
• (x) 5.3 Given an integer, print the next smallest and next largest number that have the same number of 1 bits in their binary representation.
• 5.4 Explain what the following code does: ((n & (n-1)) == 0).
• 5.5 Write a function to determine the number of bits required to convert integer A to integer B.
  • https://leetcode.com/problems/hamming-distance/description/
• 5.6 Write a program to swap odd and even bits in an integer with as few instructions as possible (e g , bit 0 and bit 1 are swapped, bit 2 and bit 3 are swapped, etc).
• 5.7 An array A[1…n] contains all the integers from 0 to n except for one number which is missing. In this problem, we cannot access an entire integer in A with a single operation. The elements of A are represented in binary, and the only operation we can use to access them is “fetch the jth bit of A[i]”, which takes constant time. Write code to find the missing integer. Can you do it in O(n) time?

5.3 这是一个对偶问题，大致思路是找到可以置换的0,1 pair, 然后将least bits进行重排列。

#!/usr/bin/env python
# coding:utf-8
# Copyright (C) dirlt


def n_bits(v):
    c = 0
    while v:
        c += (v & 0x1)
        v >>= 1
    return c


def same_n_bits(a, b):
    return n_bits(a) == n_bits(b)


def get_prev(v):
    # 找到第一个可以置换的1(least bits中存在至少一个0)
    # 并且统计least bits里面有多少个1

    c0, c1 = None, None
    least_ones = 0
    for i in range(32):
        if ((v >> i) & 0x1) == 0:
            c0 = i
            break
        least_ones += 1
    if c0 is None:
        return None
    for i in range(c0, 32):
        if ((v >> i) & 0x1) == 1:
            c1 = i
            break
    if c1 is None:
        return None

    # 下面剩余的1需要进行重排列，尽可能放置在高位
    # 我们这里不设置bit, 而是进行重组
    v = (v >> (c1 + 1)) << 1
    v = (v << 1) + 1
    assert (least_ones <= (c1 - 1))
    for i in range(0, least_ones):
        v = (v << 1) + 1
    for i in range(least_ones, c1 - 1):
        v = (v << 1)
    return v


def get_next(v):
    # 找到第一个可以置换的0(least_bits中至少有一个1)
    # 并且统计least bits里面有多少个0
    c0, c1 = None, None
    least_zeros = 0
    for i in range(32):
        if ((v >> i) & 0x1) == 1:
            c1 = i
            break
        least_zeros += 1
    if c1 is None:
        return None
    for i in range(c1, 32):
        if ((v >> i) & 0x1) == 0:
            c0 = i
            break
    if c0 is None:
        return None
    v = ((v >> (c0 + 1)) << 1) + 1
    v = (v << 1)
    assert (least_zeros <= (c0 - 1))
    for i in range(0, least_zeros):
        v = (v << 1)
    for i in range(least_zeros, c0 - 1):
        v = (v << 1) + 1
    return v


def check_prev(n):
    prev = get_prev(n)
    print('n = {}, prev = {}'.format(n, prev))
    if prev is not None:
        assert(prev < n)
        assert (same_n_bits(prev, n))
        for x in range(prev + 1, n):
            # if same_n_bits(x, n):
            #     print('bad case: prev = {}, x = {}'.format(prev, x))
            #     break
            assert not same_n_bits(x, n)


for n in range(10, 2000):
    check_prev(n)


def check_next(n):
    nextv = get_next(n)
    print('n = {}, next = {}'.format(n, nextv))
    if nextv is not None:
        assert (nextv > n)
        assert (same_n_bits(nextv, n))
        for x in range(n + 1, nextv):
            if same_n_bits(x, n):
                print('bad case: next = {}, x = {}'.format(nextv, x))
                break
            assert not same_n_bits(x, n)


for n in range(10, 2000):
    check_next(n)

5.7

#!/usr/bin/env python
# coding:utf-8
# Copyright (C) dirlt
import random


def find_missing(arr, n):
    assert (len(arr) == n)
    exp = 0
    for x in range(0, n + 1):
        exp ^= x
    for x in arr:
        exp ^= x
    return exp


for n in (100, 200, 300, 400):
    arr = list(range(0, n + 1))
    random.shuffle(arr)
    exp_missing = arr[-1]
    arr = arr[:-1]
    print(exp_missing, find_missing(arr, n))

• Don’t panic when you get a brain teaser. Interviewers want to see how you tackle a problem; they don’t expect you to immediately know the answer. Start talking, and show the inter- viewer how you approach a problem
• In many cases, you will also find that the brain teasers have some connection back to fundamental laws or theories of computer science.
• If you’re stuck, we recommend simplifying the problem. Solve it for a small number of items or a special case, and then see if you can generalize it.

Questions:

• 6.1 Add arithmetic operators (plus, minus, times, divide) to make the following expression true: 3 1 3 6 = 8. You can use any parentheses you’d like.
  • (3 + 1) / (3 / 6)
• (x) 6.2 There is an 8x8 chess board in which two diagonally opposite corners have been cut off. You are given 31 dominos, and a single domino can cover exactly two squares. Can you use the 31 dominos to cover the entire board?
• 6.3 You have a five quart jug and a three quart jug, and an unlimited supply of water (but no measuring cups). How would you come up with exactly four quarts of water?
• (x) 6.4 A bunch of men are on an island. A genie comes down and gathers everyone together and places a magical hat on some people’s heads (i e , at least one person has a hat). The hat is magical: it can be seen by other people, but not by the wearer of the hat himself. To remove the hat, those(and only those who have a hat) must dunk themselves underwater at exactly midnight. If there are n people and c hats, how long does it take the men to remove the hats? The men cannot tell each other (in any way) that they have a hat.
• (x) 6.5 There is a building of 100 floors If an egg drops from the Nth floor or above it will break. If it’s dropped from any floor below, it will not break. You’re given 2 eggs. Find N, while minimizing the number of drops for the worst case.
  • dp[t][s][e] = 1 + min{ i=[s,e], max(dp[t-1][s][i-1], dp[t][i+1][e]) }. if(s>e) 0 else if(t==0) e-s+1
  • #note: not easy to deduce actions from dp
  • #note: and only one step can be decided. I've attached the code below.
• (x) 6.6 There are one hundred closed lockers in a hallway. A man begins by opening all one hundred lockers. Next, he closes every second locker. Then he goes to every third locker and closes it if it is open or opens it if it is closed (e.g., he toggles every third locker). After his one hundredth pass in the hallway, in which he toggles only locker number one hundred, how many lockers are open?
  • only n = p * p have been flipped with odd number and final status is open.

6.5

/* coding:utf-8
 * Copyright (C) dirlt
 */

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

const int N = 100;
const int R = 2;
int dp[R][N+1][N+1];

int fill_dp(int t, int s, int e) {
    if(s > e) return 0;
    if(dp[t][s][e] != 0) {
        return dp[t][s][e];
    }
    int v = -1;
    for(int i = s; i <= e; i++) {
        int r = 1 + max(fill_dp(t, i + 1, e), dp[t-1][s][i-1]);
        if(v == -1 || r < v) {
            v = r;
        }
    }
    dp[t][s][e] = v;
    return v;
}

void solve() {
    memset(dp, 0, sizeof(dp));
    for(int i = 1; i <= N; i++) {
        for(int j = i; j <= N; j++) {
            dp[0][i][j] = (j - i + 1);
        }
    }
    for(int t = 1; t < R; t++) {
        for(int s = 1; s <= N; s++) {
            for(int e = 1; e <= N; e++) {
                fill_dp(t, s, e);
            }
        }
    }
}

void interpret() {
    int t = R - 1;
    int start = 1;
    int end = N;

    int v = dp[t][start][end];
    printf("at most %d\n", v);

    vector<int> tries;
    int s = start;
    int c = 1;

    bool more = true;
    while (more) {
        more = false;
        for(int i = s; i <= end ; i++) {
            // search first point that egg breaks.
            // and to my intuition, there will be only one point.
            if(v <= (c + dp[t-1][s][i-1])) {
                tries.push_back(i);
                s = i + 1;
                c++;
                more = true;
                break;
            }
        }
    }

    printf("tries are:\n");
    for(int i = 0; i < tries.size(); i++) {
        printf("floor %d\n", tries[i]);
    }
}

int main() {
    solve();
    interpret();
    return 0;
}

• All problems that can be solved recursively can also be solved iteratively (though the code may be much more complicated). Before diving into a recursive code, ask yourself how hard it would be to implement this algorithm iteratively. Discuss the trade-offs with your interviewer.
• Recursive algorithms can be very space inefficient. Each recursive call adds a new layer to the stack, which means that if your algorithm has O(n) recursive calls then it uses O(n) memory Ouch! This is one reason why an iterative algorithm may be better.

Questions:

• 8.1 Write a method to generate the nth Fibonacci number.
• 8.2 Imagine a robot sitting on the upper left hand corner of an NxN grid The robot can only move in two directions: right and down How many possible paths are there for the robot?
  • Imagine certain squares are “off limits”, such that the robot can not step on them Design an algorithm to get all possible paths for the robot
  • C(n,m) = n! / (m! * (n-m)!)
  • https://leetcode.com/problems/unique-paths/description/
  • https://leetcode.com/problems/unique-paths-ii/description/
• 8.3 Write a method that returns all subsets of a set.
  • https://leetcode.com/problems/subsets/description/
  • https://leetcode.com/problems/subsets-ii/description/
• 8.4 Write a method to compute all permutations of a string.
  • https://leetcode.com/problems/permutations/description/
  • https://leetcode.com/problems/permutations-ii/description/
  • https://leetcode.com/problems/next-permutation/description/
• 8.5 Implement an algorithm to print all valid (e g , properly opened and closed) combinations of n-pairs of parentheses.
  • https://leetcode.com/problems/generate-parentheses/description/
• 8.6 Implement the “paint fill” function that one might see on many image editing programs. That is, given a screen (represented by a 2-dimensional array of Colors), a point, and a new color, fill in the surrounding area until you hit a border of that color.
  • https://leetcode.com/problems/flood-fill/description/
• 8.7 Given an infinite number of quarters (25 cents), dimes (10 cents), nickels (5 cents) and pennies (1 cent), write code to calculate the number of ways of representing n cents.
  • https://www.hackerrank.com/challenges/ctci-coin-change/problem
• 8.8 Write an algorithm to print all ways of arranging eight queens on a chess board so that none of them share the same row, column or diagonal.
  • https://leetcode.com/problems/n-queens/description/
  • https://leetcode.com/problems/n-queens-ii/description/

8.4

/* coding:utf-8
 * Copyright (C) dirlt
 */

#include <vector>
using namespace std;

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        if(nums.size() == 0) return;
        // find swap position.
        int i = nums.size() - 1;
        for(;i >= 1; i--) {
            if(nums[i] > nums[i-1]) {
                break;
            }
        }
        if(i == 0) {
            sort(nums.begin(), nums.end());
            return;
        }
        // find another swap position.
        int min_value = nums[i];
        int min_index = i;
        for (int j = i + 1; j < nums.size(); j++) {
            if (nums[j] <= nums[i-1]) continue;
            if (nums[j] < min_value) {
                min_value = nums[j];
                min_index = j;
            }
        }
        swap(nums[min_index], nums[i-1]);
        sort(nums.begin() + i, nums.end());
    }
};

8.7

def make_change(coins, n):
    m = len(coins)
    dp = []
    for i in range(n + 1):
        dp.append([0] * (m + 1))

    # init.
    for i in range(n+1):
        dp[i][m] = 1
    for i in range(m+1):
        dp[0][i] = 1

    for i in range(1, n+1):
        for j in range(1, m+1):
            c = coins[j-1]
            value = dp[i][j-1]
            if(i >= c):
                value += dp[i-c][j]
            dp[i][j] = value
    return dp[n][m]

• Bubble Sort
• Selection Sort
• Merge Sort
• Quick Sort
• Bucket Sort
• Binary Search

Questions:

• 9.1 You are given two sorted arrays, A and B, and A has a large enough buffer at the end to hold B. Write a method to merge B into A in sorted order.
  • https://leetcode.com/problems/merge-sorted-array/description/
• 9.2 Write a method to sort an array of strings so that all the anagrams are next to each other.
• (x) 9.3 Given a sorted array of n integers that has been rotated an unknown number of times, give an O(logn) algorithm that finds an element in the array. You may assume that the array was originally sorted in increasing order. EXAMPLE: Input: find 5 in array (15 16 19 20 25 1 3 4 5 7 10 14) Output: 8 (the index of 5 in the array)
  • https://leetcode.com/problems/search-in-rotated-sorted-array/description/ O(lgn)
  • https://leetcode.com/problems/search-in-rotated-sorted-array-ii/description/ O(n)
• 9.4 If you have a 2 GB file with one string per line, which sorting algorithm would you use to sort the file and why?
• (x) 9.5 Given a sorted array of strings which is interspersed with empty strings, write a method to find the location of a given string
  • Example: find “ball” in [“at”, “”, “”, “”, “ball”, “”, “”, “car”, “”, “”, “dad”, “”, “”] will return 4
  • Example: find “ballcar” in [“at”, “”, “”, “”, “”, “ball”, “car”, “”, “”, “dad”, “”, “”] will return -1
• (x) 9.6 Given a matrix in which each row and each column is sorted, write a method to find an element in it.
  • https://leetcode.com/problems/search-a-2d-matrix/description/ O(lgm + lgn)
  • https://leetcode.com/problems/search-a-2d-matrix-ii/description/ O(n+m)
• (x) 9.7 A circus is designing a tower routine consisting of people standing atop one another’s shoulders. For practical and aesthetic reasons, each person must be both shorter and lighter than the person below him or her. Given the heights and weights of each person in the circus, write a method to compute the largest possible number of people in such a tower. EXAMPLE: Input (ht, wt): (65, 100) (70, 150) (56, 90) (75, 190) (60, 95) (68, 110) Output: The longest tower is length 6 and includes from top to bottom: (56, 90) (60,95) (65,100) (68,110) (70,150) (75,190)

9.3 这个题目很tricky, 有很多corner case. 最好在纸上画出所有可能的情况。

/* coding:utf-8
 * Copyright (C) dirlt
 */

#include <vector>
using namespace std;

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int size = nums.size();
        int s = 0, e = size - 1;
        while(s <= e) {
            int m = (s+e)/2;
            if(nums[m] == target) return m;
            if (target > nums[m]) {
                if (nums[m] >= nums[s]) {
                    s = m + 1;
                } else if(target >= nums[s]) {
                    e = m - 1;
                } else {
                    s = m + 1;
                }
            } else {
                if (nums[m] <= nums[s]) {
                    e = m - 1;
                } else if(target >= nums[s]) {
                    e = m - 1;
                } else {
                    s = m + 1;
                }
            }
        }
        return -1;
    }
};

Questions:

• 10.1 You have a basketball hoop and someone says that you can play 1 of 2 games
  • Game #1: You get one shot to make the hoop
  • Game #2: You get three shots and you have to make 2 of 3 shots
  • If p is the probability of making a particular shot, for which values of p should you pick one game or the other?
• 10.2 There are three ants on different vertices of a triangle. What is the probability of collision (between any two or all of them) if they start walking on the sides of the triangle? Similarly find the probability of collision with ‘n’ ants on an ‘n’ vertex polygon
• 10.3 Given two lines on a Cartesian plane, determine whether the two lines would intersect.
• (x) 10.4 Write a method to implement *, - , / operations. You should use only the + operator.
• (x) 10.5 Given two squares on a two dimensional plane, find a line that would cut these two squares in half.
• (x) 10.6 Given a two dimensional graph with points on it, find a line which passes the most number of points.
  • https://leetcode.com/problems/max-points-on-a-line/description/
• (x) 10.7 Design an algorithm to find the kth number such that the only prime factors are 3, 5, and 7.
  • https://leetcode.com/problems/ugly-number/description/
  • https://leetcode.com/problems/ugly-number-ii/description/

Data Structures

• Bloom Filter
• B/B+ Tree
• LSM Tree

Questions:

• 11.1 If you were integrating a feed of end of day stock price information (open, high, low, and closing price) for 5,000 companies, how would you do it? You are responsible for the development, rollout and ongoing monitoring and maintenance of the feed. Describe the different methods you considered and why you would recommend your approach. The feed is delivered once per trading day in a comma-separated format via an FTP site. The feed will be used by 1000 daily users in a web application.
• 11.2 How would you design the data structures for a very large social network (Facebook, LinkedIn, etc)? Describe how you would design an algorithm to show the connection, or path, between two people (e g , Me -> Bob -> Susan -> Jason -> You).
  • 我觉得可以为每个人存储2度关系，这个应该是可以接受的。比如Me, Bob, Susan(2rd by Bob)，因为2度扩展出去的人数应该不是很多比如10^6.
  • 然后如果要找到Me->You之间关系的话，因为You, Jason, Susan(2rd By Jason). 这样只需要做两个bit set的join即可找到共同联系人，拿You的2度bits和Me的2度bits做join即可。
  • 大部分情况下面使用这种方式都可以找到共同联系人，除非是这两个人关系特别特别远。
• (x) 11.3 Given an input file with four billion integers, provide an algorithm to generate an integer which is not contained in the file. Assume you have 1 GB of memory. What if you have only 10 MB of memory?
• 11.4 You have an array with all the numbers from 1 to N, where N is at most 32,000. The array may have duplicate entries and you do not know what N is. With only 4KB of memory available, how would you print all duplicate elements in the array?
• 11.5 If you were designing a web crawler, how would you avoid getting into infinite loops?
• 11.6 You have a billion urls, where each is a huge page. How do you detect the duplicate documents?
• 11.7 You have to design a database that can store terabytes of data. It should support efficient range queries. How would you do it?.

Questions:

• 12.2 You are given the source to an application which crashes when it is run. After running it ten times in a debugger, you find it never crashes in the same place. The application is single threaded, and uses only the C standard library. What programming errors could be causing this crash? How would you test each one?
• 12.3 We have the following method used in a chess game: boolean canMoveTo(int x, int y) x and y are the coordinates of the chess board and it returns whether or not the piece can move to that position. Explain how you would test this method.
• 12.4 How would you load test a webpage without using any test tools?
  • response time
  • throughput
  • resource utilization
• 12.6 How would you test an ATM in a distributed banking system?
  • multiple transactions
  • network breakdown

Questions:

• 15.2 What are the different types of joins? Please explain how they differ and why certain types are better in certain situations.
  • inner join
  • outer join
    • left outer join
    • right outer join
    • full outer join
• 15.3 What is denormalization? Explain the pros and cons.

Questions:

• 16.1 Explain the following terms: virtual memory, page fault, thrashing.
• (x) 16.2 What is a Branch Target buffer? Explain how it can be used in reducing bubble cycles in cases of branch misprediction.
• (x) 16.3 Describe direct memory access (DMA). Can a user level buffer / pointer be used by kernel or drivers?
  • The “DMA Controller” manages this by requesting the System bus access (DMA request) from CPU.
  • CPU completes its current task and grants access by as- serting DMA acknowledgement signal.
  • Once it gets the access, it reads/writes the data and returns back the system bus to the CPU by asserting the bus release signal.
  • This transfer is faster than the usual transfer by CPU.
  • Between this time CPU is involved with processing task which doesn’t require memory access.
• (x) 16.4 Write a step by step execution of things that happen after a user presses a key on the keyboard. Use as much detail as possible.
  • keyboard controller
  • save scan code into its buffer
  • sends a hardware interrupt to the processor
  • interrupt handler
• 16.5 Write a program to find whether a machine is big endian or little endian.
• 16.6 Discuss how would you make sure that a process doesn’t access an unauthorized part of the stack.
• 16.7 What are the best practices to prevent reverse engineering of DLLs?.
• (x) 16.8 A device boots with an empty FIFO queue. In the first 400 ns period after startup, and in each subsequent 400 ns period, a maximum of 80 words will be written to the queue. Each write takes 4 ns. A worker thread requires 3 ns to read a word, and 2 ns to process it before reading the next word. What is the shortest depth of the FIFO such that no data is lost?
• 16.9 Write an aligned malloc & free function that takes number of bytes and aligned byte (which is always power of 2). EXAMPLE:
  • align_malloc(1000,128) will return a memory address that is a multiple of 128 and that points to memory of size 1000 bytes.
  • aligned_free(p) will free memory allocated by align_malloc.
• 16.10 Write a function called my2DAlloc which allocates a two dimensional array. Minimize the number of calls to malloc and make sure that the memory is accessible by the notation arr[i][j].

16.8 模拟这个过程，为了保险认为在同一时间是先写入的然后读出的。计算出来最大深度是33.

#!/usr/bin/env python
# coding:utf-8
# Copyright (C) dirlt

queue = []
max_size = 0
worker = None

for t in range(0, 700):
    if t % 4 == 0 and t < (160 * 4):
        word, arrival = 'c#{}'.format(t // 4), t
        print('T{:03d} ===> +++ word: {}'.format(t, word))
        queue.append((word, arrival))
        max_size = max(max_size, len(queue))

    if worker:
        word, arrival = worker
        # 5ns之后才能处理下个任务.
        if t >= (arrival + 5):
            print('T{:03d} ===> --- word: {}'.format(t, word))
            worker = None

    if worker is None and queue:
        word, arrival = queue[0]
        # 4ns之后才能够读取
        if(t >= (arrival + 4)):
            print('T{:03d} ===> !!! word: {}'.format(t, word))
            worker = (word, t)
            queue = queue[1:]

print('max size = {}'.format(max_size))

16.9

/* coding:utf-8
 * Copyright (C) dirlt
 */

#include <cstdio>
#include <new>
#include <vector>
using namespace std;

void* align_malloc(int size, int alignment) {
    // sizeof(void*) + block(alignment-1) + block(size)
    int extra_size = sizeof(void*) + alignment - 1;
    void *p = malloc(extra_size);
    // align
    void *p1 = (void*)((size_t)p + extra_size);
    void **p2 = (void**)((size_t)p1 & (~(alignment - 1)));
    // printf("p = %p, p1 = %p, p2 = %p\n", p, p1, p2);
    p2[-1] = p;
    return (void*)p2;
}


void align_free(void *p) {
    void **p1 = (void**)p;
    free(p1[-1]);
}

int main() {
    vector<void*> pts;
    for(int size = 10; size < 100; size += 5) {
        for(int align = 16; align <= 128; align *= 2) {
            void *p = align_malloc(size, align);
            size_t addr = (size_t)p;
            if((addr % align) != 0) {
                printf("!!! addr = %p, align = %d\n", p, align);
            }
            pts.push_back(p);
        }
    }
    for(int i = 0; i < pts.size(); i++) {
        void* p = pts[i];
        align_free(p);
    }
}

Questions:

• 17.1 Explain what happens, step by step, after you type a URL into a browser. Use as much detail as possible.
• (x) 17.2 Explain any common routing protocol in detail For example: BGP, OSPF, RIP
• 17.3 Compare and contrast the IPv4 and IPv6 protocols.
  • IPv4 has di#erent class types: A,B,C,D and E.
  • Class A, Class B, and Class C are the three classes of addresses used on IP networks in common practice.
  • Class D addresses are reserved for multicast.
  • Class E addresses are simply reserved, meaning they should not be used on IP networks (used on a limited basis by some research organizations for experimental purposes).
• (x) 17.4 What is a network / subnet mask? Explain how host A sends a message / packet to host B when: (a) both are on same network and (b) both are on different networks. Explain which layer makes the routing decision and how.
• (x) 17.5 What are the differences between TCP and UDP? Explain how TCP handles reliable delivery (explain ACK mechanism), flow control (explain TCP sender’s / receiver’s window) and congestion control.

Questions:

• 18.1 What’s the difference between a thread and a process?
• 18.2 How can you measure the time spent in a context switch? cpu affinity
• (x) 18.3 Implement a singleton design pattern as a template such that, for any given class Foo, you can call Singleton::instance() and get a pointer to an instance of a singleton of type Foo. Assume the existence of a class Lock which has acquire() and release() methods. How could you make your implementation thread safe and exception safe?
• 18.4 Design a class which provides a lock only if there are no possible deadlocks.
• 18.6 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?

Questions:

• 19.1 Write a function to swap a number in place without temporary variables.
• 19.2 Design an algorithm to figure out if someone has won in a game of tic-tac-toe.
• (x) 19.3 Write an algorithm which computes the number of trailing zeros in n factorial.
  • https://leetcode.com/problems/factorial-trailing-zeroes/
  • https://leetcode.com/problems/preimage-size-of-factorial-zeroes-function/description/
• (x) 19.4 Write a method which finds the maximum of two numbers. You should not use if-else or any other comparison operator.
• 19.6 Given an integer between 0 and 999,999, print an English phrase that describes the integer (eg, “One Thousand, Two Hundred and Thirty Four”).
  • https://leetcode.com/problems/integer-to-english-words/description/
• 19.7 You are given an array of integers (both positive and negative). Find the continuous sequence with the largest sum. Return the sum.
• 19.8 Design a method to find the frequency of occurrences of any given word in a book.
• (x) 19.10 Write a method to generate a random number between 1 and 7, given a method that generates a random number between 1 and 5 (i e , implement rand7() using rand5()).
• 19.11 Design an algorithm to find all pairs of integers within an array which sum to a specified value.

19.3

int zeros(int n) {
  int c = 0;
  for(int k = 5; n >= k; k *= 5) {
    c += n / k;
  }
  return c;
}

Questions:

• (x) 20.1 Write a function that adds two numbers You should not use + or any arithmetic operators.
• (x) 20.2 Write a method to shuffle a deck of cards. It must be a perfect shuffle - in other words, each 52! permutations of the deck has to be equally likely. Assume that you are given a random number generator which is perfect.
• (x) 20.3 Write a method to randomly generate a set of m integers from an array of size n. Each element must have equal probability of being chosen.
• (x) 20.4 Write a method to count the number of 2s between 0 and n.
  • https://leetcode.com/problems/number-of-digit-one/description/
• 20.5 You have a large text file containing words. Given any two words, find the shortest distance (in terms of number of words) between them in the file. Can you make the searching operation in O(1) time? What about the space complexity for your solution?
• (x) 20.6 Describe an algorithm to find the largest 1 million numbers in 1 billion numbers. Assume that the computer memory can hold all one billion numbers. top-k selection / quick sort
• (x) 20.7 Write a program to find the longest word made of other words.
• (x) 20.8 Given a string s and an array of smaller strings T, design a method to search s for each small string in T. suffix tree
• (x) 20.9 Numbers are randomly generated and passed to a method. Write a program to find and maintain the median value as new values are generated.
  • https://leetcode.com/problems/find-median-from-data-stream/description/
  • https://leetcode.com/problems/sliding-window-median/description/
  • https://www.hackerrank.com/challenges/ctci-find-the-running-median/problem
  • 这个问题可以通过平衡树来完成，查询操作是O(1)，更新操作是O(lgn)
• (x) 20.10 Given two words of equal length that are in a dictionary, write a method to transform one word into another word by changing only one letter at a time. The new word you get in each step must be in the dictionary.
  • https://leetcode.com/problems/word-ladder/description/
  • https://leetcode.com/problems/word-ladder-ii/description/
• 20.11 Imagine you have a square matrix, where each cell is filled with either black or white. Design an algorithm to find the maximum subsquare such that all four borders are filled with black pixels.
• (x) 20.12 Given an NxN matrix of positive and negative integers, write code to find the submatrix with the largest possible sum.
  • https://leetcode.com/problems/maximal-rectangle
• (x) 20.13 Given a dictionary of millions of words, give an algorithm to find the largest possible rectangle of letters such that every row forms a word (reading left to right) and every column forms a word (reading top to bottom).

20.1

/* coding:utf-8
 * Copyright (C) dirlt
 */

#include <cstdio>

int add2(int a,int b) {
    int sum = a ^ b;
    int carry = (a & b) << 1;
    if(carry == 0) return sum;
    return add2(sum,carry);
}

int main() {
    printf("%d\n",add2(190,70));
    return 0;
}

20.4

迭代版本的优化点是 `c2r(pow-1, pow/10)` 这项其实可以预先计算出来

#!/usr/bin/env python
# coding:utf-8
# Copyright (C) dirlt

def c2r(n, pw):
    if(n == 0):
        return 0
    x = n // pw
    y = n % pw
    res = 0
    if (x == 2):
        res += (y + 1)
    elif (x > 2):
        res += pw
    res += x * c2r(pw - 1, pw // 10) + c2x(y)
    return res

def c2x(n):
    pw = 1
    while((pw * 10) <= n):
        pw *= 10
    return c2r(n, pw)


def count2(n):
    res = 0
    pw = 1
    pc = 0
    while((pw * 10) <= n):
        pw *= 10
        pc += 1
    while(n):
        x = n // pw
        y = n % pw
        if (x >= 2):
            if (x == 2):
                res += (y+1)
            else:
                res += pw
        res += x * pc * (pw // 10)
        n = y
        # print('pc = {}, pw = {}, res = {}, n = {}'.format(pc, pw, res, n))
        pc -= 1
        pw = pw // 10
    return res

for n in (279, 379, 579, 2012, 2010, 2009, 2002):
    print('====================')
    print('c2({}) = {}'.format(n, count2(n)))
    print('c2x({}) = {}'.format(n, c2x(n)))

20.9

先把item放在合适的位置，然后进行balance, 这样代码上会简单清晰很多

#!/usr/bin/env python
# coding:utf-8
# Copyright (C) dirlt

import heapq

class MedianFinder:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.lhq = []
        self.rhq = []

    def addNum(self, num):
        """
        :type num: int
        :rtype: void
        """
        # insert first.
        if(self.rhq and num >= self.rhq[0]):
            heapq.heappush(self.rhq, num)
        else:
            heapq.heappush(self.lhq, -num)
        # then balance.
        if((len(self.rhq) - len(self.lhq)) == 2):
            v = heapq.heappop(self.rhq)
            heapq.heappush(self.lhq, -v)
        elif((len(self.lhq) - len(self.rhq)) == 1):
            v = heapq.heappop(self.lhq)
            heapq.heappush(self.rhq, -v)


    def findMedian(self):
        """
        :rtype: float
        """
        if (len(self.rhq) == len(self.lhq)):
            if len(self.lhq) == 0:
                return 0.0
            return (self.rhq[0] - self.lhq[0]) * 0.5
        else:
            return self.rhq[0]

20.12

假设S'(r1, c1, r2, c2)是(r1,c1)到(r2,c2)这个区域的和，而S(r, c) = S'(0,0,r,c)的话，那么有公式：

• S(r2,c2) - S(r1,c2) - S(r2,c1) + S(r1,c1) = S'(r1+1,c1+1,r2,c2)
• S(r,c) = 0 if r < 0 or c < 0

int m[N][N];
int dp[N][N]; // dp[s][e] = sum from (0,0) to (s,e).

int v = INT_MIN;
for(int rs=0;rs<N;rs++) {
  for(int re=rs;re<N;re++) {
    for(int cs=0;cs<N;cs++) {
      for(int ce=0;ce<N;ce++) {
        int u = sum(rs,cs,re,ce);
        if(u > v) v = u;
      }
    }
  }
}

int X(int a,int b) {
  if(a < 0 || b < 0) return 0;
  return dp[a][b];
}

int sum(int rs,int cs,int re,int ce) {
  int a = X(rs-1,cs-1);
  int b = X(rs-1,ce) - X(rs-1,cs-1);
  int c = X(re,cs-1) - X(rs-1,cs-1);
  int d = X(re,ce);
  return d - a - b - c;
}