reverser LL nodes with verifying hash values coding question onsite google
Summary
I was given an onsite coding question at Google that asked me to reverse a singly‑linked list while maintaining a custom hash value for each node.
Full Experience
reverser LL nodes with verifying hashvalues
Given LL => [1,3,6,8,0]. => [0,8,6,3,1] espected output
class Node:
def __init__(self,val,next=None):
self.val=val
self.next=None
NEWNODE -> NODE [VAL] -> NULL HASH -> 0 HASH - [HASH(NXTNODE VAL) + VAL]
[Node(1,next=> 3, hash=>(18)), Node(3,next=>6,Hash(17) Node(6,Next=>8,hash(14), Node(8,next=>0,hash(8) original Node(0,None,Hash(0)) [1,3,6,8,0]. => head => [0,8,6,3,1] output [18,17,15,8,0] reversal => hashvalue=>[0,8,14,17,18]
1 => 18 => 18-1>=0 => prefix=17 3=> 17-3 =>14 >=0 [prefix=14] 6=> node x ->{ hash(x) == val + hash(next) pointer to the head node }
[0,8,6,3,1]
[None <-1 ] prev cur=head, None [Node(1,next=> 3),nxt cur.next Node(3,next=>6) <--- Node(6,Next=>8), Node(8,next=>0) Node(0,Next=> Null). 0 prefix= 0 head reverse logic // prev,nxt,cur => None,None,head // while cur: // nxt=cur.next // cur.next=prev // prev=cur // cur=nxt // return prev
Interview Questions (1)
Reverse Linked List with Hash Verification
Given a singly linked list where each node stores an integer value val and a hash value defined as hash(node) = val + hash(next), with the hash of the last node being its own value, reverse the list while preserving correct hash values for each node.
The input example is:
Original list values: [1, 3, 6, 8, 0]
Corresponding hash values (computed as described): [18, 17, 15, 8, 0]
The expected output after reversal is:
Reversed list values: [0, 8, 6, 3, 1]
Reversed list hash values: [0, 8, 14, 17, 18]
The task is to implement the reversal and ensure each node’s hash follows the same definition after reversal.