每日打卡¶
5.26 Consider a hash table of size seven, with starting index zero, and a hash function (7x+3) mod 4. Assuming the hash table is initially empty, which of the following is the contents of the table when the sequence 1, 3, 8, 10 is inserted into the table using closed hashing ? Here “__” denotes an empty location in the table. _ _ 1 _ _ _ _ 3 _ 1 _ _ _ _ 3 _ 1 8 _ _ _ 3 10 1 8 _ _ _
5.25 To implement Dijkstra’s shortest path algorithm on unweighted graphs so that it runs in linear time, the data structure to be used is？ Priority Queue
5.24 When do we consider using dynamic programming? For problem that can be solved by dividing problems to sub problems, where results of sub problems can be reused. It can be solved by recursion method but recursion here is sometimes not ideal in time complexity (too many overlapping a). Since the results can be reused. DP provides a way to record and reuse the results from previous solved sub problems, which greatly reduce the time complexity.
5.23 Analysis Complexity
5.22 Check output
5.21 Let G be a graph with n vertices and m edges. What is the tightest upper bound on the running time on Depth First Search of G? Assume that the graph is represented using adjacency matrix.
5.20 What does final mean in Java? What does finally mean in Java? final is a keyword that once a field/method/class has been designed, it’s unchangeable and un override-able. Finally is a block that always executed when the try block exits.
5.19 What is dependency injection？ https://www.freecodecamp.org/news/a-quick-intro-to-dependency-injection-what-it-is-and-when-to-use-it-7578c84fa88f/
5.18 What are the differences between overload and override? 1). The real object type in the run-time, not the reference variable's type, determines which overridden method is used at runtime. In contrast, reference type determines which overloaded method will be used at compile time. 2). Polymorphism applies to overriding, not to overloading. 3). Overriding is a run-time concept while overloading is a compile-time concept.
5.17 Which class does all the Enums directly extend? All enums extend java.lang.Enum. Enum cannot extend any other class.
5.16 Given an unsorted array. The array has this property that every element in array is at most k distance from its position in sorted array where k is a positive integer smaller than that of array. Which sorting algorithm can be easily modified for sorting this array and what is the obtainable time complexity? 收到大家的打卡啦~昨天基础题的答案是 Heap Sort，时间复杂度是O(nLogk) create a Min heap ，最小元素在第k+1位置，排序整个array，o(k)建立一个min heap,O(n-k)logk对于剩余元素，O1从min heap中取出，所以时间复杂度nlogk
5.15 What is OOPS? Could you name some important OOPS features in Java? Object Oriented Programing ,like java, is different from Process Oriented programing, like C. More focus on the object itself rather running process. we can bind the data and the function methods together in the object. Program become more flexible. Important features like inheritance, abstraction, polymorphism, Encapsulation and so on.
5.14 In a binary tree with n nodes, every node has an odd number of descendants. Every node is considered to be its own descendant. What is the number of nodes in the tree that have exactly one child? 嗯嗯，每个node的child都是2个，那node的descendent就会是0，2，4，6 and so on 如果要证明的话，可以用反正法：若存在一个只有一个孩子的结点X，假设X->right=NULL，那么由于X和X->left的descendent数目均要为奇数，但这两个值只差1，因此矛盾
5.13 What are the differences between traversing a graph and traversing a tree? tree 的遍历可以用 pre-order, in-order, post-order, level-order, 前三种都可以用 dfs 来实现，最后一种用 bfs。graph 的遍历也可以用 dfs 或者 bfs，本质上没有什么区别，需要注意的是 graph 中可能有非连通区域，需要以每个节点为起始来做一遍 bfs/dfs，当然可以使用一些 deduplicate 机制来避免重复
5.12 An unordered list contains n distinct elements. What is number of comparisons to find an element in this list that is neither maximum nor minimum? worst case是3次 复杂度是Θ(1) 需要讨论n!=length的case
5.26 Alien Dictionary https://app.laicode.io/app/problem/501
5.25 Merge Stones https://app.laicode.io/app/problem/96
5.24 Edit Distance https://app.laicode.io/app/problem/100
5.23 Largest Rectangle Of 1s https://app.laicode.io/app/problem/102
5.22 Depth Of Forest https://app.laicode.io/app/problem/323
5.21 Walls and gates https://app.laicode.io/app/problem/503
5.20 All Permutations II https://app.laicode.io/app/problem/65
5.19 Restore IP Addresses https://app.laicode.io/app/problem/147
5.18 Longest Substring With K Typed Characters https://app.laicode.io/app/problem/285
5.17 Compress String https://app.laicode.io/app/problem/173 StringBuilder in Java
5.16 Distance Of Two Nodes In Binary Tree https://app.laicode.io/app/problem/299 LCA
5.15 Longest Ascending Path Binary Tree https://app.laicode.io/app/problem/388 tree height
5.14 Merge Sort Linked List https://app.laicode.io/app/problem/29
5.13 Search In Bitonic Array https://app.laicode.io/app/problem/401 bst
5.12 Largest Container https://app.laicode.io/app/problem/201
Longest Substring With K Typed Characters¶
Given a string, return the longest contiguous substring that contains exactly k type of characters.
Return null if there does not exist such substring.
Assumptions:
The given string is not null and guaranteed to have at least k different characters. k > 0. Examples:
input = "aabcc", k = 3, output = "aabcc". input = "aabcccc", k = 2, output = "bcccc".
Analysis¶
Using sliding window to search and update the current longest string: dabaaebac: l = 0, r = 0, cnt = 0, len = 9 l = 0, r = 7: dabaaeba
Code¶
class Solution {
public:
string longest(string input, int k) {
int n = input.size();
int l = 0, r = 0, cnt = 0, len = 0;
string res = "";
int v[26];
memset(v, 0, sizeof v);
while (l < n - 1) {
while (cnt <= k && r < n) {
if (v[input[r] - 'a']++ == 0) cnt++;
r++;
}
if (cnt <= k && len < r - l) { // cnt is valid
len = r - l;
res = input.substr(l, len);
} else if (len < r - l - 1) { // cnt is invalid
len = r - l - 1;
res = input.substr(l, len);
}
if (--v[input[l] - 'a'] == 0) cnt--;
l++;
}
return res;
}
};