Project 1

Arrays

1.EQUILIBRIUM POINT

Given an array A of N positive numbers. The task is to find the position where equilibrium first occurs in the array. Equilibrium position in an array is a position such that the sum of elements before it is equal to the sum of elements after it. Complete the function whose argument is the array A and which prints the position at which the elements are at equilibrium if no equilibrium point exists print -1.

Constraints:
1 <= N <= 106
1 <= Ai <= 108

Explination:

2.LEADERS IN AN ARRAY

Given an array of positive integers. Your task is to find the leaders in the array. An element of array is leader if it is greater than or equal to all the elements to its right side. Also, the rightmost element is always a leader. Complete the function which takes the elements of the array and prints all the leaders.

Constraints:
1 <= N <= 107
0 <=

Explination : In the brute force approach, we can have nested for loops. The outer loop starts picking element from 0 while inner loop picks from 1. We compare the two elements and check if the left element is lesser or greater than right. if it is lesser then we break the inner loop and move on to the next element in the outer loop. But if it is greater we keep moving the inner loop to the next element. Once the inner loop reaches the length of the array it means the loop has not broken anywhere. This means the element on the left is greater than or equal to all of its elements on the right. Thus we print it. We then move on to the next element of the outer loop and do the same thing. This approach has a time complexity of O(n^2). i am uploaded the program file.

String

3.REVERSE WORDS IN A GIVEN STRING

Given a String of length S, reverse the whole string without reversing the individual words in it. Words are separated by dots. Complete the function which takes a string S containing characters and outputs a single line containing the reversed String.
Constraints:
1 <= T <= 100
1 <= |S| <= 2000

Explination : In this problem we can use the string method of "split" and regex (regular expressions) to easily split the string at the dot ( ) and store indivual words in an array. Then we loop through the array in reverse to print the words in reverse order. The time complexity would be O(n) where n is the number of words in the array. i am uploaded the program file.

4.REMOVE DUPLICATES

Given a string, the task is to remove duplicates from it. Expected time complexity O(n) where n is length of input string and extra space O(1) under the assumption that there are total 256 possible characters in a string. Original order of characters must be kept same. Complete the function that takes a string and prints the modified string without duplicates and same order of characters.

Constraints:
1 <= |string|<= 1000

Explination: The idea is to keep track of visited characters from given input string through an integer array of size 256 Create an integer array of size 256 in order to keep track of all possible characters. Iterate over the input string, and for each character Lookup into the array with the ASCII value of character as index If value at index is 0, then copy the character into original input array and increase the endIndex also update the value at index as -1. Else skip the character. i am uploaded the program file.

LinkedList

5.FINDING MIDDLE ELEMENT IN A LINKED LIST

Given a singly linked list of N nodes. The task is to find the middle of the linked list. For example, if given linked list is 1->2->3->4->5 then the output should be 3. If there are even nodes, then there would be two middle nodes, we need to print the
second middle element. For example, if given linked list is 1 ->2->3->4->5->6 then the output should beThe task is to complete the function getMiddle() which takes the list reference and returns data of the middle element of the linked list.

Expected Time Complexity: O(N).
Expected Space Complexity: O(1).

Constraints:
1 <= T <= 500
1 <= N <= 5000

Explination:

There are different approaches to finding the middle of a linked list. First one is to traverse through the linked list and find the length by incrementing it for each node until we reach null. And then we get the middle by diving the length obtained by 2. Next, we traverse the linked list again till we reach the middle and then print the middle node. This takes O(n) time complexity. Another method is by using two pointers. We keep both pointers at the head first and then we move the fast pointer by 2 while moving the slow pointer by 1 through the linked list. So the logic is that, when the fast pointer reaches the end of the linked list the slow pointer would've reached the middle. This method also has a time complexity of O(n). i am uploaded the program file.

6.REVERSE A LINKED LIST

Given a linked list of N nodes. The task is to reverse this list.

Example if linkedlist is Explanation: After reversing the list, elements are.

The task is to complete the function reverseList(givenList) with givenList reference and returns the list after reversing it.

Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).

Constraints:
1 <= N <= 104

Explination : In the problem, we reverse the linked list by first initialising 3 pointers prev, current and next. prev and next are set to null while current is set to head. Then we iterate through the linked list and first store the current.next in the next before chanding it then we change the current.next to prev and then move prev and current by one step each. We do this until current becomes null and when it does, then we set the prev to head and return head. i am uploaded the program file.

7.PAIRWISE SWAP ELEMENTS OF A LINKED LIST

Given a singly linked list of size N. The task is to swap elements in the linked list pairwise. For example, if the input list is 1 2 3 4, the resulting list after swaps will be 2 1 4 3.

Complete the function pairWiseSwap() which takes the the linked list and retu rns the modified linked list after swapping pairwise nodes.

Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).

Constraints:
1 <= N <= 103

Explination : in this problem need to implement parwise swap elements in linked list using this concept We start from the head node and traverse the list. While traversing we swap data of each node with its next node’s data. i am uploaded the program file.

8.ADD TWO NUMBERS REPRESENTED BY LINKED LISTS

Given two numbers represented by two linked lists of size N and M. The task is to return a sum list. The sum list is a linked list representation of the addition of two input numbers.

Complete the function addTwoLists() which takes both the linked lists and returns the new list.

Expected Time Complexity: O(N) + O(M)
Expected Auxiliary Space: O(N) + O(M)

Constraints:
1 <= N, M <= 5000

Explination : in this problem add two numbers represented by linked lists here is the approaches First reverse both the linked lists. Then call the addTwoLists() method on the reversed lista. Traverse the two linked lists from start to end Add the two digits each from respective linked lists. If one of the lists has reached the end then take 0 as its digit. Continue it until both the end of the lists. If the sum of two digits is greater than 9 then set carry as 1 and the current digit as sum % 10 Finally we reverse the output list back default order. i am uploaded the program file.

9.BINARY TREE TO DLL

Given a Binary Tree (BT), convert it to a Doubly Linked List(DLL) In -Place. The left and right references in nodes are to be used as previous and next references respectively in converted DLL. The order of nodes in DLL must be same as Inorder of the given Binary Tree. The first node of Inorder traversal (leftmost node in BT) must be the head node of the DLL.

Complete the function bToDLL() that takes root node of the tree as a parameter and returns the head of DLL .

Expected Time Complexity: O(N).
Expected Space Complexity : O(H). H is the height of the tree and this space is used implicitly for recursion stack.

Explination : binary to dll is the problem to find. i am using the order traversal of the binary tree and while doing so, keep track of the previously visited node in a variable prev. For every visited node, make it next to the prev and previous of this node as prev. i am uploaded the program file.

10.BELLMAN FORD ALGORITHM

Implement the Bellman Ford Algorithm to find Shortest paths to all vertices from a single source.

Given a graph and a source vertex src in graph, find shortest paths from src to all vertices in the given graph. The graph may contain negative weight edges.

If there is a negative weight cycle then print -1

Expected Time Complexity- O(VE)

Constraints:
1 <= Number of nodes <= 1000
1 <= Data of a node <= 1000

Explination : Bellman-Ford algorithm is used to find shortest distance to all vertices when there are negative weights in a graph. We have already discussed Dijkstra’s algorithm, which is a Greedy algorithm. Dijkstra doesn’t work for Graphs with negative weight edges, Bellman-Ford works for such graphs. Bellman-Ford is also simpler than Dijkstra and suites well for distributed systems. Bellman ford follows similar steps like Dijkstra’s algorithm, the main difference being all edges would be processed through relaxation for |V| - 1 times, instead of just once. steps to implement this : We initializes distances from the source to all vertices as infinite and distance to the source itself as 0. We create an array dist[] of size |V| with all values as infinite except dist[src] where src is source vertex. For calculating shortest distances, we do the following |V|-1 times where |V| is the number of vertices in givengraph If dist[v] > dist[u] + weight of edge uv, then we update. i am uploaded the program file.

11.MINIMUM SWAPS TO SORT

Given an array of integers. Find the minimum number of swaps required to sort the array in non-decreasing order.

complete the function minSwaps() which takes the array arr[] and prints the minimum number of swaps required to sort the array. If the array is already sorted, return 0.

Constraints:
1 <= size of A <= 105
1 <= A[] <= 106

Expected Time Complexity: O(NlogN).
Expected Space Complexity : O(N).

Explination : This problem can be solved by visualizing it as a graph. We have n nodes and an edge directed from node i to j, if the element at i'th index must be present at j'th index in the sorted array. Thus, the graph will contain many non intersecting cycles. Now a cycle with 2 nodes will inly require 1 swap to reach the correct ordering and a cycle with 3 nodes will require 2 swaps and so on. So first we store the indexes of the elements given in the array in a hashmap. Next, we sort this array. Now we go over every element to check if it has been already visited or if it is present in the right place. If any of these is true, we go on over to the next iteration. If both are false, we check for cycle by moving to the next node from one node. If cycle is greater than 0 we say answer = answer + (cycles - 1). We check this for all elements and then finally return the answer. i am uploaded the program file.

12.GET MINIMUM ELEMENT FROM STACK

You are given N elements and your task is to Implement a Stack in which you can get minimum element in O(1) time.

Complete the three methods push() which take one argument an integer 'x' to be pushed into the stack, pop() which returns a integer popped out from the stack and getMin() which returns the min element from the stack. (-1 will be returned if for pop() and getMin() the stack is empty.)

Expected Time Complexity : O(1) for all the 3 methods.
Expected Space Complexity : O(1) for all the 3 methods.

Constraints:
1 <= Number of queries <= 100
1 <= values of the stack <= 100

Explination : In this problem, we define a variable minEle that stores the current minimum element in the stack. To handle the case when the minimum element is removed, we push “2x – minEle” into the stack instead of x so that previous minimum element can be retrieved using current minEle and its value stored in stack. i am uploaded the program file.