कोडिंग इंटरव्यू: डायनेमिक प्रोग्रामिंग से एडिट डिस्टेंस की गणना कैसे करें?

समस्या और लागू होने वाले परिदृश्य

दो स्ट्रिंग्स source और target दिए जाने पर, source को target में बदलने के लिए आवश्यक एडिट्स की न्यूनतम संख्या लौटाएं। एक एडिट एक कैरेक्टर इन्सर्ट करता है, एक कैरेक्टर डिलीट करता है, या एक कैरेक्टर को रिप्लेस करता है। प्रत्येक ऑपरेशन की लागत एक है। कोई भी स्ट्रिंग खाली हो सकती है, और दोनों में केवल लोअरकेस अंग्रेजी अक्षर होते हैं।

source = "horse"
target = "ros"

horse -> rorse   replace h with r
rorse -> rose    delete r
rose  -> ros     delete e

answer = 3

मान लें m = source.length और n = target.length, जहाँ दोनों की लंबाई अधिकतम 2,000 है। यह कार्य केवल न्यूनतम लागत मांगता है, कोई एडिट स्क्रिप्ट नहीं। Wagner–Fischer पेपर स्ट्रिंग सुधार को इंसर्शन, डिलीशन और सब्स्टीट्यूशन के न्यूनतम-लागत अनुक्रम के रूप में परिभाषित करता है और एक ऐसा एल्गोरिदम देता है जिसका समय दोनों लंबाइयों के गुणनफल के समानुपाती होता है। वर्तमान 2026 इंटरव्यू गाइड अभी भी एडिट डिस्टेंस को एक प्रामाणिक टू-स्ट्रिंग डायनेमिक प्रोग्रामिंग अभ्यास के रूप में उपयोग करते हैं। यह इस विषय के तैयारी मूल्य का समर्थन करता है; यह किसी विशेष कंपनी की आवृत्ति या एट्रिब्यूशन को साबित नहीं करता है।

यह समस्या स्पेल चेकिंग, फ़ज़ी मैचिंग, रिकॉर्ड लिंकेज और सीक्वेंस कम्पेरिज़न में दिखाई देती है, लेकिन प्रोडक्शन परिभाषाएँ वेटेड ऑपरेशन्स, ट्रांस्पोज़िशन, नॉर्मलाइज़ेशन या डोमेन-विशिष्ट टोकन का उपयोग कर सकती हैं। इंटरव्यू संस्करण जानबूझकर यूनिट-कॉस्ट कैरेक्टर एडिट्स तय करता है ताकि इसका स्टेट और प्रूफ स्पष्ट रहे।

इंटरव्यूअर क्या मूल्यांकन करता है

पहला संकेत सटीक सीमाओं के साथ एक स्टेट परिभाषा है। dp[i][j] को source के पहले i कैरेक्टर्स को target के पहले j कैरेक्टर्स में बदलने के लिए आवश्यक न्यूनतम एडिट्स के रूप में परिभाषित करें। “i और j तक का उत्तर” किसी ट्रांज़िशन को सही ठहराने या किसी खाली प्रीफिक्स को इनिशियलाइज़ करने के लिए बहुत अस्पष्ट है।

दूसरा संकेत सभी तीन मिसमैचिंग-कैरेक्टर ट्रांज़िशन को व्युत्पन्न करना है। एक इष्टतम (optimal) समाधान का अंतिम ऑपरेशन डिलीट, इन्सर्ट या रिप्लेस में से एक होना चाहिए। उस अंतिम ऑपरेशन को हटाने पर एक छोटी प्रीफिक्स समस्या बचती है। उम्मीदवार को तीन निर्देशांकों (coordinates) को याद रखने के बजाय प्रत्येक ऑपरेशन को सही पड़ोसी सेल पर मैप करना चाहिए।

तीसरा संकेत बिना अतिरिक्त काम जोड़े मैचिंग अंतिम कैरेक्टर्स को संभालना है। यदि source[i - 1], target[j - 1] के बराबर है, तो एक इष्टतम समाधान उस कैरेक्टर को अपरिवर्तित छोड़ सकता है, इसलिए मान dp[i - 1][j - 1] से आता है। प्रमाण को यह भी दिखाना होगा कि इस विकल्प से कोई सस्ता समाधान नहीं छूट रहा है।

चौथा संकेत डिपेंडेंसी के आकार को पहचानना है। एक पंक्ति केवल पिछली पंक्ति और अपने स्वयं के बाएं सेल का उपयोग करती है, इसलिए केवल दूरी लौटाते समय संपूर्ण O(mn) मैट्रिक्स अनावश्यक है। छोटी स्ट्रिंग को कॉलम डायमेंशन पर रखने से O(min(m, n)) ऑक्जिलरी स्पेस मिलता है।

अंतिम संकेत समस्या के अनुबंध (contract) को बनाए रखना है। पंक्ति और कॉलम स्ट्रिंग्स की अदला-बदली यहाँ मान्य है क्योंकि यूनिट-कॉस्ट इंसर्शन और डिलीशन दूरी को सममित (symmetric) बनाते हैं। जब इंसर्शन और डिलीशन के अलग-अलग वेट होते हैं तो यह स्वचालित रूप से मान्य नहीं होता है। यूनिकोड टेक्स्ट के लिए UTF-16 कोड यूनिट्स, यूनिकोड कोड पॉइंट्स और यूजर-परसीव्ड ग्रैफ़िम क्लस्टर्स के बीच एक स्पष्ट विकल्प की भी आवश्यकता होती है।

उत्तर देने से पहले स्पष्ट करने योग्य प्रश्न

• किन ऑपरेशन्स की अनुमति है? यह समस्या इंसर्शन, डिलीशन और रिप्लेसमेंट की अनुमति देती है। आसन्न

ट्रांस्पोज़िशन (adjacent transposition) एक ऑपरेशन नहीं है।

• एक एडिट की लागत क्या है? प्रत्येक स्वीकृत ऑपरेशन की लागत एक है। वेटेड लागतें रिकरेंस को बदल देती हैं और

समरूपता (symmetry) को हटा सकती हैं।

• तुलना की इकाई (comparison unit) क्या है? प्रॉम्प्ट लोअरकेस अंग्रेजी अक्षरों का उपयोग करता है, इसलिए इस कार्यान्वयन के लिए जावास्क्रिप्ट इंडेक्सिंग सुरक्षित है। सामान्य यूनिकोड टेक्स्ट के लिए एक अलग अनुबंध की आवश्यकता होती है।
• क्या हम केवल दूरी लौटाते हैं या कोई एडिट स्क्रिप्ट? केवल दूरी। ऑपरेशन्स को फिर से बनाने के लिए आमतौर पर

पूरी तालिका या स्पष्ट पूर्ववर्ती (predecessor) जानकारी को बनाए रखा जाता है।

• क्या कोई इनपुट खाली हो सकता है? हाँ। एक खाली स्ट्रिंग को लंबाई j के प्रीफिक्स में बदलने के लिए ठीक j

इंसर्शन की आवश्यकता होती है; इसके विपरीत i डिलीशन की आवश्यकता होती है।

• आकार की सीमाएँ क्या हैं? 2,000 तक की लंबाई O(mn) समय को स्वीकार्य बनाती है लेकिन एक्सपोनेंशियल रिकर्शन

और अनावश्यक फुल-टेबल मेमोरी को अवांछनीय बनाती है।

• क्या मेमोरी बचाने के लिए इनपुट की अदला-बदली की जा सकती है? हाँ, इस यूनिट-कॉस्ट अनुबंध के तहत क्योंकि दूरी

सममित है। इसका उपयोग करने से पहले उस धारणा का उल्लेख करें।

30-सेकंड उत्तर फ्रेमवर्क

“मैं dp[i][j] को पहले i source कैरेक्टर्स से पहले j target कैरेक्टर्स तक के न्यूनतम एडिट्स के रूप में परिभाषित करता हूँ। खाली-प्रीफिक्स लागतें पहली पंक्ति और कॉलम को इनिशियलाइज़ करती हैं। समान अंतिम कैरेक्टर डायगोनल का अपरिवर्तित उपयोग करते हैं। अन्यथा अंतिम एडिट डिलीट, इन्सर्ट या रिप्लेस होता है, इसलिए मैं ऊपर, बाएँ और डायगोनल सेल के न्यूनतम में एक जोड़ता हूँ। प्रत्येक सेल केवल पिछली पंक्ति और वर्तमान पंक्ति के बाएँ मान पर निर्भर करता है, इसलिए मैं छोटी स्ट्रिंग को कॉलम पर रखता हूँ और दो पंक्तियाँ रखता हूँ। इससे O(mn) समय और O(min(m, n)) स्पेस मिलता है। मैं खाली स्ट्रिंग्स, समान स्ट्रिंग्स, असममित लंबाइयों और छोटे इनपुट पर फुल-टेबल संदर्भ के विरुद्ध परिणाम को सत्यापित करता हूँ।”

चरण-दर-चरण गहन समाधान

प्रीफिक्स से शुरू करें। मान लें dp[i][j] अनुमत एडिट्स की न्यूनतम संख्या है जो source[0..i - 1] को target[0..j - 1] में बदलती है।

खाली-प्रीफिक्स सीमाएँ सीधे अनुबंध से प्राप्त होती हैं:

dp[0][j] = j   // insert all j target characters
dp[i][0] = i   // delete all i source characters

गैर-खाली प्रीफिक्स के लिए, उनके अंतिम कैरेक्टर्स का निरीक्षण करें। यदि वे मेल खाते हैं, तो उस साझा अंतिम कैरेक्टर को बनाए रखने से समस्या दो छोटे प्रीफिक्स में कम हो जाती है:

if source[i - 1] == target[j - 1]:
  dp[i][j] = dp[i - 1][j - 1]

यदि वे भिन्न हैं, तो किसी भी इष्टतम अनुक्रम के अंतिम एडिट को वर्गीकृत करें:

delete source[i - 1]:       dp[i - 1][j]     + 1
insert target[j - 1]:       dp[i][j - 1]     + 1
replace the final character: dp[i - 1][j - 1] + 1

dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])

ये संपूर्ण (exhaustive) हैं क्योंकि अंतिम ऑपरेशन तीन स्वीकृत एडिट्स में से एक होना चाहिए। वे रचनात्मक (constructive) हैं: चयनित छोटे प्रीफिक्स के लिए एक इष्टतम समाधान में नामित एडिट जोड़ें, और यह (i, j) के लिए एक वैध समाधान उत्पन्न करता है। इसके विपरीत, किसी भी इष्टतम समाधान से अंतिम एडिट को हटा दें; शेष भाग संबंधित छोटे प्रीफिक्स को हल करता है, इसलिए इसकी लागत उस सेल से कम नहीं हो सकती। यह मिसमैच रिकरेंस को सिद्ध करता है।

मैचिंग अंतिम कैरेक्टर्स के लिए, एक इष्टतम समाधान मौजूद है जो उन्हें मैच्ड छोड़ देता है। यदि कोई इष्टतम अनुक्रम अंतिम source या target कैरेक्टर को एडिट करता है, तो उन अंतिम प्रभावों को हटा दें और इसके बजाय समान कैरेक्टर्स को संरेखित (align) करें; इससे लागत नहीं बढ़ती है। शेष कार्य बिल्कुल डायगोनल प्रीफिक्स समस्या है। खाली-प्रीफिक्स सीमाओं द्वारा एंकर किया गया i + j पर इंडक्शन, प्रत्येक सेल और इसलिए dp[m][n] को सिद्ध करता है।

एक पंक्ति भरते समय केवल तीन पुराने मानों की आवश्यकता होती है: डिलीशन के लिए previous[j], इंसर्शन के लिए current[j - 1], और रिप्लेसमेंट या मैच के लिए previous[j - 1]। कोड छोटी स्ट्रिंग को कॉलम बनाता है। वह अदला-बदली इस सममित यूनिट-कॉस्ट परिभाषा के तहत एक मेमोरी ऑप्टिमाइज़ेशन है; यह उत्तर को नहीं बदलती है।

export function editDistance(source: string, target: string): number {
  const rows = source.length >= target.length ? source : target
  const columns = source.length >= target.length ? target : source

  let previous = Array.from(
    { length: columns.length + 1 },
    (_, index) => index,
  )

  for (let row = 1; row <= rows.length; row += 1) {
    const current = new Array<number>(columns.length + 1)
    current[0] = row

    for (let column = 1; column <= columns.length; column += 1) {
      if (rows[row - 1] === columns[column - 1]) {
        current[column] = previous[column - 1]
        continue
      }

      const deleteCost = previous[column] + 1
      const insertCost = current[column - 1] + 1
      const replaceCost = previous[column - 1] + 1
      current[column] = Math.min(deleteCost, insertCost, replaceCost)
    }

    previous = current
  }

  return previous[columns.length]
}

source = "horse" और target = "ros" के लिए, छोटे कॉलम डायमेंशन की लंबाई तीन है। अंतिम पंक्ति तीन पर समाप्त होती है, जो रिप्लेसमेंट-प्लस-टू-डिलीशन अनुक्रम से मेल खाती है। एल्गोरिदम लागत लौटाता है; यह दावा नहीं करता कि यह विशेष एडिट अनुक्रम अद्वितीय है।

जटिलता, सीमाएँ और इंजीनियरिंग विकल्प

एल्गोरिदम (m + 1)(n + 1) वैचारिक स्टेट्स को भरता है, इसलिए समय O(mn) है। प्रत्येक पंक्ति में min(m, n) + 1 प्रविष्टियाँ होती हैं, और एक समय में केवल दो पंक्तियाँ मौजूद होती हैं, इसलिए ऑक्जिलरी स्पेस O(min(m, n)) है। प्रति पुनरावृत्ति एक पंक्ति को पुनः आवंटित करने से बाउंड नहीं बदलता है; दो पुन: प्रयोज्य (reusable) ऐरे एल्गोरिदम को बदले बिना आवंटन दबाव को कम कर सकते हैं।

यूनिट इंसर्शन, डिलीशन और रिप्लेसमेंट के तहत अधिकतम उत्तर max(m, n) है: पहले min(m, n) कैरेक्टर्स को बदलें, फिर लंबाई के अंतर को इन्सर्ट या डिलीट करें। न्यूनतम कम से कम |m - n| है, क्योंकि प्रत्येक एडिट लंबाई को अधिकतम एक से बदलता है। ये सीमाएँ परीक्षणों में उपयोगी असर्शन हैं।

सामान्य जावास्क्रिप्ट स्ट्रिंग्स के लिए, इंडेक्सिंग UTF-16 कोड यूनिट्स पर काम करती है। स्ट्रिंग पुनरावृत्ति यूनिकोड कोड पॉइंट्स देकर सरोगेट पेयर्स को सुरक्षित रखती है, लेकिन यह अभी भी इमोजी प्लस स्किन टोन या ज़ीरो-विड्थ-जॉइनर सीक्वेंस जैसे एक ग्रैफ़िम क्लस्टर को विभाजित कर सकती है। एक प्रोडक्शन सिमिलैरिटी फीचर को टोकनाइज़र चुनने से पहले यह तय करना होगा कि क्या एडिट्स कोड यूनिट्स, कोड पॉइंट्स, नॉर्मलाइज़्ड ग्रैफ़िम क्लस्टर्स, शब्दों या डोमेन टोकन पर लागू होते हैं। साइलेंट नॉर्मलाइज़ेशन उत्पाद के अर्थ विज्ञान (semantics) को भी बदल सकता है, इसलिए यह इस DP लूप के अंदर होने के बजाय अनुबंध में होना चाहिए।

यदि कॉलर केवल यह पूछता है कि क्या दूरी अधिकतम k है, तो पहले |m - n| > k होने पर रिजेक्ट करें, फिर केवल एक डायगोनल बैंड का मूल्यांकन करें और तब रुकें जब सक्रिय बैंड में कोई भी स्टेट k के भीतर न रह सके। वह एक अलग आउटपुट अनुबंध है; पूर्ण-दूरी कार्यान्वयन को उस जटिलता को काल्पनिक रूप से नहीं जोड़ना चाहिए।

उच्च-गुणवत्ता वाला नमूना उत्तर

“मैं प्रीफिक्स पर समस्या का मॉडल बनाऊंगा। मान लें dp[i][j] पहले i source कैरेक्टर्स को पहले j target कैरेक्टर्स में बदलने की न्यूनतम लागत है। खाली-प्रीफिक्स सीमाएँ उनकी लंबाइयाँ हैं। समान अंतिम कैरेक्टर्स के लिए मैं डायगोनल मान रखता हूँ। विभिन्न अंतिम कैरेक्टर्स के लिए, मैं एक इष्टतम अनुक्रम को उसके अंतिम एडिट द्वारा वर्गीकृत करता हूँ: डिलीट करने के लिए ऊपर के सेल का उपयोग किया जाता है, इन्सर्ट करने के लिए बाएँ सेल का उपयोग किया जाता है, और रिप्लेस करने के लिए डायगोनल का उपयोग किया जाता है, जिसमें न्यूनतम में एक जोड़ा जाता है। वे मामले संपूर्ण हैं, और अंतिम एडिट को हटाने से दूसरी दिशा में रिकरेंस सिद्ध होता है।

“चूँकि एक सेल केवल पिछली पंक्ति और वर्तमान पंक्ति के बाएँ सेल का उपयोग करता है, मैं दो पंक्तियाँ रखता हूँ। यूनिट इंसर्शन और डिलीशन लागतें इस दूरी को सममित बनाती हैं, इसलिए छोटी स्ट्रिंग कॉलम हो सकती है और मेमोरी O(min(m, n)) हो जाती है; समय O(mn) बना रहता है। मैं असममित वेट्स के लिए उस स्वैप का उपयोग नहीं करूंगा। मैं दोनों खाली दिशाओं, समान स्ट्रिंग्स, horse से ros वाले उदाहरण, और छोटी जेनरेट की गई स्ट्रिंग्स को फुल-टेबल संस्करण के विरुद्ध टेस्ट करूँगा। यदि इंटरव्यूअर को एडिट स्क्रिप्ट की आवश्यकता है, तो मैं ओवररिटन पंक्तियों से इसे पुनर्प्राप्त करने का वादा करने के बजाय पूर्ववर्ती जानकारी को बनाए रखूंगा।”

सामान्य गलतियाँ

• लालची (greedy) कैरेक्टर मिलान का उपयोग करना → दोहराए गए कैरेक्टर और बाद के बदलाव स्थानीय रूप से सुविधाजनक एडिट को

वैश्विक न्यूनतम खोने का कारण बनते हैं → इष्टतम प्रीफिक्स स्टेट्स को परिभाषित करें और सभी वैध अंतिम ऑपरेशन्स की तुलना करें।

• पहली पंक्ति और कॉलम को शून्य पर इनिशियलाइज़ करना → खाली-स्ट्रिंग मामले मुफ्त हो जाते हैं → **सीमा लागतों को

उनकी प्रीफिक्स लंबाई पर सेट करें।**

• इन्सर्ट और डिलीट पड़ोसियों को मिलाना → कोड असममित प्रीफिक्स में विफल रहते हुए सममित उदाहरणों को पास कर

सकता है → स्पष्ट करें कि अंतिम ऑपरेशन को हटाने के बाद कौन सी स्ट्रिंग बचती है।

• अंतिम कैरेक्टर मेल खाने पर एक जोड़ना → अपरिवर्तित समान कैरेक्टर्स से रिप्लेसमेंट के रूप में शुल्क लिया जाता है → **मैच होने पर

डायगोनल को ठीक वैसे ही कॉपी करें।**

• एडिट स्क्रिप्ट का वादा करते हुए रोलिंग-रो उत्तर लौटाना → ओवरराइट किए गए पूर्ववर्ती पाथ का पुनर्निर्माण नहीं कर

सकते → ऑपरेशन्स की आवश्यकता होने पर मैट्रिक्स या बैकपॉइंटर्स को बनाए रखें।

• असममित वेट्स के तहत स्ट्रिंग्स की अदला-बदली करना → एक दिशा में इंसर्शन दूसरी दिशा में डिलीशन बन जाते हैं →

मूल ओरिएंटेशन बनाए रखें जब तक कि लागत मॉडल सममित न हो।

• मनमाने यूनिकोड के लिए जावास्क्रिप्ट इंडेक्स को “कैरेक्टर” कहना → सरोगेट पेयर्स या ग्रैफ़िम क्लस्टर्स

अप्रत्याशित रूप से गिने जाते हैं → तुलना इकाई को स्पष्ट रूप से परिभाषित और टोकनाइज़ करें।

एक केंद्रित टेस्ट सेट में ("", "") = 0, ("", "abc") = 3, ("abc", "") = 3, ("same", "same") = 0, ("aaaa", "aa") = 2, ("horse", "ros") = 3, और ("intention", "execution") = 5 शामिल हैं। एक छोटे वर्णमाला से सभी छोटी स्ट्रिंग्स पर फुल-टेबल संदर्भ के साथ रोलिंग कार्यान्वयन की तुलना करें। इस लागत मॉडल के तहत पहचान, समरूपता, |m - n| ≤ d ≤ max(m, n), और जेनरेट किए गए ट्रिपल्स पर त्रिकोण असमानता (triangle inequality) की भी जाँच करें। अंत में, यह पुष्टि करने के लिए लंबाई-2,000 के समान और पूरी तरह से भिन्न इनपुट चलाएं कि अत्यधिक आकार वाला पाथ अपेक्षित द्विघात (quadratic) समय और रैखिक (linear) स्थान के भीतर रहता है।

इंटरव्यू फॉलो-अप्स

फॉलो-अप 1: आप वास्तविक एडिट ऑपरेशन्स कैसे लौटाएंगे?

पूरी तालिका रखें और (m, n) से बैकट्रैक करें। एक मैच बिना कोई ऑपरेशन उत्सर्जित किए तिरछे (diagonally) चलता है; अन्यथा एक पड़ोसी सेल चुनें जिसका मान प्लस संबंधित एडिट लागत वर्तमान मान के बराबर हो। एक स्थिर टाई-ब्रेक नियम परिभाषित करें क्योंकि कई न्यूनतम स्क्रिप्ट मौजूद हो सकते हैं। सीधा तरीका O(mn) स्थान का उपयोग करता है। डिवाइड-एंड-कॉन्कर तकनीकों के साथ एक लीनियर-स्पेस पुनर्निर्माण संभव है, लेकिन यह एक अलग एल्गोरिदम है और इसे केवल तभी पेश किया जाना चाहिए जब मेमोरी की आवश्यकता इसकी मांग करे।

फॉलो-अप 2: जब ऑपरेशन्स के अलग-अलग वेट हों तो क्या बदलता है?

एक के बजाय प्रत्येक ट्रांज़िशन में प्रासंगिक वेट जोड़ें। वही इष्टतम-सबस्ट्रक्चर प्रमाण तब काम करता है जब लागतें गैर-ऋणात्मक (nonnegative) हों और अनुबंध द्वारा परिभाषित हों। यदि इंसर्शन और डिलीशन लागतें भिन्न हैं, तो दूरी दिशात्मक हो सकती है, इसलिए पंक्ति को छोटा करने के लिए स्ट्रिंग्स की अदला-बदली करना अब स्वचालित रूप से सही नहीं है। ऋणात्मक एडिट लागतें सामान्य व्याख्या को तोड़ती हैं और मॉडल पर पुनर्विचार करने की आवश्यकता होती है।

फॉलो-अप 3: आप आसन्न ट्रांस्पोज़िशन (adjacent transposition) का समर्थन कैसे करेंगे?

पहले स्पष्ट करें कि क्या ट्रांस्पोज़िशन केवल आसन्न कैरेक्टर्स को स्वैप करता है और क्या ओवरलैपिंग ट्रांस्पोज़िशन की अनुमति है। एक प्रतिबंधित इष्टतम-स्ट्रिंग-अलाइनमेंट रिकरेंस दो अतिरिक्त पूर्ववर्ती कैरेक्टर्स और दो पंक्तियों और कॉलम पीछे के सेल का निरीक्षण कर सकता है। पूर्ण Damerau–Levenshtein दूरी की अलग-अलग स्टेट आवश्यकताएं होती हैं। केवल एक अनौपचारिक डायगोनल चेक जोड़ने से गलत वैरिएंट लागू हो सकता है।

फॉलो-अप 4: लॉन्गेस्ट कॉमन सबसीक्वेंस (LCS) से क्या संबंध है?

यदि रिप्लेसमेंट प्रतिबंधित है या इसकी लागत एक डिलीशन प्लस एक इंसर्शन के बराबर है, तो एक इंसर्शन-एंड-डिलीशन दूरी को LCS से m + n - 2 * LCS(source, target) के रूप में प्राप्त किया जा सकता है। यूनिट-कॉस्ट रिप्लेसमेंट के साथ, वह सूत्र आम तौर पर एडिट दूरी नहीं है: एक मिसमैचिंग कैरेक्टर को बदलने में एक की लागत आती है, जबकि डिलीट-प्लस-इन्सर्ट में दो की लागत आती है। संबंध का उपयोग करने से पहले ऑपरेशन की लागत बताएं।

फॉलो-अप 5: आप “क्या दूरी अधिकतम k है?” का उत्तर तेजी से कैसे देंगे?

लंबाई का अंतर k से अधिक होने पर तुरंत false लौटाएं। अन्यथा केवल मुख्य डायगोनल के k के भीतर के स्टेट्स की गणना करें, बैंड के बाहर के सेल को अगम्य (unreachable) मानें, और यदि सक्रिय फ्रंटियर बजट के भीतर वापस नहीं आ सकता है तो रुक जाएं। k छोटा होने पर यह काम को काफी कम कर सकता है, जबकि अप्रतिबंधित दूरी के लिए सबसे खराब स्थिति द्विघात (quadratic) बनी रहती है।

फॉलो-अप 6: आप वास्तविक यूजर-विजिबल यूनिकोड टेक्स्ट को कैसे संभालेंगे?

प्रोडक्ट ओनर के साथ यूनिट चुनें। कोड-पॉइंट पुनरावृत्ति सरोगेट पेयर्स को विभाजित होने से रोकती है, लेकिन यह अभी भी उपयोगकर्ता द्वारा देखे जाने वाले कुछ कैरेक्टर्स को विभाजित करती है। ग्रैफ़िम विभाजन दृश्यमान कैरेक्टर्स से बेहतर मेल खाता है, और यूनिकोड नॉर्मलाइज़ेशन विहित रूप से समकक्ष अनुक्रमों की लगातार तुलना कर सकता है। लोकेल, केस फोल्डिंग, एक्सेंट और टोकन-स्तरीय नियम उत्पाद के निर्णय हैं। DP से पहले उस प्रीप्रोसेसिंग को लागू करें और समर्थित भाषाओं के उदाहरणों का परीक्षण करें।

फॉलो-अप 7: क्या एक पंक्ति दो पंक्तियों की जगह ले सकती है?

हाँ। dp[j] को ओवरराइट करने से पहले, इसके पुराने मान को अगले डायगोनल के रूप में सहेजें; dp[j] अभी भी ऊपर के सेल का प्रतिनिधित्व करता है, और dp[j - 1] पहले से ही वर्तमान पंक्ति के बाएँ सेल का प्रतिनिधित्व करता है। यह स्थिर कारक (constant factor) को कम करता है, असिम्प्टोटिक स्पेस को नहीं। एक इंटरव्यू में, दो पंक्तियों को सिद्ध करना अक्सर आसान होता है और त्रुटि की संभावना कम होती है जब तक कि इंटरव्यूअर विशेष रूप से इन-प्लेस वैरिएंट का अनुरोध न करे।