Project 2

A set of 20 problems to solve in an optimised way with the given restrictions of time and space complexity

Arrays and Strings

1.SUBARRAY WITH GIVEN SUM

Given an unsorted array A of size N of non-negative integers, find a continuous sub-array which adds to a given number S.

Implement a method subArraySum(a[], s), where A is array of size n and s is the sum.

And return the starting and ending positions (0 indexing) of FIRST such occurring subarray from the left if sum equals to subarray, else print -1.

Code knowing that-

1 <= N <=10^7
1 <= Ai <=10^10

Explination : using two loops and for every element in the array find the sub array, add elements up and check if they equal to the target sum. But this will be taking O(n^2) time complexity as we have to loop through n element and for each of those n elements loop through n-1 elements. i am uploaded the program file

2.PERMUTATIONS OF A GIVEN STRING

Given a string S. The task is to print all permutations of a given string. Implement perm(s) method where s is a string in capital letter. Print all permutations of a given string S with single space and all permutations should be in lexicographically increasing order.

Constraints:
1 ≤ size of string ≤ 5

Explination : in this problem using those steps to solve. We fix a character in the first position and swap the rest of the character with the first character. Like in ABC, in the first iteration three string are formed : ABC, BAC, CBA by swapping A with A, B and C respectively. We repeat step 1 for rest of the characters like fixing second character B and so on. Now we swap again to go back to the previous position. Eg : from ABC, we formed ABC by fixing B again, and we backtrack to the previous position and swap B with C. So now we got ABC and ACB. Thus, we repeat the above for BAC and CBA to get all permutations. i am uploaded the program file

Trees

3.DETERMINE IF TWO TREES ARE IDENTICAL

Given two binary trees, the task is to find if both of them are identical or not.

Complete the function isIdentical() that takes two roots as parameters and returns true or false.

Expected Time Complexity: O(N).
Expected Auxiliary Space: O(Height of the Tree).

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

Explination : Two trees are identical when they have same data and arrangement of data is also same. To identify if two trees are identical, we need to traverse both trees simultaneously, and while traversing we need to compare data and children of the trees. i am uploaded the program file.

4.COUNT LEAVES IN BINARY TREE

For the above tree, the string will be: 5 2 3 1 N 7 4 N 8 N 6 N N Complete the function countLeaves() that takes the tree string as parameter and returns the count of leaves in tree.

Constraints:
1<= N <=10^14

Explination :

5.LOWEST COMMON ANCESTOR IN A BINARY TREE

Given a Binary Tree with all unique values and two nodes value n1 and n2. The task is to find the lowest common ancestor of the given two nodes. We may assume that either both n1 and n2 are present in the tree or none of them is present.

Complete the function lca() that takes nodes, n1, and n2 as parameters and returns LCA node as output.

Expected Time Complexity: O(N).
Expected Space Complexity : O(H).
H is the height of the tree.

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

Explination : the tree starting from the root. If any of the given keys (n1 and n2) matches with the root, then the root is LCA (assuming that both keys are present). If the root doesn’t match with any of the keys, we recur for the left and right subtree and call LCA again. The node which has one key present in its left subtree and the other key present in the right subtree will be the LCA. If both keys lie in the left subtree, then the left subtree has LCA also, otherwise, LCA lies in the right subtree. i am uploaded the program file.

Sorting

6.LINKED LIST OF 0S, 1S AND 2S, SORT IT.

Given a linked list of N nodes where nodes can contain values 0s, 1s, and 2s only. The task is to segregate 0s, 1s, and 2s linked list such that all zeros segregate to head side, 2s at the end of the linked list, and 1s in the mid of 0s and 2s.

complete the function segregate() which segregates the nodes in the linked list as asked in the problem statement and returns the head of the modified linked list. The printing is done automatically by the driver code.

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

Constraints:
1 <= N <=10^13

Explination : in this program first traverse the list and count the number of 0s, 1s and 2s. Let's assume the counts to be n1, n2 and n3 respectively. Next, we traverse the list once more and fill the first n1 nodes with 0, then n2 nodes with 1 and n3 nodes with 2. The time complexity for this approach would be O(n) and space complexity would be O(1) but this method would not work if the values are associated with some data. For eg : let's say the 3 values represent 3 different colours and different types of objects are assiciated with the colours and we need to sort the objects based on that. i am uploaded the program file.

Searching

7.FIND FIRST REPEATED CHARACTER

Given a string S. The task is to find the first repeated character in it. We need to find the character that occurs more than once and whose index of second occurrence is smallest.
S contains only lowercase letters.

Argument is a string S.

print the first repeating character in the string. If no such character exist print -1.

Constraints:
1 <= |S| <=10^14

Explination : we can run two nested loops. We start traversing from left side and for every character, we check if it repeats or not. If the character repeats, increment count of repeating characters. When the count becomes greater than 1, return the character. Time Complexity of this solution is O(n²) which is not going to be efficient. i am uploaded the program file.

8.CHECK IF TWO ARRAYS ARE EQUAL OR NOT

Complete the function which takes two arrays A and B of equal size. Find if given arrays are equal or not. Two arrays are said to be equal if both of them contain same set of elements, arrangements (or permutation) of elements may be different though. If there are repetitions, then counts of repeated elements must also be same for two array to be equal.

Print 1 if the arrays are equal else print 0.

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

Constraints:
1 <= N <=10^17
1 <= A[],B[] <=10^18

Explination: using hash where we store all elements of arr1[] and their counts in a hash table. Then we traverse arr2[] and check if the count of every element in arr2[] matches with the count in arr1[]. This method takes O(n) time complexity for looping through n elements of the arrays and O(n) space complexity for creating hash table. i am uploaded the program file.

Hashing

9.RELATIVE SORTING

Given two arrays A1[] and A2[] of size N and M respectively. The task is to sort A1 in such a way that the relative order among the elements will be same as those in A2. For the elements not present in A2, append them at last in sorted order. It is also given that the number of elements in A2[] are smaller than or equal to number of elements in A1[] andA2[] has all distinct elements.

Expected time complexity is O(N log(N)).

Length of arrays N and M and next two line contains N and M elements respectively.

Output:
Print the relatively sorted array.

Constraints:
1 ≤ A1[], A2[] <=10^16

Explination : We first sort the arr1 using Arrays.sort(). Next, we create a hashMap with keys as elements of the arr1 and values as their counts. We loop through arr1 and store count of every number in the hashMap. Next, we loop through arr2 and check if the element is present in hashmap, if it is then we put it in the output array that many number fo times and remove the element from the hashMap. Finally, we loop through the arr1 again and add the rest of the elements to the end of the output array in sorted order and we print the output array.

Graph

10.SHORTEST SOURCE TO DESTINATION PATH

Given a boolean 2D matrix (0-based index), find whether there is path from (0,0) to (x,y) and if there is one path, print the minimum no of steps needed to reach it, else print -1 if the destination is not reachable. You may move in only four direction ie up, down, left and right. The path can only be created out of a cell if its value is 1.

Complete the function for implementing this. Arguments are two integers n and m denoting the size of the matrix, an n*m matrix and two integers x and y denoting the index of the destination. Print the min no of steps needed to reach the destination.

Constraints:
1<=n,m<=20

Explination :

11.MINIMUM COST PATH
Given a square grid of size N, each cell of which contains integer cost which represents a cost to traverse through that cell, we need to find a path from top left cell to bottom right cell by which total cost incurred is minimum. You can move in 4 directions : up, down, left an right. It is assumed that negative cost cycles do not exist in input matrix.

N denoting the size of the grid N*N integer matrix depicting the cost of respective cell from (0,0) to (N,N).

output a single integer depicting the minimum cost to reach the destination.

Constraints:
1 <= N <= 100
1 <= grid[i][j] <= 104

Explination : Create an empty priorityqueue with a distanceComparator and enqueue the source cell and put its distance in dist array. Initially dist array is initialised with all values as Integer.MAX_VALUE. We Loop till queue is empty then Dequeue the front node and We check in all 4 directions of the popped node for the minimum cost and then if it is not already reached. If it is reached we remove it from the queue else we insert this cell in the priority queue and also update the distance. We repeat the same process until we reach end of matrix.

12.CIRCLE OF STRINGS

Given an array of strings A[], determine if the strings can be chained together to form a circle. A string X can be chained together with another string Y if the last character of X is same as first character of Y. If every string of the array can be chained, it will form a circle.

For eg for the array arr[] = {“great", “skill", “trains", “lync"} the answer will be Yes as the given strings can be chained as “great", “trains", “skill" and “lync"

Input: array A[].

Output: If chain can be formed, then print 1, else print 0.

Constraints
0 <= size of A <= 30
0 <= A[i] <= 10

Explination : in a circle of strings vertices will be the first and last character of strings, and we will draw an edge between two vertices if they are the first and last character of the same string, so a number of edges in the graph will be same as the number of strings in the array. If a loop among graph vertices is possible then, we can reorder the strings such that circle is possible otherwise we cannot.

Stacks queues

13.FIRST NON-REPEATING CHARACTER IN A STREAM

Given an input stream of N characters consisting only of lower case alphabets. The task is to find the first non repeating character, each time a character is inserted to the stream.

If no non repeating element is found print -1.

Argument is x character array which are inserted to the stream.

Output:

For each test case in a new line print the first non repeating elements separated by spaces present in the stream at every instinct when a character is added to the stream, if no such element is present print -1.

Constraints:
1 <= N <= 500

Explination: Create a count array of size 26(assuming only lower case characters are present) and initialize it with zero. Create a queue of char datatype. Store each character in queue and increase its frequency in the hash array. For every character of stream, we check front of the queue. If the frequency of character at the front of queue is one, then that will be the first non-repeating character. Else if frequency is more than 1, then we pop that element. If queue became empty that means there are no non-repeating characters so we will print -1.

Heap

14.REARRANGE CHARACTERS

Given a string S with repeated characters (only lowercase). The task is to rearrange characters in a string such that no two adjacent characters are same. It may be assumed that the string has only lowercase English alphabets.

Complete the function which takes the argument as a string of lowercase English alphabets and prints 1 if the generated string doesn't contain any same adjacent characters, else if no such string is possible to be made print 0

Constraints:
1 <= length of string <= 104

Explination : in this program first Build a Priority_queue or max_heap, pq that stores characters and their frequencies. Create a temporary Key that will be used as the previously visited element (the previous element in the resultant string. Initialize it { char = ‘#’ , freq = ‘-1’ } While pq is not empty. Pop an element and add it to the result. Decrease frequency of the popped element by ‘1’ Push the previous element back into the priority_queue if it’s frequency > ‘0’ Make the current element as the previous element for the next iteration. If the length of the resultant string and original string is not equal, print “not possible”. Else print result.

Dynamic programming

15.LONGEST COMMON SUBSEQUENCE

Given two strings: string X of length m and string Y of length n find the longest common subsequence

The longest sequence of characters that appear left-to-right (but not necessarily in a contiguous block) in both strings.

For example, if X = “ABCBDAB” and Y = “BDCABA”, the LCS(X, Y) = {“BCBA”, “BDAB”, “BCAB”}.

Explination : in this program we can check if the every subsequence of X[1..m] to see if it is also a subsequence of Y[1...n]. As there are 2^m subsequences possible of X, the time complexity for this approach would be O(n.2^m) where m is length of first string and n is length of second string.

16.MAXIMUM SUM OF INCREASING SUBSEQUENCES

Given an array A of N positive integers. Find the sum of maximum sum increasing subsequence of the given array.

Complete the function which takes the array and prints the required answer.

Constraints:
1 ≤ N ≤ 106
1 ≤ Ai ≤ 106

Testcase 1: All the increasing subsequences are : (1,101); (1,2,3,100); (1,2,3,4,5). Out of these (1, 2, 3, 100) has maximum sum,i.e., 106.

Explination : in this using the criteria here as sum instead of length. In the traditional recursive approach, let arr[0..n-1] be the input array and L(i) be the length of the LIS ending at index i such that arr[i] is the last element of the LIS. Then the recursive equations would be

L(i) = 1 + max( L(j) ) where 0 < j < i and arr[j] < arr[i]; or
L(i) = 1, if no such j exists.

To find the LIS for a given array, we need to return max(L(i)) where 0 < i < n.
Formally, the length of the longest increasing subsequence ending at index i, will be 1 greater than the maximum of lengths of all longest increasing subsequences ending at indices before i, where arr[j] < arr[i] (j < i).

17.COUNT NUMBER OF HOPS

A frog jumps either 1, 2 or 3 steps to go to top. In how many ways can it reach the top.

Complete the function which takes input N denoting the total number of steps and prints the number of ways to reach the top.

Constraints:
1 ≤ N ≤ 50

Explination : first we need to Create an array of size 3 and initialize the values for step 0,1,2 as 1,1,2 (Base cases). Run a loop from 3 to n(dist). For each index compute the value as ways[i%3] = ways[(i-1)%3] + ways[(i-2)%3] + ways[(i-3)%3] and store its value at i%3 index of array ways. If we are computing value for index 3 then the computed value will go at index 0 because for larger indices(4 ,5,6…..) we don’t need the value of index 0. Return the value of ways[n%3].

Greedy

18.N MEETINGS IN ONE ROOM

There is one meeting room in a firm. There are N meetings in the form of (S[i], F[i]) where S[i] is start time of meeting i and F[i] is finish time of meeting i.

What is the maximum number of meetings that can be accommodated in the meeting room?

Complete the function which takes the array containing the starting time of all the meetings S [ i ] and the array containing the finishing time of all the meetings F [ i ].

Print the order in which the meetings take place separated by a space.

Constraints:
1 ≤ N ≤ 100
1 ≤ S[ i ], F[ i ] ≤ 100000

Explination : first Sort the meetings according to their finishing time Select the first meeting from the sorted array and print it. Do the following for the remaining meetings in the sorted array. If the start time of this meeting is greater than or equal to the finish time of the previously selected meeting, then select this meeting and print it.

19.MINIMISE THE SUM OF PRODUCT

You are given two arrays, A and B, of equal size N. The task is to find the minimum value of A[0] * B[0] + A[1] * B[1] +…+ A[N-1] * B[N-1], where shuffling of elements of arrays A and B is allowed.

Argument is the array A[] and array B[] and print the minimum sum.

Constraints:
1 <= Size of Arrays <=10^17
1 <= A[], B[] <=10^18

Explination : in this using a built in Arrays.sort() method which uses a dual pivot quicksort algorithm and takes O(nlogn) time complexity. We can get a better time complexity of O(n) by using a linear sorting algorithm like Count sort but that would require O(n) space to store the count and output arrays. But for large input sizes count sort becomes inefficient due to large amount of space it utilises.

20.LARGEST NUMBER POSSIBLE

Given two numbers 'N' and 'S' , find the largest number that can be formed with 'N' digits and whose sum of digits should be equals to 'S'.

Input: integers N and S, where N is the number of digits and S is the sum.

Print the largest number that is possible. If their is no such number, then print -1

Constraints:
1 <= N <= 50
0 <= S <= 500

Expected Time Complexity: O(n)

Explination : in this comparing the remaining sum with 9 if the remaining sum is more than 9, so we put 9 at the current position, else we put the remaining sum. Since we fill digits from left to right, we put the highest digits on the left side, hence get the largest number.

Two pointer & sliding window

21.LONGEST DISTINCT CHARACTERS IN STRING

Given a string S, find length of the longest substring with all distinct characters. For example, for input "abca", the output is 3 as "abc" is the longest substring with all distinct characters.

Input: String s.

Print length of smallest substring with maximum number of distinct characters.

Constraints:
1 ≤ size of str ≤ 10000

Explination : in this problem the order has been store the last positions of the occurance of characters we need a hashmap to store it. Next, we loop through the array, and check if the character is present in the hashmap.

22.SMALLEST WINDOW IN A STRING CONTAINING ALL THE CHARACTERS OF ANOTHER STRING

Given a string S and text T. Output the smallest window in the string S having all characters of the text T. Both the string S and text T contains lowercase english alphabets.

Input: a string S and text T.

Output the smallest window of the string containing all the characters of the text. If such window doesn`t exist or this task can not be done then print -1.

Constraints:
1 <= |N|, |X| <= 1000

Explination : First check if the length of the string is less than the length of the given pattern, if yes then “no such window can exist “. Next, we store the occurrence of characters of the given pattern in a hash_pat[]. We start matching the characters of pattern with the characters of string i.e. increment count if a character matches. We check if (count == length of pattern ) this means a window is found. If such a window found, we try to minimize it by removing extra characters from the beginning of the current window. We delete one character from first and again find this deleted key at right, once found apply .We update min_length and finally Print the minimum length window.

23.POWER OF 2

Given a positive integer N. The task is to check if N is a power of 2. That is N is 2x for some x.

Input: a single positive integer N.

Output: Print YES if it is a power of 2 else NO

Constraints:
1 <= T <= 100
0 <= N <=10^18

Explination : If we subtract a power of 2 number by 1 then all unset bits (zeros) after the only set bit (ones) become set; and the set bit becomes unset.
For example for 4 ( 100) and 16(10000), we get the following after subtracting 1
3 –> 011
15 –> 01111

So, if a number n is a power of 2 then bitwise & of n and n-1 will be zero. We can say n is a power of 2 or not based on the value of n&(n-1).