Project 1

Arrays

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

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 <=

Ai <= 107

String

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

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

LinkedList

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 be 4.

The 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

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

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

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

Trees

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.

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

Graph

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)

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).

Stacks Queues

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