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.
Programming Praxis 
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)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.
;; 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>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… ;-)
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) ;;;