קוראים וחברים יודעים כבר שיש לי חולשה לראיונות עבודה ובפרט לשאלות מקצועיות מראיונות עבודה, ולכן כל כך שמחתי לראות באיזו קבוצת פייסבוק קישור לספר מלא שאלות מסוג זה. אחרי דפדפוף מהיר נעצרתי על שאלונת בנושא חיבור רשימות מקושרות.

1. השאלה

ניתן לייצג מספר ברשימה מקושרת באמצעות חלוקתו לספרות ואחסון כל ספרה כאיבר ברשימה בסדר הפוך, כך שספרת האחדות היא האיבר הראשון, ספרת העשרות השני וכן האלה.

בהנתן שתי רשימות כאלה, כתבו פונקציה המחשבת את סכום המספרים המיוצגים ומחזירה אותו כרשימה.

2. הכנה לפתרון

בעיה ראשונה של רובי (בעיה? אולי בעצם יתרון...) היא שאין בשפה מבנה של רשימה מקושרת. זה אגב טיעון לא רע נגד שאלות ראיונות עבודה מסוג זה, שהרי מה פתאום שואלים על רשימות מקושרות כשבעבודה היום יומית מתכנתים לא נוגעים במבנה נתונים זה. אבל אנחנו לא טיפוסים קטנוניים ובכלל כל הכיף בשאלות ראיונות עבודה שהן נותנות הפסקה מהחיים האמיתיים. בקיצור בואו נתחיל בלכתוב קוד רובי לניהול רשימה מקושרת, אתו נוכל לפתור את השאלה:

class Element
  attr_accessor :data, :next

  def initialize(data)
    @data = data
    @next = nil
  end
end  

class SinglyLinkedList
  include Enumerable

  attr_accessor :head, :tail

  def initialize()
    @head = Element.new(nil)
    @head.next = nil
    @tail = @head
  end

  def add(data)
    @tail.next = Element.new(data)
    @tail = @tail.next
    @tail.next = nil
  end

  def <<(data)
    add(data)
    self
  end

  def ==(other)
    to_a == other.to_a
  end

  def each
    l1 = head&.next
    while l1
      yield l1.data
      l1 = l1&.next
    end
  end

  def to_s
    "( #{self.to_a.join(' -> ')} )"
  end

end

הבסיס פשוט. רשימה מקושרת מורכבת מאלמנטים, וכל אלמנט מחזיק מידע וקישור לאלמנט הבא. הרשימה מחזיקה את שני המצביעים head ו tail לתחילת וסוף הרשימה, ומגדירה פעולות שרשימה יכולה לבצע. לרובי יש Mixin שנקרא Enumerable שמאפשר הגדרה אוטומטית של פעולות על בסיס פעולת each, כך שאנחנו צריכים רק לספר לרובי איך לבצע סריקה של מבנה הנתונים ורובי כבר מוסיפה אוטומטית אוסף גדול של יכולות הכולל את map, inject, המרה למערך, שליפת איברים ועוד.

פעולה שניה היא הוספה, וכאן הגדרתי שתי פונקציות בשביל שיהיה נוח: פונקציית add מוסיפה איבר לרשימה והאופרטור >> של רובי שעושה את אותו הדבר וגם מחזיר את מבנה הנתונים כך שאפשר יהיה לשרשר הוספות.

עכשיו אפשר להמשיך לחלק השני של ההכנה והוא כתיבת קוד הבדיקה. השאלה בספר כללה מקרה דוגמא יחיד של חיבור שתי רשימות באותו האורך. לי נראה הגיוני להוסיף גם בדיקות עם אורכים שונים וחיבור הרשימה הריקה. סך הכל קוד הבדיקה יצא כך:

describe 'Test Code' do
  it 'should calculate sum correctly when length is equal' do
    x = SinglyLinkedList.new << 3 << 1 << 5
    y = SinglyLinkedList.new << 5 << 9 << 2
    z = SinglyLinkedList.new << 8 << 0 << 8

    expect(x + y).to eq(z)
  end

  it 'should calculate sum correctly when first list is longer' do
    x = SinglyLinkedList.new << 3 << 1 << 5
    y = SinglyLinkedList.new << 9 
    z = SinglyLinkedList.new << 2 << 2 << 5

    expect(x + y).to eq(z)
  end

  it 'should calculate sum correctly when second list is longer' do
    x = SinglyLinkedList.new << 9 
    y = SinglyLinkedList.new << 3 << 1 << 5
    z = SinglyLinkedList.new << 2 << 2 << 5

    expect(x + y).to eq(z)
  end

  it 'should treat an empty list as 0' do
    x = SinglyLinkedList.new
    y = SinglyLinkedList.new << 3 << 1 << 5
    z = SinglyLinkedList.new << 3 << 1 << 5

    expect(x + y).to eq(z)
  end

3. פתרון השאלה

הרעיון של הפתרון די פשוט: נוסיף רשימת Carry עבור תוצאות חיבור מעל 9, וכך כל איבר ברשימת התוצאות הוא פשוט:

res = l1 + l2 + previousCarry

חשבו חיבור ארוך ודמיינו את רשימת ה Carry בתור השורה העליונה בה אנו רושמים את הספרות לזכור.

מסיבה לא ברורה בספר בחרו ללכת על פתרון רקורסיבי, מה שבעיניי היה מוריד נקודות על יעילות וגם על קריאות. חיבור איטרטיבי ברובי פשוט ירוץ על שתי הרשימות וייצור את רשימת התוצאה וה Carry תוך כדי סריקה באופן הבא:

  def +(other)
    carry = SinglyLinkedList.new << 0
    result = SinglyLinkedList.new

    l1, l2, lc  = [self, other, carry].map {|l| l.head.next}

    while l1 || l2 do
      d = (l1&.data || 0) + (l2&.data || 0) + (lc&.data || 0)
      carry.add(d / 10)
      result.add(d % 10)

      l1 = l1&.next
      l2 = l2&.next
      lc = lc&.next
    end 

    result
  end

כבונוס פתרון זה ממחיש את השימוש באופרטור &. של רובי, הוא אופרטור הניווט הבטוח. הפקודה:

l1 = l1&.next

אומרת שאם l1 מתיחס לאוביקט שיש לו שדה next ניקח ערך זה בתור הערך החדש, ובכל מצב אחר נשים שם את הערך nil. בצורה כזו אפשר להמשיך לסרוק את הרשימה גם כשאחת הרשימות קצרה מהשניה, ואין צורך בטיפול במיוחד בסוף הרשימה. ברגע שרשימה נגמרת נסיון לשלוף ממנה מידע יחזיר nil ולכן ערכה לתוצאה יהיה 0, ובנוסף האיבר הבא של סוף הרשימה יישאר nil.

בראיונות עבודה תדרשו לכתוב את הלולאה בפונקציה (או את הרקורסיה המתאימה) על לוח או דף, מה שהופך את התרגיל ליותר מלחיץ. אני גם לא בטוח שיתנו לכם לראות את כל קוד ההכנה שמסביב, אולי רק יגידו שאפשר להניח פעולות בסיסיות על רשימה.

התרגיל ועוד המון כמוהו מתוך הספר: Cracking the Coding Interview: 150 Programming Questions and Solutions

4. קוד התוכנית המלא להרצה

התוכנית המלאה זמינה להרצה כאן בקודפיקניק. רשמו במסוף rspec app.rb להרצה או פתחו את הקובץ לעריכה לראות את הקוד: