Skip to content

This repository contains my solutions to various programming problems posed on the interviewbit's website.

Notifications You must be signed in to change notification settings

sidgupta234/InterviewBit

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

InterviewBit

Popular Software Engineering interview questions posed on interviewbit and their solutions.

Level-2

Arrays

Given a list of non negative integers, arrange them such that they form the largest number.

Example: Given [3, 30, 34, 5, 9], the largest formed number is 9534330.

Note: The result may be very large, so you need to return a string instead of an integer.

Solution


Given a non-negative number represented as an array of digits, add 1 to the number ( increment the number represented by the digits ). The digits are stored such that the most significant digit is at the head of the list.

Example: If the vector has [1, 2, 3] the returned vector should be [1, 2, 4] as 123 + 1 = 124.

Note: The result may be very large, so you need to return a string instead of an integer.

Solution


Given a NxN square matrix, return an array of its anti-diagonals. Look at the example for more details.

Examples:
For, [1, 2, 3, 4, 5, 6, 7, 8, 9] you should return, [ [1], [2, 4], [3, 5, 7], [6, 8], [9] ]
For, [1, 2, 3, 4] you should return, [ [1], [2, 3], [4] ]

Solution


Given a read only array of n + 1 integers between 1 and n, find one number that repeats in linear time using less than O(n) space and traversing the stream sequentially O(1) times.

Example: For [3, 4, 1, 4, 1], you should return 1.

Note: If there are multiple possible answers ( like in the sample case above ), output any one.

Solution


Given an unsorted integer array, find the first missing positive integer.

Example: For [1,2,0] return 3, [3,4,-1,1] return 2, [-8, -7, -6] returns 1

Note: Your algorithm should run in O(n) time and use constant space.

Solution


Given an index k, return the kth row of the Pascal’s triangle.

Example: For k = 3, return [1,3,3,1]

Note: k is 0 based. k = 0, corresponds to the row [1]. Could you optimize your algorithm to use only O(k) extra space?

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 element and skipping the third element is invalid.

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: For [1, 2, 5, -7, 2, 3], their are two sub-arrays that follow the constraint; [1, 2, 5] and [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


Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

Example: For [-2,1,-3,4,-1,2,1,-5,4], the contiguous subarray [4,-1,2,1] has the largest sum, which is 6.

For this problem, return the maximum sum.

Solution


Given a collection of intervals, merge all overlapping intervals.

Example: Given [1,3], [2,6], [8,10], [15,18], return [1,6] [8,10] [15,18].

Note: Make sure the returned intervals are sorted.

Solution


You are in an infinite 2D grid where you can move in any of the 8 directions :
(x,y) to
(x+1, y),
(x - 1, y),
(x, y+1),
(x, y-1),
(x-1, y-1),
(x+1,y+1),
(x-1,y+1),
(x+1,y-1)

You are given a sequence of points and the order in which you need to cover the points. Give the minimum number of steps in which you can achieve it. You start from the first point.

Example: For [(0, 0), (1, 1), (1, 2)], return 2.
It takes 1 step to move from (0, 0) to (1, 1). It takes one more step to move from (1, 1) to (1, 2).

Solution


Given numRows, generate the first numRows of Pascal’s triangle.

Example: For numRows = 5, Return [ [1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1] ]

Solution


You are given a read only array of n integers from 1 to n. Each integer appears exactly once except A which appears twice and B which is missing. Return A and B.

Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
Note 2: that in your output A should precede B.

Example: For [3, 1, 2, 5, 3] return [3, 4]

Solution


Given an m x n matrix of 0s and 1s, if an element is 0, set its entire row and column to 0. Do it in place.

Example: For a given array A as [ [1, 0 ,1], [1, 1, 1], [1, 1, 1,] ], on returning, the array A should be [ [0, 0 ,0], [1, 0, 1], [1, 0, 1] ]

Note: Try to minimize the space and time complexity.

Solution


Given an array of integers, sort the array into a wave like array and return it, In other words, arrange the elements into a sequence such that a1 >= a2 <= a3 >= a4 <= a5.....

Example: Given [1, 2, 3, 4], possible answers could be [2, 1, 4, 3] or [4, 1, 3, 2].

Note: Multiple answers are possible, return the one that is lexicographically smallest.

Solution


About

This repository contains my solutions to various programming problems posed on the interviewbit's website.

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages