Flipkart Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: Written Test
thnx........i was stuck in the issue that how to mark the visited cell........anyways it seems u have solved this issue quite efficiently
It is an exponential solution! Better use DFS/BFS to do it via connected component way.
@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.
@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)
yeah... actually if u see the above solution is also doing the DFS only! So both the solutions are equivalent.
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.
Use BFS for each disjoint land piece
OR
DFS for finding all connected components( maximum size over all connected components will be the answer )
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
Is it 4 connected component or 8 connected component?
I mean should we consider the diagonals of a cell?
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.
@totallyred
@cerberuz.............I think my code met your requirement........please check and comment
#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 **Adj;
};
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;
G->Adj = (int**)malloc(sizeof(int*)*G->v);
for(j=0;j<G->v;j++)
{
G->Adj[j] = (int*)malloc(sizeof(int)*G->v);
}
for(i=0;i<G->v;i++)
{
for(j=0;j<G->v;j++)
{
G->Adj[i][j]=0;
}
}
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))
{
G->Adj[x][t[i-1][j]]=1;
G->Adj[t[i-1][j]][x]=1;
}
if(((i+1)>=0&&(i+1)<n)&&(j>=0&&j<n)&&(t[i+1][j]!=-1))
{
G->Adj[x][t[i+1][j]]=1;
G->Adj[t[i+1][j]][x]=1;
}
if((i>=0&&i<n)&&((j-1)>=0&&(j-1)<n)&&(t[i][j-1]!=-1))
{
G->Adj[x][t[i][j-1]]=1;
G->Adj[t[i][j-1]][x]=1;
}
if((i>=0&&i<n)&&((j+1)>=0&&(j+1)<n)&&(t[i][j+1]!=-1))
{
G->Adj[x][t[i][j+1]]=1;
G->Adj[t[i][j+1]][x]=1;
}
}
}
}
return G;
}
void DFS(struct Graph *G,int u)
{
visited[u]=1;
int i;
for(i=0;i<G->v;i++)
{
if(!visited[i]&& G->Adj[u][i]==1)
{
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;
}
}
}
struct Graph *gh = createAdjMatrix(4,c,temp);
DFStraversal(gh);
printf("maximum land= %d\n",max);
getch();
return 0;
}
#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;
}
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].
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'
//Read Input, preformatting
var reformat = input.split(/\n/);
var N = reformat[0];
var adjMatrix = [];
for (var i = 1; i < reformat.length; i++) {
adjMatrix.push(reformat[i]);
}
//for (each person x from 1 to N) CREATE-SET(x)
var sets = [];
for (var i = 0; i < N; i++) {
var s = new LinkedList();
s.add(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++){
if (isFriend(adjMatrix,potentialFriends[i]) === 'Y'){
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;
}
function LinkedList(){
this.head = null;
this.tail = null;
this.size = 0;
// Add node to the end
this.add = function(data){
var node = new Node();
node.data = data;
if (this.head == null){
this.head = node;
this.tail = node;
} else {
this.tail.next = node;
this.tail = node;
}
this.size++;
};
this.contains = function(data) {
if (this.head.data === data)
return this;
var next = this.head.next;
while (next !== null) {
if (next.data === data) {
return this;
}
next = next.next;
}
return null;
};
this.traverse = function() {
var current = this.head;
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 current = this.head;
var next = current.next;
while (next !== null) {
current = next;
next = next.next;
}
current.next = list.head;
this.size += list.size;
return this;
};
this.reverse = function() {
if (this.head == null)
return;
if (this.head.next == null)
return;
var currentNode = this.head;
var nextNode = this.head.next;
var prevNode = this.head;
this.head.next = null;
while (nextNode != null) {
currentNode = nextNode;
nextNode = currentNode.next;
currentNode.next = prevNode;
prevNode = currentNode;
}
this.head = 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) {
var listC = new LinkedList();
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++) {
head = set.slice(i, i+1);
tailcombs = k_combinations(set.slice(i + 1), k - 1);
for (j = 0; j < tailcombs.length; j++) {
combs.push(head.concat(tailcombs[j]));
}
}
return combs;
}
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.
- Xiang September 09, 2012