I was given following task in the interview: Given a string, find shortest substring in it that contains all of the different characters contained in the original string.Here is my solution in emacs lisp:(defun add-to-hash (c ht)  Add an instance of character C to hash table HT  (puthash c (1+ (gethash c ht 0)) ht))(defun remove-from-hash (c ht &optional try)  Remove an instance of character C from hash table HTReturn nil if no instances of C remain in HT  (let ((old (gethash c ht 0)))    (if (and try (< 2 old))        nil      (if (> 1 (puthash c (1- (gethash c ht 0)) ht))          (remhash c ht)        t))))(defun find-min-substring (sstr)  Find minimal substring that contains all the characters in a given string  ;; get all characters  (let* ((all-chars (make-hash-table))         (slen (length sstr))         (fcnt (progn                 (mapc (lambda (c) (add-to-hash c all-chars)) sstr)                 (hash-table-count all-chars)))         (beg 0) (end fcnt)         (res sstr))    (if (= end slen)        res      (let* ((cand (substring sstr beg end))             (cand-chars (make-hash-table))             (ccnt (progn                     (mapc (lambda (c) (add-to-hash c cand-chars)) cand)                     (hash-table-count cand-chars))))        ;; find first candidate, that is a substring with all the characters        (while (< ccnt fcnt)          (add-to-hash (aref sstr end) cand-chars)          (setq end (1+ end))          (setq ccnt (hash-table-count cand-chars)))        (setq cand (substring sstr beg end))        ;; shorten it as much as possible        (while (remove-from-hash (aref sstr beg) cand-chars t)          (setq beg (1+ beg)))        (setq cand (substring sstr beg end))        (setq res cand)        ;; check other variants        (while (< end slen)          ;; advance both ends          (add-to-hash (aref sstr end) cand-chars)          (setq end (1+ end))          (remove-from-hash (aref sstr beg) cand-chars)          (setq beg (1+ beg))          (setq ccnt (hash-table-count cand-chars))          ;; another candidate is found          (when (= ccnt fcnt)            ;; only change candidate if it was shortened            (while (remove-from-hash (aref sstr beg) cand-chars t)              (setq beg (1+ beg))              (setq cand (substring sstr beg end)))            (setq res cand)))        res))))
Minimal substring with all characters contained in string
strings;interview questions;lisp;elisp