SDE - Intern

You are given an infinite supply of coins of each of denominations D = {D0, D1, D2, D3, ...... Dn-1}. You need to figure out the total number of ways W, in which you can make a change for value V using coins of denominations from D. Print 0, if a change isn't possible.

Given an undirected graph of ‘V’ vertices (labeled 0,1,..., V-1) and ‘E’ edges . Your task is to check whether the graph is bipartite or not.

A bipartite graph is a graph whose vertices can be divided into two sets such that each edge of the graph connects one vertex from the first set and another vertex from the second set.
We can also define a bipartite graph as a graph which can be colored using two colors such that no two adjacent vertices have the same color. 

For example: 
Input: 
4 4
0 1
0 2
1 3
2 3

An undirected graph to the above input is shown below:

In the given input, the number of vertices is 4, and the number of edges is 4.
In the input, following the number of vertices and edges, a list of pairs of numbers is given where each pair (u, v) denotes an edge between vertex u and v.
As per the input, there is an edge between vertex 0 and vertex 1.
The vertices 0 and 2 have an edge between them.

The vertices 1 and 3 have an edge between them.
The vertices 2 and 3 have an edge between them.

As the graph can be colored using two colors, and no adjacent vertices share the same color, the graph is bipartite. 

Ninja has organized the new year party and invited all the programmers for it, as being the programmer also has been invited by Ninja.

To detect whether the guest is a programmer or not, Ninja has set some tasks for them, such that only programmers can code them.

You have also been asked to solve and code the following task to verify your identity.

Given two integers, 'N' and 'K' find the number of permutation arrays of 'N' integers from 0 to 'N' - 1 satisfying the below condition.

There should be at least 'K' positions in the array such that 'ARR[I] = I' ( 0 <= I < N ) satisfies.

You are required to output the answer modulo 10^9 +7.

EXAMPLE:

Input: 'N' = 4 'K' = 3 
Output: 1

There is only one permutation [0, 1, 2, 3] such that a number of elements with 'ARR[I] = I' is 'K' = 3.

You are given an array 'arr' of length 'n', consisting of integers.

A subarray is a contiguous segment of an array. In other words, a subarray can be formed by removing 0 or more integers from the beginning and 0 or more integers from the end of an array.

Find the sum of the subarray (including empty subarray) having maximum sum among all subarrays.

The sum of an empty subarray is 0.

Example :

Input: 'arr' = [1, 2, 7, -4, 3, 2, -10, 9, 1]

Output: 11

Explanation: The subarray yielding the maximum sum is [1, 2, 7, -4, 3, 2].

Given a 2-dimensional matrix of size ‘N’ x ‘M’ and an integer K. Find the size of the largest square sub-matrix whose sum is less than or equal to K. The size of a matrix is the product of rows and columns in it.

A sub-matrix is a matrix obtained from the given matrix by deletion of several (possibly, zero or all) rows/columns from the beginning and several (possibly, zero or all) rows/columns from the end. A square matrix is a matrix which has the same number of rows and columns.

For Example

Note

If there is no square sub-matrix with a sum less than or equal to K, then return 0.

When users scroll social media, the often miss some posts when they are scrolling quickly. How will you ensure that the posts they scrolled past too fast will show up again in an infinite scroll? I was asked to code an algorithm for this as well. My approach was to listen for scroll events and measure the time that each post was on the screen for. I was also asked how I would persist this data in a way that makes it easy to retrieve.

Design a text compressor for Google Docs. I went with Huffman Encoding, since I had done a project on it earlier. I needed to optimise this for changes made in the middle of the document. The approach was to split the document into smaller parts, and encode each one independently.

Why I wanted to join the company, and why I would be a good fit.