The Coding Shala

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 >> Spiral Order matrix 2 Spiral Order Matrix II Problem Solution Given an integer n, generate a square matrix filled with elements from 1 to n 2  in spiral order. Example: Given n = 3, You should return the following matrix: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ] Solution: (Java) The concept is the same as how to print the Spiral Order Matrix. Approach: Let's see for n= 4, then numbers will come from 1 to 16(n*n) in the matrix. As we need to insert numbers in spiral order so here we need 4 things to check, first and last column and top and bottom row. The following four steps we need to do: First, we need to insert numbers in the top row. Our loop will go from the left column to the right then will increase the top row by one and now the top is our second row. Now we are inserting the numbers in the right column, will start the loop from top to bottom, and then decrease the value of the right ...

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

Home >> Interview Questions >> Max Sum Contiguous Subarray Max Sum Contiguous Subarray InterviewBit Solution Problem:: Find the contiguous subarray within an array (containing at least one number) which has the largest sum. For example: Given the array  [-2,1,-3,4,-1,2,1,-5,4] , the contiguous subarray  [4,-1,2,1]  has the largest sum = 6. For this problem, return the maximum sum. Solution We can solve this problem using Kadane's Algorithm.  Java Solution:: 1 2 3 4 5 6 7 8 9 10 11 12 public class Solution { // DO NOT MODIFY THE LIST. IT IS READ ONLY public int maxSubArray ( final List < Integer > A ) { int curr_max = A . get ( 0 ); int max = curr_max ; for ( int i = 1 ; i < A . size (); i ++){ curr_max = Math . max ( A . get ( i ), curr_max + A . get ( i )); max = Math . max ( max , curr_max ); } ...