## Flipkart Interview Question for Software Engineer / Developers

Country: India
Interview Type: Written Test

Comment hidden because of low score. Click to expand.
5
of 5 vote

For each found land, increment count by one, change it to non-L, and then recursively count its up/down/left/right. The trick is at changing to non-L before counting its adjacents.

``````public static int CountLand(char[,] s)
{
int result = 0;
int count = 0;

for (int x = 0; x < s.GetLength(0); x++)
{
for (int y = 0; y < s.GetLength(1); y++)
{
if (s[x, y] == 'L')
{
count = CountContiguous(s, x, y);
if (count > result)
{
result = count;
}
}
}
}

return result;
}

private static int CountContiguous(char[,] s, int x, int y)
{
if (x < 0 || x > s.GetLength(0) - 1 || y < 0 || y > s.GetLength(1) - 1 || s[x, y] != 'L')
{
return 0;
}
else
{
s[x, y] = 'A';
return 1 + CountContiguous(s, x - 1, y) + CountContiguous(s, x + 1, y) + CountContiguous(s, x, y - 1) + CountContiguous(s, x, y + 1);
}
}

public static void Test()
{
char[,] s = {{'L', 'L', 'L', 'L'},
{'L', 'L', 'W', 'L'},
{'L', 'W', 'L', 'W'},
{'W', 'W', 'L', 'L'}};
Console.WriteLine(CountLand(s)); //8
}``````

Comment hidden because of low score. Click to expand.
0

thnx........i was stuck in the issue that how to mark the visited cell........anyways it seems u have solved this issue quite efficiently

Comment hidden because of low score. Click to expand.
0

It is an exponential solution! Better use DFS/BFS to do it via connected component way.

Comment hidden because of low score. Click to expand.
0

@totallyred.... please explain it with code...thnk u

Comment hidden because of low score. Click to expand.
0

Its O(n^3) ( see recursion as replacement for BFS queue )

Comment hidden because of low score. Click to expand.
0

@Biswajit Sinha:
Model this as an undirected graph problem such that:
Each node corresponding to a cell where cell val='L' (in the 2D array)
And then draw an edge between the nodes which are adjacent to each other (in the original 2D array).For eg.
if the 2D array was:
L1 L2 W3
L4 W5 L6
W7 W8 L9
Then the nodes would be L1 L2 L4 L6 L9 and the edges would be
L1-L2 ;L1-L4;L6-L9

now do a BFS(or DFS) to find all the connected components in this graph and then count the number of nodes in each connected component of this graph. The component which has the maximum number of nodes is the one with longest land area and the number of nodes in this component is your answer!

@ Cerberuz: If u do this via the above approach it is O(number of nodes+number of edges)=O(N^2+N^2)=O(N^2) and not O(N^3).
But if you do it via the other approach it is exponential, You can test it by running it on a sample case with 20-30 nodes.

Comment hidden because of low score. Click to expand.
0

@totallyRed hi buddy.........your solution is nice.........i got it.....but the solution which was stated above is not exponential..... as we are not visiting those cells which we have already visited...in this way the solution is restricted to O(n^2)

Comment hidden because of low score. Click to expand.
0

yeah... actually if u see the above solution is also doing the DFS only! So both the solutions are equivalent.

Comment hidden because of low score. Click to expand.
0

these are interesting solutions. i don't understand, tho, where the DP comes in?

Comment hidden because of low score. Click to expand.
0

The recursive solution is O(n^3).
The double loop will be called for all x,y <= n => O(n^2) + Inside y loop bfs will be called at least once => O(n)
=> O(n^3)
The way of implementation can be improved to reduce complexity to O(n^2) by avoiding complete double loop run and stopping when whole graph/matrix has been traversed.

Comment hidden because of low score. Click to expand.
1
of 1 vote

Use BFS for each disjoint land piece
OR
DFS for finding all connected components( maximum size over all connected components will be the answer )

Comment hidden because of low score. Click to expand.
0

how would you do a DFS or BFS search on it because the given 2D array is not an adjacency matrix.......to make it adjacency you need to create a 16by16 matrix which would be higher when the value of n is higher

Comment hidden because of low score. Click to expand.
0

It seems Xiang has already cleared that :)

Comment hidden because of low score. Click to expand.
0

Is it 4 connected component or 8 connected component?
I mean should we consider the diagonals of a cell?

Comment hidden because of low score. Click to expand.
0

It has been mentioned clearly in the question itself.........read it properly

Comment hidden because of low score. Click to expand.
0
of 0 vote

This can be modelled as a graph problem.
Assume each cell to be a node in the graph. And there is an edge between two nodes iff their corresponding cell values are L and L. Now do a BFS to find all the connected components. Then find the connected component which has maximum number of nodes and the number of nodes in this component is ur answer.

Comment hidden because of low score. Click to expand.
0
of 0 vote

@totallyred

``````#include<stdio.h>
#include<conio.h>
static char A[4][4] ={{'L','L','L','L'},{'L','L','W','L'},{'L','W','L','W'},{'W','W','L','L'}};

struct Graph
{
int v;
int e;
};
int visited[20]={0};
int count = 0;
int max = 0;
struct Graph* createAdjMatrix(int n,int l,int t[][4])
{
struct Graph *G = (struct Graph*)malloc(sizeof(struct Graph));
int i,j;
if(!G)
{
printf("memory error\n");
return NULL;
}
G->v=G->e=l;
for(j=0;j<G->v;j++)
{
}
for(i=0;i<G->v;i++)
{
for(j=0;j<G->v;j++)
{
}
}
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(t[i][j]!=-1)
{
int x=t[i][j];
if(((i-1)>=0&&(i-1)<n)&&(j>=0&&j<n)&&(t[i-1][j]!=-1))
{
}
if(((i+1)>=0&&(i+1)<n)&&(j>=0&&j<n)&&(t[i+1][j]!=-1))
{
}
if((i>=0&&i<n)&&((j-1)>=0&&(j-1)<n)&&(t[i][j-1]!=-1))
{
}
if((i>=0&&i<n)&&((j+1)>=0&&(j+1)<n)&&(t[i][j+1]!=-1))
{
}
}
}
}
return G;
}

void DFS(struct Graph *G,int u)
{
visited[u]=1;
int i;
for(i=0;i<G->v;i++)
{
{
count++;
DFS(G,i);
}
}
}

void DFStraversal(struct Graph *G)
{
int i;
for(i=0;i<G->v;i++)
{
visited[i]=0;
}
for(i=0;i<G->v;i++)
{
if(!visited[i])
{
//printf("next ")
count=1;
DFS(G,i);
if(count>max)
{
max=count;count=0;
}
else
count = 0;
}
}
}

int main()
{
int i,j,temp[4][4] ={0};
int c=0;
for(i=0;i<4;i++)
{
for(j=0;j<4;j++)
{
if(A[i][j]=='L')
{
temp[i][j]=c;
c++;
}
else
{
temp[i][j]=-1;
}

}
}
DFStraversal(gh);
printf("maximum land= %d\n",max);
getch();
return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

int main(){
int n;
cin>>n;
int a[n][n];
int count_0 = 0;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cin>>a[i][j];
if(a[i][j]==0){
count_0++;
}
}
}

int count = 0;
int seen[n*n];
memset(seen,0,sizeof(int)*n*n);
int curr = 0,max = 0;
int iter = 0;

while(count < count_0){
while(a[curr/n][curr%n] || seen[curr]){
curr++;
}

queue<int> q;
q.push(curr);
count++;
seen[curr] = 1;

int m = 0;
while(!q.empty()){
int x = q.front();
q.pop();
m++;
if(x%n < n-1 && !a[(x+1)/n][(x+1)%n] && !seen[x+1]){
q.push(x+1);
seen[x+1] = 1;
count++;
}
if(x/n < n-1 && !a[(x+n)/n][(x+n)%n] && !seen[x+n]){
q.push(x+n);
seen[x+n] = 1;
count++;
}
}

if(m > max){
max = m;
}
}
cout<<max<<endl;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Above approach assumes 0 instead of 'L' and 1 instead of 'R'.
Done using BFS on connected components!

Comment hidden because of low score. Click to expand.
0
of 0 vote

My solution is: if we use a bottom up approach to store the results from right bottom corner of the array and we store the results in additional 2d array M and original array was A,

Then for every A[i][j],

if A[i][j]=="W", that implies cannt go through it, so M[i][j]=0;

if A[i][j]=="L",
then we have to check 3 cases:
a) if its adjacent right cell A[i][j+1] is "W", then no land cannt be extended via right point, So M[i][j]=M[i+1][j]+1;
b) if its adjacent down cell A[i+1][j] is "W", then no land cannt be extended via its bottom point, So M[i][j]=M[i][j+1]+1;
c) if both A[i+1][j] && A[i][j+1] is Land, that means M[i][j] will be sum of both. But land starting from A[i][j+1] and spreading right and below as much as possible and land starting from A[i+1][j] and spreading has a common intersection which is considered twice which starts at point A[i+1][j+1].. So have to delete this intersection once :
So in this case ,
M[i][j]=M[i][j+1] + M[i][j+1] +1 -M[i+1][j+1].

Comment hidden because of low score. Click to expand.
0
of 0 vote

Linked List implementation of disjoint sets. Optimizes Merge/Union procedure. IF you use disjoint set forest Find operation is faster.

Replace Y,N with L,W for my solution.

``````var input = '5\nYYNNN\nYYYNN\nNYYNN\nNNNYN\nNNNNY'
console.log(input);
//above solution should be 3 because the components are
//{0,1,2}, because {0,1} and {1,2} therefore {0,1,2}
//{3}
//{4}

//MIT license, authored by Ling Qing Meng

//'4\nYYNN\nYYYN\nNYYN\nNNNY'

var reformat = input.split(/\n/);
var N = reformat[0];
for (var i = 1; i < reformat.length; i++) {
}

//for (each person x from 1 to N) CREATE-SET(x)
var sets = [];
for (var i = 0; i < N; i++) {
sets.push(s);
}

//populate friend potentials using combinatorics, then filters
var people =  [];
var friends = [];
for (var i = 0; i < N; i++) {
people.push(i);
}
var potentialFriends = k_combinations(people,2);
for (var i = 0; i < potentialFriends.length; i++){
friends.push(potentialFriends[i]);
}
}

//for (each pair of friends (x y) ) if (FIND-SET(x) != FIND-SET(y)) MERGE-SETS(x, y)
for (var i = 0; i < friends.length; i++) {
var x = friends[i][0];
var y = friends[i][1];
if (FindSet(x) != FindSet(y)) {
sets.push(MergeSet(x,y));
}
}

for (var i = 0; i < sets.length; i++) {
//sets[i].traverse();
}
console.log('How many distinct connected components?',sets.length);

//Linked List data structures neccesary for above to work
function Node(){
this.data = null;
this.next = null;
}

this.tail = null;
this.size = 0;

// Add node to the end
var node = new Node();
node.data = data;
this.tail = node;
} else {
this.tail.next = node;
this.tail = node;
}
this.size++;
};

this.contains = function(data) {
return this;
while (next !== null) {
if (next.data === data) {
return this;
}
next = next.next;
}
return null;
};

this.traverse = function() {
var toPrint = '';
while (current !== null) {
//callback.call(this, current); put callback as an argument to top function
toPrint += current.data.toString() + ' ';
current = current.next;
}
console.log('list data: ',toPrint);
}

this.merge = function(list) {
var next = current.next;
while (next !== null) {
current = next;
next = next.next;
}
this.size += list.size;
return this;
};

this.reverse = function() {
return;
return;

while (nextNode != null) {
currentNode = nextNode;
nextNode = currentNode.next;
currentNode.next = prevNode;
prevNode = currentNode;
}
return this;
}

}

/**
* GENERAL HELPER FUNCTIONS
*/

function FindSet(x) {
for (var i = 0; i < sets.length; i++){
if (sets[i].contains(x) != null) {
return sets[i].contains(x);
}
}
return null;
}

function MergeSet(x,y) {
var listA,listB;
for (var i = 0; i < sets.length; i++){
if (sets[i].contains(x) != null) {
listA = sets[i].contains(x);
sets.splice(i,1);
}
}
for (var i = 0; i < sets.length; i++) {
if (sets[i].contains(y) != null) {
listB = sets[i].contains(y);
sets.splice(i,1);
}
}
var res = MergeLists(listA,listB);
return res;

}

function MergeLists(listA, listB) {
listA.merge(listB);
listC = listA;
return listC;
}

//access matrix by i,j -> returns 'Y' or 'N'
function isFriend(matrix, pair){
return matrix[pair[0]].charAt(pair[1]);
}

function k_combinations(set, k) {
var i, j, combs, head, tailcombs;
if (k > set.length || k <= 0) {
return [];
}
if (k == set.length) {
return [set];
}
if (k == 1) {
combs = [];
for (i = 0; i < set.length; i++) {
combs.push([set[i]]);
}
return combs;
}
// Assert {1 < k < set.length}
combs = [];
for (i = 0; i < set.length - k + 1; i++) {
tailcombs = k_combinations(set.slice(i + 1), k - 1);
for (j = 0; j < tailcombs.length; j++) {
}
}
return combs;
}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.