thảo luận Leetcode mỗi ngày

  • Người tạo chủ đề Người tạo chủ đề _Gia_Cat_Luong_
  • Ngày bắt đầu Ngày bắt đầu
Trạng thái
Không mở để trả lời thêm.
nchhnchh đã nói:
ra lập thớt thôi, này đang LC mà
Nhấp để mở rộng...
backend cũng luyện dc như lc nữa hả bác
hmSkkXF.png
 
freedom.9 đã nói:
Mấy fen phải học nhiều graph vô vì interview thường ra Graph rồi chứ DP ra mấy đâu :ah:
Bài này xưa ra contest rồi thì phải, hồi đó chưa làm được mà nay làm tí là xong rồi
Nhấp để mở rộng...
graph là cái dễ nhìn thấy hơn dp, các kỹ thuật cũng quanh đi quanh lại vài cái, nhưng mà sao implement khó thế nhỉ bác
kS0RIYB.png
 
aNotHeRNo0b đã nói:
Các bác có cơm thêm ngoài Leetcode không nhỉ, em đi xin ít bát về Backend, cook cho vui
Q8sGcLO.png
Nhấp để mở rộng...
Có mấy câu hỏi ở thớt pv : /t/694369/unread
Fire Of Heart

thảo luận Chủ đề '[Event BOX CNTT 2023] Chia sẻ kinh nghiệm phỏng vấn!!!'

Ngồi suy nghĩ tổ chức cái gì cho đông người tham gia mà không quá khó cho mọi người, cuối cùng cũng nảy ra dc 1 ý tưởng như sau:
Chia sẻ kinh nghiệm phỏng vấn.

Thể lệ như sau:
  • Bạn kể lại ngay trong thread này về những lần phỏng vấn của bạn trong năm 2021-2022.
  • Bắt buộc: Phải ghi rõ tên công ty.
  • Càng chi tiết càng tốt. Đầy đủ từng vòng từ khâu nộp cv qua đâu, coding online, home work v.v...
  • Kể lại đầy đủ những câu hỏi phỏng vấn trong lần phỏng vấn đó. Cách bạn trả lời như nào.
  • Đúc rút kinh nghiệm sau lần phỏng vấn đó. Vì sao thành công, vì sao tạch, chỗ nào trả lời tốt...
  • Ưng

Cũ hơn: coding challenge /t/27324/unread
ScaTteRedLife

thảo luận Chủ đề '[Tổng hợp] Kể về những bài coding challenge khi phỏng vấn IT'

Trước đây thì có hình thức assignment , code tầm 3-4h, deadline 1-3 ngày, và làm ở nhà, nhưng tốn thời gian quá nên dần dần bị đào thải. Vừa rồi mới biết là dạo này nhiều cty chuộng cách phỏng vấn bằng CodePair, đề bài sẽ là 1 bài toán nho nhỏ, thường code tầm dưới 20 dòng, trong vòng 20 phút đổ lại. Code chạy được thì 90% là pass vòng đó rồi, nên có thể nói đây là 1 phần rất quan trọng của bài phỏng vấn.

Đây là bài toán của mình:
- input: "123456789", phép toán: cộng, trừ
- output: chèn phép toán cộng, trừ vào input string sao cho biểu thức có kết quả là 100.
Ví dụ: -1 +...
  • Ưng
 
Sửa lần cuối:
Python: 
class Solution:
    def minimizedMaximum(self, n: int, quantities: List[int]) -> int:
        def check(x):
            return sum((q-1) // x +1 for q in quantities) <=n
        total = sum(quantities)
        left = math.ceil(total/n)
        right = max(quantities) + 1

        while left < right:
            mid = (left + right)//2
            if check(mid):
                right = mid
            else:
                left = mid + 1
        return right
 
phải đọc 2/3 hint :waaaht:
C#: 
public class Solution {
    public int MinimizedMaximum(int n, int[] quantities)
    {
        var max = quantities.Max();
        var res = max;
        var min = 1;

        while (min <= max)
        {
            var mid = (min + max) / 2;
            int count = 0;
            var flag = false;
            foreach (var q in quantities)
            {
                var plus = (int)Math.Ceiling((double)q / mid);
                if (plus > 1) flag = true;
                count += plus;
            }
            if (count > n)
            {
                min = mid + 1;
            }
            else
            {
                if(flag) res = Math.Min(res, mid);
                max = mid - 1;
            }
        }

        return res;
    }
}
 
LmaoSuVuong đã nói:
graph là cái dễ nhìn thấy hơn dp, các kỹ thuật cũng quanh đi quanh lại vài cái, nhưng mà sao implement khó thế nhỉ bác
kS0RIYB.png
Nhấp để mở rộng...
Graph e thấy implement ko khó, nhưng mà nó dài, mà thường thường lúc pv là căng thẳng vcđ nên code càng dài càng dễ dính bug, khó là khó cái đấy.
Với cả kiến thức về Graph nó cũng dễ áp dụng trong thực tế hơn là mấy cái bài greedy trick lỏ các kiểu, nên thường interview sẽ hay hỏi.
 
Python: 
class Solution:
    def minimizedMaximum(self, n: int, quantities: List[int]) -> int:
        maxQ = max(quantities)
        res = 100000000

        l, r = 1, maxQ
        while l <= r:
            mid = (l + r) // 2
          
            maxN = 0
            for q in quantities:
                maxN += ceil(q / mid)

            if maxN > n:
                l = mid + 1
            else:
                res = min(res, mid)
                r = mid - 1

        return res
 
thangkc89 đã nói:
Bài này cần gì BS bác :sexy_girl:
Hãy dùng monotonic deque + sliding window cho nhanh :beauty:
C++: 
class Solution {
public:
    int maximumRobots(vector<int>& chargeTimes, vector<int>& runningCosts, long long budget) {
        deque<int> monotonic_deque;

        long long sum_costs = 0;
        int res = 0;
        int n = chargeTimes.size();
        for (int l=0, r=0; r<n; ++r) {
            while(!monotonic_deque.empty() && chargeTimes[monotonic_deque.back()] <= chargeTimes[r]) {
                monotonic_deque.pop_back();
            }
            monotonic_deque.push_back(r);
            sum_costs += (runningCosts[r]);

            while (l <= r && chargeTimes[monotonic_deque.front()] + 1LL*(r-l+1) * sum_costs > budget) {
                sum_costs -= runningCosts[l++];
                if (l>monotonic_deque.front()) {
                    monotonic_deque.pop_front();
                }
            }
            res = max(res, r-l+1);
        }
        return res;
    }
};
Nhấp để mở rộng...
Chưa đọc bài giải nhưng mạnh dạn dự đoán xài deque mới giải đc bằng On. Đọc qua đề thì rmthaasy kẹp cái heap mà làm thì ngon chứ giải 0n chắc khó

via theNEXTvoz for iPhone
 
Mã: 
public class Solution {
    public bool IsValid(int products, int n, int[] quantities)
    {
        int temp = 0;
        for(int i = 0; i<quantities.Length; i++)
        {
            temp += (int)Math.Ceiling((double)quantities[i] / products);
        }
        return temp <= n;
    }

    public int MinimizedMaximum(int n, int[] quantities)
    {
        int mid = 0;
        int left = 1;
        int right = quantities.Max();
        int result = 0;
        while (left <= right)
        {
            mid = (left + right) / 2;
            if(IsValid(mid, n, quantities))
            {
                result = mid;
                right = mid - 1;
            }
            else
            {
                left = mid + 1;
            }
        }
        return result;
    }
}
 
seastar đã nói:
binary search thì chỉ nên follow theo 1 pattern thôi. Làm nhiều kiểu dễ bị rối hoặc sai linh tinh lắm.

Như pattern t đi học lỏm đc + và có chỉnh sửa lại thì sẽ ntn:
  • đầu tiên là có 1 hàm check, trả về true, false để thỏa mãn mấy cái điều kiện của bài toán
  • khởi tạo giá trị bên trái, bên phải, đảm bảo rằng 1 thằng nếu quăng vào hàm check thì sẽ là true, 1 thằng sẽ là false. thằng nào là true thì dùng để return về
  • đoạn vòng lặp thì chỉ để ý chỗ gán i, j thôi
C++: 
class Solution {
public:
    int minimizedMaximum(int n, vector<int>& quantities) {
        auto check = [&quantities, n] (int p) {
            if (p == 0) return false;
            return accumulate(quantities.begin(), quantities.end(), 0, [p] (int acc, int x) {
                return acc + (x + p - 1)/p;
            }) <= n;
        };
 
        int i = 0, j = *max_element(quantities.begin(), quantities.end());
        while (i < j - 1) {
            int pivot = i + (j - i)/2;
            if (check(pivot)) j = pivot;
            else i = pivot;
        }
        return j;
    }
};

1 bài bs tương tự, áp dụng pattern, chỉ cần thay đổi 1 chút là pass
C++: 
class Solution {
public:
    int maximumCandies(vector<int>& candies, long long k) {
        auto check = [&candies, k] (int p) {
            if (p == 0) return true;
            return accumulate(candies.begin(), candies.end(), 0l, [p] (long long acc, int x) {
                return acc + x/p;
            }) >= k;
        };
 
        int i = 0, j = *max_element(candies.begin(), candies.end()) + 1;
        while (i < j - 1) {
            int pivot = i + (j - i)/2;
            if (check(pivot)) i = pivot;
            else j = pivot;
        }
        return i;
    }
};

Một bài tương tự, level hard khó hơn, áp dụng pattern tương tự, chỉ cần tối ưu hàm check
C++: 
class Solution {
public:
    int maximumRobots(vector<int>& chargeTimes, vector<int>& runningCosts, long long budget) {
        auto check = [&chargeTimes, &runningCosts, budget] (int p) {
            if (p == 0) return true;
            if (p > chargeTimes.size()) return false;
            multiset<int> charge(chargeTimes.begin(), chargeTimes.begin() + p);
            long long sum_running = accumulate(runningCosts.begin(), runningCosts.begin() + p, 0ll)*p;
            long long cost = sum_running + *charge.rbegin();
            for (int i = p; i < chargeTimes.size(); ++i) {
                charge.erase(charge.find(chargeTimes[i - p]));
                charge.insert(chargeTimes[i]);
                sum_running += ((long long)runningCosts[i] - runningCosts[i-p])*p;
                cost = min(cost, sum_running + *charge.rbegin());
            }
            return cost <= budget;
        };
 
        int i = 0, j = chargeTimes.size() + 1;
        while (i < j - 1) {
            int pivot = i + (j - i)/2;
            if (check(pivot)) i = pivot;
            else j = pivot;
        }
        return i;
    }
};
Nhấp để mở rộng...
Trả bài nha mai fen, nhìn thì mình cũng thấy có thể binary search khá rõ ràng như fen nói rồi nên xài Segment tree với sliding window..
Mà đoạn tìm max trong range thì mình nghĩ có thể dùng monotonic deque để optimize cũng được cho O(n), hoặc tay to hơn thì xài 1 cái double linked list với hashmap để drop items từ left to right
Python: 
class SEG:
    def __init__(self, nums):
        self.n = len(nums)
        self.tree = [0]*self.n + nums
        for i in range(self.n - 1, -1, -1):
            self.tree[i] = max(self.tree[i*2], self.tree[i*2 + 1])
   
    def query(self, l, r):
        l += self.n  # Adjust index to the tree's leaf level
        r += self.n + 1  # Adjust index to the tree's leaf level
        ans = 0
        while l < r:
            if l & 1:  # If l is odd (right child), include it and move to the next
                ans = max(ans, self.tree[l])
                l += 1
            if r & 1:  # If r is odd (right child), include it and move to the previous
                r -= 1
                ans = max(ans, self.tree[r])
            l >>= 1  # Move l to the parent
            r >>= 1  # Move r to the parent
        return ans

   
    def update(self, i, val):
        i += self.n  # Adjust index to the tree's leaf level
        self.tree[i] = val  # Set the value at the leaf node
        while i > 1:
            i >>= 1  # Move to parent
            self.tree[i] = self.tree[i * 2] + self.tree[i * 2 + 1]  # Recompute the sum of the parent node


class Solution:
    def maximumRobots(self, chargeTimes: List[int], runningCosts: List[int], budget: int) -> int:
        seg = SEG(chargeTimes)
        left = 0
        sumRunningCost = 0
        ans = 0
        for right in range(len(chargeTimes)):
            maxChargeTime = seg.query(left, right)
            sumRunningCost += runningCosts[right]
            currentCost = maxChargeTime + (right - left + 1)*sumRunningCost
            while currentCost > budget:
                sumRunningCost -= runningCosts[left]
                left += 1
                maxChargeTime = seg.query(left, right)
                currentCost = maxChargeTime + (right - left + 1)*sumRunningCost

            ans = max(ans, right - left + 1)

        return ans
Python: 
class Solution:
    def maximumRobots(self, chargeTimes: List[int], runningCosts: List[int], budget: int) -> int:
        left = 0
        sumRunningCost = 0
        ans = 0
        dq = deque()

        for right in range(len(chargeTimes)):
            while dq and chargeTimes[right] > chargeTimes[dq[-1]]:
                dq.pop()

            dq.append(right)
            sumRunningCost += runningCosts[right]
            
            maxChargeTime = chargeTimes[dq[0]]
            currentCost = maxChargeTime + (right - left + 1) * sumRunningCost

            while currentCost > budget:
                sumRunningCost -= runningCosts[left]
                left += 1
                if dq and dq[0] < left:
                    dq.popleft()

                maxChargeTime = chargeTimes[dq[0]] if dq else 0
                currentCost = maxChargeTime + (right - left + 1) * sumRunningCost

            ans = max(ans, right - left + 1)

        return ans
 
Sửa lần cuối:
Bo_MinhAnh đã nói:
LC 2064 GoLang
C-like: 
func minimizedMaximum(n int, q []int) int {
    rs, l, r := 100000, 1, 100000
    var mid int
    for l <= r {
        mid = (l + r) >> 1
        if cd(n, mid, q) {
            rs = mid
            r = mid - 1
        } else {
            l = mid + 1
        }
    }
    return rs
}

func cd(n, num int, q []int) bool {
    var cnt int
    for i := range q {
        cnt = q[i] / num
        if q[i]%num > 0 { cnt++ }
        n -= cnt
        if n < 0 { return false }
    }
    return true
}
Nhấp để mở rộng...
LC 2064 Java 4line
Java: 
class Solution {
    public static int minimizedMaximum(int n, int[] quantities) {
        return bS(1, 100000, m -> Arrays.stream(quantities).reduce(0, (s, q) -> s + (q - 1) / m + 1) <= n);
    }

    public static int bS(int l, int r, Predicate<Integer> cd) {
        while (l < r) { int m = l + r >>> 1; if (cd.test(m)) r = m; else l = m + 1; } return l;
    }
}
 
dis bài làm cũng căng đét, lỗi lên lỗi xuống.
Nhìn cái topic còn có cả bs, monotonic stack???:ops::misdoubt::nosebleed:

JavaScript: 
function findLengthOfShortestSubarray(arr: number[]): number {
    const n = arr.length;
    let l = 0, r = n - 1;
    while (l + 1 < n && arr[l] <= arr[l + 1]) l++;
    if (l === r) return 0;
    while (r > 0 && arr[r - 1] <= arr[r]) r--;
    let res = Math.min(n - l - 1, r);
    for (let i = 0, j = r; i <= l && j < n;) {
        if (arr[i] <= arr[j]) res = Math.min(res, j - i - 1), i++;
        else j++;
    }
    return res;
};
 
LmaoSuVuong đã nói:
vz3E3Zb.gif
cả tháng r ko đụng vào contest cái lại hỏi vì sao nước biển lại mặn
Nhấp để mở rộng...
1k4 thì guardian sợ cố ca chứ cố ca làm gì còn rate mà trừ
7DSMAM1.gif

Java: 
class Solution {
    public int findLengthOfShortestSubarray(int[] arr)
    {
        var left = 0;
        var n = arr.length;
        for (int i = 1; i < n; i++)
        {
            if (arr[i] < arr[i - 1])
                break;
            else left++;
        }
        if (left == n - 1)
            return 0;
        var right = n - 1;
        for (int i = n - 2; i >= 0; i--)
        {
            if (arr[i] > arr[i + 1])
                break;
            else right--;
        }
        var minElementToRemove = Math.min(n - 1 - left, right);
        for (int i = 0, j = right; i <= left && j < n; )
        {
            if(arr[i] <= arr[j])
            {
                minElementToRemove = Math.min(minElementToRemove, j-i-1);
                i++;
            }
            else j++;
        }
        return minElementToRemove;
    }
}
 
Trạng thái
Không mở để trả lời thêm.
AD · 970×250

Chủ đề tương tự

Thach Sanh Mat Riu
Điều gì xảy ra nếu bạn uống nước chè xanh mỗi ngày?
2
Trả lời
22
Lượt xem
2K
dattenmoi
D
megume
thảo luận Hôm nay, buổi bình minh của AI robot đã đến
Trả lời
4
Lượt xem
1K
Toc Hong
Toc Hong
Lộc Tục
(Dịch) Cuộc điều tra của CBC/Radio-Canada tiết lộ công ty Việt Nam nhắm vào người Canada bằng tin giả AI để kiếm lời
2
Trả lời
30
Lượt xem
5K
dukeng995
dukeng995
Ti Amo
[Dịch] Công ty Việt Nam dùng tin giả do AI tạo ra để kiếm tiền — nhắm vào độc giả Canada
Trả lời
0
Lượt xem
1K
Ti Amo
Ti Amo
Gấu Ted
Độc giả ngày càng tin nhà báo hơn thương hiệu báo chí
Trả lời
10
Lượt xem
906
giayasics
giayasics
AD · 300×600

Thống kê chủ đề

Ngày tạo
_Gia_Cat_Luong_,
Người trả lời cuối
Vipluckystar,
Trả lời
17.755
Lượt xem
1.215.198
AD · 300×600

Chia sẻ trang này

AD · 300×600
Quay lại
Lên đầu trang