This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
1. Name some applications of stack. | |
Ans: | |
Evaluation of arithmetic expression | |
Code generation for stack machine. | |
Backtracking. | |
Decimal to binary conversion | |
2. How do you generate code for stack machines? |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.io.*; | |
import java.util.*; | |
public class Main{ | |
public static void main(String[] args) throws Exception { | |
Scanner scn = new Scanner(System.in); | |
int n1 = scn.nextInt(); | |
int[] a1 = new int[n1]; |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
A. What exactly is a quadruplet sum? | |
1. Sum of two numbers is equal to target | |
2. Sum of three numbers is equal to target | |
3. Sum of four numbers is equal to target | |
4. None Of the above | |
Ans -> 3. Sum of four numbers is equal to target | |
Exlpain : Sum of four numbers is equal to target is a quadruplet sum. | |
B. As per the question, (a, b, c, d) is represents? |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Q1) What does that denote If I subtract my target with the value of an element in array2 and the value present in val 1 ? | |
Ans: Its denotes that the sum of both elements is equal to the target. | |
Q2) What would be the best data structure to solve this problem? | |
Ans: HashMap, which is going to store elements of array with its frequency. | |
Q3) What is the average time complexity of this problem? | |
ans: The time complexity of this code is O(N2) as we are traversing using i and j pointers where the i is traversing till n and the j pointer in the inner loop is traversing till n. . | |
Q4) What is the average space complexity of this problem? |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
1. What is the meaning of Longest Subarray With Equal Number Of 0s 1s And 2s? | |
ans -> Longest subarray for the given array which will contain equal number of 0s, 1s, and 2s , we have return its length only in this question. | |
2. How can we use HashMap in this question? | |
ans -> We make a hashmap to solve this problem where the key is a string which is represented by "x1-x0 # x2-x1" where the gap between count of 0s and 1s is separated from the gap between count of 1s and 2s by a "#". | |
3. Why the time complexity is O(n)? | |
Ans ->The time complexity is linear due to the traversal through the given array. | |
4. Can we use Hashset instead of HashMap? |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
1. Why time complexity is O(n)? | |
Ans ->O(n) where “n” is the number of elements in the array. Because we have used HashMap we are able to achieve linear time complexity. | |
2. Why space complexity is O(n)? | |
Ans -> O(n) where “n” is the number of elements in the array. Here in the HashMap we have saved the sum as key, thus linear space complexity is achieved. | |
3. How to find the smallest subarray having equal number of 0s and 1s? | |
Ans -> Following the similar to finding the maximum length having equal zeroes and ones, we need to minimise the length. | |
4. What does the term "Count of Subarray With equal number of zeroes and ones" mean? |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
1. Why is the space complexity O(n)? | |
The space complexity of the above code is also O(N) as we are storing the sum and frequency at every array index in the hashmap. | |
2. Why is the time complexity O(n)? | |
The time complexity of the above code is O(N) where N is the number of elements in the array as we are traversing the array and calculating the prefix sum to find the number of subarrays with sum K. | |
3. Why is the number of subarrays of an array given by (n * (n + 1)) / 2? | |
The number of subarrays of an array can be calculated as there are, | |
1 subarray of length n |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
1. "abll" and "ball" are anagrams. | |
A. True | |
B. False | |
Ans: A. True | |
2. "tall" and "all" are anagrams. | |
A. True | |
B. False |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Q1. What is a Anagram? | |
Ans -> a word or phrase that is made by arranging the letters of another word or phrase in a different order. | |
Q2)What will we store in our pair class? | |
Ans: We will be required to use a pair class, which is going to store Integer and an ArrayList | |
Q3) What could be the best data structure for this problem? | |
Ans: HashMap, because here we have to see the frequency of every element and the best way to see frequency is frequency map. | |
Q4. What is the average Time Complexity to solve this question? |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
1. What does the term "Longest Substring With Exactly K Unique Characters" mean? | |
Ans -> Substring that contains exactly k number of unique characters and we need to return its length. | |
2. How can we use HashMap into this question? | |
ans -> We are using Aquire and Release strategy, and HashMap for storing k number of unique characters and when we have HashMap's size is equals to k then we can calculate length of longest substring present with the help of aquire and release pointer. | |
3. While using HashMap why our time complexity is O(n + k) and why not O(n ^ k) and other? | |
ans -> Because we are storing at max k characters into HashMap | |
4. Can we use HashSet instead of HashMap? |
NewerOlder