Interview Question: Palindromes

Coding interview question from www.byte-by-byt...
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: www.byte-by-by...
You can also find me on
Twitter: / bytebybyteblog
Facebook: / bytebybyteblog
Email: [e-mail]

[@poojaguru2516]

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!

[@user-mn3iq2cs9n]

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.

[@ByteByByte]

so glad to hear it!

[@mechfiresaurabh]

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

[@ByteByByte]

Thanks! And there are a couple already as well as a few coming down the pipes, so keep your eyes peeled ;)

[@zukoric]

This is gold. KZbin needed you.

[@ByteByByte]

thank you so much!

[@arghadeep10]

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.

[@ByteByByte]

thanks! glad you're finding them useful

[@reetigarg7398]

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

[@ByteByByte]

thanks! more videos are coming soon :)

[@oceanview-u8q]

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

[@celinks123]

Try solve it using a List, assume your string was stored as a list not a string. Its easy to solve when using a string

[@ankitsharma8221]

By far the best explanation. Thank you !

[@narularohit7688]

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

[@ByteByByte]

thanks!

[@jorgesmulevici5313]

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

[@ByteByByte]

This would breakdown if we have the same elements but in a different order

[@jorgesmulevici5313]

​@@ByteByByte You are right. Also, I realized after I posted that it will fail for different elements with similar 'xor binary representation' as well. Example: 7^4^2^1 is zero

[@teeeeteeeez]

Its sooo good! Thank you! Can you please do some graph, trees and dynamic programming question? PLEAAAAASE! Just Subbed!

[@ByteByByte]

+Xiji Guo Thanks! If you check out the other videos in the playlist, there are some graph/tree and dynamic programming questions mixed in there, and I add new ones every week :) If you would like to see the solution for a specific question, though, just let me know!

[@yanma1316]

I love it, and learn a lot ,thank you

[@praveensingh1744]

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

[@salmamahameed2160]

Yep, I think that the best way to solve these kinda problems (palindrome) is using a stack it's very easy to work with

[@siddharthpateriya1745]

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

[@ByteByByte]

thanks!

[@DrShishKaboob]

Great video, thanks!

[@ByteByByte]

Thanks!

[@sandipsinha3453]

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 ?

[@phaattran]

Bro watch the whole video

[@hammerain93]

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

[@ByteByByte]

then it's not a palindrome

[@premangraithatha8273]

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.

[@shawnmofid7131]

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.

[@celinks123]

What is the actual question, let me give it a try?

[@RickySolorio]

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

[@ByteByByte]

you're welcome!

[@jays8504]

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?

[@ByteByByte]

That seems reasonable to me as long as it works!

[@NaveenKumar-tt6en]

Awesome :)

[@t.nguyen4517]

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?

[@ByteByByte]

You tell me. What would be the space complexity of each of those options?

[@mx2775]

it's AAAwesome! thank you !!

[@SoftwareEngenius]

Nice, but apparently there's a way to do it with O (1) space complexity. What color switch is your mechanical keyboard?

[@ByteByByte]

You could do it in O(1) space complexity by counting the number of elements and then traversing repeatedly to find each pair of nodes. Basically I'd say ok first compare the first node to the last node, then the second node to the second-to-last node, and so on. But to go from the last node to the second-to-last node you would have to traverse the whole list again (assuming its a singly linked list). As a result you're going to get a time complexity of O(n^2). This is pretty much what always happens. If we need to be really space efficient, we can do so at the expense of time complexity, and vice versa. The solution I showed in the video has a better time complexity but takes more space. Good catch though! And I have this keyboard: www.daskeyboard.com/model-s-professional-for-mac/, so blue switches. It's really clicky (as you can hear) and I love it.

[@SoftwareEngenius]

Ah. I actually had that keyboard for a week and I liked it but too expensive. I got some chinese knock-off but blue switches too. I find blue switches a bit _too_ loud now, I might get red or brown. And thanks. I remember reading that it is possible with O(1) and O(n) time complexity, see here: www.geeksforgeeks.org/function-to-check-if-a-singly-linked-list-is-palindrome/ You can do it by reversing in-place, but I'm not quite sure how it works since it's a singly linked list.

[@ByteByByte]

Yeah definitely a personal preference thing. I don't mind them. And oh interesting I hadn't seen that solution; it's pretty interesting. Basically you can reverse it in place by modifying the pointers. I start at the first node and save the next node to a temp variable. Then I set the next pointer to point to null. Now I save my current node to another temp variable and then go to the saved next node. Now I can update the next pointer for that node to point to my first node, and so on. Definitely a lot more of effort than most of the other solutions I've seen, but it does run in O(n) time with O(1) *extra* space. Bear in mind, though, that it still takes O(n) space total because you have to store the whole linked list.

[@SoftwareEngenius]

True, thanks :)

[@pursuitofcat]

class Node: def __init__(self, val): self.val = val self.next = None def __repr__(self): return f"Node" def isPalindrome(head: Node): """ Given a linked list determine whether the linked list is a palindrome """ slow = fast = head stack = [] # travel with slow and fast pointers # and keep pushing the slow's values into # a stack while fast and fast.next: stack.append(slow.val) slow = slow.next fast = fast.next.next # take care of the odd number of items scenario if fast is not None: slow = slow.next while slow: if slow.val != stack.pop(): return False slow = slow.next return True one = Node(1) two = Node(2) second_two = Node(2) second_one = Node(1) one.next = two two.next = second_two second_two.next = second_one # assert isPalindrome(one) three = Node(3) second_one.next = three assert isPalindrome(one) is False

[@MrAkshay2711]

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

[@ByteByByte]

Yep. Sadly there's no way to correct it in the video

[@MrAkshay2711]

Thanks

[@TheGamerGuy201]

very helpful!

[@ByteByByte]

thanks!

[@Victor-xl4ru]

what is the reason for having the second loop?

[@ByteByByte]

The first loop pushes the first half of the list onto a stack and the second loop is what verifies that the stuff you pushed onto the stack matches the second half of the list

[@Victor-xl4ru]

im sorry i meant the reason for the second if statement

[@ByteByByte]

We have to compare the value from the first half and second half

[@anthonycheng6902]

whats the runtime?

[@ByteByByte]

You tell me

[@batmanb8194]

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

[@talaviss123]

cool

[@ByteByByte]

thanks :)

[@oceanview-u8q]

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