Interview Question: Palindromes

35
29



Coding interview question from

In this video, I show how figure out if a linked list is a palindrome.

Do you have a big interview coming up with Google or Facebook? Do you want to ace your coding interviews once and for all? If so, Byte by Byte has everything that you need to go to get your dream job. We’ve helped thousands of students improve their interviewing and we can help you too.

Stuck on Dynamic Programming? Check out our free ebook: www.dynamicprogrammingbook.com

50 Practice Questions:

You can also find me on
Twitter:
Facebook:
Email: sam@byte-by-byte.com

Nguồn:https://wijstaanvooronzegrondrechten.org/

35 COMMENTS

  1. Thank you so much for the great content. I came looking for a solution for the longest palindromic string problem. Would you offer some help since it is a slightly different problem? I have seen some tutorials on it, but they do not quite work for me due to slight differences between Java and C#. I am trying to do it in C#. I am sure I'll see other methods since I just started to search, but if you can and want to give some advice on this, I would greatly appreciate it.

  2. I'm so happy that I found your channel!! Best explanation ever! Thanks a lot, Sam 🙂 & the best part is you cover every nook and corner of the problem which makes it really worth watching however long your video is gonna be!

  3. We can replace the use of the stack with an int instead. As we know that x^z^x = z. We can make an xor of the elements until runner gets to the end. If we have an odd number of elements, we need to skip the the xor of the element in the middle. Then keep iterating until the end. After, checking if the result of the xor's is zero means that the list is a palindrome

  4. Now will it work if the linked list has more than 5 nodes? In that case by the time the runner reached the end point the curr will cross the mid point of the list. How does it then know what was the mid point of the list ?

  5. i just tried to change links and trying to reverse but i stuck at that method. So i am here to watch another method to solve this problem.

  6. we can add the whole linklist to stack and then pop element one by one and compare it with the linklist from head node till end
    no need for different cases of odd length and even length 🙂

  7. This is unbelievably helpful for a beginner of data structures, and programming in general. Thanks so much, one teacher to another. I'll be going through them all, one by one. Fun months ahead.

  8. class Node:
    def __init__(self, val):
    self.value = val
    self.next = None
    def add(self, val):
    if self.next is None:
    self.next = Node(val)
    else:
    self.next.add(val)
    def printTree(self):
    print(self.value)
    if self.next:
    self.next.printTree()

    def palindrome_linkedlist(node):
    stack = []
    curr = node
    runner = node
    while runner != None and runner.next != None:
    stack.append(curr.value)
    print(stack)
    runner = runner.next.next
    curr = curr.next
    if runner != None: curr = curr.next # if length is odd,,
    while curr != None:
    if stack.pop() != curr.value: return False
    curr = curr.next
    return True

    c = Node(1)
    c.add(2)
    c.add(3)
    c.add(2)
    c.add(1)
    c.printTree()
    print(palindrome_linkedlist(c))

  9. def palindrome(string):
    length = int(len(string)/2)
    for i in range(length):
    if string[i] != string[len(string)-1-i]:
    return False
    return True

    print(palindrome("abcba")) #odd
    print(palindrome("abccba")) #even
    print(palindrome("abccbaa"))

  10. Great work! You could use a queue. Ignore the middle element obviously. Then you could remove from the queue after the half point of the list.

  11. the fact that linked lists are the de facto data structure in Haskell kind of lends itself to a somewhat elegant implementation of this algorithm

    isPalindrome' xss = go [] xss xss where
    go stack (x:xs) (_:_:rs) = go (x:stack) xs rs
    go stack (_:xs) [_] = xs == stack
    go stack xs [] = xs == stack
    go _ [] _ = True

    and of course the canonical implementation of this function in Haskell is even more elegant

    isPalindrome = (==) <*> reverse

  12. Great video.
    The use of a stack requires an O(n) in space, how does it differ from copying/reversing/comparing that you had mentioned?

  13. The way I solved the first half was just slightly different than yours, and I'm wondering if you think it's fine. It seems you started both the current and the runner in the same position, but I started current as the first Node and runner as the second Node. I wrote it as:

    Node runner = list.next;
    Node current = list;
    int counter = 2;

    while (runner != null) {

    runner = runner.next;
    counter++;
    if (runner != null) {
    runner = runner.next;
    counter++;
    }
    intStack.push(current.val);
    current = current.next;

    }

    At the end of this loop, I check whether counter is odd or even (it was originally initialized as 2). If it's odd, then I just move current one more node over and pop it off the stack (since it doesn't need to match another element), and don't do anything if it's even, and the second part seems to match your code. Can you see anything wrong with mine?

  14. I loved the way of your problem solving …. simple and worth remembering.. Keep it up ! Would love to see your videos on dynamic programming !

  15. man respect to u for ur good lectures and helping me out for interview prep for backlogged students like me.
    …sending wishes to u byte by byte from india.stay good brother.

LEAVE A REPLY

Please enter your comment!
Please enter your name here