google面試官還會告訴你這些

遞歸書寫方法

數學歸納法中的數學/自然語言–程序語言(證明遞歸函數正確執行)

嚴格定義遞歸函數作用，包括參數，返回值，Side-effect

先一般，後特殊

每次調用必須縮小問題規模

每次問題規模縮小程度必須為1

遞歸缺點

調用堆棧Stack太深，開銷大

如果數據大，就會Stack Overflow!

不要嘗試遞歸改成非遞歸

一般化的方法仍需要棧

代碼複雜

不根本解決問題

Side-effect 函數副作用。理想的狀態是函數運行完沒有side-effect。 比較函數執行中會修改全局的一些屬性，當執行完，也要將這些全局屬性還原

鏈表

package interview.recursion;

import java.util.ArrayList;

import java.util.Arrays;

import java.util.List;

import interview.common.Node;

public class LinkedListCreator {

/**

* Creates a linked list.

*

* @param data the data to create the list

* @return head of the linked list. The returned linked list

* ends with last node with getNext() == null.

*/

publicNodecreateLinkedList(Listdata) {

if (data.isEmpty()) {

return null;

}

NodefirstNode = new Node(data.get(0));

firstNode.setNext(

createLinkedList(data.subList(1, data.size())));

return firstNode;

}

public NodecreateLargeLinkedList(int size) {

Nodeprev = null;

Nodehead = null;

for (int i = 1; i = size; i ) {

Nodenode = new Node(i);

if (prev != null) {

prev.setNext(node);

} else {

head = node;

}

prev = node;

}

return head;

}

public static void main(String[] args) {

LinkedListCreator creator = new LinkedListCreator();

Node.printLinkedList(

creator.createLinkedList(new ArrayList()));

Node.printLinkedList(

creator.createLinkedList(Arrays.asList(1)));

Node.printLinkedList(

creator.createLinkedList(Arrays.asList(1, 2, 3, 4, 5)));

}

}

鏈表反轉

package interview.recursion;

import java.util.ArrayList;

import java.util.Arrays;

import interview.common.Node;

public class LinkedListReverser {

/**

* Reverses a linked list.

*

* @param head the linked list to reverse

* @return head of the reversed linked list

*/

publicNodereverseLinkedList(Nodehead) {

// size == 0 or size == 1

if (head == null || head.getNext() == null) {

return head;

}

// 第一步(對應上圖)

NodenewHead = reverseLinkedList(head.getNext());

// 第二步

head.getNext().setNext(head);

// 第三步 over

head.setNext(null);

return newHead;

}

public static void main(String[] args) {

LinkedListCreator creator = new LinkedListCreator();

LinkedListReverser reverser = new LinkedListReverser();

Node.printLinkedList(reverser.reverseLinkedList(

creator.createLinkedList(new ArrayList())));

Node.printLinkedList(reverser.reverseLinkedList(

creator.createLinkedList(Arrays.asList(1))));

Node.printLinkedList(reverser.reverseLinkedList(

creator.createLinkedList(Arrays.asList(1, 2, 3, 4, 5))));

System.out.println(Testing large data. Expect exceptions.);

reverser.reverseLinkedList(

creator.createLargeLinkedList(1000000));

System.out.println(done);

}

}

combinations([1,2,3,4],2)

縮小問題規模

選1combinations([2,3,4],1)

不選1combinations([2,3,4],2)

package interview.recursion;

import java.util.ArrayList;

import java.util.Arrays;

import java.util.List;

public class Combinations {

/**

* Generates all combinations and output them,

* selecting n elements from data.

*/

public void combinations(

Listselected, Listdata, int n) {

if (n == 0) {

// output all selected elements

for (Integer i : selected) {

System.out.print(i);

System.out.print( );

}

System.out.println();

return;

}

if (data.isEmpty()) {

return;

}

// select element 0

selected.add(data.get(0));

combinations(selected, data.subList(1, data.size()), n - 1);

// un-select element 0

selected.remove(selected.size() - 1);

combinations(selected, data.subList(1, data.size()), n);

}

public static void main(String[] args) {

Combinations comb = new Combinations();

System.out.println(Testing normal data.);

comb.combinations(

new ArrayList(), Arrays.asList(1, 2, 3, 4), 2);

System.out.println(==========);

System.out.println(Testing empty source data.);

comb.combinations(

new ArrayList(), new ArrayList(), 2);

System.out.println(==========);

comb.combinations(

new ArrayList(), new ArrayList(), 0);

System.out.println(==========);

System.out.println(Selecting 1 and 0 elements.);

comb.combinations(

new ArrayList(), Arrays.asList(1, 2, 3, 4), 1);

System.out.println(==========);

comb.combinations(

new ArrayList(), Arrays.asList(1, 2, 3, 4), 0);

System.out.println(==========);

System.out.println(Testing large data);

comb.combinations(

new ArrayList(),

Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10), 4);

}

}

循環控制(循環不變式 loop invariant)

邊界控制

列表項

初始值

特殊值

null

空字元串

數據結構

樹的遍歷

演算法複雜度

代表最壞情況用時

f(x)=O(g(x))asx-oo 當且僅當

If(x)1≤Mlg(x)l for all x =xo 相當於高等數學中極限的定義

廣義的「極限」是指「無限靠近而永遠不能到達」的意思。數學中的「極限」指：某一個函數中的某一個變數，此變數在變大(或者變小)的永遠變化的過程中，逐漸向某一個確定的數值A不斷地逼近而「永遠不能夠重合到A」(「永遠不能夠等於A，但是取等於A『已經足夠取得高精度計算結果)的過程中，此變數的變化，被人為規定為「永遠靠近而不停止」、其有一個「不斷地極為靠近A點的趨勢」。極限是一種「變化狀態」的描述。此變數永遠趨近的值A叫做「極限值」(當然也可以用其他符號表示)。

面向對象思想

商業代碼複雜性，從用戶角度思考問題

摒棄完全基於邏輯的思維

類與對象

類的成員變數對象狀態

類的成員函數對象行為

類的靜態變數

類的靜態函數

沒有this引用，靜態變數全局唯一—份

普通函數可以引用靜態變數、函數

對象上引用靜態變數、函數會產生編譯器警告

靜態函數引用普通成員變數、函數會編譯錯誤

類的特殊函數

構造函數

equals

hashCode

toString

a.equals(b)說明a.hashCode)==b.hashCode) 必要條件

介面與實現

與類相比

由編譯器強制的一個模塊間協作的合約(Contract)

無成員變數

成員函數只有申明不能有實現

介面的申明

Java:interface BankEndPoint{……

C ：一個全部是純虛函數的類

Python/大部分動態語言：依靠注釋申明

介面和抽象類有什麼不同?

從實現角度看

抽象類可以有成員變數

抽象類可以有部分實現

抽象類不可以多重繼承，介面可以

介面強調合約

強制協作雙方無法犯錯(編譯器)

但是抽象類提供公共的實現

繼承與封裝

不可變對象 Immutable Objects

可以引用傳遞，可以緩存

線程安全

final 關鍵字

類申明類不可以被繼承

函數申明函數不可以在派生類中重寫

變數申明變數不可以指向其它對象

static final變數用於定義常量，名稱一般大寫

final關鍵字無法保證不可變性

從介面定義，類的實現上保證不可變性

Collections.unmodifiableXXX

泛型

c 虛函數表

void dispatch_work(Employee* p){

p-doWork();

dispatch_ work(manager);

設計模式(解耦和)

設計模式當初的提出就是因為GOF(Erich Gamma，Richard Helm，Ralph Johnson和John Vlissides)的博士論文(這才是真正的程序員)

再談Singleton(單例模式)

確保全局至多只有一個對象

用於：構造緩慢的對象，需要統一管理的資源

缺點：很多全局狀態，線程安全性

雙重鎖 Double checked locking

第一次check全局對象是不是null,不是null直接拿來用，如果是null,鎖住，再check一次(防止其他人在這個空擋創建)

作為Java類的靜態變數(全局只有一份，不過程序員初始化就要創建這個靜態變數，所以也就增加了初始化的時間(如果是比較緩慢的對象))

使用框架提供的能力

依賴注入

變繼承關係為組合關係(狀態模式State)

描述is-a關係

不要用繼承關係來實現復用

狀態邏輯和動作實現沒有分離。在很多的系統實現中，動作的實現代碼直接寫在狀態的邏輯當中。這帶來的後果就是系統的擴展性和維護得不到保證。

使用設計模式來實現復用

Decotator裝飾器模式

interface Runnable{

void run);

如何實現LoggingRunnable,TransactionalRunnable.…

對象如何創建

使用new來創建的缺點

編譯時必須決定創建哪個類的對象

參數意義不明確

Abstract Factory Pattern 抽象工廠

task=new Logging Task(new Coding Task);

task=taskFactory.createCodingTask); (好)

Builder Pattern 生成器

解決參數意義不明確的問題

不可變對象往往配合Builder使用

employee=new Employee(

oldEmployee.getName),15000);

employee=Employee.fromExisting(oldEmployee)

.withSalary(15000)

.build();

Beautiful Numbers

1,11，111…是beautiful的

32進位11

133進位111(選位數多的)

133 1*3 1=13

13%3=1,13/3=4

4%3=1,4/3=1

1%3=1,1/3=0

1312進位11

Nr進位111…1(k個) 求大數據集思路

N=r(k-1) r(k-2) .… r 1

N=(1-r^k)/(1-r)

假設N能轉化成k個1組成的Beautiful Number

那麼這個Beautiful Number是幾進位?r=?

因為k最多是64個(最低兩位)，但是r最多就太大了

O(nlogn) 10*8 ~= 1s

package interview.google;

import java.io.BufferedReader;

import java.io.InputStreamReader;

import java.util.Scanner;

public class BeautifulNumber {

public static void main(String[] args) {

Scanner in = new Scanner(

new BufferedReader(new InputStreamReader(System.in)));

int cases = in.nextInt();

for (int i = 1; i = cases; i) {

long n = in.nextLong();

System.out.println(Case # i :

beautiful(n));

}

}

private static long beautiful(long n) {

for (long radix = 2; radix n; radix ) {

if (isBeautiful(n, radix)) {

return radix;

}

}

throw new IllegalStateException(Should not reach here.);

}

private static boolean isBeautiful(long n, long radix) {

while (n 0) {

if (n % radix != 1) {

return false;

}

n /= radix;

}

return true;

}

}

O(logn*logn*logn) 64*64*64

package interview.google;

import java.io.BufferedReader;

import java.io.InputStreamReader;

import java.util.Scanner;

public class BeautifulNumberLarge {

public static void main(String[] args) {

Scanner in = new Scanner(

new BufferedReader(new InputStreamReader(System.in)));

int cases = in.nextInt();

for (int i = 1; i = cases; i) {

long n = in.nextLong();

System.out.println(Case # i :

beautiful(n));

}

}

private static long beautiful(long n) {

for (int bits = 64; bits = 2; bits--) {

long radix = getRadix(n, bits);

if (radix != -1) {

return radix;

}

}

throw new IllegalStateException(Should not reach here.);

}

/**

* Gets radix so that n is 111...1 (bits 1 in total) in that

* radix.

*

* @return the radix. -1 if there"s no such radix.

*/

private static long getRadix(long n, int bits) {

long minRadix = 2;

long maxRadix = n;

while (minRadix maxRadix) {

// 二分查找法

long m = minRadix (maxRadix - minRadix) / 2;

long t = convert(m, bits);

if (t == n) {

return m;

} else if (t n) {

minRadix = m 1;

} else {

maxRadix = m;

}

}

return -1;

}

/**

* Returns the value of 111...1 (bits 1 in total) in radix.

* 等比數列求和

*/

private static long convert(long radix, int bits) {

long component = 1;

long sum = 0;

for (int i = 0; i bits; i ) {

if (Long.MAX_VALUE - sum component) {

sum = Long.MAX_VALUE;

} else {

sum = component;

}

// 防止內存溢出

if (Long.MAX_VALUE / component radix) {

component = Long.MAX_VALUE;

} else {

component *= radix;

}

}

return sum;

}

}

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！