Một số điểm cần lưu ý trong khi viết resume
- Với những bạn đang học đại học thì thường resume không nên dài quá 1 trang
- Bạn nên viết rõ mục tiêu của bạn [objective] vào trong resume để nhà tuyển dụng hiểu rõ bạn đang tìm kiếm điều gì trong công việc tiếp theo.
- Nhấn mạnh những kĩ năng có liên quan đến công việc bạn đang tìm kiếm, và nếu cần thiết thì phải bỏ đi những phần không liên quan.
- Nếu bạn còn đang là sinh viên thì nên ghi rõ trường bạn đang học và điểm trung bình tới thời điểm gần nhất.
- Khi bạn viết resume xong, hãy đưa thử một người khác đọc và hỏi họ xem, nếu họ là nhà tuyển dụng, họ có chú ý đến bạn hay không, từ đó bạn hãy lắng nghe những gì họ nói và sửa đổi để hoàn thiện resume của mình hơn
Ví dụ: một resume được trình bày rõ ràng
Những bước cơ bản để nộp hồ sơ và thu hút nhà tuyển dụng
- Nếu bạn có quen biết ai trong một công ty nào nó, hãy nhờ họ giới thiệu bạn vào công ty đấy [ask for referral]. Đây là cách dễ nhất để được chọn phỏng vấn, tất nhiên với điều kiện là bạn cũng phải là một người có thực lực.
- Có nhiều cách để giới thiệu bản thân đến các công ty như hội chợ việc làm, Linkedin... Bạn có thể liên hệ trực tiếp nhà tuyển dụng để giới thiệu bản thân.
- Một số công ty lớn thì sẽ yêu cầu bạn nộp hồ sơ qua Internet. Họ sẽ yêu cầu bạn có resume, thỉnh thoảng có cả thư xin việc [cover letter], và học bạ [transcript].
- Nếu bạn đang tìm kiếm một công việc có liên quan đến nghiên cứu khoa học, và bạn có một bài báo ở một hội nghị khoa học lớn, bạn nên tham dự vì sẽ có rất nhiều nhà tuyển dụng của các công ty hàng đầu thế giới đến để mời chào bạn.
Quy trình phỏng vấn thông thường
- Coding assessment: Phần này bạn sẽ phải giải 1 đến 2 bài toán trong một thời gian quy định. Các bài toán này chủ yếu tập trung vào thuật toán [algorithms] và cấu trúc dữ liệu [data structure] đơn giản, không quá phức tạp.
- Phone screening: Phần này bạn sẽ phải trả lời phỏng vấn trực tiếp qua điện thoại [hoặc Skype/Hangouts/...]
- Onsite Interview: Đến vòng phỏng vấn này, bạn sẽ được mời đến công ty và sẽ có 3-5 người phỏng vấn bạn trực tiếp tại chỗ. Ở mỗi lần phỏng vấn, sẽ có khoảng 1 đến 3 nhân viên đưa ra những câu hỏi khác nhau cho bạn. Một số công ty sẽ có nhân viên dẫn bạn đi ăn sáng/trưa/tối để đánh giá con người của bạn.
- Interview with hiring manager: Một số công ty sẽ yêu cầu bạn thêm một phần phỏng vấn với một hiring manager, người đưa ra quyết định cuối cùng về việc có tuyển dụng bạn hay không. Ở vòng này có thể là technical hoặc behavioral skills.
Những điều cần biết khi trả lời phỏng vấn
- Nếu bạn không bị bắt buộc về ngôn ngữ lập trình khi phỏng vấn, hãy nói rõ cho người phỏng vấn biết ngôn ngữ bạn lựa chọn để phỏng vấn là gì.
- Khi đọc câu hỏi xong, bạn nên xác định lại với người phỏng vấn rằng bạn đã hiểu rõ câu hỏi để tránh thời gian bạn hiểu sai câu hỏi, dẫn đến lãng phí thời gian.
- Bạn không nên hỏi người phỏng vấn về độ phức tạp của thuật toán mà họ yêu cầu. Đây là một phần đánh giá mà thường thì người phỏng vấn sẽ đặt ra để bạn tự tìm kiếm cách trả lời tối ưu.
- Trong quá trình suy nghĩ trả lời câu hỏi, bạn cần phải nghĩ đến cả các giới hạn và những điều bạn có thể giả định trước được. Ví dụ như nếu bài toán có đầu vào là một dãy số, bạn cần biết đó là dãy số tự nhiên hay số thực, và dãy số có độ dài là bao nhiêu, và định dạng của đầu vào như thế nào.
- Khi bạn trả lời một câu hỏi phỏng vấn thì hãy đưa ra một cách giải đơn giản nhất, không cần phải tối ưu [trừ khi bạn chắc chắn rằng cách giải tối ưu của bạn là đúng, và bạn có thể lập trình trong một thời gian ngắn]. Nếu như bạn không nghĩ ra cách giải tối ưu thì ít nhật bạn cũng có một cách giải để giải quyết được bài toán. Trong thực tế thì có những bài toán thì cách giải tối ưu cũng chỉ là một phép tối ưu hoá từ những cách giải đơn giản.
- Khi bạn trả lời phỏng vấn qua điện thoại thì phải nói hết ra những gì bạn suy nghĩ. Quá trình này ban đầu có vẻ rất khó để luyện tập, nhưng nếu như bạn không làm như vậy thì không cách nào người phỏng vấn có thể biết được bạn đang suy nghĩ gì, và cách họ đánh giá về bạn cũng không được rõ ràng và chính xác nhất.
- Nếu như trong vòng 2 đến 3 phút và bạn không có một ý tưởng để trả lời câu hỏi thì bạn có thể yêu cầu một gợi ý để bạn có thể giải quyết bài toán. Đây là một điều chấp nhận được và rất bình thường trong phỏng vấn.
- Điều quan trọng nhất của một cuộc phỏng vấn đó là hãy xem nó như một cuộc trò chuyện về một bài toán giữa hai lập trình viên với nhau. Bạn cần phải thoải mái bởi vì họ cũng sẽ đánh giá ở tiêu chí này. Người phỏng vấn cần biết được rằng bạn có thể là một người đồng nghiệp của họ trong tương lai được hay không.
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ời
Dạ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:
- Câu hỏi về thuật toán [algorithms]
- Câu hỏi về cấu trúc dữ liệu [data structure]
- Câu hỏi về khả năng thiết kế hệ thống [system design]
Dạng câu hỏi về kĩ năng ứng xử [behavioral questions]
- Một số công ty sẽ yêu cầu bạn trả lời những tình huống nhất định để đánh giá về con người của bạn có phù hợp với yêu cầu nhất định hay không.
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ú ý
- Khả năng chuyên môn giỏi: Điều này thể hiện qua cách bạn giải quyết các vấn đề, bài toán mà họ đưa ra. Bạn có thể không phải là người giỏi nhất, nhưng chỉ cần bạn thể hiện đúng năng lực của mình với sự tự tin và kiến thức của bản thân, họ sẽ có một đánh giá công bằng nhất về trình độ hiện tại và có thể là tương lai của bạn.
- Khả năng giao tiếp thuần thục: Họ đang tìm kiếm những nhân viên tương lai mà họ đánh giá rằng họ có thể huấn luyện/làm việc chung với chính bản thân họ được. Vì vậy, hãy cứ thoải mái chia sẻ và trao đổi với người phỏng vấn để họ biết được khả năng thật sự của bạn ở mức độ nào.
- Sự trung thật: Bạn sẽ không bao giờ thành công nếu thiếu yếu tố này. Một ví dụ đơn giản như nếu bạn đã biết chắc chắn đáp án của câu hỏi mà nhà tuyển dụng đưa ra, hãy thành thật nói với họ như vậy.
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 important
Nhiề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à
ðÿš € Làm thế nào để chúng ta thiết kế thuật toán tốt?
ðÿš € Làm thế nào để chúng ta biết rằng thuật toán của chúng ta là hiệu quả?
ðÿš € Làm thế nào để thực hiện hiệu quả các thuật toán trong ngôn ngữ lập trình?
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:
| 25 lakh | |
| Amazon | 25 lakh |
| Amazon | Walmartlabs |
| 23 lakh | Walmartlabs |
| 23 lakh | Flipkart |
| Microsoft | 24 lakh |
| Uber | 21 lakh |
| Từng trên | 18 lakh |
| Intuit | 24 lakh |
Uber
21 lakh
Từng trên
18 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ẹt
Bị 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:
ðÿš € Nói qua những gì bạn nghĩ ban đầu có thể hoạt động và giải thích lý do tại sao nó không
ðÿš € Hãy đến với nhiều trường hợp kiểm tra hơn và viết chúng ra
ðÿš € Hãy suy nghĩ về cách bạn sẽ giải quyết nó mà không cần một chương trình
ðÿš € Nhớ lại các câu hỏi trong quá khứ liên quan đến chủ đề, những câu hỏi tương tự nào trong quá khứ bạn đã gặp và bạn đã sử dụng những kỹ thuật nào để giải quyết chúng?
ðÿš € liệt kê thông qua các cấu trúc dữ liệu phổ biến và liệu chúng có thể được áp dụng cho câu hỏi hay không.Thực sự không có nhiều - ngăn xếp, hàng đợi, từ điển, đống, đồ thị, v.v.
ðÿš € Xem ra công việc lặp đi lặp lại và xác định xem bạn có thể lưu trữ các tính toán đó không.
Trong khi mã hóa
Viế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óa
Sau 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ấn
Cấ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ấu trúc dữ liệu tuyến tính: Cấu trúc dữ liệu tuyến tính là các cấu trúc có phần tử theo cách tuần tự và theo thứ tự.Ví dụ: mảng, danh sách được liên kết: Linear data structures are those whose elements are in sequential and in ordered way. For example: Array, Linked list
Cấu trúc dữ liệu phi tuyến tính: Cấu trúc dữ liệu phi tuyến tính không tạo thành một chuỗi, tức là mỗi mục hoặc phần tử được kết nối với hai hoặc nhiều mục khác trong một sắp xếp phi tuyến tính.Các yếu tố dữ liệu không được sắp xếp trong cấu trúc tuần tự.Ví dụ: đồ thị, cây: The Non-linear data structure does not form a sequence i.e. each item or element is connected with two or more other items in a non-linear arrangement. The data elements are not arranged in the sequential structure. For Example : Graphs, Trees
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à:
Lưu trữ dữ liệu ở dạng bảng.Ví dụ, chi tiết liên hệ của một người.Điều này được thực hiện thông qua các mảng.
Mảng được sử dụng rộng rãi trong xử lý hình ảnh và xử lý lời nói.
Trình phát nhạc và thanh trượt hình ảnh sử dụng danh sách được liên kết để chuyển sang các mục tiếp theo hoặc trước đó.
Một hàng đợi được sử dụng để lên lịch công việc, việc sắp xếp các gói dữ liệu để liên lạc.
Các công nghệ như blockchain, mật mã dựa trên các thuật toán băm.
Ma trận được sử dụng rộng rãi để thể hiện dữ liệu và vẽ đồ thị, thực hiện phân tích thống kê.
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:
Xóa: Xóa một phần tử hiện có khỏi cấu trúc dữ liệu: Deleting an existing element from the data structure
Chèn: Thêm một phần tử mới vào cấu trúc dữ liệu: Adding a new element to the data structure
Tìm kiếm: Tìm vị trí của một phần tử, nếu nó tồn tại, trong cấu trúc dữ liệu: Find the location of an element, if it exists, in the data structure
Sắp xếp: Sắp xếp các yếu tố của cấu trúc dữ liệu trong:: Arranging elements of the data structure in:
Traversal: Truy cập từng yếu tố của cấu trúc dữ liệu một lần để xử lý: Accessing each element of the data structure once for processing
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:
Kích thước mảng được cố định tại thời gian chạy và không thể sửa đổi sau này, nhưng các danh sách được liên kết có thể được mở rộng trong thời gian thực, theo yêu cầu.
Các danh sách được liên kết không được lưu trữ liên tục trong bộ nhớ, do đó, chúng hiệu quả hơn rất nhiều so với các mảng được lưu trữ tĩnh.
Vì kích thước của một danh sách được liên kết có thể phát triển hoặc thu nhỏ dựa trên nhu cầu của chương trình, không có bộ nhớ bị lãng phí vì nó được phân bổ trong thời gian chạy.
Quá trình chèn và xóa rất tốn kém trong một mảng vì phòng phải được tạo ra cho các yếu tố mới và các yếu tố hiện có phải được thay đổi.
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:
Ít hơn số lượng hoạt động truy cập ngẫu nhiên.
Khi chúng tôi muốn chèn các mục ở bất cứ đâu ở giữa danh sách, chẳng hạn như khi thực hiện hàng đợi ưu tiên, danh sách được liên kết phù hợp hơn.
Khi chúng ta không biết số lượng chính xác của các yếu tố trước đó.
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:
Khi chúng ta cần tốc độ trong khi lặp lại các yếu tố trong chuỗi.
Khi chúng ta cần lập chỉ mục hoặc truy cập ngẫu nhiên các yếu tố thường xuyên hơn.
Do tính chất của các mảng và danh sách được liên kết, có thể nói rằng các mảng điền sử dụng ít bộ nhớ hơn các 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.
Bộ nhớ cache của trình duyệt với các trang đã truy cập ngược
Chức năng hoàn tác và làm lại trên các nền tảng như Word, Paint, v.v., nơi bạn có thể đảo ngược nút để đến trang trước.
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à:
Kiểm tra các dấu ngoặc đơn cân bằng trong một biểu thức
Đảo ngược một chuỗi
Đánh giá các biểu thức khác nhau
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:
Trong tối đa phần tử dữ liệu có ở nút gốc phải là lớn nhất trong số tất cả các phần tử dữ liệu có trong cây.
Trong một phần nhỏ, phần tử dữ liệu có ở nút gốc phải là nhỏ nhất [hoặc tối thiểu] trong số tất cả các phần tử dữ liệu có trong cây.
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:
Hàng đợi: Điều này được triển khai bằng danh sách liên kết gấp đôi.Kích thước tối đa của hàng đợi được xác định bởi kích thước bộ đệm, tức là bằng tổng số khung có sẵn.Các trang được sử dụng gần đây nhất gần đây sẽ ở gần đầu phía trước của hàng đợi trong khi các trang được sử dụng gần đây nhất sẽ hướng về phía sau của hàng đợi.This is implemented using a doubly-linked list. The maximum size of the queue is determined by the cache size, i.e by the total number of available frames. The least recently used pages will be near the front end of the queue whereas the most recently used pages will be towards the rear end of the queue.
Hashmap: Hashmap lưu trữ số trang làm khóa cùng với địa chỉ của nút hàng đợi tương ứng làm giá trị.Hashmap stores the page number as the key along with the address of the corresponding queue node as the value.
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à:
FileSystems: Các tập tin bên trong các thư mục được đưa vào bên trong các thư mục khác.
Nhận xét trên phương tiện truyền thông xã hội: Nhận xét, trả lời nhận xét, trả lời trả lời vv tạo thành một đại diện cây.
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:
Traverse Subtree bên trái, tức là, gọi inorder [root.left]
Ghé thăm gốc, tức là in [root.val]
Traverse Subtree bên phải, tức là, gọi inorder [root.right]
Truyền hàng trước
Ghé thăm gốc, tức là in [root.val]
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]
Trực tiếp trước Traversal
Traverse Subtree bên trái, tức là, gọi bưu điện [root.left]
Traverse Subtree bên phải, tức là, gọi bưu điện [root.right]
Ghé thăm gốc, tức là in [root.val]
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]
Bưu điện truyền tải
Traverse Subtree bên trái, tức là, gọi bưu điện [root.left]
Traverse Subtree bên phải, tức là, gọi bưu điện [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.
Cây con bên trái và bên phải cũng phải là một cây tìm kiếm nhị phân.level by level whereas DFS follows first a path from the starting to the end node, then another path from the start to end, and so on until all nodes are visited.
Cấu trúc dữ liệu đồ thị là gì?queue data structure for storing the nodes whereas DFS uses the stack for traversal of the nodes for implementation.
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.
Sắp xếp cấu trúc liên kết trong một biểu đồ là gì?O[M+N], [where M is the number of edges],[where N is the number of nodes]. That's the fastest time we can expect, since we'll have to look at all the nodes and edges at least once.
Thuật toán sắp xếp tôpô lấy một biểu đồ có hướng và trả về một mảng các nút nơi mỗi nút xuất hiện trước tất cả các nút mà nó trỏ đến.Overall space complexity: O[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
Tất cả cùng nhau, độ phức tạp về thời gian là O [M+N], [trong đó m là số lượng cạnh], [trong đó n là số lượng nút].Đó là thời gian nhanh nhất chúng ta có thể mong đợi, vì chúng ta sẽ phải xem xét tất cả các nút và cạnh ít nhất một lần. It linearly scans and linearly partitions the input. This means we can make the most of every cache load.
Nói chung, chúng ta có ba cấu trúc và tất cả chúng đều là không gian o [n].Độ phức tạp không gian tổng thể: O [n]
Thuật toán sắp xếp nào được coi là nhanh nhất?Tại sao?
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 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.
Algorithm:
⮞ Take two pointers, a fast pointer, and a slow pointer pointing to the head initially.
Traverse both the pointers as slowptr = slowptr->next [1 node at a time], and fastptr = fastptr->next->next [2 nodes at a time].
⮞ When slowptr == fastptr, the common point is the node for the head of the cycle.
⮞ Fix one pointer to this node and take count = 0 and move the other pointer from the common point one by one in the linked list and increment the counter by 1 in each step
⮞ When the other pointer reaches the common point then stop the iteration and return the count.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
• The vertex set V of G can be partitioned into two disjoint and independent sets V1 and V2
• All the edges from the edge set E have one endpoint vertex from the set V1 and another endpoint vertex from the set V2Mộ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
• If a graph is a bipartite graph then it’ll never contain odd cycles.
• The subgraphs of a bipartite graph are also bipartite.
• In an undirected bipartite graph, the degree of each vertex partition set is always equal.
To check whether graph is bipartite or not we use graph coloring and BFS to determine it.
Here are the steps of algorithm:
⮞ Assign a red color to the starting vertex start
⮞ Find the neighbors of the starting vertex and assign a different color[let's say blue]
⮞ Find the neighbor’s neighbor and assign a red color
⮞ Continue this process until all the vertices in the graph get colored
⮞ During this process if a neighbour vertex and coming vertex are of same color then we return graph is not a bipartite graphLà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]
Recursion: O[2N] This is the most naive approach to calculate fibonacci number and recursion.
Iterative or using memoization: O[n] Storing these values prevent us from constantly using memory space in the Stack.
Binet Formula: This approach will fail for higher values of n. For eg. The result given by below code for n = 71 is 308061521170129, while the correct answer is 308061521170130. So, this method will work well only for small values of n and is rarely used practically.
So, The nth Fibonacci number is given by the following formula:
goldenRatio = [1 + sqrt[5]] / 2
return round[pow[goldenRatio, n] / sqrt[5]]
Time complexity of this method is 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
Algorithm:
Create an empty array of size n[n empty buckets].
Loop through the original array and put each array element in a “bucket”.
Sort each of the non-empty buckets using insertion sort.
Visit the buckets in order and put all elements back into the original arrayĐộ 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]
Average case time complexity:Θ[n+k]
Best case time complexity:Θ[n+k]
Space complexity:Θ[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 đó.
| Không có phương pháp được đồng bộ hóa. | Mỗi phương pháp được đồng bộ hóa. |
| Chủ đề không bắt buộc phải chờ và do đó hiệu suất tương đối cao. | Nó tăng thời gian chờ của luồng và do đó hiệu suất thấp. |
| Null được phép cho cả khóa và giá trị | NULL không được phép cho cả khóa và giá trị.Nếu không, chúng ta sẽ có một ngoại lệ con trỏ null. |
| Hashmap kế thừa lớp Tóm tắt. | Hashtable kế thừa lớp từ điển. |
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
| Backtracking là một kỹ thuật để khám phá tất cả các giải pháp khả thi cho một vấn đề.Khi nó nhận ra nó đã đưa ra một quyết định bị lỗi, nó đảo ngược quyết định trước đó bằng cách sao lưu nó.Nó tìm kiếm cây vũ trụ trạng thái cho đến khi tìm thấy giải pháp cho vấn đề. | Các thách thức tối ưu hóa được giải quyết với chi nhánh và ràng buộc.Nó từ bỏ giải pháp trước khi nó nhận ra rằng nó đã có một giải pháp tối ưu tốt hơn mà giải pháp trước dẫn đến.Để tìm câu trả lời tốt nhất, nó tìm kiếm toàn bộ cây vũ trụ trạng thái. |
| Backtracking liên quan đến chức năng khả thi. | Chi nhánh và giới hạn liên quan đến một chức năng giới hạn. |
| Backtracking được sử dụng để giải quyết vấn đề quyết định. | Chi nhánh và giới hạn được sử dụng để giải quyết vấn đề tối ưu hóa. |
| Nó hiệu quả hơn | Nó kém hiệu quả hơn |
| Hữu ích trong việc giải quyết vấn đề N-queen, tổng hợp tập hợp con. | Hữu ích trong việc giải quyết vấn đề nhân viên bán hàng du lịch, vấn đề ba lô. |
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.