Arrays - Q's asked by Top MNC's

           Arrays Challenge
       Subarray with given sum
   (Google, Amazon, Facebook)

Problem

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

Constraints

1 <= N <= 105​

0 <= Ai <= 101​ 0

Example

Input:​

N = 5, S = 12

A[] = {1,2,3,7,5}

Output:​2​ 4

Explanation:​T​ he sum of elements from 2nd position to 4th position is 12.

Solution

Brute Force Solution


● Find sum of all possible subarrays. If any of the sum equates to S​ , o​ utput the starting and ending index of the subarray.


Time Complexity : O​ (n2​ ​)

Optimized Approach Steps:

1.    Keep the pointers st and en, and a variable currSum that stores the sum from st to en.

2.    alize st = 0, en = 0initi

3.    Increment en till currSum + a[en + 1] > S 

4.    When 3rd condition occurs, start increasing st until currSum <= S.

5.    Whenever the condition (currSum = S) is satisfied, store st and en and BREAK from the loop.

Time Complexity: O​ (n) 


Iterations








Code:

Arrays Challenge-First Repeating Element

(Amazon, Oracle)

 

Problem

Given an array a​ rr[​ ] of size N​ .​ The task is to find the first repeating element in an array of integers, i.e., an element that occurs more than once and whose index of first occurrence is smallest.

 

Constraints

1 <= N <= 106​

0 <= Ai <= 106​

 

Example

Input:​

7

1 5 3 4 3 5 6

 

Output:​ 

2

 

Explanation:​ 

5 is appearing twice and its first appearance is at index 2 which is less than 3 whose first occurring index is 3.

 

Solution

Base idea:​ To check if an element is repeating, we maintain an array idx[], which stores the first occurrence (index) of a particular element a[i].

 

Steps

1.    Initialise the idx[] with -1, and minidx with INT_MAX. 

2.    Keep updating idx[], while traversing the given array. 

Iterations






Arrays Challenge - Smallest Positive Missing Number 

   (Amazon, Samsung, Snapdeal, Accolite)


Problem

Find the smallest positive missing number in the given array.


Example:  [0, -10, 1, 3, -20], Ans = 2


 


Intuition


If in O(1), we can tell if an element is present in an array, then our task will be simpler.


For that, we will maintain a Check[ ] array, that will if an element x is present in the array or not.


It will be of boolean type as we only need to check the presence or absence of the number.


 


1.    Build the Check[ ] array initialized with False at all indices. 


2.    By iterating over the array and marking non-negative a[i] as true i.e.  if(a[i] >= 0)      check[a[i]] = True


3.    Iterate in the Check[ ] from i=1, BREAK the loop when you find check[i] = False and store that i in the ans variable.


4.    Output the ans.


 


 


Example:


 


Given Array:  [0, -9, 1, 3, -4, 5]


 


 



Iterations 














Comments

Post a Comment

Popular posts from this blog

Subarrays - Challenges | Questions asked by Top MNC's |

Image
 Array Challenges  Maximum Sum Subarray Array   1. Brute Force:   Idea: For each subarray arr[i..j], calculate its sum.  Time Complexity: O(N3 )  Space Complexity: O(1)    2. Prefix Sum Technique:  Idea: For each subarray arr[i..j], calculate its sum. Using prefix sum can  reduce time to calculate the sum of arr[i..j] to O(1)  Time Complexity: O(N2 )  Space Complexity: O(N)     3. Kadane’s Algorithm:  Idea: Start taking the sum of the array, as soon as it gets negative, discard the current subarray, and start a new sum.  Time Complexity: O(N)  Space Complexity: O(1)      Maximum Sum Circular Subarray:    Idea: There will 2 cases,     To get the Min subarray we multiply the array by -1 and get the maximum sum subarray.  Time Complexity: O(N)     Pair Target Sum Problem  Find whether there exist 2 numbers that sum t...
Read more

Strings Challenges | C++ Placement

Image
 String Challenges  Challenge 1  UpperCase-LowerCase interconversion  Given a string s with both uppercase and lowercase latin characters (‘a’ - ‘z’).  Your task is convert whole string into   1. Lower Case  2. Upper Case    Base idea: ‘a’ - ‘A’ = 32  1. Lowercase to UpperCase Approach  1. Iterate over the string s and if s[i] is a lower case character, then update s[i] -= 32    2. UpperCase to LowerCase Approach  1. Iterate over the string s and if s[i] is a upper case character, then update s[i] +=32    Code:    Challenge 2 Form the biggest number  of integers, our task is to form the biggest number out of those numbers in the string.    Approach:  Sort the string in descending order using inbuilt sort function.    Code     Challenge 3 Max Frequency  s of latin characters, your task is to output the character which has  maximum f...
Read more