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

bribnt

Đã tốn tiền
Mình nghĩ là vừa phát hiện được một bí ẩn của hệ thống Leetcode để giải thích cho hiện tượng submit nhiều lần có thời gian khác nhau.

Lúc nãy thử optimize bằng AVX512 bài Que diêm, build bình thường. Nhưng khi bấm Run Code thì lúc bị SIGILL, lúc thì ra được kết quả.
SIGILL là lỗi thường xảy ra khi chương trình chạy một Illegal Instruction (tập lệnh mà CPU không hỗ trợ).

Điều này có nghĩa là: Leetcode có thể sử dụng nhiều server để chạy code. Nhưng các server này lại dùng CPU khác nhau. Ở đây vừa dùng server hỗ trợ AVX512, vừa dùng server không hỗ trợ.

---

Bonus thêm lời giải 0ms faster than 100% của bài Que diêm.
Vẫn là cách backtrack ở trên nhưng dùng SIMD (AVX512 và SSE4.1) để thực hiện các phép so sánh.

https://leetcode.com/submissions/detail/745924447/

1657702047591.png
 

_Gia_Cat_Luong_

Senior Member
Mình nghĩ là vừa phát hiện được một bí ẩn của hệ thống Leetcode để giải thích cho hiện tượng submit nhiều lần có thời gian khác nhau.

Lúc nãy thử optimize bằng AVX512 bài Que diêm, build bình thường. Nhưng khi bấm Run Code thì lúc bị SIGILL, lúc thì ra được kết quả.
SIGILL là lỗi thường xảy ra khi chương trình chạy một Illegal Instruction (tập lệnh mà CPU không hỗ trợ).

Điều này có nghĩa là: Leetcode có thể sử dụng nhiều server để chạy code. Nhưng các server này lại dùng CPU khác nhau. Ở đây vừa dùng server hỗ trợ AVX512, vừa dùng server không hỗ trợ.

---

Bonus thêm lời giải 0ms faster than 100% của bài Que diêm.
Vẫn là cách backtrack ở trên nhưng dùng SIMD (AVX512 và SSE4.1) để thực hiện các phép so sánh.

https://leetcode.com/submissions/detail/745924447/

View attachment 1262609
Thím đam mê 100% ghê. Đang làm mảng nào v thím ?
 

Tuấn Mỏ

Senior Member
Mình nghĩ là vừa phát hiện được một bí ẩn của hệ thống Leetcode để giải thích cho hiện tượng submit nhiều lần có thời gian khác nhau.

Lúc nãy thử optimize bằng AVX512 bài Que diêm, build bình thường. Nhưng khi bấm Run Code thì lúc bị SIGILL, lúc thì ra được kết quả.
SIGILL là lỗi thường xảy ra khi chương trình chạy một Illegal Instruction (tập lệnh mà CPU không hỗ trợ).

Điều này có nghĩa là: Leetcode có thể sử dụng nhiều server để chạy code. Nhưng các server này lại dùng CPU khác nhau. Ở đây vừa dùng server hỗ trợ AVX512, vừa dùng server không hỗ trợ.

---

Bonus thêm lời giải 0ms faster than 100% của bài Que diêm.
Vẫn là cách backtrack ở trên nhưng dùng SIMD (AVX512 và SSE4.1) để thực hiện các phép so sánh.

https://leetcode.com/submissions/detail/745924447/

View attachment 1262609

chắc vậy đấy Bác, nếu server nào dùng CPU intel thì mới chạy đc
mà Bác áp dụng thử SIMD trên leetcode cũng hay thật đấy, mình bt chỉ cố gắng tối ưu hoá giải thuật thôi chứ ko dùng SIMD trên này
 
Mình nghĩ là vừa phát hiện được một bí ẩn của hệ thống Leetcode để giải thích cho hiện tượng submit nhiều lần có thời gian khác nhau.

Lúc nãy thử optimize bằng AVX512 bài Que diêm, build bình thường. Nhưng khi bấm Run Code thì lúc bị SIGILL, lúc thì ra được kết quả.
SIGILL là lỗi thường xảy ra khi chương trình chạy một Illegal Instruction (tập lệnh mà CPU không hỗ trợ).

Điều này có nghĩa là: Leetcode có thể sử dụng nhiều server để chạy code. Nhưng các server này lại dùng CPU khác nhau. Ở đây vừa dùng server hỗ trợ AVX512, vừa dùng server không hỗ trợ.

---

Bonus thêm lời giải 0ms faster than 100% của bài Que diêm.
Vẫn là cách backtrack ở trên nhưng dùng SIMD (AVX512 và SSE4.1) để thực hiện các phép so sánh.

https://leetcode.com/submissions/detail/745924447/

View attachment 1262609
Đỉnh quá, chuyển qua làm HFT đi thím, sẽ có nhiều đất diễn, lương cao nữa, :big_smile: .

btw, cái này cũng giải thích tại sao dùng java trên leetcode đôi khi runtime rất ảo, nhanh hơn C++ nhiều lần. Do nó có JIT, tận dụng được hết phần cứng. :big_smile:
 

Violet_7

Senior Member
14/7/2022:
  • 1 câu medium khá hay
  • Nhìn vào đề bài cho 2 mảng preorder và inorder để tạo thành cái cây -> áp dụng các tính chất của inorder và preorder
  • Tính chất inorder: Nếu biết root của 1 sub tree và mảng inorder của cái sub tree đó thì left subtree của root chính là cái phần bên trái của root trong mảng inorder
  • VD có 1 subtree
1657758725787.png

  • inorder của subtree là [1, 10, 2, 3, 7, 20, 8] -> biết được [1, 10, 2] là inorder của left subtree của root 3 và [7, 20, 8] là inorder của right subtree
  • Nhưng sẽ gặp vấn đề là sẽ ko thể biết đc trong [1, 10, 2] cái nào sẽ là root của cái subtree đó
  • Vì vậy cần tính chất của preorder, mảng preorder là [3, 10, 1, 2, 20, 7, 8]. Vì preorder là root - left - right nên 3 là root -> 10 chính là root của cái left subtree của root 3, 1 chính root của left subtree root 10. đến 1 ko còn subtree thì 2 sẽ là right của right subtree của root 10, ...
  • có thể dùng duyệt for hoặc đệ quy
  • ra đáp án
  • Code duyệt for (hơi khó hiểu vì đây là code lần đầu) https://leetcode.com/submissions/detail/676286416/
  • Code đệ quy: https://leetcode.com/submissions/detail/746495769/
- Câu này là 1 câu medium khá hay, mất khá nhiều thời gian để nghĩ, nếu làm lần đầu thì khá khó để nghĩ ra được cách tối ưu nhất.
 

Arik97

Senior Member
14/7/2022:
  • 1 câu medium khá hay
  • Nhìn vào đề bài cho 2 mảng preorder và inorder để tạo thành cái cây -> áp dụng các tính chất của inorder và preorder
  • Tính chất inorder: Nếu biết root của 1 sub tree và mảng inorder của cái sub tree đó thì left subtree của root chính là cái phần bên trái của root trong mảng inorder
  • VD có 1 subtree
View attachment 1263595
  • inorder của subtree là [1, 10, 2, 3, 7, 20, 8] -> biết được [1, 10, 2] là inorder của left subtree của root 3 và [7, 20, 8] là inorder của right subtree
  • Nhưng sẽ gặp vấn đề là sẽ ko thể biết đc trong [1, 10, 2] cái nào sẽ là root của cái subtree đó
  • Vì vậy cần tính chất của preorder, mảng preorder là [3, 10, 1, 2, 20, 7, 8]. Vì preorder là root - left - right nên 3 là root -> 10 chính là root của cái left subtree của root 3, 1 chính root của left subtree root 10. đến 1 ko còn subtree thì 2 sẽ là right của right subtree của root 10, ...
  • có thể dùng duyệt for hoặc đệ quy
  • ra đáp án
  • Code duyệt for (hơi khó hiểu vì đây là code lần đầu) https://leetcode.com/submissions/detail/676286416/
  • Code đệ quy: https://leetcode.com/submissions/detail/746495769/
- Câu này là 1 câu medium khá hay, mất khá nhiều thời gian để nghĩ, nếu làm lần đầu thì khá khó để nghĩ ra được cách tối ưu nhất.
Bài này hay. Nếu mà nghĩ ra được idea tìm root node xong build left tree và right tree recursively thì code ngắn gọn trong vài dòng rất dễ hiểu
 
Bài hôm nay dùng đệ quy thôi.

Dựa vào 3 tính chất của preorder và inorder như sau:
  • preorder[0] luôn là root
  • Gọi x là index của phần tử preorder[0] trong dãy inorder => inorder[:x] là inorder của left tree, inorder[x+1:] là inorder của right tree
  • preorder và inorder của 1 tree bất kì luôn có độ dài bằng nhau

Python:
class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        if len(preorder) == 0:
            return None
       
        split = inorder.index(preorder[0])
        l_inorder = inorder[:split]
        r_inorder = inorder[split+1:]
        l_preorder = preorder[1:split+1]
        r_preorder = preorder[split+1:]
       
        return TreeNode(preorder[0], self.buildTree(l_preorder, l_inorder), self.buildTree(r_preorder, r_inorder))
 

tdat00

Đã tốn tiền
Tối hôm qua nhậu bê bết quá nên giờ mới tỉnh để làm task
yndaNMk.png


  • Ý tưởng giống thím @thuyduong2007 :
    • item đầu tiên trong mảng preorder sẽ là root node
    • Vì các node value là unique nên sẽ tìm được index của root node trong mảng inorder. Khi đó các item bên trái vị trí index này sẽ thuộc left node, bên phải sẽ thuộc right node.
  • Với ví dụ như sample test case preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] thì:
    • Root node sẽ là preorder[0] = 3 => ứng với index = 1 trong mảng inorder => số lượng node bên left sẽ là 1, và số lượng node bên right sẽ là 3.
    • Đệ quy cho left node: do chi có 1 node nên sẽ quay về bài toán con preorder = [9], inorder = [9]
    • Đệ quy cho right node: do có 3 nodes nên sẽ quay về bài toán con preorder = [20, 15, 7], inorder = [15, 20, 7]

https://leetcode.com/submissions/detail/746697929/

C#:
public class Solution {
    Dictionary<int, int> inorder_indexes = new ();
 
    public TreeNode BuildTree(int[] preorder, int[] inorder) {
        for (var i = 0; i < preorder.Length; i++)
        {
            inorder_indexes.Add(inorder[i], i);
        }
    
        return build(preorder, 0, preorder.Length-1, inorder, 0, inorder.Length - 1);
    }
 
    TreeNode build(int[] preorder, int preorder_left, int preorder_right, int[] inorder, int inorder_left, int inorder_right)
    {
        //Console.WriteLine($"{preorder_left} - {preorder_right}; {inorder_left} - {inorder_right}");
        if (preorder_left > preorder_right || inorder_left > inorder_right)
            return null;
    
        TreeNode node = new TreeNode { val = preorder[preorder_left] };
        int node_inorder_index = inorder_indexes[node.val];
        int left_length = node_inorder_index - inorder_left;
        int right_length = inorder_right - node_inorder_index;
    
        node.left = build(preorder,
                          preorder_left + 1,
                          preorder_left + left_length,
                          inorder,
                          inorder_left,
                          inorder_left + left_length - 1);
    
        node.right = build(preorder,
                           preorder_right - right_length + 1,
                           preorder_right,
                           inorder,
                           inorder_right - right_length + 1,
                           inorder_right);
        return node;
    }
}
 
Tối hôm qua nhậu bê bết quá nên giờ mới tỉnh để làm task
yndaNMk.png


  • Ý tưởng giống thím @thuyduong2007 :
    • item đầu tiên trong mảng preorder sẽ là root node
    • Vì các node value là unique nên sẽ tìm được index của root node trong mảng inorder. Khi đó các item bên trái vị trí index này sẽ thuộc left node, bên phải sẽ thuộc right node.
  • Với ví dụ như sample test case preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] thì:
    • Root node sẽ là preorder[0] = 3 => ứng với index = 1 trong mảng inorder => số lượng node bên left sẽ là 1, và số lượng node bên right sẽ là 3.
    • Đệ quy cho left node: do chi có 1 node nên sẽ quay về bài toán con preorder = [9], inorder = [9]
    • Đệ quy cho right node: do có 3 nodes nên sẽ quay về bài toán con preorder = [20, 15, 7], inorder = [15, 20, 7]

https://leetcode.com/submissions/detail/746697929/

C#:
public class Solution {
    Dictionary<int, int> inorder_indexes = new ();
 
    public TreeNode BuildTree(int[] preorder, int[] inorder) {
        for (var i = 0; i < preorder.Length; i++)
        {
            inorder_indexes.Add(inorder[i], i);
        }
   
        return build(preorder, 0, preorder.Length-1, inorder, 0, inorder.Length - 1);
    }
 
    TreeNode build(int[] preorder, int preorder_left, int preorder_right, int[] inorder, int inorder_left, int inorder_right)
    {
        //Console.WriteLine($"{preorder_left} - {preorder_right}; {inorder_left} - {inorder_right}");
        if (preorder_left > preorder_right || inorder_left > inorder_right)
            return null;
   
        TreeNode node = new TreeNode { val = preorder[preorder_left] };
        int node_inorder_index = inorder_indexes[node.val];
        int left_length = node_inorder_index - inorder_left;
        int right_length = inorder_right - node_inorder_index;
   
        node.left = build(preorder,
                          preorder_left + 1,
                          preorder_left + left_length,
                          inorder,
                          inorder_left,
                          inorder_left + left_length - 1);
   
        node.right = build(preorder,
                           preorder_right - right_length + 1,
                           preorder_right,
                           inorder,
                           inorder_right - right_length + 1,
                           inorder_right);
        return node;
    }
}
Chào CTO
 
Top