### 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.

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
``` ;; 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) ;;; ```