שאלות מראיונות עבודה: סכום רשימות ב Ruby
קוראים וחברים יודעים כבר שיש לי חולשה לראיונות עבודה ובפרט לשאלות מקצועיות מראיונות עבודה, ולכן כל כך שמחתי לראות באיזו קבוצת פייסבוק קישור לספר מלא שאלות מסוג זה. אחרי דפדפוף מהיר נעצרתי על שאלונת בנושא חיבור רשימות מקושרות.
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
להרצה או פתחו את הקובץ לעריכה לראות את הקוד: