Theory – III

Inheritance

Single Inheritance: It is the inheritance hierarchy wherein one derived class inherits from one base class.
Multiple Inheritance: It is the inheritance hierarchy wherein one derived class inherits from multiple base class(es)
Hierarchical Inheritance: It is the inheritance hierarchy wherein multiple subclasses inherit from one base class.
Multilevel Inheritance: It is the inheritance hierarchy wherein subclass acts as a base class for other classes.
Hybrid Inheritance: The inheritance hierarchy that reflects any legal combination of other four types of inheritance.

xyz

Friend class/function

A friend function of a class is defined outside that class’ scope but it has the right to access all private and protected members of the class. friends are not member functions.

class Distance
{
    private:
        int meter;
    public:
        Distance(): meter(0){ }
        friend int func(Distance);  //friend function
};

Immutable object – state cannot be modified after it is created. Immutability can have a performance cost, since when an object cannot be mutated we need to copy it if we want to write to it.

Immutable objects are often useful because

  • they are inherently thread-safe.
  • Immutable objects are good Map keys and Set elements, since these typically do not change once created.
  • References to immutable objects can be cached as they are not going to change.

Make a class immutable by following these guidelines:

  • ensure the class cannot be overridden – make the class final, or use static factories and keep constructors private.
  • make fields private and final.
  • force callers to construct an object completely in a single step, instead of using a no-argument constructor combined with subsequent calls to setXXX methods
  • do not provide any methods which can change the state of the object in any way – not just setXXX methods, but any method which can change state.
  • If the instance fields include references to mutable objects, don’t allow those objects to be changed:
    • Don’t provide methods that modify the mutable objects.
    • Don’t share references to the mutable objects.

Interface

Interface were primarily made popular by Java.
Below are the nature of interface and its C++ equivalents:

  1. interface can contain only body-less abstract methods; C++ equivalent is pure virtual methods, though they can/cannot have body
  2. interface can contain only static final data members; C++ equivalent is static const data members which are compile time constants
  3. Multiple interface can be implemented by a Java class, this facility is needed because a Java class can inherit only 1 class; C++ supports multiple inheritance straight away with help of virtual keyword when needed

Because of point 3 interface concept was never formally introduced in C++. Still one can have a flexibility to do that.

Interface in Java

An interface is a collection of abstract methods. A class implements an interface, thereby inheriting the abstract methods of the interface.

  • You cannot instantiate an interface.
  • An interface does not contain any constructors.
  • All of the methods in an interface are abstract.
  • An interface is not extended by a class; it is implemented by a class.
  • An interface can extend multiple interfaces.

Interfaces have the following properties:

  • An interface is implicitly abstract. You do not need to use the abstract keyword when declaring an interface.
  • Each method in an interface is also implicitly abstract, so the abstract keyword is not needed.
  • Methods in an interface are implicitly public.

Example

public interface NameOfInterface
{
   //Any number of final, static fields
   //Any number of abstract method declarations\
}

When overriding methods defined in interfaces there are several rules to be followed:

  • Checked exceptions should not be declared on implementation methods other than the ones declared by the interface method or subclasses of those declared by the interface method.
  • The signature of the interface method and the same return type or subtype should be maintained when overriding the methods.
  • An implementation class itself can be abstract and if so interface methods need not be implemented.

When implementation interfaces there are several rules:

  • A class can implement more than one interface at a time.
  • A class can extend only one class, but implement many interfaces.
  • An interface can extend another interface, similarly to the way that a class can extend another class.

Implement vs. Extends

Implements

/* File name : Animal.java */
interface Animal {

   public void eat();
   public void travel();
}

* File name : MammalInt.java */
public class MammalInt implements Animal{

   public void eat(){
      System.out.println("Mammal eats");
   }

   public void travel(){
      System.out.println("Mammal travels");
   } 

   public int noOfLegs(){
      return 0;
   }

   public static void main(String args[]){
      MammalInt m = new MammalInt();
      m.eat();
      m.travel();
   }
}

Extends

public interface Sports
{
   public void setHomeTeam(String name);
   public void setVisitingTeam(String name);
}

//Filename: Hockey.java
public interface Hockey extends Sports
{
   public void homeGoalScored();
   public void visitingGoalScored();
   public void endOfPeriod(int period);
   public void overtimePeriod(int ot);
}

The Hockey interface has four methods, but it inherits two from Sports; thus, a class that implements Hockey needs to implement all six methods.

Extending Multiple Interfaces:

public interface Hockey extends Sports, Event

NOTE

class Sub extends Super implements interface // extends before implements

Final

Final can be:

  1. variable
  2. method
  3. class

final variable that have no value it is called blank final variable or uninitialized final variable. It can be initialized in the constructor or by calling this() only. The blank final variable can be static also which will be initialized in the static block only.

Static blocks are also called Static initialization blocks . A static initialization block is a normal block of code enclosed in braces, { }, and preceded by the static keyword.

Example:

class A{  
static final int data;  //static blank final variable  
      static { data=50;}  
public static void main(String args[]){  
       System.out.println(A.data);  
     }  
}

Final variable

If you make any variable as final, you cannot change the value of final variable


Final Method

If you make any method as final, you cannot override it. It can be inherited.

Constructor can’t be final as they are never inherited.

Final Class

If you make any class as final, you cannot extend it.

Final Parameter

If you declare any parameter as final, you cannot change the value of it.

Const Vs Final

A const object can only call const methods, and is generally considered immutable.

const Person* person = myself;
person = otherPerson; //Valid... unless we declared it const Person* const!
person->setAge(20); //Invalid, assuming setAge isn't a const method (it shouldn't be)

A final object cannot be set to a new object, but it is not immutable – there is nothing stopping someone from calling any set methods.

final Person person = myself;
person = otherPerson; //Invalid
person.setAge(20); //Valid!

Java has no inherent way of declaring objects immutable; you need to design the class as immutable yourself.

When the variable is a primitive type, final/const work the same.

const int a = 10; //C++
final int a = 10; //Java
a = 11; //Invalid in both languages

FEW POINTS

  • Final member variable must be initialized at the time of declaration or inside constructor.
  • Local final variable must be initializing during declaration.
  • All variable declared inside java interface are implicitly final.
  • final class can not be abstract in java.
  • Final methods are bonded during compile time also called static binding.
  • Making a class, method or variable final in Java helps to improve performance because JVM gets an opportunity to make assumption and optimization.
  • Making a collection reference variable final means only reference can not be changed but you can add, remove or change object inside collection.

Stack Unwinding

When an exception occurs, the function call stack is linearly searched for the exception handler, and all the entries before the function with exception handler are removed from the function call stack.

When an exception is thrown and control passes from a try block to a handler, the C++ run time calls destructors for all automatic objects constructed since the beginning of the try block. The automatic objects are destroyed in reverse order of their construction.

Issues related to stack unwinding:

  • you should never throw an exception before any existing exception has been handled. This means that the stack unwinding process should never throw an exception

Theory – II

How to overload main

To overload main, it is necessary to use class & declare main as member function

class Overloading1{
     public static void main(int a){
     System.out.println(a);
}

public static void main(String args[]){
        System.out.println("main() method invoked");
         main(10);
   }
}

New is a c++ operator which will dynamically allocate memory and call constructor of the class to initialize memory for which object is created. It Doesn’t need size and gets casted appropriately and returns the exact datatype.

abcd

Ifdef -> if following is defined
Ifndef -> if following is not defined
Commenting  code

#if 0
   Commented code
#endif

xyz

Constructor

Copy constructor – creates object by initializing it with an object of same class, which was already created. The copy constructor is used to:

  • Initialize one object from another of the same type.
  • Copy an object to pass it as an argument to a function.
  • Copy an object to return it from a function.

Example:

classname (const classname &obj) {
   // body of constructor
}

Conversion constructor – if class has constructor with 1 argument, it is conversion constructor as it allows automatic conversion of the class being constructed.

Example

class Test 
{
 private:
   int x;
 public:
   Test(int i) {x = i;}
   void show() { cout<<" x = "<<x<<endl; }
};
 
int main()
{
 Test t(20);
 t.show();
 t = 30; // conversion constructor is called here.
 t.show();
 getchar();
 return 0;
}

Static member function can’t be constant or volatile as const affects the this pointer of nonstatic function whereas static function doesn’t have this pointer.

No virtual constructor is allowed but virtual destructor is allowed to remove object from derived class.

Virtual constructor

“virtual” allows us to call a function knowing only any interfaces and not the exact type of the object. To create an object you need complete information. In particular, you need to know the exact type of what you want to create. Consequently, a “call to a constructor” cannot be virtual.

Virtual destructors are used to delete an instance of a derived class through a pointer to base class:

class Base 
{
    // some virtual methods
};

class Derived : public Base
{
    ~Derived()
    {
        // Do some important cleanup
    }
}

Base *b = new Derived();
// use b
delete b; // Here's the problem!

Since Base’s destructor is not virtual and b is a Base* pointing to a Derived object, delete b has undefined behaviour. In most implementations, the call to the destructor will be resolved like any non-virtual code, meaning that the destructor of the base class will be called but not the one of the derived class, resulting in resources leak.

To sum up, always make base classes’ destructors virtual when they’re meant to be manipulated polymorphically.

If you want to prevent the deletion of an instance through a base class pointer, you can make the base class destuctor protected and nonvirtual; by doing so, the compiler won’t let you call delete on a base class pointer.

Abstract class

Abstract class has atleast one pure virtual function as any class with at least 1 pure virtual function must be abstract because it needs to be extended so that method can actually be implemented.

An abstract method is just another way of describing the characteristics of a pure virtual function. Both just mean a method with no implementation provided that needs to be implemented in a sub-class before the class can actually be instantiated.

If we do not override the pure virtual function in derived class, then derived class also becomes abstract class.

Characteristics

  • Classes inheriting an abstract class must provide definition to the pure virtual function, otherwise they will also become abstract class.
  • Abstract classes can’t be instantiated, but pointers and references of Abstract class type can be created.
  • Abstract can have normal functions and variables along with pure virtual function.

Virtual function

Virtual function whose behavior can be overridden within inherited class by function with same signature.

A pure virtual function (or abstract function) in C++ is a virtual function for which we don’t have implementation, we only declare it. A pure virtual function is declared by assigning 0 in declaration. See the following example.

// An abstract class
class Test
{   
    // Data members of class
public:
    // Pure Virtual Function
    virtual void show() = 0;
   
   /* Other members */
};

Storage class

A storage class defines the scope (visibility) and life-time of variables and/or functions within a C++ Program. Types are:-

  • auto – default storage class for all local variables.
  • Register – should be stored in a register instead of RAM. Can’t have the unary ‘&’ operator as it doesn’t have memory location. should only be used for variables that require quick access such as counters
  • Static – instructs the compiler to keep a local variable in existence during the life-time of the program instead of creating and destroying it each time it comes into and goes out of scope. The static modifier may also be applied to global variables. When this is done, it causes that variable’s scope to be restricted to the file in which it is declared.
  • Extern – give a reference of a global variable that is visible to ALL the program files. When you use ‘extern’ the variable cannot be initialized as all it does is point the variable name at a storage location that has been previously defined.
  • Mutable – Mutable means “subject to change or alteration.” The mutable keyword allows constant member functions to modify mutable data members of constant structures and objects.

Extern

If you want a variable to be accessible across multiple files then define the variable as extern int count in a header file and import it across multiple files.

First File:

int count ;
extern void write_extern();
 
main()
{
   count = 5;
   write_extern();
}

Second File:

extern int count;
void write_extern(void)
{
   std::cout << "Count is " << count << std::endl;
}

xyz

Static

  1. If the static keyword is applied to a class, all the members of the class must be static.
  2. Static methods can only access static members of same class. Static properties are used to get or set the value of static fields of a class.
  3. Static constructor can’t be parameterized. Access modifiers can’t be applied on Static constructor, it is always a public default constructor which is used to initialize static fields of the class.

Mutable

There are some cases where data members are declaring as const, and later want to change the value of the const variable.In C++, it is not legal to change the const value, by using mutable it is possible. This keyword can be applied to only non-static and non-constant data members.

The mutable keyword allows constant member functions to modify mutable data members of constant structures and objects.

class mute{
 
public:
 int x ;
 mutable int y;  // mutable variable declaration
 mute() // constructor
 {
    x=10;
    y=10;
 }
};

int main()
{
   const mute m; // constant object
   //m.x=20; // Illegal cant change the data members in a constant object  
   m.y=20; // Legal, we can change , because its a mutable
}

Volatile

volatile keyword is intended to prevent the compiler from applying certain optimizations which it might have otherwise applied because ordinarily it is assumed variables cannot change value “on their own”.

Consider this code:

int some_int = 100;
while(some_int == 100)
{
   //your code
}

When this program gets compiled, the compiler may optimize this code, if it finds that the program never ever makes any attempt to change the value of some_int, so it may be tempted to optimize the while loop by changing it from while(some_int == 100) to simply while(true) so that the execution could be fast.

However, sometimes, optimization (of some parts of your program) may be undesirable, because it may be that someone else is changing the value of some_int from outside the program which compiler is not aware of, since it can’t see it; but it’s how you’ve designed it. In that case, compiler’s optimization would not produce the desired result!

So, to ensure the desired result, you need to somehow stop the compiler from optimizing the while loop. That is where the volatile keyword plays it’s role. All you need to do is this,

volatile int some_int = 100;

xyz

Operator overloading

Done so as to use operators with user-defined types or objects.

Overloaded operators are functions with special names the keyword operator followed by the symbol for the operator being defined.

class temp
{
   private:
      int count;
   public:
        temp():count(5){  }
        void operator ++() { 
        count=count+1; 
       }
       void Display() { cout<<"Count: "<<count; }
};
int main()
{
    temp t;
    ++t;        /* operator function void operator ++() is called */
    t.Display();
    return 0;
}

NOTE

  1. Operator overloading cannot be used to change the way operator works on built-in types. Operator overloading only allows to redefine the meaning of operator for user-defined types.
  2. There are two operators assignment operator(=) and address operator(&) which does not need to be overloaded. Because these two operators are already overloaded in C++ library. For example: If obj1 and obj2 are two objects of same class then, you can use code obj1=obj2; without overloading = operator. This code will copy the contents object of obj2 to obj1.
  3. Operator overloading cannot change the precedence of operators and associativity of operators. But, if you want to change the order of evaluation, parenthesis should be used.
  4. The operators that cannot be overloaded in C++ are ::(scope resolution), .(member selection), .*(member selection through pointer to function) and ?:(ternary operator).

Inline function

If a function is inline, the compiler places a copy of the code of that function at each point where the function is called at compile time which reduces the overhead of function calling. Inline function increases efficiency but if we make large function inline then it might lead to code bloat and affect speed as well. Call infine where function size is small and is getting called quite often.

Inline is a request to the compiler. Very complicated function like Recursive function, function containing static variable, function containing return statement or loop or goto or switch statements are not made inline even if we declare them so.Also small functions which are defined inside a class (ie their code is written inside the class) are taken as inline by the compiler even if we don’t explicitly declare them so. They are called auto inline functions.xyz

Static class

There are no static class in java or c++. There are static nested classes in Java.

But a class can be simulated to behave like a static class like this:

  • Declare your class final – Prevents extension of the class since extending a static class makes no sense
  • Make the constructor private – Prevents instantiation by client code as it makes no sense to instantiate a static class
  • Make all the members and functions of the class static – Since the class cannot be instantiated no instance methods can be called or instance fields accessed.

Theory – I

abcd

xyz

Stack and the heap both are stored in the computer’s RAM. In a multi-threaded application, each thread will have its own stack. But, all the different threads will share the heap. object can be stored on the stack if an object is created inside a function without using the “new” operator.

Once a function call runs to completion, any data on the stack created specifically for that function call will automatically be deleted. Any data on the heap will remain there until it’s manually deleted by the programmer.

Dijkstra’s shortest path algorithm

Algorithm
1) Create a set sptSet (shortest path tree set) that keeps track of vertices included in shortest path tree, i.e., whose minimum distance from source is calculated and finalized. Initially, this set is empty.
2) Assign a distance value to all vertices in the input graph. Initialize all distance values as INFINITE. Assign distance value as 0 for the source vertex so that it is picked first.
3) While sptSet doesn’t include all vertices
    a) Pick a vertex u which is not there in sptSetand has minimum distance value.
    b) Include u to sptSet.
    c) Update distance value of all adjacent vertices of u. To update the distance values, iterate through all adjacent vertices. For every adjacent vertex v, if sum of distance value of u (from source) and weight of edge u-v, is less than the distance value of v, then update the distance value of v.

void dijkstra(int graph[V][V], int src)
{
     int dist[V];     
     bool sptSet[V]; 
 
     for (int i = 0; i < V; i++)
        dist[i] = INT_MAX, sptSet[i] = false;
 
     dist[src] = 0;

     for (int count = 0; count < V-1; count++)
     {
       
       int u = minDistance(dist, sptSet);
        sptSet[u] = true;
 
       for (int v = 0; v < V; v++){
         if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX 
                                       && dist[u]+graph[u][v] < dist[v])
            dist[v] = dist[u] + graph[u][v];
     }
    }
}

Prim’s Minimum Spanning Tree

Algorithm
1) Create a set mstSet that keeps track of vertices already included in MST.
2) Assign a key value to all vertices in the input graph. Initialize all key values as INFINITE. Assign key value as 0 for the first vertex so that it is picked first.
3) While mstSet doesn’t include all vertices
   a) Pick a vertex u which is not there in mstSet and has minimum key value.
   b) Include u to mstSet.
   c) Update key value of all adjacent vertices of u. To update the key values, iterate through all adjacent vertices. For every adjacent vertex v, if weight of edge u-v is less than the previous key value of v, update the key value as weight of u-v

void primMST(int graph[V][V])
{
     int parent[V];
     int key[V];  
     bool mstSet[V]; 

     for (int i = 0; i < V; i++)
        key[i] = INT_MAX, mstSet[i] = false;
 
     key[0] = 0;   
     parent[0] = -1;
     for (int count = 0; count < V-1; count++)
     {
      
        int u = minKey(key, mstSet);
         mstSet[u] = true;
        for (int v = 0; v < V; v++){
        
        // graph[u][v] is non zero only for adjacent vertices of m
        // mstSet[v] is false for vertices not yet included in MST
        // Update the key only if graph[u][v] is smaller than key[v]
        if (graph[u][v] && mstSet[v] == false && graph[u][v] <  key[v])
             parent[v]  = u, key[v] = graph[u][v];
        }
         }
}

Huffman Coding

Steps to build Huffman Tree
1. Create a leaf node for each unique character and build a min heap of all leaf nodes (Min Heap is used as a priority queue. The value of frequency field is used to compare two nodes in min heap. Initially, the least frequent character is at root)
2. Extract two nodes with the minimum frequency from the min heap.
3. Create a new internal node with frequency equal to the sum of the two nodes frequencies. Make the first extracted node as its left child and the other extracted node as its right child. Add this node to the min heap. 
4. Repeat steps#2 and #3 until the heap contains only one node. The remaining node is the root node and the tree is complete.

CODE
struct MinHeapNode* buildHuffmanTree(char data[], int freq[], int size)
{
    struct MinHeapNode *left, *right, *top;
 
    struct MinHeap* minHeap = createAndBuildMinHeap(data, freq, size);
 
    // Iterate while size of heap doesn't become 1
    while (!isSizeOne(minHeap))
    {
        left = extractMin(minHeap);
        right = extractMin(minHeap);
 
        // Create a new internal node with frequency equal to the
        // sum of the two nodes frequencies. Make the two extracted node as
        // left and right children of this new node. 
        // Add this node to the min heap
        
        top = newNode('$', left->freq + right->freq);
        top->left = left;
        top->right = right;
        insertMinHeap(minHeap, top);
    }
 
    return extractMin(minHeap);
}
 
void printCodes(struct MinHeapNode* root, int arr[], int top)
{
    if (root->left)
    {
        arr[top] = 0;
        printCodes(root->left, arr, top + 1);
    }
    if (root->right)
    {
        arr[top] = 1;
        printCodes(root->right, arr, top + 1);
    }
    if (isLeaf(root))
    {
        printf("%c: ", root->data);
        printArr(arr, top);
    }
}

Kruskal’s Minimum Spanning Tree Algorithm

Pseudocode

KRUSKAL(G):
 A = ∅
 foreach v ∈ G.V:
   MAKE-SET(v)
 foreach (u, v) ordered by weight(u, v), increasing:
    if FIND-SET(u) ≠ FIND-SET(v):
       A = A ∪ {(u, v)}
       UNION(u, v)
 return A

MAIN CODE

struct Edge
{
    int src, dest, weight;
};
 
struct Graph
{
    int V, E; 
    struct Edge* edge;
};
  
struct subset
{
    int parent;
    int rank;
};
 
int find(struct subset subsets[], int i)
{
    // find root and make root as parent of i (path compression)
    if (subsets[i].parent != i)
        subsets[i].parent = find(subsets, subsets[i].parent);
 
    return subsets[i].parent;
}
 
// (uses union by rank)
void Union(struct subset subsets[], int x, int y)
{
    int xroot = find(subsets, x);
    int yroot = find(subsets, y);
 
    if (subsets[xroot].rank < subsets[yroot].rank)
        subsets[xroot].parent = yroot;
    else if (subsets[xroot].rank > subsets[yroot].rank)
        subsets[yroot].parent = xroot;
     else
    {
        subsets[yroot].parent = xroot;
        subsets[xroot].rank++;
    }
}
 
int myComp(const void* a, const void* b)
{
    struct Edge* a1 = (struct Edge*)a;
    struct Edge* b1 = (struct Edge*)b;
    return a1->weight > b1->weight;
}
 
void KruskalMST(struct Graph* graph)
{
    int V = graph->V;
    struct Edge result[V]; 
    int e = 0;  
    int i = 0;  

    qsort(graph->edge, graph->E, sizeof(graph->edge[0]), myComp);
 
    struct subset *subsets =
        (struct subset*) malloc( V * sizeof(struct subset) );
 
    for (int v = 0; v < V; ++v)
    {
        subsets[v].parent = v;
        subsets[v].rank = 0;
    }
 
    while (e < V - 1)
    {
        
        struct Edge next_edge = graph->edge[i++];
 
        int x = find(subsets, next_edge.src);
        int y = find(subsets, next_edge.dest);
 
        if (x != y)
        {
            result[e++] = next_edge;
            Union(subsets, x, y);
        }
    }
    return;
}

Union-Find Algorithm

Detect Cycle in a an Undirected Graph

Find: Determine which subset a particular element is in. This can be used for determining if two elements are in the same subset.
Union: Join two subsets into a single subset.
        0
        |  \
        |    \
        1-----2
For each edge, make subsets using both the vertices of the edge. If both the vertices are in the same subset, a cycle is found.
Initially, all slots of parent array are initialized to -1 (means there is only one item in every subset). 
0   1   2
-1 -1  -1 
Edge 0-1: Find the subsets in which vertices 0 and 1 are. Since they are in different subsets, we take the union of them. For taking the union, either make node 0 as parent of node 1 or vice-versa. 
0   1   2     <---- 1 is made parent of 0 
                    (1 is now representative of subset {0, 1})
1  -1  -1     
Edge 1-2: 1 is in subset 1 and 2 is in subset 2. So, take union. 
0   1   2    <----- 2 is made parent of 1 
                   (2 is now representative of subset {0, 1, 2})
1   2  -1
Edge 0-2: 0 is in subset 2 and 2 is also in subset 2. Hence, including this edge forms a cycle.
How subset of 0 is same as 2?
0->1->2 // 1 is parent of 0 and 2 is parent of 1

CODE
// (uses path compression technique)
int find(struct subset subsets[], int i)
{
    if (subsets[i].parent != i)
        subsets[i].parent = find(subsets, subsets[i].parent);
 
    return subsets[i].parent;
}
 
// (uses union by rank)
void Union(struct subset subsets[], int x, int y)
{
    int xroot = find(subsets, x);
    int yroot = find(subsets, y);
 
    if (subsets[xroot].rank < subsets[yroot].rank)
        subsets[xroot].parent = yroot;
    else if (subsets[xroot].rank > subsets[yroot].rank)
        subsets[yroot].parent = xroot;
    else
    {
        subsets[yroot].parent = xroot;
        subsets[xroot].rank++;
    }
}
 
int isCycle( struct Graph* graph )
{
    int V = graph->V;
    int E = graph->E;
 
    struct subset *subsets =
        (struct subset*) malloc( V * sizeof(struct subset) );
 
    for (int v = 0; v < V; ++v)
    {
        subsets[v].parent = v;
        subsets[v].rank = 0;
    }
 
    for(int e = 0; e < E; ++e)
    {
        int x = find(subsets, graph->edge[e].src);
        int y = find(subsets, graph->edge[e].dest);
 
        if (x == y)
            return 1;
 
        Union(subsets, x, y);
    }
    return 0;
}

Remove duplicate from unsorted linked list

METHOD 1 (Using two loops)
 
struct node
{
 int data;
 struct node *next;
};
 
void removeDuplicates(struct node *start)
{
  struct node *ptr1, *ptr2, *dup;
  ptr1 = start;
 
  while(ptr1 != NULL && ptr1->next != NULL)
  {
     ptr2 = ptr1;
 
     while(ptr2->next != NULL)
     {
       
       if(ptr1->data == ptr2->next->data)
       {
          
          dup = ptr2->next;
          ptr2->next = ptr2->next->next;
          free(dup);
       }
       else 
       {
          ptr2 = ptr2->next;
       }
     }
     ptr1 = ptr1->next;
  }
}
 
Time Complexity: O(n^2)
 
METHOD 2 (Use Sorting)
In general, Merge Sort is the best suited sorting algorithm for sorting linked lists efficiently.
1) Sort the elements using Merge Sort. O(nLogn)
2) Remove duplicates in linear time using the algorithm for removing duplicates in sorted Linked List. O(n)
Please note that this method doesn’t preserve the original order of elements.
Time Complexity: O(nLogn)

METHOD 3 (Use Hashing)
void deleteDups(LinkedListNode n)
 { 
      Hashtable table = new Hashtable();
      LinkedListNode previous = null;
      while (n != null) {
          if (table.containsKey(n.data)) 
              previous.next = n.next;
                          
          else {
              table.put(n.data, true);
              previous = n;
              }
              n = n.next;
      }
 }

Time Complexity: O(n) on average (assuming that hash table access time is O(1) on average).

Find k closest elements to a given value

Runtime: O(Logn + k)

int findCrossOver(int arr[], int low, int high, int x)
{
if (arr[high] <= x)
return high;
if (arr[low] > x)
return low;

int mid = (low + high)/2;
if (arr[mid] <= x && arr[mid+1] > x)
return mid;

if(arr[mid] < x)
return findCrossOver(arr, mid+1, high, x);
return findCrossOver(arr, low, mid - 1, x);
}

void printKclosest(int arr[], int x, int k, int n)
{
int l = findCrossOver(arr, 0, n-1, x);
int r = l+1; // Right index to search
int count = 0; 

if (arr[l] == x) l--; // Assumption: all elements in arr[] are distinct

while (l >= 0 && r < n && count < k)
{
if (x - arr[l] < arr[r] - x)
printf("%d ", arr[l--]);
else
printf("%d ", arr[r++]);
count++;
}

while (count < k && l >= 0)
printf("%d ", arr[l--]), count++;

while (count < k && r < n)
printf("%d ", arr[r++]), count++;
}