hieunm3538
Senior Member
Bài 3 4 nay khoai thật 
(( Thử lại tuần sau thui anh em
(( Thử lại tuần sau thui anh em
thảo luận Leetcode contest, đường tới Guardian
- Người tạo chủ đề freedom.9
- Ngày bắt đầu
- Trạng thái
chiyeuemthoi
Senior Member
ai lafm b2 chưa cho e xin idea với ạ lần nào mấy dạng tọa độ cũng tịt ngóm 
TLE_WA
Junior Member
Đầu tiên bạn check xem 2 hình chữ nhật có overlap không (nếu không làm được thì lên StackOverflow tra cũng có đó)ai lafm b2 chưa cho e xin idea với ạ lần nào mấy dạng tọa độ cũng tịt ngóm
Sau đó để tìm xem cạnh hình vuông lớn nhất fit được trong cái đoạn overlap đó là bao nhiêu
dx = min(rec1.xright, rec2.xright) - max(rec1.xleft, rec2.xleft)
dy = min(rec1.ytop,rec2.ytop) - max(rec1.ybot,rec2.ybot)
d = min(dx,dy)
area = d * d
dy = min(rec1.ytop,rec2.ytop) - max(rec1.ybot,rec2.ybot)
d = min(dx,dy)
area = d * d
toosriet
Junior Member
Này là solution của mình cho bài 2
Find the Largest Area of Square Inside Two Rectangles - LeetCode
Can you solve this real interview question? Find the Largest Area of Square Inside Two Rectangles - Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
Aluminum21
Junior Member
Đợt contest này bọn top làm bài giống người hơn rồi ấy.Top 1 mất 41 phút xong. thế mà câu cuối 6 điểm
Câu 2 thằng nào viết câu này làm hiểu lầm, cứ tưởng phải cộng dồn region lại. Đáng chém
hieunm3538
Senior Member
Câu 2 viết rối mù luôn 
) Tìm hình vuông lớn nhất vừa 1 đoạn giao, rôi lại tìm hình vuông to nhất trong đống đấy )))) Top 10 cũng thấy submit sai bài này 1-2 phát )
) Tìm hình vuông lớn nhất vừa 1 đoạn giao, rôi lại tìm hình vuông to nhất trong đống đấy )))) Top 10 cũng thấy submit sai bài này 1-2 phát )
freedom.9
Senior Member
Câu 2 nhìn rõ ràng là brute force rồi mà cái trick lấy max(bottomLeft) + min(topRight) ảo quá, nó đúng với tất cả các trường hợp giao nhau luôn đm.Câu 2 viết rối mù luôn
Mình lúc đầu cũng làm như thế nhưng ko thèm chứng minh là nó đúng tất cả trường hợp nên rối mù luôn. Còn đọc đề sai nữa đm.
Toang quá
via theNEXTvoz for iPhone
hieunm3538
Senior Member
Em cũng ăn 2 gậy câu này, lần đầu nhầm là tìm diện tích giao nhau nhỏ nhất, lần 2 nhầm là tìm diện tích nhỏ nhất vừa mọi vùng giao
) Mấy testcases cơ bản cũng không cover được case này, toang
dinhxahoii
Junior Member
Thấy anh em thảo luận sôi nổi quá, nếu tôi gạ một buổi offline có ai đi không?
chiyeuemthoi
Senior Member
off đấu kiếm à bác
Kể ra off một buổi vào sáng CN ở một co-working nào đó. Làm contest cùng nhau xong bàn luận có thưởng
Violet_7
Member
ai thưởng bácKể ra off một buổi vào sáng CN ở một co-working nào đó. Làm contest cùng nhau xong bàn luận có thưởng
thưởng pháo tay thôiai thưởng bác
FoolAgainDT
Senior Member
Dev gà xin ý kiến mấy bác về tối ưu giải thuật.
———-
Em có một file với định dạng mỗi dòng như sau: < key> SPACE < value>. Mục tiêu là tìm N key với giá trị lớn nhất, yêu cầu là đọc file với vài triệu dòng.
Ý tưởng của em là đọc mỗi lần 100k dòng, rồi tìm ra N key value lớn nhất, lưu ở dạng dict (đã xử lí trùng key bằng cách append value vào list). Sau đó em sẽ có được M nhóm, rồi tổng hợp M nhóm đó để N key với maximum value.
em cảm giác ý tưởng em nó đơn giản cũng không tối ưu thuật toán lắm, nhờ các bậc cao nhận trải qua rồi cho em vài gợi ý. Sẽ hậu tạ ạ
———-
Em có một file với định dạng mỗi dòng như sau: < key> SPACE < value>. Mục tiêu là tìm N key với giá trị lớn nhất, yêu cầu là đọc file với vài triệu dòng.
Ý tưởng của em là đọc mỗi lần 100k dòng, rồi tìm ra N key value lớn nhất, lưu ở dạng dict (đã xử lí trùng key bằng cách append value vào list). Sau đó em sẽ có được M nhóm, rồi tổng hợp M nhóm đó để N key với maximum value.
em cảm giác ý tưởng em nó đơn giản cũng không tối ưu thuật toán lắm, nhờ các bậc cao nhận trải qua rồi cho em vài gợi ý. Sẽ hậu tạ ạ
freedom.9
Senior Member
Mình vừa comment bên kia xong thì xóa thớt à.Dev gà xin ý kiến mấy bác về tối ưu giải thuật.
———-
Em có một file với định dạng mỗi dòng như sau: < key> SPACE < value>. Mục tiêu là tìm N key với giá trị lớn nhất, yêu cầu là đọc file với vài triệu dòng.
Ý tưởng của em là đọc mỗi lần 100k dòng, rồi tìm ra N key value lớn nhất, lưu ở dạng dict (đã xử lí trùng key bằng cách append value vào list). Sau đó em sẽ có được M nhóm, rồi tổng hợp M nhóm đó để N key với maximum value.
em cảm giác ý tưởng em nó đơn giản cũng không tối ưu thuật toán lắm, nhờ các bậc cao nhận trải qua rồi cho em vài gợi ý. Sẽ hậu tạ ạ
Xài 1 min heap lưu N phần tử, duyệt từng file add vô heap. Số phần tử trong heap mà lớn hơn N thì pop phần tử đầu tiên trong heap ra.
Time complexity O(max(10tr, nlogn) space O(n) đó là lí do tại sao nên luyện leetcode và học Dsa
via theNEXTvoz for iPhone
FoolAgainDT
Senior Member
Cám ơn thím nha, chỗ kia là duyệt từng line đúng không?Mình vừa comment bên kia xong thì xóa thớt à.
Xài 1 min heap lưu N phần tử, duyệt từng file add vô heap. Số phần tử trong heap mà lớn hơn N thì pop phần tử đầu tiên trong heap ra.
Time complexity O(max(10tr, nlogn) space O(n) đó là lí do tại sao nên luyện leetcode và học Dsa
via theNEXTvoz for iPhone
freedom.9
Senior Member
Ko duyệt từng file thì làm gì còn cách nào lấy dữ liệu từng file, dự đoán tương lai hảCám ơn thím nha, chỗ kia là duyệt từng line đúng không?
Optimize chỗ duyệt file thì muốn nhanh dùng multi threading, cho vô dó 30 cái workers, segment 10tr files thành 10tr/30 files cho nhanh.
Còn chỗ min heap thì phải xử lí concurrency để tránh conflict giữa việc đọc + lưu dữ liệu vô heap từ các threads.
- Trạng thái
Chủ đề tương tự
