Leetcode lu&ocirc;n l&agrave; một thế mạnh gi&uacute;p c&aacute;c lập tr&igrave;nh vi&ecirc;n vượt qua b&agrave;i phỏng vấn về code. Tuy nhi&ecirc;n, nhiều lập tr&igrave;nh vi&ecirc;n đ&atilde; n&oacute;i rằng c&aacute;ch thức phỏng vấn hiện nay đ&atilde; ho&agrave;n to&agrave;n thay đổi. Ba năm trước, c&aacute;c c&ocirc;ng ty c&ocirc;ng nghệ sẽ kh&ocirc;ng bao giờ y&ecirc;u cầu bạn trả lời hai c&acirc;u hỏi kh&oacute; về Leetcode trong một lần duy nhất. Mặc d&ugrave; vậy, nhiều doanh nghiệp c&ocirc;ng nghệ hiện nay như Facebook sẽ y&ecirc;u cầu bạn trả lời hai c&acirc;u hỏi ở độ kh&oacute; trung b&igrave;nh - nếu kh&ocirc;ng bạn sẽ kh&ocirc;ng đủ điều kiện tham gia v&ograve;ng tiếp theo của cuộc phỏng vấn.
H&igrave;nh thức phỏng vấn n&agrave;y trở th&agrave;nh cuộc chiến xem ai l&agrave; người c&oacute; thể nhận ra c&aacute;c c&acirc;u hỏi giống dạng Leetcode nhất trong một lần duy nhất v&agrave; n&oacute; kh&ocirc;ng thực sự kiểm tra năng lực v&agrave; kinh nghiệm giải quyết vấn đề.
Nhiều doanh nghiệp nhận thấy rằng việc sử dụng c&aacute;c thuật to&aacute;n th&ocirc;ng thường của Leetcode kh&ocirc;ng phải l&agrave; phương ph&aacute;p tối ưu để đ&aacute;nh gi&aacute; khả năng th&agrave;nh c&ocirc;ng của ứng vi&ecirc;n tại nơi l&agrave;m việc. Ch&iacute;nh v&igrave; thế, một loại h&igrave;nh thức c&acirc;u hỏi phỏng vấn mới đ&atilde; xuất hiện nhằm mục đ&iacute;ch kiểm tra khả năng xử l&yacute; vấn đề v&agrave; kinh nghiệm l&agrave;m việc của ứng vi&ecirc;n.
<h2 style="text-align: justify;">C&acirc;u hỏi</h2>
C&oacute; một dịch vụ cần thực hiện một số c&ocirc;ng việc v&agrave; gọi API b&ecirc;n thứ 3 - t&ecirc;n l&agrave; <code>API A</code>. <code>API A</code> mất kh&aacute; nhiều thời gian để t&iacute;nh to&aacute;n n&ecirc;n dịch vụ chỉ gọi <code>API A</code> một lần.
<img style="width: 450px; display: block; margin-left: auto; margin-right: auto;" src="https://tek4.vn/public_files/03a0fd83-5939-407f-98db-3b483017bf88" alt="0_ZT-IkPTaH3JdZt7C" />
L&agrave;m thế n&agrave;o để dịch vụ kh&ocirc;ng nạp th&ecirc;m <code>API A</code>?
Giải ph&aacute;p được c&aacute;c ứng vi&ecirc;n thường sử dụng l&agrave; d&ugrave;ng cache.
<img style="width: 500px; display: block; margin-left: auto; margin-right: auto;" src="https://tek4.vn/public_files/914db9f3-500a-4391-abd7-e067abb7ecc6" alt="0_3kh2_gSJDDfJZwvA" />
Giả sử bạn muốn tạo một bộ nhớ cache. Giao diện bộ nhớ cache tr&ocirc;ng như sau:
<pre class="language-python"><code>trait Cache[K, V] {
 def get(key: K): Option[V]
 def compareAndSet(key:Key, prevValue: V, currValue: V): Boolean
}</code></pre>
Bộ nhớ cache triển khai một lệnh <code>get</code> v&agrave; một lệnh <code>compareAndSet</code>. Với thao t&aacute;c <code>get</code>, nếu key kh&ocirc;ng tồn tại th&igrave; value trả về gi&aacute; trị <code>null</code>. <code>compareAndSet</code> sẽ so s&aacute;nh <code>prevValue</code>, gi&aacute; trị ở trước, với gi&aacute; trị hiện tại trong bộ nhớ cache. Nếu <code>prevValue</code> l&agrave; gi&aacute; trị hiện tại, <code>currValue</code> sẽ ghi đ&egrave; l&ecirc;n <code>prevValue</code>. Giả sử <code>prevValue</code> được nhập v&agrave;o trong tham số kh&ocirc;ng phải l&agrave; gi&aacute; trị cuối c&ugrave;ng trong bộ nhớ cache. Khi đ&oacute;, <code>currValue</code> sẽ kh&ocirc;ng được nhập v&agrave;o bộ nhớ cache. <code>compareAndSet</code> trả về một gi&aacute; trị boolean nếu nhập <code>currValue</code> th&agrave;nh c&ocirc;ng.
Bạn cần phải triển khai getAPI để kết hợp giao diện cache:
<pre class="language-python"><code>// third party API
def fetchAPIA[K,V](key:K): Future[V]

def getAPI[K, V](key: K) : Future[V] = ???</code></pre>
<h2 style="text-align: justify;">B&agrave;i kiểm tra đ&aacute;nh gi&aacute; kiến thức g&igrave;?</h2>
B&agrave;i phỏng vấn kh&ocirc;ng chỉ hỏi c&aacute;c kiến thức đơn giản như c&aacute;ch v&ocirc; hiệu h&oacute;a bộ nhớ cache, ch&iacute;nh s&aacute;ch loại bỏ bộ nhớ cache hay mục đ&iacute;ch của bộ nhớ cache.
Phần lớn ứng vi&ecirc;n đều c&oacute; hiểu biết về bộ nhớ cache v&agrave; biết mục đ&iacute;ch của việc tạo bộ nhớ cache l&agrave; để giảm độ trễ của ứng dụng hoặc tăng th&ocirc;ng lượng đọc. Với nội dung n&agrave;y th&igrave; chỉ cần một lệnh t&igrave;m kiếm Google đơn giản l&agrave; ra ngay một loạt c&acirc;u trả lời.
C&acirc;u hỏi về triển khai bộ nhớ cache được d&ugrave;ng để kiểm tra kiến thức v&agrave; kinh nghiệm viết dịch vụ v&agrave; APIs của ứng vi&ecirc;n qua c&aacute;ch xử l&yacute; lỗi. Phần viết code được đ&aacute;nh gi&aacute; qua c&aacute;ch xử l&yacute; trong c&aacute;c v&iacute; dụ thực tiễn.
Hầu hết c&acirc;u hỏi cơ bản về triển khai <code>getAPI</code> li&ecirc;n quan sử dụng mệnh đề if.
Hiểu biết ban đầu
Gọi <code>get</code> với key được cho sẵn. Nếu thao t&aacute;c gặp cache miss, h&atilde;y gọi <code>fetchAPIA</code>. Sau khi gọi, triển khai lệnh <code>compareAndSet</code> để l&agrave;m mới bộ nhớ cache với key cho trước.
<pre class="language-python"><code>def getAPI[K,V](key:K): Future[V] = get(key).getOrElse{
 fetchAPIA(key).flatMap{value =&gt; 
 Future(compareAndSet(key, null, value)).map{bool =&gt;
 getApi(key)
 }
 }
}</code></pre>
Qu&aacute; tr&igrave;nh triển khai ban đầu diễn ra su&ocirc;n sẻ. Tuy nhi&ecirc;n, triển khai chỉ kh&ocirc;ng gặp vấn đề khi c&oacute; 1 request v&agrave; 1 người d&ugrave;ng. Nếu c&oacute; nhiều lệnh gọi đồng thời đến bộ nhớ cache v&agrave; đều gặp cache miss, dịch vụ b&ecirc;n thứ 3 sẽ bị qu&aacute; tải với nhiều lệnh gọi c&ugrave;ng l&uacute;c. Khi lưu lượng truy cập dịch vụ tăng đột biến, dịch vụ c&oacute; thể gặp sự cố ngừng hoạt động. HIện tượng n&agrave;y được gọi l&agrave; cache stampede (t&igrave;nh trạng chất đống cache).
N&ecirc;n code thế n&agrave;o để ngăn t&igrave;nh trạng chất đống cache?
Ứng vi&ecirc;n đ&atilde; từng gặp vấn đề n&agrave;y sẽ biết c&aacute;ch giải quyết ph&ugrave; hợp. Tuy nhi&ecirc;n, với những ứng vi&ecirc;n chưa từng gặp phải vấn đề n&agrave;y th&igrave; đ&acirc;y l&agrave; b&agrave;i kiểm tra năng lực giải quyết vấn đề c&oacute; thể gặp phải như tr&ecirc;n.
Ngo&agrave;i ra, b&agrave;i kiểm tra n&agrave;y cũng đ&aacute;nh gi&aacute; khả năng xử l&yacute; lỗi. Điều g&igrave; xảy ra nếu <code>compareAndSet</code> trả về <code>false</code>? Bạn sẽ thử l&agrave;m lại hay trả về gi&aacute; trị với th&ocirc;ng b&aacute;o lỗi?
Loại c&acirc;u hỏi n&agrave;y đ&agrave;o s&acirc;u v&agrave;o những kh&iacute;a cạnh s&acirc;u xa của một b&agrave;i code đơn giản. Một ứng vi&ecirc;n đầy kinh nghiệm sẽ biết loại lỗi n&agrave;o cần kh&ocirc;i phục v&agrave; loại lỗi n&agrave;o n&ecirc;n bỏ qua.
<h2 style="text-align: justify;">Giải ph&aacute;p</h2>
T&igrave;nh trạng chất đống cache l&agrave; một lỗi cơ bản trong lập tr&igrave;nh đồng thời. Nếu tiến tr&igrave;nh đa luồng cố gắng truy cập một vị tr&iacute; bộ nhớ, l&agrave;m thế n&agrave;o để đảm bảo chỉ c&oacute; một gi&aacute; trị truy cập v&agrave;o vị tr&iacute; bộ nhớ đ&oacute;? N&oacute;i c&aacute;ch kh&aacute;c, l&agrave;m thế n&agrave;o để chỉ c&oacute; 1 luồng v&agrave;o thời điểm truy cập ứng dụng? C&acirc;u trả lời l&agrave; sử dụng kỹ thuật locking.&nbsp;
Khi một lập tr&igrave;nh vi&ecirc;n thực hiện t&iacute;nh to&aacute;n tr&ecirc;n bộ nhớ cache, cache sẽ chiếm quyền t&agrave;i nguy&ecirc;n - ngăn kh&ocirc;ng cho người kh&aacute;c t&iacute;nh to&aacute;n tr&ecirc;n vị tr&iacute; bộ nhớ đ&oacute;. Bất kỳ ai n&agrave;o c&oacute; bộ nhớ cache cũ hoặc thiếu bộ nhớ cache cần phải đợi cho đến khi lock được giải ph&oacute;ng. Sau đ&oacute;, lập tr&igrave;nh vi&ecirc;n sẽ thử lại tr&igrave;nh đọc cache. Do đ&oacute;, nguồn dữ liệu ch&iacute;nh kh&ocirc;ng bị qu&aacute; tải do request.
Ch&iacute;nh v&igrave; vậy, việc giải quyết t&igrave;nh trạng chất đống cache thực chất l&agrave; giới hạn số lượng request đến nguồn t&agrave;i nguy&ecirc;n ch&iacute;nh. C&oacute; nhiều c&aacute;ch để xử l&yacute; t&igrave;nh trạng n&agrave;y. Dưới đ&acirc;y l&agrave; hai phương ph&aacute;p đơn giản nhất c&oacute; thể &aacute;p dụng.
<h3 style="text-align: justify;">Tạm dừng request</h3>
Đ&acirc;y l&agrave; hướng tiếp cận đầu ti&ecirc;n trong những phương ph&aacute;p kỹ ngăn chặn việc k&iacute;ch hoạt những sự kiện tr&ugrave;ng lặp v&agrave; g&acirc;y nhiễu hệ thống trong JavaScript.
Kỹ thuật n&agrave;y thường được c&aacute;c lập tr&igrave;nh vi&ecirc;n frontend gọi l&agrave; Debouncing (Tr&igrave; ho&atilde;n). H&agrave;m debounce sẽ tạm dừng việc gọi h&agrave;m sau 100 mili gi&acirc;y kể từ thời điểm cuối c&ugrave;ng k&iacute;ch hoạt h&agrave;m được tr&igrave; ho&atilde;n.
DoorDash đ&atilde; thực hiện <a href="https://doordash.engineering/2018/08/03/avoiding-cache-stampede-at-doordash/">c&aacute;ch n&agrave;y</a> trong backend sử dụng Kotlin Coroutine. Tuy nhi&ecirc;n nếu kh&ocirc;ng sử dụng ng&ocirc;n ngữ cụ thể với cơ chế n&agrave;y, bạn cần triển khai phương thức debounce. C&aacute;ch triển khai cũng kh&ocirc;ng qu&aacute; kh&oacute; khăn. Ngo&agrave;i ra, phương ph&aacute;p n&agrave;y y&ecirc;u cầu c&oacute; một dịch vụ kh&aacute;c hoặc dựa tr&ecirc;n tr&igrave;nh gọi để c&oacute; cơ chế đ&oacute;, điều n&agrave;y l&agrave;m tăng sự phụ thuộc đối với dịch vụ.
<h3 style="text-align: justify;">Compare and Set</h3>
<code>compareAndSet</code> l&agrave; đ&aacute;p &aacute;n ch&iacute;nh x&aacute;c cho c&acirc;u hỏi n&agrave;y bởi đ&acirc;y l&agrave; c&aacute;ch duy nhất c&oacute; thể đồng bộ h&oacute;a từ b&ecirc;n trong.
Nhập một số từ kh&oacute;a v&agrave;o bộ nhớ cache để th&ocirc;ng b&aacute;o một lập tr&igrave;nh vi&ecirc;n đ&atilde; thực hiện nạp t&agrave;i nguy&ecirc;n, v&igrave; thế c&aacute;c lập tr&igrave;nh vi&ecirc;n kh&aacute;c c&oacute; thể đợi hoặc thử lại sau.
V&iacute; dụ, khi lập tr&igrave;nh vi&ecirc;n gọi bộ nhớ cache v&agrave; gặp cache miss, hệ thống sẽ ghi một value c&oacute; key v&agrave;o bộ nhớ cache, như l&agrave; &ldquo;in-progress&rdquo; để th&ocirc;ng b&aacute;o rằng key hiện tại l&agrave; một cache mis v&agrave; c&oacute; một lập tr&igrave;nh vi&ecirc;n đang nạp t&agrave;i nguy&ecirc;n ch&iacute;nh.&nbsp;
Y&ecirc;u cầu bắt buộc l&agrave; thao t&aacute;c gọi cần so s&aacute;nh v&agrave; thiết lập tiến tr&igrave;nh với atomic primitive (thao t&aacute;c đơn vị). Lập tr&igrave;nh vi&ecirc;n kh&aacute;c c&oacute; thể đợi v&agrave; gọi h&agrave;m đệ quy lần nữa để xem &ldquo;in-progress&rdquo; đ&atilde; chuyển đổi th&agrave;nh gi&aacute; trị kh&aacute;c chưa.
<pre class="language-python"><code>def getAPI[K,V](key:K): Future[V] = get(key).getOrElse{
 for {
 bool &lt;- Future(compareAndSet(key, null, "in-progress"))
 value &lt;- fetchAPIA(key)
 bool1 &lt;- Future(compareAndSet(key, "in-progress", value))
 } yield (value)
}</code></pre>
B&agrave;i to&aacute;n liệu đ&atilde; thực sự kết th&uacute;c? C&ograve;n lỗi n&agrave;o c&oacute; thể ph&aacute;t sinh kh&ocirc;ng?
C&oacute; trường hợp <code>compareAndSet</code> ban đầu trả về gi&aacute; trị <code>false</code> hoặc <code>compareAndSet</code> cuối c&ugrave;ng trả về <code>false</code>.
Phương thức tr&ecirc;n sẽ kh&ocirc;ng triển khai những g&igrave; xảy ra khi <code>get(key)</code> trả về <code>in-progress</code>. Liệu bạn c&oacute; n&ecirc;n đợi v&agrave; thử lại, hay l&agrave; trả về th&ocirc;ng b&aacute;o cụ thể của lệnh gọi đang trong trạng th&aacute;i &ldquo;waiting&rdquo;?
<h2 style="text-align: justify;">Lời kết</h2>
H&igrave;nh thức c&acirc;u hỏi mới n&agrave;y được &aacute;p dụng để kiểm tra năng lực giải quyết vấn đề v&agrave; kinh nghiệm ph&aacute;t triển phần mềm của ứng vi&ecirc;n.
Những ứng vi&ecirc;n c&oacute; kinh nghiệm sẽ biết khi n&agrave;o cần thử lại code v&agrave; khi n&agrave;o th&igrave; kh&ocirc;ng n&ecirc;n thử lại. Nội dung xoay quanh qu&aacute; tr&igrave;nh triển khai hỗn hợp thiết kế hệ thống kiến tr&uacute;c thực sẽ l&agrave; c&acirc;u hỏi đ&aacute;nh gi&aacute; tốt hơn so với c&acirc;u hỏi kiến thức như &ldquo;c&aacute;ch duyệt c&acirc;y nhị ph&acirc;n t&igrave;m kiếm&rdquo;.
Nếu l&agrave; một ứng vi&ecirc;n tham gia phỏng vấn, bạn sẽ giải quyết b&agrave;i to&aacute;n tr&ecirc;n như n&agrave;o? L&agrave;m thế n&agrave;o để xử l&yacute; c&aacute;c lỗi? Liệu c&oacute; trường hợp đặc biệt n&agrave;o c&oacute; thể xảy ra cần phải xử l&yacute; kh&ocirc;ng?&nbsp;
Bạn c&oacute; biết c&acirc;u hỏi phỏng vấn n&agrave;o gi&uacute;p đ&aacute;nh gi&aacute; kỹ năng xử l&yacute; vấn đề v&agrave; kinh nghiệm của ứng vi&ecirc;n h&oacute;c b&uacute;a hơn kh&ocirc;ng? H&atilde;y b&igrave;nh luận v&agrave; chia sẻ suy nghĩ của bạn ở dưới cho <a href="https://tek4.vn/">Tek4</a> biết nh&eacute;!

Admin

Câu hỏi phỏng vấn kiểm tra năng lực dành cho lập trình viên

Cùng tác giả

Admin

Có liên quan