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 realtime.
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 frontend 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 fromstack1
are moved tostack2
and top ofstack2
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 runtime 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()
andhashcode()
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 worstcase 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:
Operations  peek  insert  delete 

Linked List  O(1)  O(n)  O(1) 
Binary Heap  O(1)  O(log n)  O(log n) 
Binary Search Tree  O(1)  O(log n)  O(log n) 
18. What is a heap data structure?
Heap is a special treebased nonlinear 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:

MaxHeap:
 In a MaxHeap 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 subtrees of that binary tree.

MinHeap:
 In a MinHeap 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 subtrees 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(rightleft>=0) ans+=rightleft+1;//since on adding a new element new subarrays formed is ri+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 nonnegative 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 threesize 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=n1;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 keyvalue 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[irange]); } 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 preorder 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==0grid[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<0i>=mj<0j>=ngrid[i][j]!='1') return; grid[i][j]='X'; mergeIslands(grid, i1, j); mergeIslands(grid, i+1, j); mergeIslands(grid, i, j1); mergeIslands(grid, i, j+1); }}