Given pointers to the heads of two linked lists. They intersect at some element, and proceed as a single list there-onwards. Find the point of intersection in O(n).
one of the solution can be using two for loops and checking individual pointers at each node if they matches. o(n^2).
Another solution can be by adding one more field in linked list of boolean type which will store information about whether that node is already visited.
1) Get count of the nodes in first list, let count be c1. 2) Get count of the nodes in second list, let count be c2. 3) Get the difference of counts d = abs(c1 – c2) 4) Now traverse the bigger list from the first node till d nodes so that from here onwards both the lists have equal no of nodes. 5) Then we can traverse both the lists in parallel till we come across a common node. (Note that getting a common node is done by comparing the address of the nodes)
You are given n real numbers in an array. A number in the array is called a decimal dominant if it occurs more than n/10 times in the array. Give an O(n) time algorithm to determine if the given array has a decimal dominant.
Implement a function getbits, that returns the(right adjusted) n bits that begin at position p of an integer. Assume bit position 0 is at the right end and that n and p are sensible positive values.
one of the solution can be using two for loops and checking individual pointers at each node if they matches.
ReplyDeleteo(n^2).
Another solution can be by adding one more field in linked list of boolean type which will store information about whether that node is already visited.
o(m+n)
1) Get count of the nodes in first list, let count be c1.
ReplyDelete2) Get count of the nodes in second list, let count be c2.
3) Get the difference of counts d = abs(c1 – c2)
4) Now traverse the bigger list from the first node till d nodes so that from here onwards both the lists have equal no of nodes.
5) Then we can traverse both the lists in parallel till we come across a common node. (Note that getting a common node is done by comparing the address of the nodes)