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

premature optimization is the root of all evil
cái bài đòi đảo LL kia mà giải O(1) mem là premature optimization nhóe
Xv0BtTR.png

chạy đúng là được, chạy tối ưu tốc độ, bộ nhớ là chuyện khác ko liên quan tới chuyện đúng sai
Xv0BtTR.png
 
thì tất nhiên bài nào cũng có đủ kiểu giải.

Quan trọng là giải theo mục đích gì?

Nếu để ôn pv thì nên làm theo kiểu O(1) memory.

Còn nếu làm để pass test case thôi thì làm kiểu gì chả dc :)
 
Bài hôm nay độ khó hard và nếu phải tự implement thì đúng là chua thật, nhưng với python full lib thì cũng chỉ là muỗi:

Python:
from sortedcontainers import SortedList
class Solution:
    def countSmaller(self, nums: List[int]) -> List[int]:
        sl = SortedList()
        counts = []
        for i in range(len(nums) - 1, -1, -1):
            sl.add(nums[i])
            counts.append(sl.bisect_left(nums[i]))
           
        counts.reverse()
        return counts
 
Bài hôm nay mà accept O(n^2) thì nó lại là bài easy rồi, nên thử ngồi nghĩ cách O(nlogn). Có 1 cách là Binary Indexed Tree như bác ở trên nói, với ngồi nghĩ mãi cách sort xem có được không thì thấy merge sort có thể áp dụng đc trong bài này.
  • Lưu các số trong nums dưới dạng tuple(value, index) và 1 mảng để count số phần tử bên phải nhỏ hơn số hiện tại, mặc định ban đầu là 0.
  • Merge sort với value từ nhỏ đến lớn.
  • Trong khi merge 2 array lại với nhau, tạo 1 biến đếm = 0, mỗi khi pick 1 số ở array bên phải thì cho biến đếm tăng thêm 1. Mỗi khi pick 1 số ở array bên trái thì update lại count[index] += biến đếm đó. Khi có 2 số ở 2 array = nhau thì ưu tiên pick số ở array bên trái.
  • Return ra vector chứa count.

Time: Onlogn

https://leetcode.com/submissions/detail/754202606/
 
Bài hôm nay mà accept O(n^2) thì nó lại là bài easy rồi, nên thử ngồi nghĩ cách O(nlogn). Có 1 cách là Binary Indexed Tree như bác ở trên nói, với ngồi nghĩ mãi cách sort xem có được không thì thấy merge sort có thể áp dụng đc trong bài này.
  • Lưu các số trong nums dưới dạng tuple(value, index) và 1 mảng để count số phần tử bên phải nhỏ hơn số hiện tại, mặc định ban đầu là 0.
  • Merge sort với value từ nhỏ đến lớn.
  • Trong khi merge 2 array lại với nhau, tạo 1 biến đếm = 0, mỗi khi pick 1 số ở array bên phải thì cho biến đếm tăng thêm 1. Mỗi khi pick 1 số ở array bên trái thì update lại count[index] += biến đếm đó. Khi có 2 số ở 2 array = nhau thì ưu tiên pick số ở array bên trái.
  • Return ra vector chứa count.

Time: Onlogn

https://leetcode.com/submissions/detail/754202606/
Bài này khó vãi nồi, sau gần 45p ko tìm dc hướngsau khi 4 lần error, e thấy solution của thím thì e tự implement thêm theo cách cũ thử, chỉ khác là e sử dụng Merge sort nghịch và delta biến thiên giữa nums và nums[i + x], ban đầu e sử dụng Merge thuận thì lại phải loop thêm 1 vòng check biến nums + delta
Cuối cùng loop kqua để reverse lại
Sấp mặt 6 lần lỗi mới accepted =((

Screen Shot 2022-07-23 at 12.00.48.png
 
Bài hôm nay độ khó hard và nếu phải tự implement thì đúng là chua thật, nhưng với python full lib thì cũng chỉ là muỗi:

Python:
from sortedcontainers import SortedList
class Solution:
    def countSmaller(self, nums: List[int]) -> List[int]:
        sl = SortedList()
        counts = []
        for i in range(len(nums) - 1, -1, -1):
            sl.add(nums[i])
            counts.append(sl.bisect_left(nums[i]))
          
        counts.reverse()
        return counts
Ủa python ngắn vậy hả anh :eek:
 
Đấy là lười chứ đú bẩn 1-2 line còn được. Nói chung là python run-time chậm nhưng đc cái nhiều lib, code ngắn và gọn gàng. Mấy ng k care micro-optimization như mềnh hay xài khỏe não.
Mình làm xong bài này bằng Java mình bỏ bữa trưa hôm nay thím ạ =((
 
Tự nhiên dc thứ 7 nghỉ ngơi tí cho tinh thần vui vẻ, làm cái bài hard này đột nhiên trầm cảm, rơi vào trạng thái tĩnh lặng mất =((
 
Tự nhiên dc thứ 7 nghỉ ngơi tí cho tinh thần vui vẻ, làm cái bài hard này đột nhiên trầm cảm, rơi vào trạng thái tĩnh lặng mất =((
Đồng cảm, mình cũng stuck 2 bài mất cả tuần chưa ra, đến giờ vẫn vậy. Mỗi lần open mylist lên thấy 2 con hàng đó là lại trầm cảm T_T.
 
các bác siêng vl :(
Siêng gì đâu bác, cũng là nghĩa vụ, trách nhiệm với miếng cơm manh áo thôi :LOL:À nói mới nhớ, mới pvan 2 cty ngoài, 1 đã pass, 1 đợi kqua, nhìn lại đề 5 câu chả khác leetcode chỗ nào :LOL:
cũng may rèn tí leetcode nên vô livecoding tự tin hơn tí :byebye:
 
Siêng gì đâu bác, cũng là nghĩa vụ, trách nhiệm với miếng cơm manh áo thôi :LOL:À nói mới nhớ, mới pvan 2 cty ngoài, 1 đã pass, 1 đợi kqua, nhìn lại đề 5 câu chả khác leetcode chỗ nào :LOL:
cũng may rèn tí leetcode nên vô livecoding tự tin hơn tí :byebye:
lương lậu thế nào bác :shame::shame:
 
lương lậu thế nào bác :shame::shame:
Cũng ổn bác :love: , nói chung tiền bạc không lo nữa nếu đạt high commitment và deadline breakpoint target :p , nhưng chắc sẽ học hỏi tụi Tàu nhiều tại cty toàn mấy thằng DH Thanh Hoa, BắcĐại ng Trung, Sin, Mã,Ấn là nhiều, HR bảo tụi nó giỏi lắm,
 
Siêng gì đâu bác, cũng là nghĩa vụ, trách nhiệm với miếng cơm manh áo thôi :LOL:À nói mới nhớ, mới pvan 2 cty ngoài, 1 đã pass, 1 đợi kqua, nhìn lại đề 5 câu chả khác leetcode chỗ nào :LOL:
cũng may rèn tí leetcode nên vô livecoding tự tin hơn tí :byebye:

Giải quyết xong được là hạnh phúc rồi thím, chứ mình làm mấy bài stuck mãi nó cứ ở trong đầu mới ức chế. Btw thím phỏng vấn công ty ở VN hay nước ngoài đó? Mình ở HN cũng thấy ít công ty pv LC

Sent from Samsung SM-J730G using vozFApp
 
Giải quyết xong được là hạnh phúc rồi thím, chứ mình làm mấy bài stuck mãi nó cứ ở trong đầu mới ức chế. Btw thím phỏng vấn công ty ở VN hay nước ngoài đó? Mình ở HN cũng thấy ít công ty pv LC

Sent from Samsung SM-J730G using vozFApp
Mình pvan bên Sing với Canada thím, cty trc mình làm chain thì họ vẫn dùng leetcode để pvan (Mẽo quốc giãy chết)
 
Siêng gì đâu bác, cũng là nghĩa vụ, trách nhiệm với miếng cơm manh áo thôi :LOL:À nói mới nhớ, mới pvan 2 cty ngoài, 1 đã pass, 1 đợi kqua, nhìn lại đề 5 câu chả khác leetcode chỗ nào :LOL:
cũng may rèn tí leetcode nên vô livecoding tự tin hơn tí :byebye:
Nôn đề ra nào thím :sure:
 
Bài hôm nay độ khó hard và nếu phải tự implement thì đúng là chua thật, nhưng với python full lib thì cũng chỉ là muỗi:

Python:
from sortedcontainers import SortedList
class Solution:
    def countSmaller(self, nums: List[int]) -> List[int]:
        sl = SortedList()
        counts = []
        for i in range(len(nums) - 1, -1, -1):
            sl.add(nums[i])
            counts.append(sl.bisect_left(nums[i]))
          
        counts.reverse()
        return counts
Haizz, chắc phải học bi thòng để còn đi phỏng vấn quá, nhìn mấy dòng code kia mà ham :too_sad:
 
Cũng ổn bác :love: , nói chung tiền bạc không lo nữa nếu đạt high commitment và deadline breakpoint target :p , nhưng chắc sẽ học hỏi tụi Tàu nhiều tại cty toàn mấy thằng DH Thanh Hoa, BắcĐại ng Trung, Sin, Mã,Ấn là nhiều, HR bảo tụi nó giỏi lắm,
Ủa là sao thím nhỉ ? Pass rồi mà còn phải cạnh tranh với tụi Thanh Hoa, Bắc Đại ? Mà tụi này là quái vật rồi cạnh gì nổi ??
 
Back
Top