Avatar
AI
Câu hỏi yêu thích phỏng vấn thuật toán của công ty công nghệ

Câu hỏi yêu thích phỏng vấn thuật toán của các công ty công nghệ

Bài toán "Two sum" trên LeetCode là một bài toán thông dụng được các công ty công nghệ sử dụng trong vòng phỏng vấn của mình nhằm mục đích kiểm tra kiến thức cơ bản của người lập trình về xử lý mảng và bảng băm. Bài toán phát biểu:

Cho một mảng số nguyên nums và một số nguyên target, trả về chỉ mục của hai số sao cho tổng của chúng bằng giá trị target.

Đường dẫn đề bài: https://leetcode.com/problems/two-sum/

Đây là lời giải Python:

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # Tạo một từ điển trống
        d = {}
        # Lặp qua mảng
        for i, num in enumerate(nums):
            # Kiểm tra xem số bù của số hiện tại có trong từ điển không - tức là cộng vào số hiện tại có bằng target hay không
            if target - num in d:
                # Nếu có, trả về chỉ số của số bù và số hiện tại
                return [d[target - num], i]
            # Ngược lại, thêm số hiện tại và chỉ số của nó vào từ điển
            d[num] = i

Cách này sử dụng bảng băm (công nghệ đằng sau một từ điển trong Python) để lưu trữ các số trong mảng và chỉ mục của chúng. Cho mỗi số trong mảng, nó kiểm tra xem số bù của số đó (target - num) đã có trong bảng băm hay chưa.

  • Nếu có tức là là chúng ta đã tìm thấy một cặp số mà chúng có tổng bằng target, sau đó chúng ta trả về chỉ mục của những số đó.

  • Nếu không chúng ta thêm số hiện tại và chỉ mục của nó vào bảng băm và tiếp tục với số tiếp theo.

Trong trường hợp này, giải pháp sử dụng bảng băm để lưu trữ các số và chỉ mục, vì vậy độ phức tạp thời gian lấy giá trị khỏi từ điển là O(1) vì ta không cần sắp xếp hoặc duyệt qua toàn bộ các phần tử. Tổng độ phức tạp thời gian là O(n), với n là số phần tử trong mảng.

Xem thêm về độ phức tạp về thuật toán nếu bạn chưa hiểu các công thức BigO.

Luyện tập thêm Leetcode tại lớp học Leetcode 200 - Luyện thuật toán với chuyên gia

Avatar
AI
Học gì để trở thành kỹ sư dữ liệu?

Học gì để trở thành kỹ sư dữ liệu?

Nếu bạn chưa biết, công việc tiền xử lý dữ liệu là một công việc rất quan trọng trước khi training một mô hình học máy.

Người kỹ sư dữ liệu (Data Engineer) là người thiết kế, xây dựng và duy trì cơ sở hạ tầng và hệ thống hỗ trợ các ứng dụng hướng dữ liệu (data-driven), thường sử dụng các cấu trúc dữ liệu và thuật toán khác nhau để tối ưu hiệu năng. Tương lai các ứng dụng học máy sử dụng dữ liệu lớn (Big Data) sẽ trở nên phổ biến hơn vì vậy vị trí kỹ sư dữ liệu sẽ được tìm kiếm nhiều hơn bao giờ hết.

Tìm hiểu thêm về học máy tại lớp học AI miễn phí.

Đầu tiên thì kỹ sư dữ liệu cần học lập trình tốt. Ngôn ngữ phổ biến để xử lý dữ liệu tại thời điểm hiện tại là Python. Đây là ngôn ngữ được dùng nhiều nhất để làm Machine Learning vì tính đơn giản gọn nhẹ của nó.

Mình đã đóng gói các kiến thức Python vào lớp học Python miễn phí tại đây

Ngoài cấu trúc dữ liệu và giải thuật, người kỹ sư dữ liệu còn phải học rất nhiều chủ đề khác nhau bao gồm:

  • Lưu trữ và quản lý dữ liệu: Các kỹ sư dữ liệu nên có hiểu biết tốt về các loại hệ thống lưu trữ dữ liệu khác nhau, chẳng hạn như cơ sở dữ liệu quan hệ (SQL) và cơ sở dữ liệu không quan hệ (NoSQL), và có thể thiết kế và triển khai các giải pháp lưu trữ dữ liệu hiệu quả.

  • Xử lý và phân tích dữ liệu: Các kỹ sư dữ liệu nên nắm bắt được các kỹ thuật xử lý và phân tích dữ liệu, chẳng hạn như batch processing và stream processing, và có thể thiết kế và triển khai các dữ liệu dòng sử dụng các công cụ như Apache Kafka và Apache Spark.

  • Cloud: Các kỹ sư dữ liệu nên quen thuộc với các nền tảng tính toán Cloud, chẳng hạn như Amazon Web Services (AWS), Microsoft Azure và Google Cloud Platform (GCP), và có thể thiết kế và triển khai các giải pháp cơ sở hạ tầng dữ liệu trên các nền tảng này.

  • Quản lý, bảo mật và tuân thủ dữ liệu: Một phần rất quan trọng đó là quản lý, bảo mật, mã hóa dữ liệu, kiểm soát truy cập dữ liệu.

  • Giao tiếp: Và cuối cùng là kỹ năng giao tiếp tốt để có thể hợp tác với đồng nghiệp, giải thích các khái niệm kỹ thuật phức tạp cho các nhà quản lý không phải người làm kỹ thuật và trình bày công việc của mình trước đám đông.

Hi vọng bài viết này đã giúp bạn có cái nhìn tổng quan về vị trí này.

Filter