100 câu hỏi phỏng vấn cấu trúc dữ liệu hàng đầu năm 2022
Một số điểm cần lưu ý trong khi viết resume
Ví dụ: một resume được trình bày rõ ràng Show
Những bước cơ bản để nộp hồ sơ và thu hút nhà tuyển dụng
Quy trình phỏng vấn thông thường
Những điều cần biết khi trả lời phỏng vấn
Bạn cũng có thể tham khảo thêm hướng dẫn phỏng vấn của Google Những dạng câu hỏi và cách luyện tập trả lờiDạng câu hỏi về kĩ thuật (technical questions) 90% các câu hỏi sẽ thuộc về dạng này. Các câu hỏi ở dạng này sẽ có những loại như sau:
Dạng câu hỏi về kĩ năng ứng xử (behavioral questions)
Với những bạn chưa có nhiều kiến thức hoặc muốn ôn tập lại kiến thức về thuật toán và cấu trúc dữ liệu thì các bạn có thể tìm đọc những cuốn sách (như sách của thầy Lê Minh Hoàng) hoặc những bài viết tiếp theo của chúng tôi về những kiến thức cơ bản/nâng cao cần biết về thuật toán. Với những bạn đã có những kiến thức cơ bản về thuật toán và cấu trúc dữ liệu thì cơ bản các bạn chỉ cần luyện tập kĩ năng trả lời câu hỏi sao cho thật là thuần thục. Một số trang web để các bạn luyện tập như leetcode, hackerrank, ... Nếu bạn có quen một ai đó có thể giúp đỡ bạn, bạn hãy nhờ họ làm một cuộc phỏng vấn thử. Trong lúc phỏng vấn thử này, họ sẽ đưa cho bạn một câu hỏi, và nhiệm vụ của bạn là hãy trả lời một cách suôn sẻ, và họ sẽ đưa ra ý kiến của riêng họ về những điều bạn có thể cải thiện để tiến bộ hơn. Những điều mà các nhà tuyển dụng thường chú ý
Tác giả: Đinh Hoàng Phong (Software Engineer - Facebook) Bạn có thể tự hỏi những câu hỏi bạn sẽ phải đối mặt trong cuộc phỏng vấn cấu trúc dữ liệu tiếp theo của bạn.Chỉ cần nhớ rằng những người phỏng vấn cấu trúc dữ liệu không cố gắng lừa bạn và không mong đợi sự hoàn hảo, nhưng đó là cơ hội của họ để xác định kiến thức của bạn trước khi họ đầu tư vào việc làm của bạn.Chuẩn bị thích hợp luôn luôn được khuyên. Cấu trúc dữ liệu Câu hỏi phỏng vấn là một phần thiết yếu của bất kỳ cuộc phỏng vấn lập trình nào, chủ yếu là một cho vai trò dựa trên khoa học dữ liệu và Java.Hiểu biết kỹ lưỡng và kiến thức sâu sắc về các cấu trúc dữ liệu và thuật toán sẽ phục vụ như một lợi ích cho bạn nổi bật so với các ứng cử viên khác.Các câu hỏi phỏng vấn cấu trúc dữ liệu sau đây sẽ giúp bạn bẻ khóa cuộc phỏng vấn tiếp theo của bạn! Tìm hiểu thêm tại sao các khái niệm cấu trúc dữ liệu là quan trọng️ Why data structures concepts are importantNhiều lần sinh viên tốt nghiệp khoa học máy tính làm giảm tầm quan trọng của việc học cấu trúc dữ liệu và thuật toán coi nó là phức tạp, không liên quan hoặc lãng phí thời gian.Tuy nhiên, họ sớm nhận được một kiểm tra thực tế khi họ bước vào thế giới thực để săn việc.Các công ty lớn như Amazon, Google, Microsoft thường đặt câu hỏi liên quan đến thuật toán và cấu trúc dữ liệu để kiểm tra khả năng giải quyết vấn đề của các ứng cử viên Vì vậy, hãy chuẩn bị cho cuộc phỏng vấn công nghệ bằng cách học các cấu trúc dữ liệu và các khái niệm thuật toán Điều thực sự quan trọng là phải hiểu tầm quan trọng trong thế giới thực của các thuật toán và các thuộc tính của nó bởi vì sử dụng các ý tưởng khác nhau, người ta có thể thiết kế nhiều thuật toán để tính toán một giải pháp cho một vấn đề nhất định.Các câu hỏi quan trọng quan trọng trong các thuật toán là
Chúng ta hãy xem xét một số công ty dựa trên sản phẩm quan trọng kiểm tra các cấu trúc dữ liệu và kỹ năng thuật toán trong các vòng mã hóa:
Uber21 lakh
Từng trên18 lakh Intuit 19 lakh Quả táo Trong cuộc phỏng vấn mã hóa Xin chúc mừng, bạn đã sẵn sàng để đưa các kỹ năng của mình vào thực tế!Trong một cuộc phỏng vấn mã hóa thực sự, bạn sẽ được người phỏng vấn đặt câu hỏi kỹ thuật (hoặc câu hỏi), viết mã vào một trình soạn thảo hợp tác thời gian thực (màn hình điện thoại/tại chỗ ảo) hoặc trên bảng trắng (tại chỗ) để giải quyết vấn đề trong vòng 30-45 phút.Đây là nơi mà niềm vui thực sự bắt đầu! Khi nhận được các câu hỏi phỏng vấn cấu trúc dữ liệu Nhiều ứng cử viên nhảy vào mã hóa ngay khi họ nghe câu hỏi.Đó thường là một sai lầm lớn.Hãy dành một chút thời gian để lặp lại câu hỏi ở người phỏng vấn và đảm bảo rằng bạn hiểu chính xác những gì họ đang hỏi.Lặp lại trở lại/tái hiện câu hỏi sẽ làm giảm cơ hội truyền thông sai. Phải làm gì khi bị mắc kẹtBị mắc kẹt trong các cuộc phỏng vấn mã hóa là vô cùng phổ biến.Nhưng đừng lo lắng, đó là một phần của quá trình và là một bài kiểm tra về khả năng giải quyết vấn đề của bạn.Dưới đây là một số mẹo để thử khi bạn bị mắc kẹt:
Trong khi mã hóaViết mã của bạn với một kiểu mã hóa gọn gàng (thụt lề nhất quán, khoảng cách xung quanh các nhà khai thác của bạn).Đọc mã được viết bởi người khác thường không phải là một nhiệm vụ thú vị.Sử dụng tên biến rõ ràng, tránh tên chữ cái trừ khi chúng được lặp lại. Luôn luôn giải thích những gì bạn hiện đang viết/gõ cho người phỏng vấn.Đây không phải là về việc đọc theo nghĩa đen những gì bạn đang gõ cho người phỏng vấn.Nói về phần của mã bạn hiện đang thực hiện ở cấp độ cao hơn, giải thích lý do tại sao nó được viết như vậy và những gì nó đang cố gắng đạt được. Sau khi mã hóaSau khi bạn đã hoàn thành mã hóa, đừng thông báo ngay cho người phỏng vấn rằng bạn đã hoàn thành.Trong hầu hết các trường hợp, mã của bạn thường không hoàn hảo và chứa một số lỗi hoặc lỗi cú pháp.Những gì bạn cần làm bây giờ là xem lại mã của bạn. Tiếp theo, hãy chủ động đưa ra các trường hợp thử nghiệm nhỏ và bước qua mã (không phải thuật toán của bạn!) Với các đầu vào mẫu đó.Những gì người phỏng vấn thường làm sau khi bạn đã hoàn thành mã hóa sẽ là để bạn viết bài kiểm tra.Đó là một điểm cộng rất lớn nếu bạn viết bài kiểm tra cho mã của mình ngay cả trước khi họ nhắc bạn làm như vậy. Cuối cùng, cung cấp độ phức tạp về thời gian/không gian của mã của bạn và giải thích tại sao nó như vậy.Nếu người phỏng vấn của bạn hài lòng với giải pháp, cuộc phỏng vấn thường kết thúc ở đây.Cũng không có gì lạ khi người phỏng vấn hỏi bạn các câu hỏi mở rộng, chẳng hạn như cách bạn sẽ xử lý vấn đề nếu toàn bộ đầu vào quá lớn để phù hợp với bộ nhớ hoặc nếu đầu vào đến dưới dạng luồng. Có thể giải quyết các câu hỏi mở rộng này sẽ chỉ ra rằng bạn là một ứng cử viên mạnh mẽ có thể sẽ dẫn đến một đề nghị tốt hơn. Cấu trúc dữ liệu Câu hỏi phỏng vấnCấu trúc dữ liệu là gì? Một cấu trúc dữ liệu cung cấp một cách thuận tiện để tổ chức cũng như thao túng dữ liệu.Nói một cách đơn giản, nó cho phép dữ liệu được sử dụng một cách hiệu quả.Có một loạt các cấu trúc dữ liệu và mỗi trong số chúng phù hợp cho một tập hợp các ứng dụng riêng biệt.convenient way of organizing as well as manipulating the data. Simply put, it allows the data to be used in an effective manner. There is a galore of data structures and each of them is suitable for a distinct set of applications. Đó là một khái niệm cơ bản của bất kỳ ngôn ngữ lập trình, cần thiết cho thiết kế thuật toán. Cấu trúc dữ liệu không phải là ngôn ngữ lập trình như C, C ++, Java, v.v ... Đây là một tập hợp các thuật toán có thể được sử dụng trong bất kỳ ngôn ngữ lập trình nào để sắp xếp dữ liệu trong bộ nhớ. Các loại cấu trúc dữ liệu khác nhau là gì? Đây là một trong những câu hỏi phỏng vấn các cấu trúc dữ liệu được hỏi thường gặp nhất trong đó người phỏng vấn mong đợi bạn đưa ra câu trả lời rõ ràng.Cấu trúc dữ liệu có hai loại:
Các ứng dụng khác nhau của cấu trúc dữ liệu là gì? Trong các cấu trúc dữ liệu, dữ liệu được tổ chức theo cách làm cho nó hiệu quả để được sử dụng.Một số ứng dụng thực tế của cấu trúc dữ liệu là:
Giải thích sự khác biệt giữa cấu trúc tệp và cấu trúc lưu trữ? Cấu trúc tệp: Một đĩa cứng hoặc thiết bị bên ngoài (như USB), lưu trữ dữ liệu vẫn còn nguyên vẹn cho đến khi bị xóa thủ công.Một đại diện của dữ liệu thành bộ nhớ phụ hoặc phụ trợ được gọi là cấu trúc tệp. A hard disk or external device (such as USB), stores data that remains intact till manually deleted. Such a representation of data into secondary or auxiliary memory is called a file structure. Cấu trúc lưu trữ: Trong loại cấu trúc, dữ liệu (biến, hằng số, v.v.) này được lưu trữ trong bộ nhớ chính, tức là RAM và bị xóa khi hàm sử dụng dữ liệu này được hoàn thành. In this type of structure, data (variables, constants, etc.) are stored in the main memory, i.e. RAM, and is deleted once the function that uses this data gets completed. Liệt kê các hoạt động khác nhau có thể được thực hiện trên cấu trúc dữ liệu? Sau đây là các hoạt động khác nhau có thể được thực hiện trên cấu trúc dữ liệu:
Cấu trúc dữ liệu danh sách được liên kết là gì? Đây là một trong những câu hỏi phỏng vấn cấu trúc dữ liệu thường gặp nhất trong đó người phỏng vấn mong đợi bạn đưa ra câu trả lời kỹ lưỡng.Cố gắng giải thích càng nhiều càng tốt thay vì hoàn thành câu trả lời của bạn trong một câu! Danh sách được liên kết là một cấu trúc dữ liệu có chuỗi các nút trong đó mọi nút được kết nối với nút tiếp theo bằng một con trỏ tham chiếu.Các yếu tố không được lưu trữ trong các vị trí bộ nhớ liền kề.Chúng được liên kết bằng cách sử dụng con trỏ để tạo thành một chuỗi.sequence of nodes where every node is connected to the next node by means of a reference pointer. The elements are not stored in adjacent memory locations. They are linked using pointers to form a chain. Mỗi nút có hai trường: Trường dữ liệu: Để lưu trữ giá trị dữ liệu. For storing data values. Trường tham chiếu: Để lưu trữ địa chỉ. For storing address. Điểm vào trong một danh sách được liên kết được gọi là đầu.Trong đó danh sách trống, đầu là một tham chiếu null và nút cuối cùng có tham chiếu đến null.head. Where the list is empty, the head is a null reference and the last node has a reference to null. Danh sách được liên kết là một cấu trúc dữ liệu động, trong đó số lượng nút không cố định và danh sách có khả năng phát triển và thu nhỏ theo yêu cầu.dynamic data structure, where the number of nodes is not fixed, and the list has the ability to grow and shrink on demand. Các danh sách được liên kết được coi là cấu trúc dữ liệu tuyến tính hoặc phi tuyến tính? Danh sách được liên kết được coi là cả cấu trúc dữ liệu tuyến tính và phi tuyến tính tùy thuộc vào ứng dụng mà chúng được sử dụng.Khi được sử dụng cho các chiến lược truy cập, nó được coi là một cấu trúc dữ liệu tuyến tính.Khi được sử dụng để lưu trữ dữ liệu, nó được coi là một cấu trúc dữ liệu phi tuyến tính.both linear and non-linear data structures depending upon the application they are used for. When used for access strategies, it is considered as a linear data-structure. When used for data storage, it is considered a non-linear data structure. Những cách nào được liên kết danh sách tốt hơn mảng? Danh sách được liên kết tốt hơn các mảng theo các cách sau:
Giải thích các kịch bản nơi bạn có thể sử dụng danh sách và mảng được liên kết? Sau đây là các kịch bản mà chúng tôi sử dụng danh sách được liên kết qua mảng:
Dưới đây là các trường hợp chúng tôi sử dụng các mảng trong danh sách được liên kết:
Tóm lại, các yêu cầu về không gian, thời gian và dễ thực hiện được xem xét trong khi quyết định cấu trúc dữ liệu nào phải được sử dụng so với những gì. Danh sách liên kết gấp đôi (DLL) là gì?ứng dụng của nó là gì? Nó là một loại phức tạp (LL kết thúc kép) của một danh sách được liên kết trong đó một nút có hai liên kết, một liên kết kết nối với nút tiếp theo trong chuỗi và một nút khác kết nối với nút trước đó.Điều này cho phép truyền tải trên các yếu tố dữ liệu theo cả hai hướng.
Giải thích ngăn xếp và cũng đề cập đến một số ứng dụng quan trọng của nó?
Stack là một cấu trúc dữ liệu tuyến tính theo cách tiếp cận LIFO (lần cuối trong lần đầu tiên) để truy cập các yếu tố.PUSH, POP và TOP (hoặc PEEK) là các hoạt động cơ bản của một ngăn xếp.LIFO (Last In First Out) approach for accessing elements.Push, pop, and top (or peek) are the basic operations of a stack. Một số ứng dụng đáng chú ý của ngăn xếp là:
Hàng đợi là gì?Làm thế nào nó khác với một ngăn xếp? Hàng đợi là một dạng cấu trúc tuyến tính theo cách tiếp cận FIFO (đầu tiên trong lần đầu tiên) để truy cập các yếu tố.Dequeue, enqueue, phía trước và phía sau là các hoạt động cơ bản trên hàng đợi.Giống như một ngăn xếp, một hàng đợi có thể được thực hiện bằng các mảng và danh sách được liên kết.FIFO (First In First Out) approach for accessing elements. Dequeue, enqueue, front, and rear are basic operations on a queue. Like a stack, a queue can be implemented using arrays and linked lists. Trong một ngăn xếp, các mục được thêm gần đây nhất đã bị loại bỏ trước tiên.Trái ngược với điều này, mục ít nhất được thêm gần đây được xóa đầu tiên trong trường hợp hàng đợi. Cấu trúc dữ liệu heap là gì? Heap là một cấu trúc dữ liệu phi tuyến tính dựa trên cây đặc biệt, trong đó cây là một cây nhị phân hoàn chỉnh.Một cây nhị phân được cho là hoàn thành nếu tất cả các cấp độ hoàn toàn được lấp đầy ngoại trừ có thể cấp cuối cùng và cấp độ cuối cùng có tất cả các yếu tố hướng tới bên trái càng tốt.Hàng đống có hai loại:
Hashmap trong cấu trúc dữ liệu là gì?Độ phức tạp về thời gian của các hoạt động cơ bản nhận được () và đặt () trong lớp HashMap là gì? Hashmap là một cấu trúc dữ liệu sử dụng việc triển khai cấu trúc dữ liệu bảng Hash cho phép truy cập dữ liệu trong thời gian không đổi (O (1))) Độ phức tạp nếu bạn có khóa.constant time (O(1)) complexity if you have the key. Độ phức tạp của thời gian là O (1) giả sử rằng hàm băm được sử dụng trong bản đồ băm phân phối các phần tử đồng đều giữa các thùng. Trong một ngăn xếp, các mục được thêm gần đây nhất đã bị loại bỏ trước tiên.Trái ngược với điều này, mục ít nhất được thêm gần đây được xóa đầu tiên trong trường hợp hàng đợi. Giải thích bộ đệm LRU?Những cấu trúc dữ liệu nào được sử dụng để triển khai bộ đệm LRU? Đây là một trong những câu hỏi phỏng vấn yêu thích trong đó người phỏng vấn yêu cầu một lời giải thích toàn diện về nguyên tắc làm việc. Hãy giải thích nó một cách từng bước. Máy tính có bộ nhớ bộ nhớ cache tạm thời lưu trữ dữ liệu được sử dụng thường xuyên nhất.Đó là một cách tuyệt vời để có được dữ liệu được sử dụng thường xuyên nhất vì quá trình truy xuất là siêu nhanh Tuy nhiên, bộ nhớ bộ nhớ cache bị giới hạn về kích thước và cần phải có một cách để quản lý dữ liệu nào cần được xóa khỏi bộ đệm để lưu trữ dữ liệu mới.Đó là nơi có bộ nhớ cache LRU đi vào.limited in size and there needs to be a way to manage what data needs to be removed from the cache in order to store new data. That's where LRU cache comes in. Đó là một thuật toán thay thế bộ đệm giúp loại bỏ dữ liệu ít được sử dụng gần đây nhất để nhường chỗ cho dữ liệu mới.Để đạt được điều này, hai cấu trúc dữ liệu được sử dụng:
Việc thực hiện là khó khăn.Nó thực hiện nhiều kỹ năng và kiến thức cơ bản lập trình của bạn như sử dụng lập trình hướng đối tượng. -Bạn có thể kiểm tra video giải thích khóa học của chúng tôi! Giải thích bộ đệm LFU?Những cấu trúc dữ liệu nào được sử dụng để triển khai bộ đệm LFU? Như tên cho thấy, chúng ta phải thiết kế một bộ đệm sẽ trục xuất vật phẩm ít được sử dụng nhất khi bộ đệm đầy đủ và một mục mới cần được thêm vào trong bộ đệm, cũng là các hoạt động nhận được (k) và đặt (k, v)Nên dành thời gian O (1).get(K) and put(K, V) should take O(1) time. Để triển khai bộ đệm LFU, chúng tôi sẽ sử dụng kết hợp danh sách được liên kết OUTBLY và cấu trúc dữ liệu bản đồ băm.Xác định một nút trong danh sách liên kết gấp đôi.Mỗi nút sẽ chứa thông tin như khóa, giá trị, tần số (số lần truy cập khóa đã được truy cập), nút bên trái và nút phải.Đối với mỗi khóa mới, một nút mới sẽ được thêm vào danh sách được liên kết.Tại bất kỳ thời điểm nào, các nút trong danh sách được liên kết gấp đôi sẽ được sắp xếp dựa trên tần suất truy cập của chúng.Đầu của danh sách được liên kết sẽ là nút ít được truy cập nhất.Điều này sẽ giúp chúng tôi có được nút ít được truy cập ít nhất trong thời gian O (1).oubly linked list and a hash map data structures. Define a node in the doubly linked list. Each node will contain information like key, value, frequency(number of times the key has been accessed), left node, and right node. For every new key, a new node will be added to the linked list. At any point in time, the nodes in the doubly linked list will be sorted based on their frequency of access. The head of the linked list will be the node that is least frequently accessed. This will help us get the node which is least frequently accessed in O(1) time. Bây giờ, làm thế nào để chúng ta truy cập một khóa trong thời gian không đổi?Với mục đích này, chúng tôi sẽ sử dụng bản đồ băm sẽ lưu trữ nút (nút trong danh sách được liên kết gấp đôi) Hãy xem một ví dụ về Lfucache của Công suất 2.capacity 2. bộ nhớ cache = lfucache (2).# Bộ nhớ cache trống 1.cache.put (1, 1) Một datanode mới (key = 1, val = 1, tần số = 1) sẽ được chèn vào bộ đệm. Bộ đệm trở thành: [Tần số = 1] -> [Key = 1, value = 1] 2.cache.put (2, 2) Datanode thứ hai (khóa = 2, val = 2, tần số = 1) sẽ được chèn vào số cache #. [tần số = 1] -> [key = 1, value = 1], [key = 2, value = 2] 3.cache.get(1) Trả về 1 (cho phím = 1, value = 1), datanode có phím = 1 được quảng bá, [Tần số = 1] -> [Key = 2, value = 2] [tần số = 2] -> [key = 1, value = 1] 4.Cache.put (3, 3) Vì bộ đệm đầy đủ và không có khóa 3, khóa có tần số ít nhất (2 trong # trường hợp này) sẽ bị trục xuất và Datanode mới (khóa = 3, val = 3, tần số # = 1) sẽ được thêm vào. [Tần số = 1] -> [Key = 3, value = 3] [tần số = 2] -> [key = 1, value = 1] 5. Cache.get (2) Vì phím 2 không có trong bộ đệm, không sẽ được trả về.Bộ nhớ cache vẫn như nó đã được. Việc thực hiện là khó khăn.Nó thực hiện nhiều kỹ năng và kiến thức cơ bản lập trình của bạn như sử dụng lập trình hướng đối tượng. -Bạn có thể kiểm tra video giải thích khóa học của chúng tôi! Cấu trúc dữ liệu cây là gì? Cây là một cấu trúc dữ liệu đệ quy, phi tuyến tính bao gồm tập hợp một hoặc nhiều nút dữ liệu trong đó một nút được chỉ định là gốc và các nút còn lại được gọi là con của rễ. Một số ứng dụng của cây là:
Số lượng nút tối đa trong cây nhị phân có chiều cao k là bao nhiêu? Các nút tối đa là: 2K2k Viết một hàm đệ quy để tính chiều cao của cây nhị phân? Hãy xem xét rằng mọi nút của cây đại diện cho một lớp gọi là nút như được đưa ra dưới đây: class Node: # Constructor to create a new node def __init__(self, data): self.data = data self.left = None self.right = None Sau đó, chiều cao của cây nhị phân có thể được tìm thấy như sau: def height_of_tree(root): # base case: empty tree has a height of 0 if root is None: return 0 # recur for the left and right subtree and consider maximum depth return 1 + max(height_of_tree(root.left), height_of_tree(root.right)) Những chiếc xe đạp cây là gì? Cây truyền tải là một quá trình truy cập tất cả các nút của cây.Vì root (đầu) là nút đầu tiên và tất cả các nút được kết nối thông qua các cạnh (hoặc liên kết), chúng tôi luôn bắt đầu với nút đó.Có ba cách mà chúng ta sử dụng để đi qua một cây:
Truyền hàng trước
Trực tiếp trước Traversal
Bưu điện truyền tải Traverse Subtree bên trái, tức là, gọi đặt hàng trước (root.left) Traverse Subtree bên phải, tức là, gọi đặt hàng trước (root.right)
Cây tìm kiếm nhị phân là gì? Đây là một loại cây thú vị, tức là cây tìm kiếm nhị phân vì nó tuân theo các tham số nhất định.set of nodes (or vertices) and a set of edges connecting them. A pair (x,y) is referred to as an edge, which communicates that the x vertex connects to the y vertex. Subtree bên trái của một nút chỉ chứa các nút có các phím nhỏ hơn phím của nút. Subtree bên phải của một nút chỉ chứa các nút có các phím lớn hơn phím của nút.
Biểu đồ là một cấu trúc dữ liệu phổ biến bao gồm một tập hợp các nút (hoặc đỉnh) hữu hạn và một tập hợp các cạnh kết nối chúng.Một cặp (x, y) được gọi là một cạnh, giao tiếp rằng X đỉnh kết nối với đỉnh y. Sự khác biệt giữa tìm kiếm đầu tiên (BFS) và tìm kiếm đầu tiên (DFS) là gì?directed graph and returns an array of the nodes where each node appears before all the nodes it points to. Cả BFS và DFS đều là các phương thức đi qua cho một biểu đồ.Biểu đồ truyền tải không là gì ngoài quá trình truy cập tất cả các nút của đồ thị.Directed Acyclic graph(DAG) Sự khác biệt chính giữa BFS và DFS là BFS đi qua cấp độ theo cấp độ trong khi DFS đi theo một đường dẫn đầu tiên từ nút bắt đầu đến cuối, sau đó một đường dẫn khác từ đầu đến cuối, v.v. cho đến khi tất cả các nút được truy cập. def topological_sort(digraph): # digraph is a dictionary: # key: a node # value: a set of adjacent neighboring nodes # construct a dictionary mapping nodes to their # indegrees indegrees = {node : 0 for node in digraph} for node in digraph: for neighbor in digraph[node]: indegrees[neighbor] += 1 # track nodes with no incoming edges nodes_with_no_incoming_edges = [] for node in digraph: if indegrees[node] == 0: nodes_with_no_incoming_edges.append(node) # initially, no nodes in our ordering topological_ordering = [] # as long as there are nodes with no incoming edges # that can be added to the ordering while len(nodes_with_no_incoming_edges) > 0: # add one of those nodes to the ordering node = nodes_with_no_incoming_edges.pop() topological_ordering.append(node) # decrement the indegree of that node's neighbors for neighbor in digraph[node]: indegrees[neighbor] -= 1 if indegrees[neighbor] == 0: nodes_with_no_incoming_edges.append(neighbor) # we've run out of nodes with no incoming edges # did we add all the nodes or find a cycle? if len(topological_ordering) == len(digraph): return topological_ordering # got them all else: raise Exception("Graph has a cycle! No topological ordering exists.") BFS sử dụng cấu trúc dữ liệu hàng đợi để lưu trữ các nút trong khi DFS sử dụng ngăn xếp cho các nút của các nút để thực hiện.
Chỉ áp dụng trong biểu đồ Acyclic có định hướng (DAG) Dưới đây là phần triển khai trong Python:QuickSort algorithm is generally considered the fastest because it has the best performance for most inputs. Sự phức tạp về thời gian và không gian
Một thuật toán sắp xếp duy nhất không thể được coi là tốt nhất, vì mỗi thuật toán được thiết kế cho một cấu trúc dữ liệu và tập dữ liệu cụ thể.Tuy nhiên, thuật toán QuickSort thường được coi là nhanh nhất vì nó có hiệu suất tốt nhất cho hầu hết các đầu vào. Ưu điểm của nó so với các thuật toán sắp xếp khác bao gồm các thuật toán sau:divide-and-conquer algorithm for sorting the data. It works by merging and sorting adjacent data to create bigger sorted lists, which are then merged recursively to form even bigger sorted lists until you have one single sorted list. Sẽ rõ hơn nếu bạn trải qua dưới đây hoạt hình Đây là việc thực hiện trong Python def mergeSort(arr): if len(arr) > 1: # Finding the mid of the array mid = len(arr)//2 # Dividing the array elements L = arr[:mid] # into 2 halves R = arr[mid:] # Sorting the first half mergeSort(L) # Sorting the second half mergeSort(R) i = j = k = 0 # Copy data to temp arrays L[] and R[] while i < len(L) and j < len(R): if L[i] < R[j]: arr[k] = L[i] i += 1 else: arr[k] = R[j] j += 1 k += 1 # Checking if any element was left while i < len(L): arr[k] = L[i] i += 1 k += 1 while j < len(R): arr[k] = R[j] j += 1 k += 1 def printList(arr): for i in range(len(arr)): print(arr[i], end=" ") print() # Driver Code if __name__ == '__main__': arr = [3,7,0,8,9] print("Given array is", end="\n") printList(arr) mergeSort(arr) print("Sorted array is: ", end="\n") printList(arr) Những lợi thế của tìm kiếm nhị phân trên một tìm kiếm tuyến tính là gì? Trong danh sách sắp xếp
Liệt kê các cấu trúc dữ liệu được sử dụng trong cơ sở dữ liệu quan hệ, mô hình dữ liệu mạng và mô hình dữ liệu phân cấp? Các cấu trúc dữ liệu chính được sử dụng như sau:
Cấu trúc dữ liệu nào được sử dụng để thực hiện đệ quy? Cấu trúc dữ liệu ngăn xếp được sử dụng trong đệ quy do bản chất cuối cùng của nó.Hệ điều hành duy trì ngăn xếp để lưu các biến lặp ở mỗi cuộc gọi chức năng Ví dụ cơ bản nhất về đệ quy là sê -ri Fibonacci.Sê -ri Fibonacci là một loạt các con số được hình thành bởi việc bổ sung hai số trước trong chuỗi.Hai thuật ngữ đầu tiên là 0 và một tương ứng.Các thuật ngữ sau này được tạo bằng cách thêm hai thuật ngữ trước đó 2 được tính bằng cách thêm hai số trước nó (1+1), 3 được tính bằng cách thêm hai số trước nó (1+2), 5 là (2+3), v.v. Dưới đây trong hình ảnh, chúng tôi chỉ ra cách thiết kế loạt Fibonacci bằng cách sử dụng đệ quy.Đệ quy sử dụng nội bộ ngăn xếp bộ nhớ Các loại tìm kiếm được sử dụng trong các cấu trúc dữ liệu là gì? Các thuật toán tìm kiếm được thiết kế để kiểm tra một phần tử hoặc truy xuất một phần tử từ bất kỳ cấu trúc dữ liệu nào nơi nó được lưu trữ. Các loại thuật toán tìm kiếm khác nhau là: Tìm kiếm tuyến tính Tìm kiếm nhị phân Tìm kiếm Jump Tìm kiếm nội suy Tìm kiếm theo cấp số nhân Độ phức tạp về thời gian của một số thuật toán tìm kiếm trong cấu trúc dữ liệu Khi nào một tìm kiếm nhị phân được áp dụng tốt nhất? Tìm kiếm nhị phân là một thuật toán được áp dụng tốt nhất để tìm kiếm danh sách khi các phần tử đã được hoặc sắp xếp.Danh sách được tìm kiếm bắt đầu từ giữa, sao cho nếu giá trị giữa đó không phải là khóa tìm kiếm đích, nó sẽ kiểm tra xem liệu nó sẽ tiếp tục tìm kiếm ở nửa dưới của danh sách hoặc nửa cao hơn.Việc chia và tìm kiếm sau đó sẽ tiếp tục theo cách tương tự. Thuật toán tìm kiếm nhị phân là một trong những kỹ thuật tìm kiếm được sử dụng rộng rãi.Nó có thể được sử dụng để sắp xếp các mảng.Kỹ thuật tìm kiếm này theo chiến lược phân chia và chinh phục.Không gian tìm kiếm luôn giảm xuống một nửa trong mỗi lần lặp.Thuật toán tìm kiếm nhị phân là một kỹ thuật rất hiệu quả để tìm kiếm nhưng nó cần một số thứ tự mà phân vùng của mảng sẽ xảy ra. Sự khác biệt giữa một thuật toán phân loại ổn định và không ổn định? Đây là một khái niệm khó khăn.Chúng tôi chưa bắt gặp bất kỳ trường hợp sử dụng thực tế nào của vấn đề này nhưng chỉ cần biết khái niệm này tốt từ góc độ phỏng vấn.
Một số ví dụ về các thuật toán ổn định là sắp xếp hợp nhất, sắp xếp chèn, sắp xếp bong bóng.Trong khi, Quicksort, Sắp xếp HEAP và Sắp xếp lựa chọn là các thuật toán sắp xếp không ổn định. Làm thế nào để bạn trao đổi hai số mà không sử dụng biến thứ ba? Một câu hỏi khó khác là dễ dàng nếu bạn biết thủ thuật.Vâng, chúng ta có thể trao đổi hai số mà không cần sử dụng biến tạm thời hoặc thứ ba nếu chúng ta có thể lưu trữ số số trong một số và sau đó trừ tổng với số khác Giải pháp 1 - Sử dụng bổ sung và trừ a = a + b; b = a - b; // actually (a + b) - (b), so now b is equal to a a = a - b; // (a b) -(a), now a is equal to b Nhưng nó sẽ không hoạt động trong mọi điều kiện.Integer sẽ tràn nếu việc bổ sung nhiều hơn giá trị tối đa của int nguyên thủy theo định nghĩa của integer.max_value và nếu phép trừ nhỏ hơn giá trị tối thiểu, tức là integer.min_value.. Integer will overflow if the addition is more than the maximum value of int primitive as defined by Integer.MAX_VALUE and if subtraction is less than the minimum value, i.e. Integer.MIN_VALUE. Giải pháp 2 - Sử dụng XOR Trick Nếu bạn nhớ bảng sự thật XOR thì bạn sẽ biết rằng A XOR B sẽ trả về 1 nếu A và B khác nhau và 0 nếu A và B giống nhau.Tài sản này sinh ra mã sau, thường được gọi là XOR Trick: x = x ^ y; y = x ^ y; // now y = x x = x ^ y; // now x = y Sự khác biệt giữa một danh sách và một tuple [trong Python] là gì? Sự khác biệt giữa danh sách và tuple trong Python:
Sự khác biệt giữa việc quay lại và một lực lượng vũ phu là gì? Do thực tế là một thuật toán quay lại có tất cả các kết quả có thể xảy ra cho một quyết định, nó tương tự từ quan điểm này với thuật toán vũ lực.Sự khác biệt bao gồm trong thực tế là đôi khi một thuật toán quay lại có thể phát hiện rằng một tìm kiếm toàn diện là không cần thiết và do đó nó có thể thực hiện tốt hơn. Phương pháp vũ lực thực sự mất rất nhiều thời gian trong việc giải quyết các vấn đề bởi vì trong đó chúng tôi tạo ra tất cả các giải pháp đó cũng không phải là một giải pháp.Và điều này làm cho nó tốn thời gian.Nhưng ý tưởng quay lại là khác nhau.Trong backtracking, chúng tôi không tạo ra tất cả các giải pháp có thể, thay vì chúng tôi tiếp tục kiểm tra xem giải pháp có chính xác hay không ở mỗi bước.Nếu đúng, chúng tôi tiếp tục tạo các giải pháp tiếp theo cho vấn đề.Nếu không chính xác, chúng tôi quay lại bước trước và kiểm tra các giải pháp khác. Tại sao sắp xếp nhanh được ưa thích cho các mảng và sắp xếp hợp nhất cho các danh sách được liên kết? Tại sao Sắp xếp nhanh được ưa thích cho các mảng?
Tại sao Merge sắp xếp được ưa thích cho các danh sách được liên kết?
Làm thế nào để bạn kiểm tra xem một chuỗi đã cho là một palindrom? Một chuỗi được cho là một palindrom nếu mặt trái của chuỗi bằng với chính nó giống như "ABA" là một palindrom vì ngược lại với "ABA" cũng là "ABA", nhưng "ABC" không phải là một palindrom vì mặt trái của "ABC "là" CBA "không bằng nhau. Chương trình rất đơn giản, và đây là các bước để tìm chuỗi palindrom: 1. TUYỆT ĐỐI 2. Kiểm tra nếu phần ngược của chuỗi bằng chính nó;Nếu có, thì chuỗi đã cho là một palindrom. Đây là việc thực hiện trong Python: def isPalindrome(s): i = 0 j = len(s) - 1 while i < j: if s[i] != s[j]: return False i = i + 1 j = j - 1 return True if __name__ == '__main__': s = 'MADAM' if isPalindrome(s): print('Palindrome') else: print('Not Palindrome') Làm thế nào để bạn đảo ngược các từ trong một câu đã cho mà không sử dụng bất kỳ phương thức thư viện nào? Ban đầu, đảo ngược các từ riêng lẻ của chuỗi đã cho từng mộtĐảo ngược toàn bộ chuỗi từ đầu đến cuối để có được đầu ra mong muốn "rất nhiều chương trình như tôi" trong ví dụ này. import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); System.out.print("Original string : "); String originalStr = scanner.nextLine(); scanner.close(); String words[] = originalStr.split("\\s"); String reversedString = ""; //Reverse each word's position for (int i = 0; i < words.length; i++) { if (i == words.length - 1) reversedString = words[i] + reversedString; else reversedString = " " + words[i] + reversedString; } // Displaying the string after reverse System.out.print("Reversed string : " + reversedString); } } Làm thế nào để bạn kiểm tra xem hai chuỗi có phải là đối thủ của nhau không? Hai chuỗi được gọi là Anagram, nếu chúng chứa cùng một ký tự nhưng theo thứ tự khác nhau, ví dụ:Army và Mary, Stop và Pots, v.v ... Cách thực sự là sự pha trộn của các nhân vật trong chuỗi.Nếu bạn quen thuộc với API chuỗi, tức là java.lang.String thì bạn có thể dễ dàng giải quyết vấn đề này. Để kiểm tra xem các chuỗi có phải là đảo chữ hay không, bạn cần có được mảng ký tự của chúng và xem chúng có bằng hay không.Mặc dù bạn cũng có thể sử dụng indexof (), subring () và lớp StringBuffer hoặc StringBuilder để giải quyết câu hỏi này. // Java program to check if two strings // are anagrams of each other class Solution{ static int NO_OF_CHARS = 256; // function to check if two strings // are anagrams of each other static boolean areAnagram(char[] str1,char[] str2) { // Create a count array and initialize // all values as 0 int[] count = new int[NO_OF_CHARS]; int i; // For each character in input strings, // increment count in the corresponding // count array for(i = 0; i < str1.length; i++) { count[str1[i] - 'a']++; count[str2[i] - 'a']--; } // If both strings are of different // length. Removing this condition // will make the program fail for // strings like "aaca" and "aca" if (str1.length != str2.length) return false; // See if there is any non-zero // value in count array for(i = 0; i < NO_OF_CHARS; i++) if (count[i] != 0) { return false; } return true; } // Driver code public static void main(String[] args) { char str1[] = "logicmojo".toCharArray(); char str2[] = "mojologic".toCharArray(); // Function call if (areAnagram(str1, str2)) System.out.print("The two strings are " + "anagram of each other"); else System.out.print("The two strings are " + "not anagram of each other"); } } Làm thế nào để bạn kiểm tra xem một biểu đồ nhất định có phải là cây hay không Một biểu đồ không mong muốn là cây nếu nó có các thuộc tính sau. 1. Không có chu kỳ 2. Biểu đồ được kết nối.Đối với một biểu đồ không mong muốn, chúng ta có thể sử dụng BFS hoặc DFS để phát hiện trên hai thuộc tính. Đây là việc thực hiện trong Python: from collections import defaultdict class Graph: def __init__(self,n_vertices): self.V = n_vertices self.graph = defaultdict(list) def add_edge(self,u,v): self.graph[u].append(v) self.graph[v].append(u) def iscycle(self,v,visited_arr,parent): visited_arr[v] = "Visited" for i in self.graph[v] : if(visited_arr[i] == "not Visited") : if (self.iscycle(i,visited_arr,v)): return True elif i != parent: return False return False def is_tree(self): visited_arr = ["not Visited"] * self.V if (self.iscycle(0,visited_arr,-1)) : return False for i in range(self.V) : if(visited_arr[i] == "not Visited"): return False return True # Eg1 : Graph is a Tree g2 = Graph(5) g2.add_edge(1, 0) g2.add_edge(0, 2) g2.add_edge(0, 3) g2.add_edge(3, 4) if (g2.is_tree() == True): print("Graph is a tree") else : print("Graph is a not a Tree") Sự khác biệt giữa thuật toán phân chia và chinh phục và lập trình động là gì? Lập trình động là một phần mở rộng của mô hình phân chia và chinh phục.
Phương pháp lập trình động chỉ có thể được áp dụng cho vấn đề nếu vấn đề có một số hạn chế hoặc điều kiện tiên quyết nhất định:
Thuật toán của Dijkstra có phải là thuật toán lập trình tham lam hoặc động? Bạn có thể nói cả hai chúng ta hãy xem làm thế nào.both let's see how. Thật là tham lam bởi vì chúng ta luôn đánh dấu đỉnh gần nhất.closest vertex. Đó là động vì khoảng cách được cập nhật bằng các giá trị được tính toán trước đó.previously calculated values. Nhưng sẽ nói rằng nó chắc chắn gần với chương trình năng động hơn là một thuật toán tham lam.Để tìm khoảng cách ngắn nhất từ A đến B, nó không quyết định cách đi từng bước.Thay vào đó, nó tìm thấy tất cả những nơi mà người ta có thể đi từ mộtcloser to dynamic programming than to a greedy algorithm. To find the shortest distance from A to B, it does not decide which way to go step by step. Instead, it finds all places that one can go from A Các quyết định tối ưu không được thực hiện một cách tham lam, nhưng được thực hiện bằng cách làm cạn kiệt tất cả các tuyến có thể có thể làm cho khoảng cách ngắn hơn.Do đó, đó là một thuật toán lập trình động, biến thể duy nhất là các giai đoạn không được biết trước, nhưng được xác định động trong quá trình của thuật toán. Đưa ra một ví dụ về chương trình động nhưng không có đệ quy Sau đây sẽ được coi là DP, nhưng không có đệ quy (sử dụng phương pháp DP từ dưới lên hoặc bảng). def height_of_tree(root): # base case: empty tree has a height of 0 if root is None: return 0 # recur for the left and right subtree and consider maximum depth return 1 + max(height_of_tree(root.left), height_of_tree(root.right))0 Làm thế nào để bạn đếm sự xuất hiện của một ký tự nhất định trong một chuỗi? Bạn có thể tìm thấy số lần xuất hiện của một ký tự trong một chuỗi bằng cách làm theo cách tiếp cận bên dưới: 1. Trong một biến bộ đếm để lưu trữ tổng số lần xuất hiện của một ký tự trong một chuỗi. 2.Traurese Chuỗi ký tự theo ký tự. 3.Nếu ký tự của chuỗi khớp với ký tự đã cho, tăng giá trị của biến số đếm.Cuối cùng, trả lại biến bộ đếm. def height_of_tree(root): # base case: empty tree has a height of 0 if root is None: return 0 # recur for the left and right subtree and consider maximum depth return 1 + max(height_of_tree(root.left), height_of_tree(root.right))1 Ưu điểm của việc sử dụng Bellman-Ford so với Dijkstra là gì? Thuật toán Bellman-Ford tìm thấy các đường ngắn nhất của nguồn bằng cách liên tục thư giãn khoảng cách cho đến khi không còn khoảng cách để thư giãn.Khoảng cách thư giãn được thực hiện bằng cách kiểm tra xem một điểm trung gian có cung cấp một đường dẫn tốt hơn đường dẫn hiện được chọn hay không. Thuật toán này có lợi thế so với Dijkstra vì nó có thể xử lý các biểu đồ với các cạnh âm, trong khi Dijkstra bị giới hạn ở các biểu tượng không âm.Hạn chế duy nhất nó có là đồ thị với các chu kỳ có đường dẫn âm tổng thể, nhưng điều này chỉ có nghĩa là không có giải pháp hữu hạn. def height_of_tree(root): # base case: empty tree has a height of 0 if root is None: return 0 # recur for the left and right subtree and consider maximum depth return 1 + max(height_of_tree(root.left), height_of_tree(root.right))2 Làm thế nào để bạn phát hiện một vòng lặp trong một danh sách được liên kết? Có hai cách tiếp cận về cơ bản. Cách tiếp cận đầu tiên chúng ta có thể sử dụng bảng băm trong bảng băm về cơ bản chúng ta ghi lại tham chiếu (hoặc địa chỉ bộ nhớ) của từng nút trong bảng băm.Nếu nút hiện tại là null, chúng tôi đã đạt đến cuối danh sách được liên kết và nó không phải là một chu kỳ nếu không nếu tham chiếu của nút có trong bảng băm, thì có một vòng lặp.use Hash Table in hash table basically we record each node's reference (or memory address) in a hash table. if the current node is null we reached the end of the Linked List and its not a cycle otherwise if the node's reference present in the Hash table, then there is a loop. Đây là cách tiếp cận thứ hai về cơ bản thuật toán tìm chu kỳ của Floyd là thuật toán nhanh nhất được mô tả dưới đâyFloyd's Cycle-Finding Algorithm which is the fastest algorithm described below 1. Danh sách liên kết được liên kết bằng hai con trỏ. 2.Move con trỏ chậm theo một vị trí 3.Move Con trỏ nhanh theo hai vị trí. 4. Nếu hai con trỏ này gặp nhau ở cùng một nút thì có một vòng lặp.Nếu họ không gặp nhau ở cùng một vị trí (con trỏ) thì LinkedList không có vòng lặp. Làm thế nào để bạn phát hiện nếu hai số nguyên có dấu hiệu ngược lại? Thao tác bit cho phép một lập trình viên làm việc với các bit trái ngược với các bản tóm tắt được sử dụng trong các ngôn ngữ lập trình hiện đại.Họ thường sử dụng loại lập trình này để phát hiện và sửa các thuật toán. Thao tác bit sử dụng các hoạt động bitwise, đây là một mức độ hoạt động hoạt động với các bit riêng lẻ, là đơn vị dữ liệu nhỏ nhất. Khi hai số nguyên có các dấu hiệu ngược lại, điều đó có nghĩa là các bit quan trọng nhất của chúng là khác nhau.Một chút đáng kể nhất của bất kỳ số âm nào sẽ luôn là một, trong khi bit quan trọng nhất cho các số dương sẽ luôn bằng không.Nếu bạn áp dụng độc quyền của toán tử bitwise hoặc (xor "^") cho hai số nguyên có các dấu hiệu ngược lại, bạn sẽ nhận được một số âm.Điều này có nghĩa là nếu toán tử XOR được áp dụng cho hai số nguyên và trả về ít hơn 0, hai số có các dấu hiệu ngược lại.most significant bits are different. The most significant bit of any negative number will always be one, whereas the most significant bit for positive numbers will always be zero. If you apply the bitwise operator exclusive OR (XOR "^") to two integers with opposite signs, you will get a negative number. This means that if the XOR operator is applied to two integers and returns less than zero, the two numbers have opposite signs. Tìm XOR của hai số mà không cần sử dụng toán tử XOR? Một giải pháp đơn giản là đi qua tất cả các bit từng cái một.Đối với mỗi cặp bit, kiểm tra xem cả hai đều giống nhau, đặt bit tương ứng là 0 trong đầu ra, nếu không được đặt là 1. def height_of_tree(root): # base case: empty tree has a height of 0 if root is None: return 0 # recur for the left and right subtree and consider maximum depth return 1 + max(height_of_tree(root.left), height_of_tree(root.right))3 Một giải pháp tốt hơn có thể tìm thấy XOR mà không cần sử dụng một vòng lặp.Biểu thức (x | y) - (x & y) tương đương với x ^ y(x | y) - (x & y) is equivalent to x ^ y def height_of_tree(root): # base case: empty tree has a height of 0 if root is None: return 0 # recur for the left and right subtree and consider maximum depth return 1 + max(height_of_tree(root.left), height_of_tree(root.right))4 Số lượng hàng đợi tối thiểu cần thiết khi thực hiện hàng đợi ưu tiên là bao nhiêu? Số lượng hàng đợi tối thiểu cần thiết để thực hiện hàng đợi ưu tiên là hai.Một hàng đợi được sử dụng để lưu trữ dữ liệu thực tế và dữ liệu còn lại được sử dụng để lưu trữ các ưu tiên.two. One queue is used for the actual storing of data, and the other one is used for storing the priorities. Làm thế nào để bạn tìm thấy số trùng lặp trên một mảng số nguyên nhất định? Vấn đề chính, trong khi xử lý một mảng là không tìm thấy các bản sao, đó là về việc loại bỏ chúng.Vì một mảng là một cấu trúc dữ liệu có độ dài cố định, tĩnh, bạn không thể thay đổi độ dài của nó.Điều này có nghĩa là, xóa một phần tử khỏi một mảng yêu cầu tạo một mảng mới và sao chép nội dung vào mảng đó. Thuật toán: 1.Traurese mảng đã cho từ đầu đến cuối. 2. Đối với mọi phần tử trong mảng tăng phần tử ARR [i]%n'th của n. 3 Cách tiếp cận này hoạt động bởi vì tất cả các yếu tố nằm trong phạm vi từ 0 đến N-1 và ARR [i] sẽ lớn hơn n chỉ khi một giá trị "i" đã xuất hiện nhiều hơn một lần. Đây là việc thực hiện trong Python: def height_of_tree(root): # base case: empty tree has a height of 0 if root is None: return 0 # recur for the left and right subtree and consider maximum depth return 1 + max(height_of_tree(root.left), height_of_tree(root.right))5 Giả sử t là một cây đầy đủ.Thuật toán tìm kiếm đầu tiên về độ sâu (DFS) và thuật toán tìm kiếm đầu tiên (BFS) có chiều rộng vượt qua một lá T sớm nhất? Câu trả lời đúng là DFS.Một thuật toán DFS, (tức là tìm kiếm đầu tiên độ sâu) như tên của nó ngụ ý, các nút đi qua các cấp dưới nút hiện tại trước khi nó xử lý phần còn lại của các nút ở cùng cấp.DFS. A DFS algorithm, (i.e. depth first search) as its name implies, traverses nodes at levels below the current node before it processes the rest of the nodes at the same level. BFS thực hiện ngược lại-- làm cạn kiệt tất cả các nút đã biết ở cấp độ trước khi nó đi qua một nút ở cấp độ bên dưới.Vì t là đầy đủ, tất cả các lá của nó ở cùng một cấp cây.BFS chỉ đến một chiếc lá chỉ sau khi tất cả các nút bên trong đi qua, trong khi DF đến một chiếc lá sớm nhất có thể. Bạn có thể lưu trữ khóa trùng lặp trong Hashmap không? Không, các khóa trùng lặp không được phép trong Hashmap.Chìa khóa trong một cặp mục là một tham chiếu duy nhất cho giá trị, cũng là vị trí của cặp đó trong HashMap.Khi có một nỗ lực để đặt một mục với một khóa hiện có, mục nhập hiện tại sẽ được thay thế bằng cái mới.Trong trường hợp như vậy, phương thức hashmap `put ()` trả về mục nhập hiện tại đã bị xóa., duplicate keys are not allowed in HashMap. The key in a entry pair is a unique reference to the Value, also to the location of that pair in the HashMap. When there is an attempt to put an entry with an existing key, the existing entry will be replaced with the new one. In such a case, the `put()` method of HashMap returns the existing entry that has been deleted. Hashmap không cho phép các khóa trùng lặp tuy nhiên, nó cho phép các giá trị trùng lặp.Điều này có nghĩa là có thể có nhiều khóa khác nhau với cùng một giá trị. Hashmap cũng cho phép khóa null, tuy nhiên đây là khóa chỉ có thể có một khóa null trên mỗi hashmap.Bạn có thể có nhiều giá trị null. Thuật toán tại chỗ là gì?Bạn có thể đưa ra một ví dụ không? Đây là một câu hỏi mở để kiểm tra kiến thức của bạn về các thuật toán tại chỗ để xem liệu nó có đủ kỹ lưỡng để bạn tạo ra một ví dụ giải thích nó hay không. Thuật toán tại chỗ là một thuật toán không sử dụng bộ nhớ bổ sung để xử lý đầu vào trong khi nó có thể sử dụng đầu vào để thực hiện.Mục đích của một thuật toán tại chỗ là để lưu không gian bộ nhớ trong khi thực hiện.doesn't use additional memory to process the input while it could use the input itself for its execution. The purpose of an in-place algorithm is to save memory space during execution. Một ví dụ điển hình là đảo ngược một mảng.Hãy xem xét một thuật toán để đảo ngược các giá trị được lưu trữ trong một mảng 'InputArray' để trong 'OutputArray', ô đầu tiên sẽ giữ giá trị tại ô cuối cùng của 'Inarray', v.v. def height_of_tree(root): # base case: empty tree has a height of 0 if root is None: return 0 # recur for the left and right subtree and consider maximum depth return 1 + max(height_of_tree(root.left), height_of_tree(root.right))6 Sự khác biệt giữa tài liệu tham khảo và con trỏ là gì? Sự khác biệt chính giữa các con trỏ và tham số tham chiếu là - 1.References được sử dụng để giới thiệu một biến hiện có trong một tên khác trong khi con trỏ được sử dụng để lưu trữ địa chỉ của biến 2.References không thể có giá trị null được gán nhưng con trỏ có thể. 3. Một biến tham chiếu có thể được tham chiếu bằng cách vượt qua giá trị trong khi một con trỏ có thể được tham chiếu bằng cách vượt qua tham chiếu. 4. Một tham chiếu phải được khởi tạo theo khai báo trong khi không cần thiết trong trường hợp con trỏ. 5. Một tham chiếu chia sẻ cùng một địa chỉ bộ nhớ với biến ban đầu nhưng cũng chiếm một số không gian trên ngăn xếp trong khi con trỏ có địa chỉ và kích thước bộ nhớ riêng trên ngăn xếp Sự khác biệt giữa null và void là gì? Một con trỏ null có nghĩa là nó không chỉ vào bất cứ điều gì.Nếu, không có địa chỉ được gán cho một con trỏ, sau đó đặt nó thành null. Một loại con trỏ, tức là, int *, char * Mỗi loại có giá trị con trỏ null. Cú pháp như sau- def height_of_tree(root): # base case: empty tree has a height of 0 if root is None: return 0 # recur for the left and right subtree and consider maximum depth return 1 + max(height_of_tree(root.left), height_of_tree(root.right))7 Một con trỏ void không là gì ngoài người không có bất kỳ loại dữ liệu nào với nó.Nó cũng được gọi là một con trỏ mục đích chung.Nó có thể giữ địa chỉ của bất kỳ loại dữ liệu. Cú pháp như sau - Sự khác biệt giữa cây B và cây B+ là gì? Cây B là một loại cấu trúc cây tự cân bằng được thiết kế để lưu trữ một lượng lớn dữ liệu để truy vấn nhanh và truy xuất. Họ thường có thể bị nhầm lẫn với mối quan hệ gần gũi của họ - cây tìm kiếm nhị phân.Mặc dù cả hai đều là một loại cây tìm kiếm M-Way, cây tìm kiếm nhị phân được coi là một loại cây b đặc biệt. B-cây có thể có nhiều cặp khóa/giá trị trong một nút, được sắp xếp tăng dần theo thứ tự chính.Chúng tôi gọi cặp khóa/giá trị này là tải trọng.multiple key/value pairs in a node, sorted ascendingly by key order. We call this key/value pair a payload. Cây B được coi là rất thuận lợi vì chúng cung cấp độ phức tạp thời gian O (log (n)) logarit khi nói đến các hoạt động chèn, xóa và tìm kiếm.logarithmic O(log(n)) time complexity when it comes to insert, delete, and search operations. Phiên bản nổi tiếng nhất của cây B là cây B+.Điều gì phân biệt cây B+với cây B là hai khía cạnh chính: Tất cả các nút lá được liên kết với nhau trong một danh sách liên kết gấp đôi.Dữ liệu vệ tinh chỉ được lưu trữ trên các nút lá.Các nút bên trong chỉ giữ các phím và hoạt động như các bộ định tuyến đến nút lá chính xác Trong các cây B+, dữ liệu được lưu trữ trên nút lá giúp tìm kiếm hiệu quả hơn vì chúng ta có thể lưu trữ nhiều khóa hơn trong các nút bên trong - điều này có nghĩa là chúng ta cần truy cập ít nút hơn Xóa dữ liệu khỏi cây B+dễ dàng hơn và ít tốn thời gian hơn vì chúng ta chỉ cần xóa dữ liệu khỏi các nút láeasier and less time consuming because we only need to remove data from leaf nodes Trên thực tế, 99% hệ thống quản lý cơ sở dữ liệu sử dụng cây B+để lập chỉ mục. Trừu tượng dữ liệu là gì? Trừu tượng dữ liệu đề cập đến việc chỉ cung cấp thông tin cần thiết cho thế giới bên ngoài và ẩn các chi tiết nền của họ, tức là, để thể hiện thông tin cần thiết trong chương trình mà không cần trình bày các chi tiết.Trừu tượng dữ liệu là một kỹ thuật lập trình (và thiết kế) phụ thuộc vào việc tách giao diện và triển khai. Ví dụ: chương trình của bạn có thể thực hiện một cuộc gọi đến hàm Sắp xếp () mà không biết thuật toán nào chức năng thực sự sử dụng để sắp xếp các giá trị đã cho.Trên thực tế, việc triển khai cơ bản của chức năng sắp xếp có thể thay đổi giữa các bản phát hành của thư viện và miễn là giao diện vẫn giữ nguyên, cuộc gọi chức năng của bạn vẫn sẽ hoạt động.sort() function without knowing what algorithm the function actually uses to sort the given values. In fact, the underlying implementation of the sorting functionality could change between releases of the library, and as long as the interface stays the same, your function call will still work. Làm thế nào để các số đã ký và không dấu ảnh hưởng đến bộ nhớ? Trong trường hợp số đã ký, bit đầu tiên được sử dụng để cho biết liệu dương hay âm, khiến bạn còn một chút.Với các số không dấu, bạn có tất cả các bit có sẵn cho số đó.Hiệu ứng được thấy rõ nhất trong phạm vi số (số 8 bit không dấu có phạm vi 0-255, trong khi số ký 8 bit có phạm vi -128 đến +127. Làm thế nào để bạn tìm kiếm một khóa đích trong danh sách được liên kết? Để tìm khóa đích trong danh sách được liên kết, bạn phải áp dụng tìm kiếm tuần tự.Mỗi nút được đi qua và so sánh với phím đích và nếu nó khác nhau, thì nó sẽ theo liên kết đến nút tiếp theo.Việc truyền tải này tiếp tục cho đến khi tìm thấy khóa đích hoặc nếu đạt được nút cuối cùng. Infix, tiền tố và postfix trong cấu trúc dữ liệu là gì? Cách viết các biểu thức số học được gọi là ký hiệu.Có ba loại ký hiệu được sử dụng trong một biểu thức số học, tức là, mà không thay đổi bản chất hoặc đầu ra của biểu thức.Những ký hiệu này là: Ký hiệu tiền tố (đánh bóng) - Trong đó, toán tử được tiền tố cho các toán hạng, tức là trước các toán hạng. - In this, the operator is prefixed to operands, i.e. ahead of operands. Ký hiệu Infix - Trong đó, các toán tử được sử dụng ở giữa các toán hạng. - In this, operators are used in between operands. Ký hiệu Postfix (Đảo ngược -Polish) - Trong đó, toán tử được chuyển sang các toán hạng, tức là, sau các toán hạng. - In this, the operator is postfixed to the operands, i.e., after the operands.
Bạn có thể giải thích với một ví dụ làm thế nào để một hoạt động khai báo biến sẽ tiêu thụ hoặc ảnh hưởng đến phân bổ bộ nhớ? Lượng không gian hoặc bộ nhớ được chiếm hoặc phân bổ phụ thuộc vào loại dữ liệu của các biến được khai báo.Vì vậy, hãy giải thích tương tự bằng cách xem xét một ví dụ: Giả sử biến được khai báo là loại số nguyên thì 32 bit lưu trữ bộ nhớ được phân bổ cho biến cụ thể đó.Vì vậy, dựa trên loại dữ liệu của biến, không gian bộ nhớ sẽ được phân bổ. Có nghĩa là "thời gian khấu hao liên tục" khi nói về độ phức tạp về thời gian của thuật toán Thời gian khấu hao được giải thích bằng các thuật ngữ đơn giản: Nếu bạn thực hiện một hoạt động nói một triệu lần, bạn không thực sự quan tâm đến trường hợp xấu nhất hoặc trường hợp tốt nhất của hoạt động đó-điều bạn quan tâm là tổng cộng bao nhiêu thời gian khiBạn lặp lại hoạt động một triệu lần.Vì vậy, không có vấn đề gì nếu hoạt động rất chậm một lần, miễn là "một lần" là đủ hiếm để sự chậm chạp bị pha loãng. Về cơ bản thời gian khấu hao có nghĩa là "thời gian trung bình được thực hiện cho mỗi hoạt động, nếu bạn thực hiện nhiều hoạt động".Thời gian khấu hao không phải là hằng số;Bạn có thể có thời gian khấu hao tuyến tính và logarit hoặc bất cứ thứ gì khác., if you do many operations". Amortised time doesn't have to be constant; you can have linear and logarithmic amortised time or whatever else. Cấu trúc dữ liệu Trie là gì? Trie là một cấu trúc dữ liệu truy xuất thông tin hiệu quả.Sử dụng Trie, sự phức tạp tìm kiếm có thể được đưa đến giới hạn tối ưu (chiều dài khóa).Nếu chúng ta lưu trữ các khóa trong cây tìm kiếm nhị phân, một BST cân bằng tốt sẽ cần thời gian tỷ lệ thuận với m * log n, trong đó m là chiều dài chuỗi tối đa và n là số lượng các phím trong cây.Sử dụng Trie, chúng ta có thể tìm kiếm khóa trong thời gian O (M).O(M) time. Mỗi nút Trie bao gồm nhiều nhánh.Mỗi nhánh đại diện cho một đặc tính có thể của các phím.Chúng ta cần đánh dấu nút cuối cùng của mọi khóa là đầu của nút từ.Một trường Trie isendofword được sử dụng để phân biệt nút là đầu của nút từ.Một cấu trúc đơn giản để biểu diễn các nút của bảng chữ cái tiếng Anh có thể như sau, def height_of_tree(root): # base case: empty tree has a height of 0 if root is None: return 0 # recur for the left and right subtree and consider maximum depth return 1 + max(height_of_tree(root.left), height_of_tree(root.right))8 So sánh hoạt động tra cứu trong bảng băm trie vs? Các cố gắng hỗ trợ được lặp lại, trong khi việc lặp qua bảng băm sẽ dẫn đến thứ tự giả được đưa ra bởi hàm băm (cũng, thứ tự va chạm băm được thực hiện được xác định), thường là vô nghĩa. Cố gắng có xu hướng trung bình nhanh hơn khi chèn so với các bảng băm vì các bảng băm phải xây dựng lại chỉ số của chúng khi nó trở nên đầy đủ - một hoạt động rất tốn kém.Do đó, cố gắng có chi phí thời gian trường hợp xấu nhất bị ràng buộc tốt hơn nhiều, điều này rất quan trọng đối với các chương trình nhạy cảm về độ trễ. Cố gắng tạo điều kiện cho việc kết hợp lâu nhất, nhưng băm không, do hậu quả của những điều trên.Thực hiện một "phù hợp gần nhất" như vậy, có thể, tùy thuộc vào việc thực hiện, nhanh như một phát hiện chính xác. Sự khác biệt giữa các bảng băm và băm là gì? Băm: đơn giản là hành động biến một đoạn dữ liệu có độ dài tùy ý thành giá trị chiều rộng cố định (sau đây gọi là giá trị băm) có thể được sử dụng để biểu thị phần đó trong các tình huống liên quan đến khối dữ liệu gốc sẽ bất tiện. is simply the act of turning a data chunk of arbitrary length into a fixed-width value (hereinafter called a hash value) that can be used to represent that chunk in situations where dealing with the original data chunk would be inconvenient. Một bảng băm là một trong những tình huống đó;Nó chỉ đơn giản lưu trữ các tham chiếu đến các khối dữ liệu như vậy trong một bảng được lập chỉ mục bởi mỗi giá trị băm của từng khối.Bằng cách này, thay vì có khả năng so sánh khối khóa mong muốn của bạn với một số lượng lớn các khối, bạn chỉ cần tính toán giá trị băm của khối khóa và tìm kiếm nhanh hơn nhiều với giá trị băm đó. is one of those situations; it simply stores references to such data chunks in a table indexed by each chunk's hash value. This way, instead of potentially comparing your desired key chunk against a huge number of chunks, you simply compute the hash value of the key chunk and do a much faster lookup with that hash value. Khi nào bạn muốn sử dụng cấu trúc dữ liệu heap? Hàng đống là các cấu trúc có nghĩa là cho phép truy cập nhanh vào tối thiểu hoặc tối đa.Nó cho phép bạn kéo nhỏ nhất hoặc lớn nhất và nhanh chóng biết nhỏ nhất hoặc lớn nhất tiếp theo.Đó là lý do tại sao nó được gọi là hàng đợi ưu tiênPriority Queue Sử dụng nó bất cứ khi nào bạn cần truy cập nhanh vào vật phẩm lớn nhất (hoặc nhỏ nhất), bởi vì mục đó sẽ luôn là phần tử đầu tiên trong mảng hoặc ở gốc của cây.Tuy nhiên, phần còn lại của mảng được giữ một phần chưa được phân loại.Do đó, truy cập tức thì chỉ có thể đối với mục lớn nhất (nhỏ nhất).Các phần chèn vào rất nhanh, vì vậy đó là một cách tốt để đối phó với các sự kiện hoặc dữ liệu đến và luôn có quyền truy cập vào sớm nhất/lớn nhất.quick access to the largest (or smallest) item, because that item will always be the first element in the array or at the root of the tree. However, the remainder of the array is kept partially unsorted. Thus, instant access is only possible to the largest (smallest) item. Insertions are fast, so it's a good way to deal with incoming events or data and always have access to the earliest/biggest. Làm thế nào để bạn chuyển đổi một hàng đợi thành ngăn xếp? Để xây dựng một ngăn xếp bằng hàng đợi, chúng tôi cần hai hàng đợi (Q1, Q2) và cần mô phỏng các hoạt động ngăn xếp bằng cách sử dụng các hoạt động hàng đợi: Đẩy (phần tử E)(E element) 1. Nếu Q1 trống, Enqueue E đến Q1 2. Nếu Q1 không trống, Enqueue tất cả các yếu tố từ Q1 đến Q2, thì Enqueue E đến Q1 và Enqueue tất cả các phần tử từ Q2 trở lại Q1 nhạc pop dequeue một yếu tố từ q1 Như chúng ta thấy, Q1 đóng vai trò là nguồn chính cho ngăn xếp, trong khi Q2 chỉ là một hàng đợi người trợ giúp mà chúng ta sử dụng để bảo tồn thứ tự dự kiến bởi ngăn xếp. Giải thích làm thế nào để tìm thấy 100 số lớn nhất trong số 1 tỷ số? Cách tiếp cận đầu tiên của vấn đề là sắp xếp mảng trong thời gian O (nlogn) và lấy 100 số cuối cùng.Nhưng người phỏng vấn sẽ không hài lòng với giải pháp này vì vậy chúng ta cần phải nghĩ ra một giải pháp tốt hơn. Chúng tôi có thể giữ một hàng đợi ưu tiên của 100 số lớn nhất, lặp lại thông qua các số tỷ, bất cứ khi nào bạn gặp một số lớn hơn số nhỏ nhất trong hàng đợi (đầu của hàng đợi), hãy loại bỏ đầu của hàng đợi và thêm số mớiđến hàng đợi.priority queue of the 100 biggest numbers, iterate through the billion numbers, whenever you encounter a number greater than the smallest number in the queue (the head of the queue), remove the head of the queue and add the new number to the queue. Với hàng đợi ưu tiên được thực hiện với một đống, độ phức tạp của việc chèn vào hàng đợi là o (log n).Trong trường hợp xấu nhất, bạn nhận được tỷ*log2 (100) tốt hơn tỷ*log2 (tỷ)O(log N). In the worst case you get billion*log2(100) which is better than billion*log2(billion) Ưu điểm chính của việc cố gắng đối với các cây tìm kiếm nhị phân (BST) là gì? Sau đây là những lợi thế chính của việc cố gắng đối với các cây tìm kiếm nhị phân (BSTS): Nhìn lên chìa khóa nhanh hơn.Nhìn lên một khóa có độ dài m mất thời gian xấu nhất O (M).Một BST thực hiện các so sánh O (log (n)) của các khóa, trong đó n là số lượng các phần tử trong cây, bởi vì tra cứu phụ thuộc vào độ sâu của cây, là logarit về số lượng các phím nếu cây được cân bằng.Do đó, trong trường hợp xấu nhất, một BST mất thời gian O (m log n).Hơn nữa, trong nhật ký trường hợp xấu nhất (n) sẽ tiếp cận m.Ngoài ra, các hoạt động đơn giản cố gắng sử dụng trong quá trình tra cứu, chẳng hạn như lập chỉ mục mảng bằng cách sử dụng ký tự, nhanh chóng trên các máy thực.faster. Looking up a key of length m takes worst case O(m) time. A BST performs O(log(n)) comparisons of keys, where n is the number of elements in the tree, because lookups depend on the depth of the tree, which is logarithmic in the number of keys if the tree is balanced. Hence in the worst case, a BST takes O(m log n) time. Moreover, in the worst case log(n) will approach m. Also, the simple operations tries use during lookup, such as array indexing using a character, are fast on real machines. Số lượng các nút bên trong từ gốc đến lá bằng chiều dài của phím.Cân bằng cây do đó không quan tâm. Các thử có hiệu quả hơn khi chúng chứa một số lượng lớn các phím ngắn, bởi vì các nút được chia sẻ giữa các khóa với các chuỗi ban đầu chung. Sự khác biệt giữa chuỗi và mảng ký tự
Tại sao bảng băm không được sử dụng thay vì cây b để truy cập dữ liệu bên trong cơ sở dữ liệu? Trong một loại chỉ mục là một cây B và truy cập một phần tử trong một cây B trong thời gian logarit.Mặt khác, việc truy cập một phần tử trong bảng băm nằm trong O (1) thì tại sao chúng ta đang sử dụng B-Tree trong cơ sở dữ liệu.Lý do là bạn chỉ có thể truy cập các phần tử bằng khóa chính của chúng trong hashtable. Điều này nhanh hơn thuật toán cây (O (1) thay vì O (logn)) nhưng bạn không thể chọn phạm vi (mọi thứ ở giữa X và Y).Các thuật toán cây hỗ trợ điều này trong logn trong khi các chỉ mục băm có thể dẫn đến quét toàn bộ bảng o (n).O(1) then why we are using b-tree in database. The reason is you can only access elements by their primary key in a hashtable.This is faster than a tree algorithm(O(1) instead of O(logn)) but you cannot select ranges(everything in between x and y). Tree algorithms support this in logn whereas hash indexes can result in full table scan O(n). Làm thế nào để bạn in tất cả các lá của một cây nhị phân? Đây là một vấn đề mã hóa hấp dẫn khác dựa trên một cây nhị phân thường được hỏi về các lập trình viên mới.Nó khá đơn giản để giải quyết nếu bạn có bất kỳ sự quen thuộc nào với các vấn đề liên quan đến cây nhị phân.Chúng ta có thể sử dụng đệ quy ở đây.Bởi vì đệ quy được sử dụng trong hầu hết các vấn đề về cây nhị phân, chúng tôi áp dụng nó cho cả hai con trái và phải.Để trả lời vấn đề này, trước tiên bạn phải hiểu một nút lá là gì, vì nếu bạn không, bạn sẽ không thể giải quyết nó.Vì vậy, một nút lá là một nút có các nút con trái và phải là null.Vì vậy, chúng ta có thể in các nút lá của một BST kiểm tra từng nút nếu cả con trái và bên phải của chúng là null sau đó in nút.Trẻ em của nó là null ⮞ Lặp lại quá trình ở cả cây con trái và phải bằng cách sử dụng đệ quy. Khi nào danh sách liên kết gấp đôi hiệu quả hơn danh sách liên kết đơn lẻ? Bởi vì các danh sách được liên kết gấp đôi có quyền truy cập ngay vào cả hai đầu trước và mặt sau của danh sách, chúng có thể chèn và xóa dữ liệu ở hai bên trong thời gian O (1).Danh sách được liên kết gấp đôi là cấu trúc dữ liệu cơ bản lý tưởng cho hàng đợi vì chúng có thể chèn dữ liệu ở cuối thời gian O (1) và xóa dữ liệu khỏi phía trước trong thời gian O (1).Danh sách liên kết gấp đôi được sử dụng trong thiết kế bộ đệm LRU vì chúng tôi cần loại bỏ các mục ít nhất gần đây nhất.Hoạt động xóa nhanh hơn.Trong danh sách liên kết đơn, tất cả các hoạt động đòi hỏi một con trỏ thêm trước để được duy trì.Ví dụ, trong chèn, chúng ta cần sửa đổi các con trỏ trước đó cùng với các gợi ý tiếp theo. Tìm độ dài của vòng lặp trong danh sách được liên kết có chứa chu kỳ Thuật toán phát hiện chu kỳ của Floyd là nền tảng cho vấn đề này.Ý tưởng là sử dụng hai con trỏ, một gợi ý nhanh chóng và cái kia di chuyển chậm.Cả hai điểm đều di chuyển danh sách được liên kết ở các tốc độ khác nhau và khi chúng gặp nhau, nó chỉ ra rằng danh sách liên kết có một chu kỳ.Lưu địa chỉ của nút này và bắt đầu tăng một bộ đếm với 1 trong khi đi qua danh sách liên kết bằng cách sử dụng một con trỏ khác từ điểm chung.Chúng tôi sẽ có số lượng nút của chúng tôi trong số lượng chu kỳ trong con trỏ bất cứ khi nào chúng tôi đạt được con trỏ chung một lần nữa.Số này sẽ được trả lại cho bạn.Algorithm: ⮞ Lấy hai con trỏ, một con trỏ nhanh và một con trỏ chậm trỏ vào đầu ban đầu.Traverse cả hai con trỏ là SlowPtr = SlowPtr-> Tiếp theo (1 nút tại một thời điểm) và fastPtr = fastPtr-> next-> next (2 nút cùng một lúc).Khi SlowPtr == FASTPTR, điểm chung là nút cho đầu chu kỳ.⮞ Khắc phục một con trỏ tới nút này và lấy Count = 0 và di chuyển con trỏ khác từ điểm chung một trong danh sách được liên kết và tăng bộ đếm 1 trong mỗi bước ⮞ Khi con trỏ khác đạt đến điểm chung sau đó dừng lần lặp lạivà trả lại số lượng. Biểu đồ bipartite là gì?Làm thế nào để phát hiện một? Hãy để xem xét một biểu đồ G (V, E).Biểu đồ G là biểu đồ lưỡng cực nếu: • Tập đỉnh v của g có thể được phân vùng thành hai bộ phân tách và tập hợp độc lập v1 và v2 • Tất cả các cạnh từ bộ cạnh e có một đỉnh điểm cuối từ tập V1 và một đỉnh điểm cuối khác từtập V2 Một số điểm quan trọng liên quan đến biểu đồ bipartite • Nếu biểu đồ là biểu đồ lưỡng cực thì nó sẽ không bao giờ chứa các chu kỳ lẻ.• Các sơ đồ con của biểu đồ lưỡng cực cũng là bipartite.• Trong một biểu đồ lưỡng cực không mong muốn, mức độ của mỗi bộ phân vùng đỉnh luôn luôn bằng nhau.Để kiểm tra xem đồ thị có phải là bipartite hay không, chúng tôi sử dụng màu đồ thị và BFS để xác định nó.Dưới đây là các bước của thuật toán: gán một màu đỏ cho đỉnh bắt đầu bắt đầu ⮞ Tìm các hàng xóm của đỉnh bắt đầu và gán một màu khác (giả sử màu xanh)Tất cả các đỉnh trong biểu đồ được tô màu ⮞ Trong quá trình này nếu một đỉnh hàng xóm và đỉnh đến có cùng màu thì chúng ta trả về đồ thị không phải là biểu đồ lưỡng cực Làm thế nào để tính toán số fibonacci mà không cần đệ quy? Đôi khi một người phỏng vấn hỏi bạn một số câu hỏi khó chỉ để kiểm tra xem bạn có thể đi được bao xa.Vì vậy, câu hỏi này là một trong số đó.Chúng ta đều biết cách tìm số Fibonacci trong đệ quy hoặc lặp và đối với số lượng lớn hơn, chúng ta có thể sử dụng kỹ thuật ghi nhớ để lưu trữ các giá trị chồng chéo.Độ phức tạp về thời gian cho từng phương pháp như sau: đệ quy: O (2N) Đây là cách tiếp cận ngây thơ nhất để tính toán số fibonacci và đệ quy.Trong công thức Stack.binet: Cách tiếp cận này sẽ thất bại đối với các giá trị cao hơn của n.Ví dụ như ví dụ.Kết quả được đưa ra bởi mã dưới đây cho n = 71 là 308061521170129, trong khi câu trả lời đúng là 308061521170130. Vì vậy, phương pháp này sẽ chỉ hoạt động tốt cho các giá trị nhỏ của N và hiếm khi được sử dụng thực tế.Vì vậy, số fibonacci thứ n được đưa ra bởi công thức sau: Goldenratio = (1 + sqrt (5)) / 2 vòng quay trở lại (pow (goldenratio, n) / sqrt (5)) Độ phức tạp thời gian của phương pháp này là O (1) Thuật toán sắp xếp xô là gì? Thùng sắp xếp, còn được gọi là BIN Sắp xếp, là một thuật toán sắp xếp phân chia nội dung của một mảng thành nhiều thùng.Các thùng sau đó được sắp xếp từng cái một, với một thuật toán sắp xếp riêng hoặc bằng cách áp dụng quy trình sắp xếp xô đệ quy.Vòng lặp qua mảng ban đầu và đặt từng phần tử mảng vào một thùng xô.Sắp xếp từng thùng không trống bằng cách sử dụng sắp xếp chèn.Ghé thăm các thùng theo thứ tự và đặt tất cả các yếu tố trở lại vào mảng ban đầu Độ phức tạp: Độ phức tạp thời gian trường hợp xấu nhất: θ (N2) Độ phức tạp về thời gian trường hợp trung bình: θ (n+k) Độ phức tạp thời gian trường hợp tốt nhất: θ (n+k) Độ phức tạp không gian: θ (n+k) Sự khác biệt giữa hashmap và hashtable Hashmap và khóa cửa hàng Hashtable và các cặp giá trị.Khi sử dụng hashtable hoặc hashmap, chúng tôi chỉ định một đối tượng để làm khóa và giá trị được liên kết với khóa đó.
Giải thích thuật toán Boyer Moore? Thuật toán Boyer Moore là một thuật toán tìm kiếm tìm kiếm một chuỗi có chiều dài n và một mẫu có độ dài m.Nó in tất cả các sự xuất hiện của mẫu trong văn bản.Boyer Moore sử dụng cả một nhân vật xấu heuristic và một nhân vật tích cực heuristic.Mỗi người trong số họ được sử dụng để tự mình tìm kiếm mẫu.Xử lý mẫu được sử dụng để tạo ra các mảng riêng biệt cho cả hai phương pháp phỏng đoán trong phương pháp này và heuristic tốt nhất được sử dụng ở mỗi giai đoạn.Boyer Moore bắt đầu bằng cách khớp với mẫu trước đó, khác với phương pháp của KMP và Naive. Tại sao chúng ta sử dụng O Big O thay vì Big Theta (θ) Bởi vì, khi phân tích hiệu suất, chúng tôi thường chỉ quan tâm đến trường hợp xấu nhất.Do đó, biết giới hạn trên là đủ.Khi nó hoạt động tốt hơn dự kiến cho đầu vào đã cho.Một số thuật toán không bị ràng buộc chặt chẽ chút nào.Hơn nữa, giới hạn chặt chẽ thường khó tính hơn. Sự khác biệt giữa kỹ thuật quay lại và liên kết nhánh
Cấu trúc dữ liệu Câu hỏi phỏng vấn một cách ngắn gọnĐây là một số trong những câu hỏi phỏng vấn cấu trúc dữ liệu thường gặp nhất.Các câu hỏi phụ thuộc vào mức độ kinh nghiệm của bạn và vị trí bạn đang phỏng vấn.Nói chung, các công ty cố gắng đánh giá bạn tốt như thế nào trong những điều bạn tuyên bố biết. Chúng tôi hy vọng rằng các cấu trúc dữ liệu trên các câu hỏi phỏng vấn đã đủ để giải thích cho bạn tầm quan trọng của việc nghiên cứu các cấu trúc dữ liệu và thuật toán.Đừng chán nản nếu bạn không biết làm thế nào để thực hiện các bước cần thiết để cải thiện kiến thức của bạn về DSA và nhận được công việc bạn có trong khi trả lời các câu hỏi phỏng vấn các cấu trúc dữ liệu này. Bạn có thể tham gia khóa học cấu trúc dữ liệu và thuật toán của LogicMojo để nâng cao kiến thức, kinh nghiệm và hướng dẫn kỹ thuật của bạn sẽ giúp bạn đảm bảo công việc mơ ước. Cấu trúc dữ liệu nào được hỏi nhiều nhất trong cuộc phỏng vấn?Có các cấu trúc dữ liệu khác nhau dựa trên băm, nhưng cấu trúc dữ liệu được sử dụng phổ biến nhất là bảng băm.Các bảng băm thường được triển khai bằng các mảng ... Hàm băm .. Kích thước của bảng băm .. Phương pháp xử lý va chạm .. Câu hỏi phỏng vấn cấu trúc dữ liệu yêu thích của bạn là gì?Đảo ngược một chuỗi bằng cách sử dụng ngăn xếp.Thực hiện hai ngăn xếp trong một mảng ... Chèn?Thêm một mục dữ liệu mới trong bộ sưu tập các mục dữ liệu đã cho .. Xóa?Xóa một mục dữ liệu hiện có khỏi bộ sưu tập các mục dữ liệu đã cho .. Đi qua?Truy cập chính xác từng mục dữ liệu một lần để có thể xử lý .. Đang tìm kiếm ?.... Sắp xếp?. Các câu hỏi quan trọng trong cấu trúc dữ liệu là gì?Cấu trúc dữ liệu cơ bản Câu hỏi phỏng vấn cho sinh viên năm mới.. Cấu trúc dữ liệu là gì?.... Tại sao tạo cấu trúc dữ liệu?.... Một số ứng dụng của cấu trúc dữ liệu là gì?.... Giải thích quá trình đằng sau việc lưu trữ một biến trong bộ nhớ..... Bạn có thể giải thích sự khác biệt giữa cấu trúc tệp và cấu trúc lưu trữ không ?. 5 cấu trúc dữ liệu chính là gì?Cấu trúc dữ liệu tuyến tính.. Cấu trúc dữ liệu mảng.Trong một mảng, các phần tử trong bộ nhớ được sắp xếp trong bộ nhớ liên tục..... Stack Cấu trúc dữ liệu.Trong cấu trúc dữ liệu ngăn xếp, các phần tử được lưu trữ trong nguyên tắc LIFO..... Cấu trúc dữ liệu hàng đợi..... Cấu trúc dữ liệu danh sách được liên kết .. |
