שאלות מראיונות עבודה: כיווץ מחרוזות

02/09/2021

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

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

aaaabbccc

אז אנחנו מחליפים את רצף ה a-ים ב a4, את רצף ה b-ים ב b2 ואת רצף ה c-ים ב c3 ומקבלים:

a4b2c3

אם התוצאה ארוכה יותר מהמחרוזת המקורית יש להחזיר את המחרוזת המקורית, ואם התוצאה קצרה יותר יש להחזיר את התוצאה המכווצת.

תוכן עניינים

  1. פיתרון

1. פיתרון

כל פעם שאני שומע "רצף של אותיות" בשאלה מהסוג הזה מיד אני חושב על ביטויים רגולאריים. בביטוי רגולארי אני יכול לסגור קטע מסוים שמצאתי בסוגריים ואז להתיחס אליו שוב באמצעות \1. לכן רצף של אותיות הוא בסך הכל הצירוף (\w)\1+ או אם הרצף יכול להיות גם באורך 1 זה יהיה (\w)\1*.

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

import re

def compress(original):
    compressed =  re.sub(
            r'(\w)\1*',
            lambda m: m[0][0] + str(len(m[0])),
            original)
    return compressed if len(compressed) < len(original) else original

def test_compress():
    assert compress("a")       == "a"
    assert compress("aaa")     == "a3"
    assert compress("aaabbb")  == "a3b3"
    assert compress("aaabccc") == "a3b1c3"