面试整理
2021-01-09 本文已影响0人
学而不思则罔思而不学则殆
网络工程总结
传输层使用TCP/IP协议，应用层使用HTTP，HTTPS协议。
网络协议
iOS基础总结
iOS底层总结
《iOS知识点梳理-Runloop》
《iOS知识点梳理-Runtime》
算法编程面试题
1. 判断一个单向链表是否有环？
- 快慢双指针法，快指针一次走两步，慢指针一次走一步，如果有环必会相遇
public class ListNode {
public var val: Int
public var next: ListNode?
public init(_ val: Int) {
self.val = val
self.next = nil
}
}
func validedCycleNoded(_ node: ListNode?) -> Bool {
if node == nil {
return false
}
var fast = node, slow = node
while fast != nil {
fast = fast?.next?.next
slow = slow?.next
if fast?.val == slow?.val {
return true
}
}
return false
}
- 可以使用集合（Set）来判断，来一次遍历，把所有node添加到集合中，如果有重复，则肯定要有环
2.如何计算二叉树的高度？
递归算法
/**
* Definition for a binary tree node.
* public class TreeNode {
* public var val: Int
* public var left: TreeNode?
* public var right: TreeNode?
* public init(_ val: Int) {
* self.val = val
* self.left = nil
* self.right = nil
* }
* }
*/
class Solution {
func maxDepth(_ root: TreeNode?) -> Int {
guard let root = root else {return 0;}
return max(maxDepth(root.left), maxDepth(root.right)) + 1
}
}
3. 合并两个有序数组，同时去重
func mergeSortedArray(_ a: [Int], b:[Int]) ->[Int] {
var i = 0
var j = 0
var ans = [Int]()
//合并数组
while i < a.count && j < b.count {
if a[i] > b[j] {
ans.append(b[j])
j += 1
}else if (a[i] == b[j]) {
ans.append(b[j])
j += 1
i += 1
}else {
ans.append(a[i])
i += 1
}
}
//数组a有未合并元素
while i < a.count {
ans.append(a[i])
i += 1
}
//数组b有未合并元素
while j < b.count {
ans.append(b[j])
j += 1
}
return ans
}
复制代码
4. 字符串编辑最短距离(LeeCode)
LeeCode-72.编辑距离
解法：动态规划
5. 判断括号的有效性(LeeCode)
class Solution {
func isValid(_ s: String) -> Bool {
if s.isEmpty {
return true;
}
let map = ["}":"{", ")":"(","]":"["]
var stack = [String]()
for c in s {
let key = String(c)
if key == "{" || key == "(" || key == "[" {
stack.append(key)
} else if !stack.isEmpty && map[key] == stack.last {
stack.removeLast()
} else {
return false
}
}
return stack.isEmpty
}
}
复制代码
6. 25匹马，现有5条跑道，没有计时器，要找出最快3匹马，至少要跑几场？
至少跑7场，
- 对25匹马随机分成5个组（A,B,C,D,E,F),每组跑一场，记录每一匹马在当前组中名次（第1名，第2名，第3名）（跑了五场）
- 从各个组中选取名次为第一名的马组成一组，跑一场，记录名次（第六场），本组第1名则确定了25匹马中最快的一匹马
- 选取第六场中名次为第1名的所在原来组名次为第2、3名马，选取第六场中名次为第2名的所在原来组名次第1、2名马（它自己+第2名），选取第六场中名次为第3名所在原来组名次第1名的马（它自己），组成一组，跑一场，记录名次（第七场），本场的第1、2名就是25匹马中最快的第2、3名
7. 8瓶液体，其中1瓶有毒药，毒药1小时后至死，请问最快找出毒药，需要几只老鼠？
1只老鼠可以断定2瓶液体，2^3=8，所以需要3只老鼠即可，
对液体进行编号，001，010，011，100，101，110，111
给1号老鼠喂编码个位数上是1的液体（001，011，101，111），
给2号老鼠喂编码十位数上是1的液体（010，011，110，111），
给3号老鼠喂编码百位数上是1的液体（100，101，110，111），
1小时后，
如果老鼠全活, 8号液体有毒，
如果全都死，7号液体有毒，
如果1号死，2，3活， 1号液体有毒
如果2号死， 1，3活，2号液体有毒
如果3号死，1，2活， 4号液体有毒
如果1，2号死，3活， 3号液体有毒
如果1，3号死，2活， 5号液体有毒
如果2，3号死，1活， 6号液体有毒
其他
如下结构体，大小是多少？
struct Node {
char a;
int b;
} node;
复制代码
结构体大小是8，考察结构体特性，内存对齐原则。
定义一个全局变量a = 0; 开辟两条子线程访问 a = a + 1; 各for loop 10次，a的最终结果是多少？
<=20,线程安全问题。
公司员工表(user)中有入职时间(t1)和离职时间(t2)，请编写sql语句，查询18年3月(date1)-18年6月(date2)所有在职员工人信息
select * from user where 入职时间<201806 and (离职时间 is null or离职时间>201803)。
