Trước em hẹn lịch pv vòng 2 (vòng phone thuật toán) với 1 recruiter google mà có vẻ bị nó bùng, đến ngày thì nó bảo submit cv trên trang career của google.
Đã phân tích xong thì bài mình ra là Onlogn, vẫn may mắn pass testcase của leetcode á bác
Ý là kết quả của vòng thuật toán, chiếm không đến 30% kết quả chung của quá trình phỏng vấn. Nhưng newbie hay focus quá vào thuật toán vì vòng này mang tính sàng lọc, không làm được = toang.
Thì ý em là 90% công ty thuật toán chiếm 0% kết quả, hoặc chỉ cho vài câu rất dễ để sàng lọc, không cần học gì cũng qua.
Mình pvan trước giờ cũng gần 9 công ty, đi làm 3 công ty, trong đó hầu hết 7 công ty là phỏng vấn live coding trên máy và viết trên bảng, cãi lộn với interviewers (basic app + algo), từ easy tới medium, tới hard, còn lại 2 công ty chỉ hỏi chung chung (3, 4 năm trc)
from typing import List
class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
nums, prev = set(nums), dict()
def find(n):
if n in prev and prev[n] != n-1:
return prev[n]
if n-1 in nums:
prev[n] = find(n-1)
return prev[n]
else:
return n-1
best = 0
for i in nums:
best = max(best, i - find(i))
print("i: {}, prev: {}".format(i, prev))
return best
nums = [100, 4, 200, 1, 3, 2]
s = Solution()
s.longestConsecutive(nums)i: 1, prev: {}
i: 2, prev: {2: 0}
i: 3, prev: {2: 0, 3: 0}
i: 100, prev: {2: 0, 3: 0}
i: 4, prev: {2: 0, 3: 0, 4: 0}
i: 200, prev: {2: 0, 3: 0, 4: 0}
. Vì prev thì 4:3, 3:2, 2:1 mới hợp lí chứ nhỉ
yes, tên sai đó. Thường thì tên là parent.Python:from typing import List class Solution: def longestConsecutive(self, nums: List[int]) -> int: nums, prev = set(nums), dict() def find(n): if n in prev and prev[n] != n-1: return prev[n] if n-1 in nums: prev[n] = find(n-1) return prev[n] else: return n-1 best = 0 for i in nums: best = max(best, i - find(i)) print("i: {}, prev: {}".format(i, prev)) return best nums = [100, 4, 200, 1, 3, 2] s = Solution() s.longestConsecutive(nums)
Code:i: 1, prev: {} i: 2, prev: {2: 0} i: 3, prev: {2: 0, 3: 0} i: 100, prev: {2: 0, 3: 0} i: 4, prev: {2: 0, 3: 0, 4: 0} i: 200, prev: {2: 0, 3: 0, 4: 0}
Bác giải thích cho em về cái Union sao nó lại hoạt động vậy, trên đây là thuật toán tinh giản, em copy được ở discussion.
Nó chỉ bao gồm mỗi một function find và một dict tên là prev. Nhưng lúc print các kết quả prev ra thì thấy không đúng với cái tên của nó nhỉ. Ví dụ prev của 4 lại ra 0, prev của 3 cũng là 0, prev của 2 cũng là 0
cái prev\[i\] chính là số đầu tiên trong dãy liên tiếp đó bác (prev\[i\]...i] -> độ dài của dãy là i - prev\[i\]. tại mỗi bước họ tìm xem số đầu tiên của dãy tăng mà kết thúc là i là bao nhiêu, i này tìm trong setPython:from typing import List class Solution: def longestConsecutive(self, nums: List[int]) -> int: nums, prev = set(nums), dict() def find(n): if n in prev and prev[n] != n-1: return prev[n] if n-1 in nums: prev[n] = find(n-1) return prev[n] else: return n-1 best = 0 for i in nums: best = max(best, i - find(i)) print("i: {}, prev: {}".format(i, prev)) return best nums = [100, 4, 200, 1, 3, 2] s = Solution() s.longestConsecutive(nums)
Code:i: 1, prev: {} i: 2, prev: {2: 0} i: 3, prev: {2: 0, 3: 0} i: 100, prev: {2: 0, 3: 0} i: 4, prev: {2: 0, 3: 0, 4: 0} i: 200, prev: {2: 0, 3: 0, 4: 0}
Bác giải thích cho em về cái Union sao nó lại hoạt động vậy, trên đây là thuật toán tinh giản, em copy được ở discussion.
Nó chỉ bao gồm mỗi một function find và một dict tên là prev. Nhưng lúc print các kết quả prev ra thì thấy không đúng với cái tên của nó nhỉ. Ví dụ prev của 4 lại ra 0, prev của 3 cũng là 0, prev của 2 cũng là 0
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
std::unordered_map<int, int> len;
int maxl = 0;
for (auto i : nums) {
auto ii = &len[i];
if (*ii > 0) continue;
auto l = (*ii = 1);
int *s_end = ii, *s_begin = ii;
if (auto it = len.find(i+1); it != end(len)) {
s_end = &((it->second == 1) ? it : len.find(i + it->second))->second;
l += it->second;
};
if (auto it = len.find(i-1); it != end(len)) {
s_begin = &((it->second == 1) ? it : len.find(i - it->second))->second;
l += it->second;
};
*s_begin = *s_end = l;
if (l > maxl) maxl = l;
}
return maxl;
}
};
auto _ = [](){
cin.sync_with_stdio(false);
cout.sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
return 0;
}();class Solution {
public:
int longestConsecutive(vector<int>& nums) {
if (nums.empty()) return 0;
std::transform(begin(nums), end(nums), begin(nums), [](int i) { return i + (1<<30); });
countSort0(nums);
countSort1(nums);
//std::cin.get();
int maxl = 0;
auto sz = nums.size();
auto end = std::begin(output) + sz;
auto it = begin(output);
while(it != end) {
auto it2 = it + 1;
auto l = 1;
while (it2 != end) {
auto d = *it2 - *(it2 - 1);
if (d == 1) ++l;
else if(d > 1) break;
++it2;
}
if (l > maxl)
maxl = l;
it = it2;
}
return maxl;
}
private:
// count sort for 16 lsd bits
void countSort0(vector<int>& a) {
std::memset(count.data(), 0, count.size() * sizeof(int));
for (auto i : a) ++count[i & 0xffff];
for (int i = 1; i < 65536; ++i) count[i] += count[i-1];
for (auto it = a.rbegin(); it != a.rend(); ++it) {
output[--count[*it & 0xffff]] = *it;
}
std::memcpy(a.data(), output.data(), sizeof(int) * a.size());
}
// count sort for 16 msd bits
void countSort1(vector<int>& a) {
std::memset(count.data(), 0, count.size() * sizeof(int));
for (auto i : a) ++count[(i >> 16) & 0xffff];
for (int i = 1; i < 65536; ++i) count[i] += count[i-1];
for (auto it = a.rbegin(); it != a.rend(); ++it) {
output[--count[(*it >> 16) & 0xffff]] = *it;
}
}
static std::array<int, 65536> count;
static std::array<int, 100'000> output;
};
std::array<int, 65536> Solution::count{};
std::array<int, 100'000> Solution::output{};
auto _ = [](){
std::cin.sync_with_stdio(false);
std::cout.sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
return 0;
}();- Radix sort có thể dùng cho nhiều kiểu khác nữa. Chỉ cần đảm bảo điều kiện: gồm nhiều trường integer, các trường có độ ưu tiên cho trước.
public int LongestConsecutive(int[] nums) {
if(nums.Length <= 1) return nums.Length;
Array.Sort(nums);
int result = 0;
int count = 1;
for(int i = 0; i < nums.Length - 1; i++){
if(nums[i+1] == nums[i] + 1){
count++;
}
if(nums[i+1] > nums[i] + 1){
count = 1;
}
result = Math.Max(result, count);
}
return result;
}65536 này lấy ở đâu vậy ạ, em thấy radix sort mô tả là sort trên chữ số từ phải sang trái. Cách cài đặt của bác hơi khác thì phải
65536 = 2^16.
class Solution {
public:
unordered_map<int,bool>vis;
unordered_map<int,bool>have;
unordered_map<int,int>dp;
void dfs(int u,int x){
vis[u]=true;
if(have[u-1]){
if(vis[u-1]) dp[x]+=dp[u-1];
else{
dp[x]++;
dfs(u-1,x);
}
}
}
int longestConsecutive(vector<int>& nums) {
for(auto x:nums) have[x]=true;
for(auto x:nums){
if(!vis[x]){
dp[x]=1;
dfs(x,x);
}
}
int res=0;
for(auto x:nums) res=max(res,dp[x]);
return res;
}
};Vậy là bác sort trên bit à, thế thì sort được cả float hay âm/dương thật, hay quá
class Solution {
public:
int fibo[31] = {
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55,
89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765,
10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040
};
int fib(int n) {
return fibo[n];
}
};
