check if a linked list is pallendrom.

Question

Saveena · Accepted Answer

do below steps:- 
1) get the middle node of linked list and total number of nodes in O(n) . 
2) get a stack of size n/2 
3) start pushing node values of linked list to stack till(n-1/2 th node if n is odd else n/2 th node) 
4) pop an element from stack and compare with next remaining node of the linked list after middle node.
5) if all values are same till stack is empty then palindrome else not.

devsathish · Answer

Solution with O(n) time, and O(1) space complexity:
1) Use two pointers to find the middle node (i.e, define pointer A, B and initialise them to head. Move pointer by one step, and B by two steps. When B reaches the null, A will be in the middle of the list). The n/2 approach takes extra iteration to compute the size/length of the list.
2) Now reverse the first half of the list.
3) Compare first and second half one by one. If there is a mismatch, the list is not palindrome.

Sveena · Answer

use TreeMap for characters  frequency and print top k keys.

MakeMyTrip

Pergunta de entrevista da empresa MakeMyTrip

Respostas da entrevista

Empresas seguidas

Buscas de vagas