Intersection of Linked Lists

Intersection of Linked Lists


Continuing with the skitch experiment, here’s another attempt to explain spotting the intersection of Linked Lists with some cool images. Allow me to quickly introduce you to two good friends, Linked List 1 and Linked List 2. The linked list 1 is  (1 -> 2 -> 3 -> 4 -> 5 -> 6) having a length L1 and linked list 2 is (-1 -> -2 -> 3 -> 4 -> 5 -> 6) having a length L2. As we can ...

Kth maximum element in unsorted collection


Finding the Kth maximum element in an unsorted array doesn’t seem to be a big deal. Because, we know that finding the maximum and if we keep on eliminating the largest element from the array. And this we will take us to the Kth maximum element in an array. But this solution is of order O(n2). Can it be done in linear way? Yes. Well, almost. Have a look at the following method written in Java. Generalizing into an algorithm ...

No. of Step Calculation in an Algorithm


There was a time when the processor were just starting to explore their potential. Then code optimization made a huge difference in the performance of the code. But, today most programmers take the optimization for granted as the compilers are smarter and the processors run like they have fire on their ass. But, to be a good programmer, one should always stick to the roots of programming. Let their be three arrays, A, B and C of equal lengths n. ...

Greatest Common Divisor: Euclid Style


Euclid out of nowhere proposed this algorithm which calculates the greatest common divisor of two numbers. The simplest way of calculating the GCD is probably the simple prime factorization method. But, Euclid was no common chap. He devised a way which calculates the GCD recursively. The idea was to simplify the problem each time, preserving the GCD. Lets discuss the algorithm, in order to understand it- getGCD(n, m) {    while(n % m != 0) {        r = ...