Linked List Palindrome

September 8, 2017

Today’s exercise is an Amazon interview question from Career Cup (this is the exact question asked):

There is a given linked list where each node can consist of any number of characters :- For example
a–>bcd–>ef–>g–>f–>ed–>c–>ba.
Now please write a function where the linked list will return true if it is a palindrome .
Like in above example the linked list should return true

Your task is to write a program to determine if a list of strings forms a palindrome. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Advertisements

Pages: 1 2

5 Responses to “Linked List Palindrome”

  1. chaw said

    The following should run in time linear in the input size, and is a
    bit more general than needed.

    (import (scheme base)
            (only (srfi 1) list= fold)
            (only (srfi 13) string-fold))
    
    (define input-1
      '("a" "bcd" "ef" "g" "f" "ed" "c" "ba"))
    
    (define (palindrome? = lst)
      (list= = lst (reverse lst)))
    
    ;; equivalent to (reverse (apply append (map string->list slist)))
    ;; but more direct.
    (define (string-list->rlist slist)
      (fold (lambda (str acc)
              (string-fold cons acc str))
            '()
            slist))
    
    (define (palindrome-string-list? lst)
      (palindrome? char=? (string-list->rlist lst)))
    
    (palindrome-string-list? input-1)
    

  2. John Cowan said

    I was asked a palindrome question yesterday, but it explicitly excluded any solution that involved reversing or flattening, as it had to execute in O(1) space.

  3. 
    ;; Simple solution.
    ;; O(n) in time. (assuming amortized O(n) with-output-to-string implementation).
    ;; 2n space. (for string and its reverse).
    ;; programmer time: the time to write it, correct on the first write.
    
    (defun palindromic-list-p (list-of-strings)
      (flet ((list-to-string (los)
               (with-output-to-string (*standard-output*)
                 (dolist (string los)
                   (write-string string)))))
        (let ((string (list-to-string list-of-strings)))
          (string= string (reverse string)))))
    
    (assert      (palindromic-list-p '("a" "bcd" "ef" "g" "f" "ed" "c" "ba")))
    (assert (not (palindromic-list-p '("a" "bcd" "ef" "g" "f" "Xd" "c" "ba"))))
    
    
    
    ;; Sophisticated solution: the characters are compared in place.
    ;; O(n) in time
    ;; O(e) in space with e = (length list-of-strings), which may be much smaller than n if the strings are big.
    ;; programmer time: a lot; debugging and tuning.
    
    (defun palindromic-list-p (list-of-strings)
      (labels ((equal-palindromic-string (size a start-a b start-b)
                 (loop
                   :repeat size
                   :for i :from start-a
                   :for j :from (- (length b) start-b 1) :downto 0
                   :always (char= (aref a i) (aref b j))))
               (equal-list-of-strings (a start-a b start-b)
                 (cond
                   ((endp a) (endp b))
                   ((endp b) nil)
                   (t        (let* ((size (min (- (length (first a)) start-a)
                                               (- (length (first b)) start-b)))
                                    (new-start-a (+ start-a size))
                                    (new-start-b (+ start-b size)))
                               (and (equal-palindromic-string size (first a) start-a (first b) start-b)
                                    (equal-list-of-strings
                                     (if (< new-start-a (length (first a)))   a           (rest a))
                                     (if (< new-start-a (length (first a)))   new-start-a 0)
                                     (if (< new-start-b (length (first b)))   b           (rest b))
                                     (if (< new-start-b (length (first b)))   new-start-b 0))))))))
        (equal-list-of-strings list-of-strings 0
                               (reverse list-of-strings) 0)))
    
    
    (assert      (palindromic-list-p '("a" "bcd" "ef" "g" "f" "ed" "c" "ba")))
    
    (assert (not (palindromic-list-p '("a" "bcd" "ef" "g" "f" "Xd" "c" "ba"))))
    
    
    ;; To see how this works, let's trace equal-palindromic-string:
    
    cl-user>       (palindromic-list-p '("a" "bcd" "ef" "g" "f" "ed" "c" "ba"))
    
    (equal-palindromic-string 1 "a" 0 "ba" 0) 
    (equal-palindromic-string 1 "bcd" 0 "ba" 1) 
    (equal-palindromic-string 1 "bcd" 1 "c" 0) 
    (equal-palindromic-string 1 "bcd" 2 "ed" 0) 
    (equal-palindromic-string 1 "ef" 0 "ed" 1) 
    (equal-palindromic-string 1 "ef" 1 "f" 0) 
    (equal-palindromic-string 1 #1="g" 0 #1# 0) 
    (equal-palindromic-string 1 "f" 0 "ef" 0) 
    (equal-palindromic-string 1 "ed" 0 "ef" 1) 
    (equal-palindromic-string 1 "ed" 1 "bcd" 0) 
    (equal-palindromic-string 1 "c" 0 "bcd" 1) 
    (equal-palindromic-string 1 "ba" 0 "bcd" 2) 
    (equal-palindromic-string 1 "ba" 1 "a" 0) 
    t
    cl-user>       (palindromic-list-p '("a" "bcd" "ef" "g" "f" "Xd" "c" "ba"))
    
    (equal-palindromic-string 1 "a" 0 "ba" 0) 
    (equal-palindromic-string 1 "bcd" 0 "ba" 1) 
    (equal-palindromic-string 1 "bcd" 1 "c" 0) 
    (equal-palindromic-string 1 "bcd" 2 "Xd" 0) 
    (equal-palindromic-string 1 "ef" 0 "Xd" 1) 
    nil
    cl-user>
    
  4. Note: it is possible to make it O(1) in space, but this will degrade into O(e^2)+O(n) instead of O(e)+O(n) in time since we will have to traverse the list several time, by index. (with e = (length list) and n = total number of characters). It will also be O(t^2) in programmer time, with t being the time the programmer took to implement the second version above… ;-)

  5. chaw said

    Prompted by John Cowan’s comment above, here is a version that is
    constant space, but quadratic time.

    If using SRFI-135 is considered “cheating” then we could impagine we
    have included code from portable implementation from that SRFI. (We
    could also use “istrings” from SRFI 140 or Kawa, etc.)

    ;; Tested with Larceny Scheme
    
    (import (scheme base)
            (scheme write)
            (only (srfi 1) fold)
            (only (srfi 135) text text-length text-ref string->text))
    
    (define input-1t
      (map string->text '("a" "bcd" "ef" "g" "f" "ed" "c" "ba")))
    
    (define input-2t
      (map string->text '("a" "bcd" "f" "g" "f" "ed" "c" "ba")))
    
    ;; An "ltext" is a list of texts, viewed as a segmented text/string.
    ;; ltext-ref is then analogous to text-ref, string-ref, etc.
    ;; Since text-ref is O(1), ltext-ref is O(n) time, O(1) space.
    (define (ltext-ref ltxt idx)
      (let ((flen (text-length (car ltxt))))
        (if (< idx flen)
            (text-ref (car ltxt) idx)
            (ltext-ref (cdr ltxt) (- idx flen)))))
    
    ;; ltext analogue of text-length, string-length etc.
    ;; O(n) time, O(1) space.
    (define (ltext-length ltxt)
      (fold (lambda (txt c)
              (+ c (text-length txt)))
            0
            ltxt))
    
    ;; An array-style palindrome-check.
    ;; Given above, it is O(n^2) time, O(1) space.
    (define (ltext-palindrome? ltxt)
      (let ((len (ltext-length ltxt)))
        (let f ((i 0))
          (or (>= i (/ len 2))
              (and (char=? (ltext-ref ltxt i)
                           (ltext-ref ltxt (- len i 1)))
                   (f (+ i 1)))))))
    
    (display (map ltext-palindrome? `((,(text))
                                      (,(text #\a))
                                      (,(text #\a #\a))
                                      (,(text #\a #\b))
                                      ,input-1t
                                      ,input-2t)))
    (newline)
    ;;;
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: