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/

I like how you pretend to be coming up with answers yourself.

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.

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!

Thank you!

Very good!

By far the best explanation. Thank you !

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

What if the palindrome is not centered in the input array? e.g. [0,0,0,0,11,22,33,22,11] ?

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 ?

it's AAAwesome! thank you !!

Awesome 🙂

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.

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 🙂

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.

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

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"))

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.

whats the runtime?

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

You have the best explanation for every problem. Thank you.

Hi loved your video, Just have one question shoudnt we should have OR in while instead of AND?

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?

This is gold. YouTube needed you.

Love how clear and concise you are with your explanations. Please make more videos.

Love the clear explanation you gave, very helpful! Thanks a lot! 🙂

I love it, and learn a lot ,thank you

very helpful!

what is the reason for having the second loop?

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?

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

awesome 🙂

Thanks man your videos are very helpful; keep up the good work. 🙂

cool

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.

You are the best.

great video.