Q1. (LinkedIn) Find minimum distance between two words in a string array
e.g (“the”, “quick”, “brown”, “fox”, “quick”)
distance(“fox”,”the”) = 3
distance(“quick”, “fox”) = 1
int distance(vector<string> &input, string start, string end) {
//sanity check
if (input.size() == 0) return -1;
int idx1 = -1;
int idx2 = -1;
int minl = input.size()+1;
for (int fast = 0; fast < input.size(); fast++) {
if (input[fast] == start) {
idx1 = fast;
if (idx2 != -1) {
minl = min(minl, idx1 - idx2);
}
} else if (input[fast] == end) {
idx2 = fast;
if (idx1 != -1) {
minl = min(minl, idx2 - idx1);
}
}
}
if (minl == input.size()+1) return -1;
return minl;
}
time complexity: O(n)
就是一个fast指针在前面跑，两个index来记录位置，每次只要一个index发生变化就更新global_min，其实是很简单的题目，但是第一反应总是不知道用快慢指针，而总是想到利map来记录所有的位置，如果这个题目能想到用快慢指针的思想去实时记录位置并计算最小差值，就很简单了。
Q2: There are N pieces of wood, with their lengths (in meters) stored in Bords[N]. k painters are assigned to paint all these wood together. For each piece of wood, it can only be painted by 1 and only 1 painter, and each painter can only paint contiguous woods.
Each painter can paint wood at the same speed, say 1 meter per minute. How can we find an assignments such that the total time for painting the wood is minimized.
(MINI_MAX problem)
____ ___________ | _________ …| _______
B0 B1 B3 BN-1
这个题目问题是求使得painting 时间最短的分配，一般这种最小最大问题，我们直接能想到用DP来做，但是对于DP需要知道dp 的含义和递推式子，这个题目K个人刷N个板子，M[N][K]代表N个人刷K个板子的最小时间，于是需要找到次小号的问题，我们需要求K个人粉刷的最短时间，需要从K－1个人粉刷的最短时间，如果是K－1个人粉刷前N－1个board， 那么第K个人需要粉刷第N个board，所以这样分派时间是Max(M[N-1][k-1], B[N-1]), 如果K-1个人粉刷前N-2个板子，那么第K个人需要粉刷最后两个板子，时间是Max(M[N-2][k-1], B(N-1) + B(N-2)),.......遍历所有可能的分配方式，最后取所有可能的最小值。
base case : 如果板子数比人数少的话，即N <= K, 每个板子分配一个人，最后的时间是粉刷用时最长的那个板子，即Max（board[i]）.
int minTime(vector<int> &board, int k) {
}
Q3: if-else expression.
Implement a solution to parse a ternary expression in string type into a binary tree.
Example1: a? b:c --> a
/ \
b c
Example2: a? b?c:d:e --> a
/ \
b e
/ \
c d
Example3: a? b:c?d:e -->
0 a
/ \
b c
/ \
d e
这是一道serialize tree的问题，serialize tree之前在preorder + inorder等这类题目中做过，思想是先找到root所在index，然后找root的左子树对应的index范围和root的右子树对应的index范围，这个题目中也可以用这个思想做，string 的第一个元素肯定是root，但是难点在于找左子树和右子树的对应范围。 怎么去找左子树和右子树呢？ 观察example可以发现，只要找到第一个？ 后面（不包括这个？在内的）第一个没有匹配的：， 在这个：左边的就是与这个root对应的左子树，右边的就是与这个root对应的右子树。这样的解法是O(n^2) 时间复杂度
这个题目还有一种O(n)的解法： 一直便利整个string，遇到？就把后面的扔到左子树，：的扔到右子树，只有左子树分配好后，才能去考虑右子树。
Method2 (O(n))
Node* BuildTree(const string& input, int& index) {
if (index >= input.size()) {
return NULL:
}
Node* curr = new Node(input[index]);
bool already_go_left = false;
// CASE1: Go left if possible
if (index + 1 < input.size() && string[index + 1] == ‘?’) {
already_go_left = true;
index = index + 2;
curr->left = BuildTree(input, index);
}
// CASE2: Go right if possible
if (index + 1 < input.size() && string[index + 1] == ‘:’
&& already_go_left == true) {
index = index + 2;
curr->right = BuildTree(input, index);
}
return curr;
}
Q5:
Find the smallest window in a string containing all characters of another string
Given two strings s1 and s2, find the shortest substring in s1 containing all characters in s2.
For Example:
s1= “the given test strings”sliding window
left + right + hashtable: sliding window -> vairiable length of the window.
string findString (string &input) {
int left = 0;
int right = 0;
int minl = input.size();
map<char, int> imap;
for (int i = 0; i < input.size(); i++ ) {
imap[input[i]]++;
}
int match = 0;
for ( ; right < input.size(); right++) {
if (imap.find(input[right]) != imap.end()) {
imap[input[right]]—;
if (imap[input[right]] == 0) match++;
}
while (match == imap.size()) {
minl = min(minl, right - slow+1);
for (; slow < input.size(); slow++) {
if (imap.find(input[slow]) != imap.end()) {
imap[input[slow]—;
if (imap[input[slow]] == 1) match—;
break;
}
}
}
}
return minl;
}
No comments:
Post a Comment