KK's blog

每天积累多一些

0%

Posted on Edited on Disqus:

LeetCode 006 ZigZag Conversion

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

<pre>P A H N A P L S I I G Y I R </pre>

And then read line by line: "PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows:

<pre>string convert(string text, int nRows);</pre>

convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".

题目大意：

给定字符串按如上的“Z”字锯齿形进行按行重排。

解题思路：

这是一个周期性的字符串。周期是竖+折（不含首节点）。 首节点和竖的最后一点在每周期只会出现一次，其他点会出现两次。 T=2×numRows-2(因为不含竖节点最后一点+折线上的最后一点属于另一个周期)。nT是有几个周期，即使不完成的周期也算一个。 按行遍历（实质是周期上的每个点），再按周期遍历，非顶点有两个需加入到结果中：j×T+i,(j+1)×T-i。由于周期可能不完成，只要写一个API检查边界且加入字符即可。

注意事项：

一个字符的字符串。此时T=0.直接返回原字符串。

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public String convert2(String s, int numRows) {
	StringBuffer sb = new StringBuffer();
	int T = numRows*2-2;
	if(T==0)
		return s;
	int nT = (int)Math.ceil((s.length()+0.0)/T);
	for(int i=0;i<numRows;i++){
		for(int j=0;j<nT;j++){
			if(i==0 || i==numRows-1)
				sb.append(addChar(s, j*T+i));
			else{
				sb.append(addChar(s, j*T+i));
				sb.append(addChar(s, (j+1)*T-i));
			}
		}
	}
	return sb.toString();
}

public String addChar(String s, int index){
	String a = "";
	if(index<s.length())
		return s.substring(index, index+1);
	return a;
}

算法分析：

时间复杂度为O(n)，空间复杂度O(1)。

Posted on Edited on Disqus:

LeetCode 123 Best Time to Buy and Sell Stock III

Say you have an array for which the i<sup>th</sup> element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most two transactions.

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

题目大意：

假设你有一个数组，它的第i个元素是一支给定的股票在第i天的价格。设计一个算法来找到最大的利润。你最多可以完成两笔交易。

解题思路：

回顾一下前两题：只能进行一次交易和可以无数次交易。分别是用(min, p),sum(prices[i]-prices[i-1])的方法。这题很明显比较接近只能进行一次交易的题。
如果考虑将此问题分为两个子问题(Divide & Conquer,二分法)，prices[0,k]和prices[k,n-1]，只要将k取遍所有值就得到解。

Java代码：

1
2
3
4
5
6
7
8
9
10
public int maxProfit(int[] prices) {
	int max = 0;
	for(int i=0;i<prices.length;i++){
		int p = maxProfitSingle(Arrays.copyOfRange(prices,0, i+1))
				+ maxProfitSingle(Arrays.copyOfRange(prices,i, prices.length));
		if(max<p)
			max = p;
	}
	return max;
}

算法分析：

时间复杂度为<code>O(n<sup>2</sup>)</code>，空间复杂度O(1)。

上述解法并非最优，因为计算prices[0,k-1]到prices[0,k]时候再次重复计算用了O(n)，但由只能进行一次交易题解中知道，其实O(1)可得，只要在计算过程中把结果存入left数组中即可。
下面的难点在于计算prices[k,n-1]。右端点固定，从右到左计算，所以其实是只能进行一次交易题解的逆运算并把结果存入到right数组。区别是(max, p)。最后只要遍历left[k]+right[k],即可得到最大利润。

注意事项：

  1. 数组长度为0。
  2. 二分法
  3. 用数组存储重复计算结果(DP)

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public int maxProfit(int[] prices) {
	if(prices.length==0)
		return 0;
	//前i天最大利润，并非需要第i天卖出
	int[] left = new int[prices.length];
	int[] right = new int[prices.length];
	
	int min = prices[0], maxPL = 0;
	for(int i=0;i<prices.length;i++){
		int p = prices[i] - min;
		if(maxPL<p)
			maxPL = p;
		left[i] = maxPL;
		if(min>prices[i])
			min=prices[i];
	}
	int max=prices[prices.length-1],maxPR=0;
	for(int j=prices.length-1;j>=0;j--){
		int p=max-prices[j];
		if(maxPR<p)
			maxPR = p;
		right[j] = maxPR;
		if(max<prices[j])
			max=prices[j];
	}
	int maxP = 0;
	for(int k=0;k<prices.length;k++){
		if(maxP<left[k]+right[k])
			maxP = left[k]+right[k];
	}
	return maxP;
}

算法分析：

时间复杂度为<code>O(n)</code>，空间复杂度O(n)。

相关题目：

LeetCode 121 Best Time to Buy and Sell Stock
LeetCode 122 Best Time to Buy and Sell Stock II LeetCode 309 Best Time to Buy and Sell Stock with Cooldown LeetCode 123 Best Time to Buy and Sell Stock III

Posted on Edited on Disqus:

常用知识点

类型 函数名 作用 输入参数 返回值 例子
String split 根据输入参数分拆成字符串数组 String String[] String[] tokens = s.split(" ");
String trim 将前后空格去掉 N/A String s = s.trim()
String toCharArray 将字符串变成字符数组 N/A char char[] a = s.toCharArray()
String charAt 取某字符 int char num1.charAt(i)
String length 取某字符长度 int int num1.length()
String equals 判断相等 String boolean "".equals(str)
String substring 取某字符[beginIdx, endIdx)子串 int, int String "smiles".substring(1,5)->"mile"
Integer parseInt 字符串变整型 String int Integer.parseInt("2"); Integer.parseInt("100", 2) -> 4，任意进制数转为10进制。
Integer Integer.MIN_VALUE 整型最小值 N/A int Integer.MIN_VALUE
Integer Integer.toString 整型->String int String Integer.toString(root.val)
StringBuilder append 将新字符（串）加入到末尾 String或char N/A sb.append("abc")
StringBuilder new StringBuilder() 新建这个类当然也将目前字符串清空 N/A N/A sb=new StringBuilder()
StringBuilder reverse 反转 N/A StringBuilder sb.reverse()
StringBuilder toString StringBuilder变成字符串 N/A String sb.reverse().toString()
StringBuilder deleteCharAt StringBuilder删除某字符 N/A int sb.deleteCharAt(sb.length() - 1);
Arrays length 数组长度 N/A int ary.length
Arrays sort 对数组正(逆)排序 T[] N/A Arrays.sort(nums1); Arrays.sort(nums1,Collections.reverseOrder()); Arrays.sort(nums1,new Comparator<int[]>(){});
Arrays asList 包装类型数组转化成List T[] List Arrays.asList(ary), ary为Integer数组或者常量 List: Arrays.asList("a", "b");
Arrays stream 基本类型数组转化成List N/A N/A List<Integer> re = Arrays.stream(ints).boxed() .collect(Collectors.toList())
Arrays N/A 去重 int[] int[] Set<Integer> set = new HashSet<>(list);set->int[]
Collections sort 对List排序 List N/A Collections.sort(list); Collections.sort(l, Collections.reverseOrder());
ArrayList new ArrayList<>() 新建List N/A List List<Integer> l = new ArrayList<>()
ArrayList stream List转为基本类型数组 List int[] int[] re = l.stream().mapToInt(i->i).toArray()
ArrayList stream List转为Object类型数组 List Integer[] Integer[] re = l.toArray(new Integer[0]);
ArrayList add 把一个元素加入到List l中 List N/A l.add("pen");
ArrayList addAll 把一个List的所有元素加入到另一个中 List N/A l2.addAll(l);
ArrayList get 返回给定的下标对应的元素 List T l.get(2);
ArrayList remove 把给定下标的元素从List l中删除 List N/A l.remove(2);
ArrayList remove 把第一个出现的元素从List l中删除 List N/A l.remove("pen");
ArrayList size 大小 List int l.size();
ArrayList reverse 反转 List N/A Collections.reverse(l);
LinkedList add 加到末尾 T N/a ll.add(2);
LinkedList remove 头部删除 N/A T ll.remove();
LinkedList addFirst 加到头部 T N/A ll.addFirst(2);
LinkedList removeLast 末尾删除 N/A T ll.removeLast();
Queue new LinkedList<Integer>() 新建/复制队列 N/A Queue Queue<Integer> q = new LinkedList<>(q2)
Queue offer 不抛异常的加入尾元素 T N/A q.offer(5)
Queue poll 不抛异常的取出头元素 N/A T Integer i = q.poll()
Queue peek 不抛异常的看看头元素 N/A T Integer i = q.peek()
Stack new Stack 新建栈 N/A Stack Stack<Integer> s = new Stack<>()
Stack peek 获取栈顶元素但不出栈 N/A T Integer i = s.peek()
Stack pop 获取栈顶元素且出栈 N/A T Integer i = s.pop()
Stack push 加入 T N/A s.push(5)
Stack isEmpty 是否为空 N/A boolean s.isEmpty()
HashMap new HashMap 新建哈希表 N/A Map Map<Character, Integer> m = new HashMap<>()
HashMap get 获取 T T m.get('a')
HashMap put 加入 T,T N/A m.put('a',5)
HashMap containsKey 是否含有某个key T boolean m.containsKey('a')
HashMap get,put 更新key对应的value N/A N/A m.put('a',m.get('a')+1)
Map Map.of Map常量 N/A Map Map.of(2, "abc", 3, "def");
Iterator Iterator entrySet N/A N/A Iterator it = map.entrySet().iterator();
Iterator Iterator keySet N/A N/A Iterator it = map.keySet().iterator();
Iterator hasNext 有无下一个元素 N/A N/A while(it.hasNext())
Iterator next 下一个元素 N/A N/A Map.Entry pair = (Map.Entry)it.next()
Map.Entry getValue, getKey 得到key, Value N/A N/A pair.getValue(), pair.getKey()
HashSet new HashSet 新建哈希集 N/A Set Set<Character> m = new HashSet<>()
HashSet add 加入 T N/A m.add('a')
HashSet remove 删除 T N/A m.remove('a')
HashSet contains 是否含有某个元素 T boolean m.contains('a')
PriorityQueue offer,poll,peek 与Queue相同 N/A N/A N/A
PriorityQueue Comparator k大小的heap N/A N/A 见下 

1
2
3
4
5
6
7
8
PriorityQueue<Node> minHeap = new PriorityQueue<Node>(k,
				new Comparator<Node>() {
					@Override
					public int compare(Node o1, Node o2) {
						return o1.value - o2.value;
					}
				}
		);

Arrays的二分法： 若找不到，返回比tgt大的数的下标数组长度的负值-1。 

1
2
3
4
5
6
7
8
int[] lis = new int[len];
int index = Arrays.binarySearch(lis, 0, len, tgt);
if(index < 0) {
	index = -index - 1;
	lis[index] = tgt;
}
else
	lis[index] = tgt;

Posted on Edited on Disqus:

题目大意：

生成唯一ID如用户ID，订单ID。

解题思路：

基本思路是将所有网站映射到一个整数。 三大核心需求：

  1. 全局唯一(unique)
  2. 按照时间粗略有序(sortable by time)。按时间查询是普遍的请求，如得到最新的1000个用户。
  3. 尽可能短。省空间，查询要更有效率。

UUID：

UUID是一类算法的统称，具体有不同的实现。UUID的有点是每台机器可以独立产生ID，理论上保证
不会重复，所以天然是分布式的，缺点是生成的ID太长，不仅占用内存，而且索引查询效率低。 4个字节表示的Unix timestamp, 3个字节表示的机器的ID 2个字节表示的进程ID 3个字节表示的计数器

多机器分别自增：

假设用8台MySQL服务器协同工作，第一台MySQL初始值是1，每次自增8，第二台MySQL初始值是2，
每次自增8，依次类推。前面用一个 round-robin load balancer 挡着，每来一个请求，由
round-robin balancer 随机地将请求发给8台MySQL中的任意一个，然后返回一个ID。
load balance可以确保请求平均分配到不同的机器，所以粗略有序，缺点是加机器要re-hash这些Id
且顺序不够稳定。

Twitter Snowflake：

原理与UUID基本一样。也是时间戳+机器id+自增序号。时间戳保证有序。

Posted on Edited on Disqus:

题目大意：

Design a chatting application like Chime

了解用户需求：

通过不断和面试官沟通，了解用户角度的需求。把这些需求逐一列举在白板上。面试者一开始会刻意只说出1-2点。面试者通过联系实际，不够构想
一些需求，若得到确认就要写入。

  1. 用户可以单对单相互聊天(one-on-one chat)
  2. 用户可以群聊(group chat)
  3. 用户可登陆
  4. 用户可以添加好友(sending)，接受好友(accepting)，拒绝添加(rejecting). 好友相互添加(mutual)，不支持两人分别添加。
  5. 用户更新状态为offline, available, busy, don't disturb，还有个性化签名

面试者通过重新排序user life cycle更有助于理解和记忆

  1. 用户可登陆
  2. 用户可以添加好友(sending)，接受好友(accepting)，拒绝添加(rejecting)
  3. 用户可以单对单相互聊天(one-on-one chat)
  4. 用户可以群聊(group chat)
  5. 用户更新状态为offline, available, busy, don't disturb，还有个性化签名

本面试不支持以下use cases 音频会议，视频会议，文件传输

Block/Component diagram：

最简单的设计就是一系列的clients，一系列的servers，还有存储系统。
存储系统可以选择SQL或者No SQL。No SQL就会更加scalable.这里可以讨论它们之间的pros和cons。 传输协议(client-server)可用Java中的Socket和ServerSocket对象，它们建立一个TCP连接，用IO Stream传输。 服务器端用多个服务器避免single point of failure。server端的memory会存一些用户状态等数据（当然它也会被持久化），这表示它需要
replicate一些数据减少不同机器之间的lookup时间。

这些大概讨论一下即可，本design主要针对OOD。

Class diagram：

从User开始写fields和key methods，因为需求就是针对用户，比较直观。当参数含有多个属性时，就应该考虑产生一个新的class，如Message，
因为Message不只内容String还有发送时间甚至styling等。 还有注意每个类是否存在状态(如UserStatus)，如果有，就要考虑用enum。

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
User:
   int id;
   String fullName;
   String alias;
   List<User> friends;
   List<GroupChat> gChats;
   List<PrivateChat> pChats;
   UserStatus s;
   
   void sign();
   void signout();
   void sendFriend(FriendRequest r);
   void acceptFriend(FriendRequest r);
   void rejectFriend(FriendRequest r);
   void setUserStatus(UserStatus s);
   PrivateChat createConversation(User b);
   GroupChat createConversation(List<User> c);
   void sendMessage(PrivateChat s, String msg);
   void sendMessage(GroupChat s, String msg);

Conversation:
   int id;
   List<User> users;
   List<Message> messages;
   
   void addMessage(Message msg);
   
PrivateChat extends Conversation:
   PrivateChat(User user, User user2);

GroupChat extends Conversation:
   void addUser(User u);
   void removeUser(User u);
   
Message:
   int id;
   Date timestamp;
   User user;//I would like to know who sent this msg
   String content;

FriendRequest:
   User from;
   User to;
   Date timestamp;
   RequestStatus Status;

UserStatus:
   String message;
   UserStatusType type;

enum RequestStatus:
   ACCEPTED, REJECTED, PENDING
 
enum UserStatusType:
   offline, available, busy, DONT_disturb

//这个类最为复杂，主要是维护用户关系和用户状态以及对应的数据库读写。这里有几个隐形需求。。可以根据alias搜索用户，  
//如果用户offline，即使是好友也不能发信息。它是singleton。
UserManager:
   HashMap<String, User> usersByAlias;
   //User类需要含有UserManager，查看要发送信息的对象是否在线，若不在线，不能发出信息。
   HashMap<Integer, User> onlineUsers;
   
   public static UserManager getInstance(){
       if (instance==null) instance = new UserManager();
	   return instance;
   }
   //用observer模式，User调用UserManager这个接口来更新onlineUsers
   void signInUser(String alias);
   void signOutUser(String alias);
   //User to的acceptFriend会调用这个函数来更新User a和User b的friend list同时更新FriendRequest的状态。
   void approveRequest(FriendRequest f);

具体实现可以选择approveRequest或者某用户发信息怎么令group chat的其他用户收到该信息sendMessage(GroupChat s, String msg)。

void sendMessage(GroupChat s, String msg){ List<User> users = s.getUsers(); }

扩展问题：

  1. 怎么知道某用户真的在线
  2. 怎么处理内存和数据冲突的信息
  3. 怎么让server scale
  4. 怎么防止DDOS攻击
Free mock interview