面試常見程式考題

常見考題包含了基礎的演算法和資料結構，以及一些其他類型的程式實作考題。

演算法

• 分治法 (Divide and conquer)
  • 二元搜索法 (Binary Search)
• 動態規劃 (Dynamic Programming)
  • 費波那西數列 (Fibonacci)
  • 上下樓梯問題 & (籃球) 得分問題
  • 最大子序列 (Maximum Subarray)
• 排序演算法 (Sorting)

資料結構

• 連結串列 (LinkedList)
• 堆疊 (Stack)
• 佇列 (Queue)

其他考古題

• 不使用暫存變數交換兩個變數 (Swap two variables without using a temporary variable)
• 計算 1 + 2 + 3 + … + N 的總和 (Sum the Integers from 1 to N)
  可以思考不同的解法，例如：
  • 使用遞迴
  • 比 O(n) 時間複雜度更快的方法
• 計算1 * 2 + 2 * 3 + … + (N - 1) * N的總和 (Write a function to calculate 1 * 2 + 2 * 3 + … + (N - 1) * N)
• 在一個未排序數列中找到最大值的方法
  我想這題很簡單應該就不用寫了，相反的找最小值也是用相同解法即可。
• 在一個未排序數列中找到第二大的值的方法 (Find second largest number in an array)
• 在一個未排序數列中找到第K大的值的方法 (Find Kth largest number in an array)
• 未排序的 n 個連續整數中少了一個，試著找到最快的方法算出少了哪一個 (How to find the missing integer in an array)
  可以思考空間複雜度為 O(1) 的解法。
• 從兩個數字中找出最大的一個而不使用判斷描述 (There are two int variables: a and b, don’t use “if”, “? :”, “switch” or other judgement statements, find out the biggest one of the two numbers)