Data Structure Interview Questions and Answers

1. What is a data structure?

A data structure is a way of organizing and storing data to perform operations efficiently. It defines the relationship between the data and the operations that can be performed on the data.

2. Explain the difference between an array and a linked list.

An array stores elements in contiguous memory locations, allowing random access, while a linked list uses nodes with pointers to represent a sequence of elements, supporting efficient insertions and deletions.

3. What are Data Structures?

A data structure is a mechanical or logical way that data is organized within a program. The organization of data is what determines how a program performs. There are many types of data structures, each with its own uses. When designing code, we need to pay particular attention to the way data is structured. If data isn't stored efficiently or correctly structured, then the overall performance of the code will be reduced.

4. Why Create Data Structures?

Data structures serve a number of important functions in a program. They ensure that each line of code performs its function correctly and efficiently, they help the programmer identify and fix problems with his/her code, and they help to create a clear and organized code base.

5. Explain the process behind storing a variable in memory.

• A variable is stored in memory based on the amount of memory that is needed. Following are the steps followed to store a variable:
  • The required amount of memory is assigned first.
  • Then, it is stored based on the data structure being used.
• Using concepts like dynamic allocation ensures high efficiency and that the storage units can be accessed based on requirements in real-time.

6. Can you explain the difference between file structure and storage structure?

• File Structure: Representation of data into secondary or auxiliary memory say any device such as a hard disk or pen drives that stores data which remains intact until manually deleted is known as a file structure representation.
• Storage Structure: In this type, data is stored in the main memory i.e RAM, and is deleted once the function that uses this data gets completely executed.

The difference is that the storage structure has data stored in the memory of the computer system, whereas the file structure has the data stored in the auxiliary memory.

7. What are different operations available in stack data structure?

Some of the main operations provided in the stack data structure are: 

• push: This adds an item to the top of the stack. The overflow condition occurs if the stack is full.
• pop: This removes the top item of the stack. Underflow condition occurs if the stack is empty.
• top: This returns the top item from the stack.
• isEmpty: This returns true if the stack is empty else false.
• size:  This returns the size of the stack.

8. What are different operations available in queue data structure?

• enqueue: This adds an element to the rear end of the queue.  Overflow conditions occur if the queue is full.
• dequeue: This removes an element from the front end of the queue. Underflow conditions occur if the queue is empty.
• isEmpty: This returns true if the queue is empty or else false.
• rear: This returns the rear end element without removing it.
• front: This returns the front-end element without removing it.
• size: This returns the size of the queue.

9. How to implement a queue using stack?

A queue can be implemented using two stacks. Let q be the queue andstack1 and stack2 be the 2 stacks for implementing q. We know that stack supports push, pop, and peek operations and using these operations, we need to emulate the operations of the queue - enqueue and dequeue. Hence, queue q can be implemented in two methods (Both the methods use auxillary space complexity of O(n)):

1. By making enqueue operation costly:

• Here, the oldest element is always at the top of stack1 which ensures dequeue operation occurs in O(1) time complexity.
• To place the element at top of stack1, stack2 is used.
• Pseudocode:
  • Enqueue: Here time complexity will be O(n)

enqueue(q, data):  While stack1 is not empty:     Push everything from stack1 to stack2.      Push data to stack1      Push everything back to stack1.

• Dequeue: Here time complexity will be O(1)

deQueue(q): If stack1 is empty then error  else Pop an item from stack1 and return it

2. By making the dequeue operation costly:

• Here, for enqueue operation, the new element is pushed at the top of stack1. Here, the enqueue operation time complexity is O(1).
• In dequeue, if stack2 is empty, all elements from stack1 are moved to stack2 and top of stack2 is the result. Basically, reversing the list by pushing to a stack and returning the first enqueued element. This operation of pushing all elements to a new stack takes O(n) complexity.
• Pseudocode:
  • Enqueue: Time complexity: O(1)

enqueue(q, data):    Push data to stack1

• Dequeue: Time complexity: O(n)

dequeue(q): If both stacks are empty then raise error.If stack2 is empty:  While stack1 is not empty: push everything from stack1 to stack2.   Pop the element from stack2 and return it.

10. How do you implement stack using queues?

• A stack can be implemented using two queues. We know that a queue supports enqueue and dequeue operations. Using these operations, we need to develop push, pop operations.
• Let stack be ‘s’ and queues used to implement be ‘q1’ and ‘q2’. Then, stack ‘s’ can be implemented in two ways:

1. By making push operation costly:

• This method ensures that the newly entered element is always at the front of ‘q1’ so that pop operation just dequeues from ‘q1’.
• ‘q2’ is used as auxillary queue to put every new element in front of ‘q1’ while ensuring pop happens in O(1) complexity.
• Pseudocode:
  • Push element to stack s: Here push takes O(n) time complexity.

push(s, data):    Enqueue data to q2    Dequeue elements one by one from q1 and enqueue to q2.    Swap the names of q1 and q2

• Pop element from stack s: Takes O(1) time complexity.

pop(s):dequeue from q1 and return it.

2. By making pop operation costly:

• In push operation, the element is enqueued to q1.
• In pop operation, all the elements from q1 except the last remaining element, are pushed to q2 if it is empty. That last element remaining of q1 is dequeued and returned.
• Pseudocode:
  • Push element to stack s: Here push takes O(1) time complexity.

push(s,data):Enqueue data to q1

• Pop element from stack s: Takes O(n) time complexity.

pop(s): \tStep1: Dequeue every elements except the last element from q1 and enqueue to q2.\tStep2: Dequeue the last item of q1, the dequeued item is stored in result variable. \tStep3: Swap the names of q1 and q2 (for getting updated data after dequeue)  \tStep4: Return the result.

11. What is an asymptotic analysis of an algorithm?

Asymptotic analysis of an algorithm defines the run-time performance as per its mathematical boundations. Asymptotic analysis helps us articulate the best case(Omega Notation, Ω), average case(Theta Notation, θ), and worst case(Big Oh Notation, Ο) performance of an algorithm.

12. What is hashmap in data structure?

Hashmap is a data structure that uses an implementation of a hash table data structure which allows access to data in constant time (O(1)) complexity if you have the key.

13. What is the requirement for an object to be used as key or value in HashMap?

• The key or value object that gets used in the hashmap must implement equals() and hashcode() method.
• The hash code is used when inserting the key object into the map and the equals method is used when trying to retrieve a value from the map.

14. How does HashMap handle collisions in Java?

• The java.util.HashMap class in Java uses the approach of chaining to handle collisions. In chaining, if the new values with the same key are attempted to be pushed, then these values are stored in a linked list stored in a bucket of the key as a chain along with the existing value.
• In the worst-case scenario, it can happen that all keys might have the same hashcode, which will result in the hash table turning into a linked list. In this case, searching a value will take O(n) complexity as opposed to O(1) time due to the nature of the linked list. Hence, care has to be taken while selecting hashing algorithm.

15. What is the time complexity of basic operations get() and put() in HashMap class?

The time complexity is O(1) assuming that the hash function used in the hash map distributes elements uniformly among the buckets.

16. What are some key operations performed on the Deque data structure?

Following are the key operations available deque:

• insertFront(): This adds an element to the front of the Deque.
• insertLast(): This adds an element to the rear of the Deque.
• deleteFront(): This deletes an element from the front of the Deque.
• deleteLast():This deletes an element from the front of the Deque.
• getFront(): This gets an element from the front of the Deque. 
• getRear(): This gets an element from the rear of the Deque. 
• isEmpty(): This checks whether Deque is empty or not.
• isFull(): This checks whether Deque is full or not.

17. Compare different implementations of priority queue

The following table contains an asymptotic analysis of different implementations of a priority queue:

18. What is a heap data structure?

Heap is a special tree-based non-linear data structure in which the tree is a complete binary tree. A binary tree is said to be complete if all levels are completely filled except possibly the last level and the last level has all elements as left as possible. Heaps are of two types:

• Max-Heap:
  • In a Max-Heap the data element present at the root node must be the greatest among all the data elements present in the tree.
  • This property should be recursively true for all sub-trees of that binary tree.
• Min-Heap:
  • In a Min-Heap the data element present at the root node must be the smallest (or minimum) among all the data elements present in the tree.
  • This property should be recursively true for all sub-trees of that binary tree.

19. Write a program to remove duplicates from a sorted array in place?

• Input: {1, 1, 1, 2, 3, 3, 6, 6, 7}
• Output: {1, 2, 3, 6, 7}
• Explanation: The given input has only 1,2,3,6, and 7 as unique elements, hence the output only lists them out.

#include <bits/stdc++.h>using namespace std;class Solution{public:    //function that takes an array and its size as arguments    int removeDuplicates(int a[],int n){        int index=0;        for(int i=1;i<n;i++) {                    if(a[i]!=a[index]) { //change index                index++; //swap next line                a[index]=a[i];             }           }          return index+1;    }};int main(){    int T;    //taking the number of test cases from user    cin>>T;    //running the loop for all test cases    while(T--)    {        int N;        //taking size input from user        cin>>N;        int a[N];        //taking array input from user        for(int i=0;i<N;i++)        {            cin>>a[i];        }        Solution ob;        //calling the removeDuplicates in the Solution class        int n = ob.removeDuplicates(a,N);        //printing the array after removing duplicates        for(int i=0;i<n;i++)            cout<<a[i]<<" ";            cout<<endl;        }}

• Time Complexity: O(n)
• Space Complexity: O(1)

20. Write a function for zigzag traversal in a binary tree

• Input: 
• Output: [1, 3, 2, 4, 5, 6, 8, 7]
• Explanation: Zigzag Traversal first iterates the given level of the tree from left to right and then the next level as the right to the level.

// Tree Nodestruct Node {    int data;    Node* left;    Node* right;};//Function to store the zigzag order traversal of a tree in a list.    vector <int> zigZagTraversal(Node* root)    {     //creating two stacks for level traversals in both order    \tstack<Node*> st1;    \tstack<Node*> st2;     //vector to store the zigzag traversal    \tvector<int> result;    \t     //Initialize the first stack with the root element    \tst1.push(root);    \t     //Iterate until either of the stack is not empty    \twhile(!st1.empty() || !st2.empty()){        //iterate until the first stack is not empty    \t    while(!st1.empty()){    \t        Node* temp=st1.top();    \t        st1.pop();    \t        result.push_back(temp->data);    \t            \t        if(temp->left)    \t            st2.push(temp->left);    \t        if(temp->right)    \t            st2.push(temp->right);    \t    }         //Iterate until the second stack is not empty    \t    while(!st2.empty()){    \t        Node* temp=st2.top();    \t        st2.pop();    \t        result.push_back(temp->data);    \t            \t        if(temp->right)    \t            st1.push(temp->right);    \t        if(temp->left)    \t            st1.push(temp->left);    \t            \t    }    \t}    \treturn result;    }

• Time Complexity: O(n)
• Space Complexity: O(n)

21. Write a function to sort a linked list of 0s, 1s and 2s

• Input: 0->1->0->2->1->0->2->1
• Output: 0->0->0->1->1->1->2->2
• Explanation: All 0’s will come first then 1s and then 2s. This can be done in O(n) time by counting the occurrences of all three and rearranging them in the linked list.

//structure of the linked liststruct Node {   int data;   Node *left;   Node *right;}//function take the head of the linked list as a parametervoid sortList(Node *head){   //if linked list is empty then return back    if(head==NULL)       return;   else   {       Node *temp=head;       Node *temp1=head;       //to store count of 0s, 1s, and 2s       int count0=0,count1=0,count2=0;       //calculating the count of 0s, 1s, and 2s       while(temp!=NULL)       {           if(temp->data==0)               count0++;           else if(temp->data==1)               count1++;           else               count2++;           temp=temp->next;       }       //iterating over count of 0s and filling the linked list       while(count0!=0)       {           temp1->data=0;           temp1=temp1->next;           count0--;       }     //iterating over count of 1s and filling the linked list       while(count1!=0)       {           temp1->data=1;           temp1=temp1->next;           count1--;       }        //iterating over count of 2s and filling the linked list       while(count2!=0)       {           temp1->data=2;           temp1=temp1->next;           count2--;       }   }}

• Time Complexity: O(n)
• Space Complexity: O(1)

22. Write a function to detect cycle in an undirected graph

• Input: n = 4, e = 4 , 0 1, 1 2, 2 3, 3 1
• Output: Yes
• Explanation: The graph is represented as follows in adjacency list representation:
  0->1
  1->2
  2->3
  3->1

From the above representation, we can see that there exists a cycle: 1→2→3→1

//function to run dfs for a given node in the graph  int dfs(int v,vector<int> adj[],vector<int> &visited,vector<int> &rec,int i,int parent){        int ans=0;        visited[i]=1;        rec[i]=1;        for(auto x : adj[i]){             if(x!=parent) {                if(rec[x])                     return 1;                ans=dfs(v,adj,visited,rec,x,i);                if(ans)                    return 1;            }        }        rec[i]=0;        return 0;    }    // Function to detect cycle in an undirected graph.    // it takes adjacency list representation as an argument    bool isCycle(int v, vector<int> adj[]) {        vector<int> visited(v,0),rec(v,0);        int ans=0;        for(int i=0;i<v;i++){            if(visited[i]==0)                 ans=dfs(v,adj,visited,rec,i,-1);            if(ans)                 return 1;        }        return 0;    }

• Time Complexity: O(V+E)
• Space Complexity: O(V)

23. Write a function to convert an infix expression to postfix expression

• Input: a+b*(c^d)
• Output: abcd^*+

int prec(char c){    if (c == '^')        return 3;    else if (c == '/' || c == '*')        return 2;    else if (c == '+' || c == '-')        return 1;    else        return -1;}  public:    // Function to convert an infix expression to a postfix expression.    string infixToPostfix(string s) {        stack<char> st; // For stack operations, we are using C++ built in stack        string result;         for (int i = 0; i < s.length(); i++) {            char c = s[i];             // If the scanned character is            // an operand, add it to the output string.            if ((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z')            || (c >= '0' && c <= '9'))                result += c;             // If the scanned character is an            // '(', push it to the stack.            else if (c == '(')                st.push('(');             // If the scanned character is an ')',            // pop and to output string from the stack            // until an '(' is encountered.            else if (c == ')') {                while (st.top() != '(') {                    result += st.top();                    st.pop();                }                st.pop();            }             // If an operator is scanned            else {                while (!st.empty()                   && prec(s[i]) <= prec(st.top())) {                    if (c == '^' && st.top() == '^')                        break;                    else {                        result += st.top();                        st.pop();                    }                }                st.push(c);            }        }         // Pop all the remaining elements from the stack        while (!st.empty()) {            result += st.top();            st.pop();        }         return result;    }

• Time Complexity: O(n)
• Space Complexity: O(n)

24. Write a function to find the maximum for each and every contiguous subarray of size k.

• Input: N = 9, K = 3 arr[] = {1, 2, 3, 1, 4, 5, 2, 3, 6}
• Output: {3, 3, 4, 5, 5, 5, 6}
• Explanation: In the first subarray of size 3: {1,2,3}, the value 3 is maximum, similarly for all such subarrays for size 3.

//function to find maximum in each subarray using sliding window approachvector<int> max_of_subarrays(vector<int> arr, int n, int k){        int i=0,j=0;        deque<int> dq;        dq.push_front(i++);        while(i<k)        {            while(!dq.empty()&&arr[dq.back()]<=arr[i])            dq.pop_back();            dq.push_back(i++);        }        vector<int> ans;        while(i<n)        {            ans.push_back(arr[dq.front()]);            while(!dq.empty()&&j>=dq.front())            {                dq.pop_front();                            }            j++;             while(!dq.empty()&&arr[dq.back()]<=arr[i])            dq.pop_back();            dq.push_back(i++);        }        ans.push_back(arr[dq.front()]);        return ans;        }

• Time Complexity: O(n)
• Space Complexity: O(k)

25. Write a function to merge two sorted binary search tree

Input:

First BST 

       7

    /     \\

   5       9

Second BST

    4

  /   \\

3       12

Output: 3 4 5 6 7 9 12

//Function to return a list of integers denoting the node //values of both the BST in a sorted order.    void inorder(Node*root,vector<int>&v){        if(root==NULL)            return;        inorder(root->left,v);        v.push_back(root->data);        inorder(root->right,v);    }    vector<int> merge(vector<int>v1,vector<int>v2){        vector<int>v;        int n1=v1.size(),n2=v2.size(),i=0,j=0;        while(i<n1&&j<n2){            if(v1[i]>v2[j]){                v.push_back(v2[j]);                j++;            }            else{                v.push_back(v1[i]);                i++;            }        }        while(i<n1){            v.push_back(v1[i]);            i++;        }        while(j<n2){            v.push_back(v2[j]);            j++;        }        return v;    }    vector<int> merge(Node *root1, Node *root2)    {       vector<int>v1,v2;       inorder(root1,v1);       inorder(root2,v2);       return merge(v1,v2);    }

• Time Complexity: O(m+n) 
• Space Complexity: O(height of the first tree + height of the second tree)

26. Write a function to print all unique rows of the given matrix.

Input:

     {{1, 1, 1, 0, 0},

      {0, 1, 0, 0, 1},

      {1, 0, 1, 1, 0},

      {0, 1, 0, 0, 1},

      {1, 1, 1, 0, 0}}

Output:

    {{1, 1, 1, 0, 0},

     {0, 1, 0, 0, 1},

     {1, 0, 1, 1, 0}}

vector<vector<int>> uniqueRow(int M[MAX][MAX],int row,int col){set<vector<int>> st;vector<vector<int>> v;for(int i=0; i<row; i++) {    vector<int> v1;    for(int j=0; j<col; j++) {        v1.push_back(M[i][j]);    }    if(st.count(v1) == 0) {         v.push_back(v1);         st.insert(v1);    }}return v;}

• Time Complexity: O( ROW x COL )
• Space Complexity: O( ROW )

27. Write a function to find number of subarrays with product less than K

• Input: arr = [1, 6, 2, 3, 2, 1], k = 12
• Output: 11

int numSubarrayProductLessThanK(vector<int>& nums, int k) {        int ans=0;        int pdt=1;        int left=0,right=0;        while(right<=nums.size()-1){                        pdt*=nums[right];            while(pdt>=k and left<nums.size()){                pdt/=nums[left];                left++;                            }            if(right-left>=0)            ans+=right-left+1;//since on adding a new element new subarrays formed is r-i+1;            right++;                    }        return ans;    }

• Time Complexity: O(n)
• Space Complexity: O(1)

28. Find the subsequence of length 3 with the highest product from a sequence of non-negative integers, with the elements in increasing order.

• Input: n = 8 arr[ ] = {6, 7, 10, 1, 2, 3, 11, 12}
• Output: {10, 11, 12}

The three increasing elements of the given arrays are 10, 11, and 12, which form a three-size subsequence with the highest product.

 vector<int> maxProductSubsequence(int *a , int n)     {         set<int> s;        long long largestOnLeft[n];        for(int i=0;i<n;i++)        {               s.insert(a[i]);            auto it=s.lower_bound(a[i]);            if(it==s.begin())            {                largestOnLeft[i]=-1;                continue;            }            it--;            largestOnLeft[i]=*it;        }        int m=0;        long long p=INT_MIN;        vector<int> result(3);        result[0]=-1;        for(int i=n-1;i>=0;i--)        {             if(a[i]>=m){          m=a[i];}          else          {              if(largestOnLeft[i] !=-1)              {                  if(largestOnLeft[i]*a[i]*m >p)                  {                      p=largestOnLeft[i]*a[i]*m;                      result[0]=largestOnLeft[i];                      result[1]=a[i];                      result[2]=m;                  }              }          }        }        return v;    }

• Time Complexity: O(nlog(n))
• Space Complexity: O(n)

29. Write a function to implement Quicksort on Doubly Linked List

• Input: 8<->10<->1<->7<->6
• Output: 1<->6<->7<->8<->10

class Solution{public:    Node* partition(Node *l, Node *h){        //Your code goes here        Node*temp = h;        Node*tt = l;        Node*first = l;                while(tt != h){              if(tt->data <= temp->data){                  swap(first->data, tt->data);                  first = first->next;              }              tt = tt -> next;        }        swap(first-> data, h->data);        return first;        }};void _quickSort(struct Node* l, struct Node *h){    if (h != NULL && l != h && l != h->next)    {        Solution ob;        struct Node *p = ob.partition(l, h);        _quickSort(l, p->prev);        _quickSort(p->next, h);    }} void quickSort(struct Node *head){    struct Node *h = lastNode(head);    _quickSort(head, h);}

• Time Complexity: O(n^2) in the worst case when the list is already sorted. O(nlog(n)) in the best and average case.
• Space Complexity: O(n)

30. Write a function to connect nodes at the same level of a binary tree

Input:              100    

                        /     \\                

                   13      15   

                   /  \\         \\       

              14    1        20 

Output:          100-> NULL    

                        /      \\                

                  13   ->  15   -> NULL

                  /      \\           \\       

               14  ->  1   -> 20 -> NULL

class Solution{    public:    //Function to connect nodes at the same level.    void connect(Node *p)    {       map<int,vector<Node *> > m;       queue<Node *> q;       queue<int> l;       q.push(p);       l.push(0);       while(!q.empty())       {           Node *temp=q.front();           int level=l.front();           q.pop();           l.pop();           m[level].push_back(temp);           if(temp->left!=NULL)           {               q.push(temp->left);               l.push(level+1);           }           if(temp->right!=NULL)           {               q.push(temp->right);               l.push(level+1);           }       }       for(map<int,vector<Node *> > ::iterator it=m.begin();it!=m.end();it++)       {           vector<Node *> temp1=it->second;           for(int i=0;i<temp1.size()-1;i++)           {               temp1[i]->nextRight=temp1[i+1];           }           temp1[temp1.size()-1]->nextRight=NULL;       }    }};

• Time Complexity: O(n)
• Space Complexity: O(n)

31. Write a function to find number of structurally unique binary trees are possible

Input: N = 3 

Output: 5 for N = 3, there are 5 possible BSTs:

1           3      3        2 1

   \\         /      /          /  \\   \\

     3     2      1      1    3     2

   /      /          \\                     \\

2      1         2                       3

class Solution{    public:     //function to calculate binomial coefficient C(n,k)    long long int binomialCoefficient(long long int n, long long int k)    {        long long int res = 1;        if (k > n - k)            k = n - k;            for (long long int i = 0; i < k; ++i)        {            res *= (n - i);            res /= (i + 1);        }             return res;    }        //function to calculate Nth Catalan Number      long long int catalanNumber(long long in n)    {        // Calculate value of 2nCn        long long int C = binomialCoefficient(2*n, n);            // return 2nCn/(n+1)        return C/(n+1);    }        //Function to return the total number of possible unique BST.     long long int numOfUniqueBinarySearchTrees(int n)     {         // find nth catalan number        long long int countOfUniqueBinarySearchTrees = catalanNumber(n);             // return nth catalan number        return countOfUniqueBinarySearchTrees;    }};

• Time Complexity: O(n) 
• Space Complexity: O(1)

32. Implement LRU(Least Recently Used) Cache

class LRUCache{    private:    class node_t {        public:        int key;        int value;        node_t * next;        node_t * prev;    };        int cap;    node_t head;    unordered_map<int, node_t*> tbl;        void remove_node(node_t * node) {        node->next->prev = node->prev;        node->prev->next = node->next;    }    void add_node(node_t * node) {        node->next = head.next;        node->prev = &head;        head.next = node;        node->next->prev = node;    }    public:    //Constructor for initializing the cache capacity with the given value.    LRUCache(int cap): cap(cap)    {        // code here        head.prev = &head;        head.next = &head;    }        //Function to return value corresponding to the key.    int get(int key)    {        // your code here        unordered_map<int, node_t*>::iterator it = tbl.find(key);        if(it==tbl.end())            return -1;        remove_node(it->second);        add_node(it->second);        return it->second->value;    }        //Function for storing key-value pair.    void set(int key, int value)    {        // your code here           unordered_map<int, node_t*>::iterator it = tbl.find(key);        if(it!=tbl.end())        {            remove_node(it->second);            add_node(it->second);            it->second->value = value;        }        else {            node_t * node = new node_t;            node->key = key;            node->value = value;            add_node(node);            tbl[key] = node;            if(tbl.size()>cap) {                auto * old_node = head.prev;                tbl.erase(old_node->key);                remove_node(old_node);                delete old_node;            }        }    }};

• Time Complexity: O(1) to get an element
• Space Complexity: O(n)

33. Write a function to determine whether duplicate elements in a given array are within a given distance of each other.

• Input: arr[] = {1, 2, 3, 4, 2, 1, 2} range=3
• Output: True

class Solution {    public:        bool checkDuplicatesWithinRange(vector<int> arr, int range)    {        // Creating an empty hashset        unordered_set<int> myset;             // Traversing the input array        for (int i = 0; i < arr.size(); i++)        {            // If already present in hashset, then we found a duplicate within range distance            if (myset.find(arr[i]) != myset.end())                return true;                 // Add this item to hashset            myset.insert(arr[i]);                 // Remove the range+1 distant item from the hashset            if (i >= range)                myset.erase(arr[i-range]);        }        return false;    }};

• Time Complexity: O(n)
• Space Complexity: O(n)

34. Write a recursive function to calculate the height of a binary tree in Java.

• Consider that every node of a tree represents a class called Node as given below:

public class Node{     int data;     Node left;     Node right; }

• Then the height of the binary tree can be found as follows:

     int heightOfBinaryTree(Node node)       {          if (node == null)              return 0; // If node is null then height is 0 for that node.         else          {              // compute the height of each subtree             int leftHeight = heightOfBinaryTree(node.left);              int rightHeight = heightOfBinaryTree(node.right);                  //use the larger among the left and right height and plus 1 (for the root)             return Math.max(leftHeight, rightHeight) + 1;          }      }

35. Write Java code to count number of nodes in a binary tree

int countNodes(Node root){    int count =  1;             //Root itself should be counted    if (root ==null)        return 0;    else    {        count += countNodes(root.left);        count += countNodes(root.right);        return count;    }}

36. Print Left view of any binary trees.

• The main idea to solve this problem is to traverse the tree in pre order manner and pass the level information along with it. If the level is visited for the first time, then we store the information of the current node and the current level in the hashmap. Basically, we are getting the left view by noting the first node of every level.
• At the end of traversal, we can get the solution by just traversing the map.
• Consider the following tree as example for finding the left view:
• Left view of a binary tree in Java:

 import java.util.HashMap;  //to store a Binary Tree node  class Node  {      int data;      Node left = null, right = null;      Node(int data) {          this.data = data;      }  }  public class InterviewBit  {      // traverse nodes in pre-order way      public static void leftViewUtil(Node root, int level, HashMap<Integer, Integer> map)      {          if (root == null) {              return;          }          // if you are visiting the level for the first time          // insert the current node and level info to the map          if (!map.containsKey(level)) {              map.put(level, root.data);          }          leftViewUtil(root.left, level + 1, map);          leftViewUtil(root.right, level + 1, map);      }      // to print left view of binary tree      public static void leftView(Node root)      {          // create an empty HashMap to store first node of each level          HashMap<Integer, Integer> map = new HashMap<>();          // traverse the tree and find out the first nodes of each level          leftViewUtil(root, 1, map);          // iterate through the HashMap and print the left view          for (int i = 0; i <map.size(); i++) {              System.out.print(map.get(i) + " ");          }      }      public static void main(String[] args)      {          Node root = new Node(4);          root.left = new Node(2);          root.right = new Node(6);          root.left.left = new Node(1);          root.left.left = new Node(3);          root.right.left = new Node(5);          root.right.right = new Node(7);          root.right.left.left = new Node(9);          leftView(root);      }  }

37. Given an m x n 2D grid map of '1’s which represents land and '0’s that represents water return the number of islands (surrounded by water and formed by connecting adjacent lands in 2 directions - vertically or horizontally).

Constraints are:

38. m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j] can only be ‘0’ or ‘1’.

Example:

39. Input: grid = [
[“1” , “1” , “1” , “0” , “0”],
[“1” , “1” , “0” , “0” , “0”],
[“0” , “0” , “1” , “0” , “1”],
[“0” , “0” , “0” , “1” , “1”]
]

class InterviewBit {    public int numberOfIslands(char[][] grid) {        if(grid==null || grid.length==0||grid[0].length==0)            return 0;        int m = grid.length;        int n = grid[0].length;        int count=0;        for(int i=0; i<m; i++){            for(int j=0; j<n; j++){                if(grid[i][j]=='1'){                    count++;                    mergeIslands(grid, i, j);                }            }        }        return count;    }    public void mergeIslands(char[][] grid, int i, int j){        int m=grid.length;        int n=grid[0].length;        if(i<0||i>=m||j<0||j>=n||grid[i][j]!='1')            return;        grid[i][j]='X';        mergeIslands(grid, i-1, j);        mergeIslands(grid, i+1, j);        mergeIslands(grid, i, j-1);        mergeIslands(grid, i, j+1);    }}