The Coding Shala

Home >> Interview Questions >> Triplets with sum between given range Triplets with Sum between given range Java Solution Given an array of real numbers greater than zero in the form of strings. Find if there exists a  triplet  (a,b,c) such that  1  <  a+b+c  <  2  .  Return  1  for  true  or  0  for  false . Example: Given [0.6, 0.7, 0.8, 1.2, 0.4] , You should return  1 as 0.6+0.7+0.4=1.7 1<1.7<2 Hence, the output is 1. Triplets with Sum between given range Java Solution Here an array will be given, we need to find three values whose sum will be in the given range. We can solve this using brute force using three loops but that will give time limit error.  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 public class Solution { pub...

Home >> Interview Questions >> Kth row of pascal's triangle Kth Row of Pascal's Triangle Solution Java Given an index k, return the kth row of Pascal’s triangle. Example: Input : k = 3 Return : [1,3,3,1] Java Solution of Kth Row of Pascal's Triangle One simple method to get the Kth row of Pascal's Triangle is to generate Pascal Triangle till Kth row and return the last row.  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 public class Solution { public ArrayList < Integer > getRow ( int A ) { ArrayList < ArrayList < Integer >> res = new ArrayList < ArrayList < Integer >>(); for ( int i = 0 ; i <= A ; i ++){ ArrayList < Integer > tmp = new ArrayList < Integer >(); for ( int j = 0 ; j <= i ; j ++){ if ( j == i || j == 0 ) tmp . add ( 1 ); else tmp . add ( r...

Home >> Interview Questions >> Pascal Triangle Pascal Triangle Java Solution Given numRows, generate the first numRows of Pascal’s triangle. Pascal’s triangle: To generate A[C] in row R, sum up A’[C] and A’[C-1] from previous row R - 1. Example: Given numRows = 5, Return [ [1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1] ] Solution: (Java) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 public class Solution { public ArrayList < ArrayList < Integer >> solve ( int A ) { ArrayList < ArrayList < Integer >> res = new ArrayList < ArrayList < Integer >>(); for ( int i = 0 ; i < A ; i ++){ ArrayList < Integer > temp = new ArrayList < Integer >(); for ( int j = 0 ; j <= i ; j ++){ if ( j == i || j == 0 ) temp . add ( 1 ); else { temp . add ...

Home >> Interview Questions >> Max non-negative subarray Max Non-Negative SubArray InterviewBit Solution Find out the maximum sub-array of non-negative numbers from an array. The sub-array should be continuous. That is, a sub-array created by choosing the second and fourth elements and skipping the third element is invalid. The maximum sub-array is defined in terms of the sum of the elements in the sub-array. Sub-array A is greater than sub-array B if  sum(A) > sum(B) . Example: A : [1, 2, 5, -7, 2, 3] The two sub-arrays are [1, 2, 5] [2, 3]. The answer is [1, 2, 5] as its sum is larger than [2, 3] NOTE:   If there is a tie, then compare with segment's length and return segment which has maximum length NOTE 2:   If there is still a tie, then return the segment with minimum starting index Solution: (Java) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 3...

Home >> Interview Questions >> Flip Flip InterviewBit Solution You are given a binary string( i.e.  with characters  0  and  1 ) S consisting of characters S 1 , S 2 , …, S N . In a single operation, you can choose two indices L and R such that 1 ≤ L ≤ R ≤ N and flip the characters S L , S L+1 , …, S R . By flipping, we mean to change the character  0  to  1  and vice-versa. Your aim is to perform ATMOST one operation such that in final string number of 1's is maximized. If you don’t want to perform the operation, return an empty array. Else, return an array consisting of two elements denoting L and R. If there are multiple solutions, return the lexicographically smallest pair of L and R. Notes : Pair (a, b) is lexicographically smaller than pair (c, d) if a < c or, if a == c and b < d. For example, S = 010 Pair of [L, R] | Final string ________ | _____________ [1 2] | 100 [1 1] ...

Home >> Programming Questions >> Maximum Absolute Difference Maximum Absolute Difference InterviewBit Solution You are given an array of N integers, A 1 , A2, …, A N . Return maximum value of   f(i, j)   for all 1 ≤   i, j   ≤ N. f(i, j)  is defined as  |A[i] - A[j]| + |i - j| , where |x| denotes the absolute value of x. For example , A=[1, 3, -1] f(1, 1) = f(2, 2) = f(3, 3) = 0 f(1, 2) = f(2, 1) = |1 - 3| + |1 - 2| = 3 f(1, 3) = f(3, 1) = |1 - (-1)| + |1 - 3| = 4 f(2, 3) = f(3, 2) = |3 - (-1)| + |2 - 3| = 5 So, we return 5. Solution Here function f(i, j) = |A[i] - A[j]| + |i-j] can be written in four ways -  (A[i] + i) - (A[j] + j) -(A[i] - i) + (A[j] - j) (A[i] - i) - (A[j] - j) (-A[i] - i) + (A[j] + j) = -(A[i] + i) + (A[j] + j) we just have to store minimum and maximum values of expressions  A[i] + i  and  A[i] - i  for all  i. Java Code:: 1 2 3 4 5...