Nguồn gốc của việc yêu cầu người được phỏng vấn phân tích cú pháp một chuỗi bằng tay như một int là gì?

Question

Tôi tự hỏi, nguồn gốc của việc yêu cầu những người được phỏng vấn phân tích cú pháp chuỗi bằng tay là gì? (mà không dựa vào bất kỳ phép chuyển đổi/loại nào có thể được tích hợp vào ngôn ngữ). Đây có phải là câu hỏi tiêu chuẩn, được đề xuất từ ​​sách hoặc danh sách hay gì đó không?

Có ai khác ở đây trên SO đã hỏi câu hỏi cụ thể này trong cuộc phỏng vấn không? Tôi đoán tôi đóng đinh nó khi giải thích nó và viết nguệch ngoạc nó trên bảng trắng, như tôi đã nhận được một đề nghị công việc dự kiến ​​:)

Dưới đây là thực hiện xác thịt của tôi trong Javascript. Có một số khía cạnh ngây thơ (ví dụ: nó không có một đối số radix) để sau đây nhưng nó chứng minh một (nhiều hơn hoặc ít hơn) thuật toán chính xác.

function to_i(strValue) { //named so as to not be confused with parseInt 
    if (typeof strValue !== 'string' || strValue.length === 0) { 
     return Number.NaN; 
    } 

    var tmpStr = strValue; 
    var intValue = 0; 
    var mult = 1; 

    for (var pos=tmpStr.length-1; pos>=0; pos--) { 
     var charCode = tmpStr.charCodeAt(pos); 
     if (charCode < 48 || charCode > 57) { 
      return Number.NaN; 
     } 

     intValue += mult * Math.abs(48-charCode); 
     tmpStr = tmpStr.substr(0, tmpStr.length-1); 
     mult *= 10; 
    } 

    return intValue; 
} 

Answer 1

Dựa trên bằng chứng giai thoại từ các câu trả lời khác, tôi sẽ tự trả lời và chấp nhận như vậy: đây không phải là câu hỏi phỏng vấn "đóng hộp".

Answer 2

Không bao giờ nghe câu hỏi này, trong khi phỏng vấn ở Hoa Kỳ, họ luôn hỏi tôi nhiều câu hỏi khó hơn. Tôi ước họ hỏi tôi một câu hỏi đơn giản như vậy.

Answer 3

Tôi chưa được hỏi câu hỏi này.

Thoạt nhìn, có vẻ như một trong số đó là "loại bỏ những kẻ ngốc không đủ năng lực rõ ràng càng sớm càng tốt để bỏ thời gian phỏng vấn có giá trị" loại câu hỏi.

Nhưng nếu bạn xem xét kỹ hơn, thực tế có một số nội dung thú vị trong đó. Vì vậy, nếu tôi là một hỏi câu hỏi đó, đây là những gì tôi sẽ tìm kiếm

• Câu hỏi đó rõ ràng là ngu ngốc, vì đã có là một hàm trong thư viện chuẩn ECMAScript mà không chính xác đó. Và tôi muốn người được phỏng vấn cho biết tôi rằng câu hỏi là ngu ngốc, bởi vì nếu không thì họ là một trong số đó). chức năng tồn tại. Nó cũng rõ ràng là một vấn đề phân tích cú pháp, và nó là thú vị để xem liệu người được phỏng vấn tiếp cận nó như là một vấn đề hacking chuỗi hoặc một vấn đề phân tích cú pháp chính thức và bao nhiêu chi phí hoặc cách tiếp cận tạo ra. Trong trường hợp đặc biệt này, tôi tin rằng việc hack chuỗi là cách tiếp cận đúng, nhưng nó vẫn dẫn đến một câu hỏi tiếp theo tuyệt vời: "Bây giờ làm điều tương tự với trình phân tích cú pháp đệ quy". Bất kỳ lập trình viên nào cũng có thể phác họa trình phân tích cú pháp đệ quy cho vấn đề này trong vòng vài phút.
• Cuối cùng nhưng không kém phần quan trọng, điều này rõ ràng là gấp một lần so với các ký tự của chuỗi. Bây giờ, tôi sẽ không nhất thiết phải mong đợi một lập trình viên mới để phát hiện ra lần này ngay lập tức, nhưng nếu tôi gợi ý rằng có một nếp gấp trong đó, họ có thể phát hiện ra nó và viết lại giải pháp của họ dưới dạng gấp .
• Và tất nhiên, bạn có thể đánh giá tất cả những phẩm chất chung mà loại câu hỏi này cho phép bạn: người phỏng vấn có dừng lại và suy nghĩ về vấn đề này hay anh ta bắt đầu hack. Anh ấy có bắt đầu với các yêu cầu, tài liệu, đặc điểm kỹ thuật, ví dụ, kiểm tra hoặc mã hay không. Liệu anh ta có yêu cầu làm rõ các trường hợp góc (như những gì xảy ra với chuỗi rỗng không, điều gì sẽ xảy ra với một chuỗi chỉ chứa dấu trừ và không có gì khác, khoảng trống, là các chuỗi được đảm bảo là các số nguyên được định dạng tốt, là số không âm một số nguyên được định dạng tốt). Anh ta có thường xuyên sử dụng tập hợp con nghiêm ngặt của ES5 không. Anh ấy có viết mã có thể đọc được không.Anh ta viết jslint -friendly đang

Dưới đây là một ví dụ về việc giải quyết vấn đề với một lần (mà trong ECMAScript được gọi reduce):

"use strict"; 

function toInteger(s) { 
    return s.split('').reverse().reduce(function (n, c, i) { 
     if (c === '-') return -n; 
     return n + (c.charCodeAt(0) - 48) * Math.pow(10, i); 
    }, 0); 
} 

Và đây là một phân tích cú pháp đệ quy-gốc đơn giản mà xây dựng tăng giá trị khi đang bay:

"use strict"; 

function toInteger(s) { 
    var input, 
     output = 0, 
     sign = 1, 

     lookahead = function() { 
      return input.charAt(0); 
     }, 

     consume = function() { 
      var res = input.slice(0, 1); 
      input = input.slice(1, input.length); 
      return res; 
     }, 

     isDigit = function (c) { 
      return /[0-9]/.test(c); 
     }, 

     signParser = function() { 
      if (lookahead() === '-') { 
       sign *= -1; 
       consume(); 
      } 
     }, 

     digitParser = function() { 
      if (!isDigit(lookahead())) return false; 
      output *= 10; 
      output += (consume().charCodeAt(0) - 48); 
      return true; 
     }, 

     numberParser = function() { 
      signParser(); 
      while (digitParser()); 
     }; 

    input = s; 
    numberParser(); 
    if (!input.length === 0) return false; 
    output *= sign; 

    return output; 
} 

Như mọi khi với loại câu hỏi phỏng vấn này, không ai có thể kỳ vọng người được phỏng vấn chỉ viết những chức năng đó xuống trên bảng trắng. Đặc biệt là trình phân tích cú pháp đệ quy. Nhưng IMHO, bất kỳ ai nên đều có thể phác họa ra chức năng sẽ trông như thế nào. Đặc biệt, một trong những nét đẹp của trình phân tích cú pháp đệ quy là chuyển đổi trực tiếp ngữ pháp tự do thành ngữ thành một tập hợp các hàm phân tích cú pháp, và người được phỏng vấn có thể giải thích loại chức năng phân tích cú pháp tương ứng với loại cấu trúc ngữ pháp nào.

---

phew, có nghĩa là rất nhiều thứ mà bạn có thể thoát ra khỏi một câu hỏi đơn giản như vậy!

Answer 4

Họ muốn kiểm tra kiến ​​thức toán học của bạn, bởi vì nhiều "khỉ mã" không nhận được giáo dục toán học phù hợp.

Một số được biểu thị bằng chữ số $ d_1 d_2 ... d_n $ có thể được viết theo dạng này: $ d_1 r^(n - 1) + ... + d_ (n - 1) r^1 + d_n $, trong đó r là cơ số.

Điều đó có nghĩa, 123 trong số thập phân = $ 1 * 10^2 + 2 * 10^1 + 3 $ trong khi 123 trong bát phân là $ 1 * 8^2 + 2 * 8^1 + 3 $ = 83

function to_i(str, rad) { 
    // the function to transform an ascii code into a number value 
    function dig(c) { 
    if (c >= 48 && c <= 57) { 
     // 0 - 9: as-is 
     return c - 48; 
    } else if (c >= 97 && c <= 122) { 
     // a - z: a means 10, b means 11 and so on until z 
     return 10 + c - 97; 
    } else { 
     return Number.NaN; 
    } 
    } 

    // validate arguments 
    if (str == '' || rad < 2 || rad > 35) return Number.NaN; 
    // strip extra characters and lowercase ("$10" -> "10") 
    var result = str.toLowerCase().match(/^.*?(-?)([a-z0-9]+).*?$/); 
    // break on empty numbers 
    if (result == null || !result[2]) return Number.NaN; 
    // get sign multiplier 
    var sign = (result[1] == '-' ? -1 : 1), val = result[2], num = 0; 
    // num = dv_0 * rad ** n + dv1 * rad ** (n - 1) + ... dv_n * rad ** 0 
    // where dv_n = dig(val.charCodeAt(i)) 
    // and a ** b = a * ... * a, b times 
    // for each digits 
    for (var i = val.length - 1, m = 1; i >= 0; i --, m *= rad) { 
    // get digit value 
    var dv = dig(val.charCodeAt(i)); 
    // validate digit value (you can't put 5 in binary) 
    if (dv >= rad || num == Number.NaN) return Number.NaN; 
    // multiply 
    num += m * dv; 
    } 
    // return 
    return num * sign; 
} 

to_i("ff", 16); 

Chế độ này hỗ trợ các bản sao, a nghĩa là 10, b có nghĩa là 11 và cứ như vậy cho đến z. Hy vọng công trình này hoạt động.