这次的interview questions有一道我觉得很有意思的题，之前没有遇到过。

Inorder traversal with constant extra space. Design an algorithm to perform an inorder traversal of a binary search tree using only a constant amount of extra space.

这道题是Leetcode #94题 Binary Tree Inorder Traversal, 在dicuss中大家的方法大多都是recurssion和iterative的。iterative的话用一个栈解决就可以了。但是没有想到可以用O(1)的空间复杂度就可以解决这个问题。查阅了一些资料之后发现这其实是Morris Traversal的应用。

经过了申请学校、实习和毕设之后又能好好刷课了…接着从上次的讲起，week3的interview questions主要和merge sort相关。

Merging with smaller auxiliary array. Suppose that the subarray a[0] to a[n−1] is sorted and the subarray a[n] to a[2∗n−1] is sorted. How can you merge the two subarrays so that a[0] to a[2∗n−1] is sorted using an auxiliary array of length n (instead of 2n)?

两个长度相同、排好序的数组只需要大小为一半的辅助数组。将a[0]-a[n-1]放入辅助数组中，再使用两个指针进行排序即可。

Counting inversions. An inversion in an array a[] is a pair of entries a[i] and a[j] such that i a[j]. Given an array, design a linearithmic algorithm to count the number of inversions.

这道题在leetcode上出现过，第一次碰到可能觉得很tricky，其实就是在merge sort的时候计数即可。

Shuffling a linked list. Given a singly-linked list containing nnn items, rearrange the items uniformly at random. Your algorithm should consume a logarithmic (or constant) amount of extra memory and run in time proportional to nlogn in the worst case.

参考了一下hint，大概思路就是在merge sort的时候不按照大小排序，而是随机挑选。具体实现我先占个坑。

JAVA类装载方式

1. 隐式装载 程序在运行过程中当碰到通过new 等方式生成对象时，隐式调用类装载器加载对应的类到jvm中
2. 显式装载 通过class.forname()等方法，显式加载需要的类

类加载的动态性体现

一个应用程序总是由n多个类组成，Java程序启动时，并不是一次把所有的类全部加载后再运行，它总是先把保证程序运行的基础类一次性加载到jvm中，其它类等到jvm用到的时候再加载，这样的好处是节省了内存的开销，因为java最早就是为嵌入式系统而设计的，内存宝贵，这是一种可以理解的机制，而用到时再加载这也是java动态性的一种体现

本周的主题是Collinear Points, 作业巧妙地把模式识别的基础和排序结合在一起。在给出的点坐标的情况下，返回练成线的个数和起点终点。
课程Speficication

作业分为3个部分
1) Point.java 定义Point类，完成相关操作
2) BruteCollinearPoints.java 通过暴力算法得到有几条连成的线
3) 与2)对比的，有了FastCollinearPoints.java，我们需要自己设计算法，提高时间效率

相比于Week1的作业，week2的比较简单，但是近几年在Permulation文件中设置了一个Bonus也是将难度提升了不少。

链接：课程的Specification

此次作业的目的是实现double-ended queue 和一个randomized queue。

之前接触到一道面试题大概是这样的：

给你一个大文件，里面每一行包含一个字符串，设计一种算法随机返回k个字符串，要求每一个字符串返回的概率相同.

果断选择看下一题… 而最近在做Algorithm part1 week2的作业中bonus竟然涉及到了这个问题，没想到竟然是一种算法。于是学习了一番，并再次感叹Algorithm真是门神课…

在博文Use linked list&array to create stack&queue 中，提到了对象游离。到底什么是对象游离呢？
本文转自 CSDN LuodiJack博主的一篇博文 Java对象游离1
具体代码抽象成如下：

1
2
3
4
5
6
7

public Item pop(){
    //删除栈顶元素
    Item item = a[--N];
    a[N] = null; //避免对象游离
    ...
    return item;
}

使用链表和数组来实现栈和队列是一个很基本的问题。在Algorithm的课上老师提到了这一点，因此我花了一点时间重新实现了一遍。老师在课上没有提到用ResizingArray来实现队列的方法，“Not difficult, but
a definitely tricky programming exercise that people are welcome to try”，因此我也尝试了一下。

最近又回顾了一遍Coursera上的神课，普林斯顿大学教授Robert Sedgewick主讲的Algorithms. Week1中interview questions已经贴出来了，今天给大家分享的是Week1的assignment:Percolation.

链接：课程的Specification

这个作业的目的是通过蒙特卡洛来估算一个由n*n格子组成系统的渗透阈值。