## justhack4fun688

BAN USER- 0of 2 votes

AnswersGiven a N*N adjacency matrix of graph I need to find the size of maximum set of vertices that do not share any common edge between any two vertices of the graph.

- justhack4fun688 in United States

Like : Say we have 3*3 matrix as

0 1 0

1 0 1

0 1 0

Then here answer is 2 as vertex 1 and vertex 3 dont have any edge in common.

I was asked this question in my interview to implement it in c++.| Report Duplicate | Flag | PURGE

Adobe Software Engineer / Developer Algorithm - 0of 2 votes

AnswerGiven a N*M grid I want to find biggest submatrix not necessarily a square one that has all the value in it same.

- justhack4fun688 in United States

Like

If N=4 and M=5 and matrix is

1 2 3 4 5

1 2 2 2 3

4 2 2 2 6

3 4 5 6 7

Then here answer will be matrix will be

2 2 2

2 2 2

So I need to find upper leftmost coordinate of this submatrix that is [2,2] and bottommost right coordinate that is [3,4].

I was to write a code for it in c++ in my interview| Report Duplicate | Flag | PURGE

Accenture Software Engineer Intern Algorithm - -3of 3 votes

AnswerGiven N Vertices and M Edges. Each Edge connects two vertices.

- justhack4fun688 in United States

There is at most one way to move between each pair of vertices.

Each vertex is either locked or unlocked .There is a perfect path between two different vertices if both vertices are unlocked, and are connected with each other by some way.

The question is What is the number of pairs of vertices, which have a perfect path between them and also What is the number of the vertices, which have at least one perfect path passing through that vertex.

NOTE : There is at most one way to move between each pair of vertices, that is, the given graph is a forest

EXAMPLE : Say we have 6 Vertices and 5 Edges.

A=[1,1,1,1,1,0] It shows that A[i]=1 if ith vertex is unlocked otherwise 0.

Let the connected pair of vertices are : (1,2),(1,6),(1,5),(2,4),(4,3)

Here ,Answer for first question is 10 and second one is 5.

So,interviewer asked me to device an efficient algorithm for it and also code it in c++| Report Duplicate | Flag | PURGE

Amdocs Software Engineer Intern Algorithm - 0of 0 votes

AnswersGiven a 2d array N*M made of only 1's and 0's . I need to find a maximum subarray(square or rectangle) between two rows of the given 2d array which has all ones inside it. I need to find count of ones in this maximum subarray

- justhack4fun688 in United States

EXAMPLE : Let N=4 and M=5 and the array be

1 0 1 1 0

1 0 1 1 1

0 1 1 1 1

0 0 0 0 1

Now if their are Q(say here it be 2) queries each describing upper and lower row between which we need to find this subarray.

Query 1 : 1 1(means start at row 1 and end also at row 1).Then we can clearly see answer will be 2

Query 2 : 2 3(means start at row 2 and end at row 3).Then answer will be 6 here.

Now,if queries can be very large in number(say upto 10^6) .How to tackle this problem| Report Duplicate | Flag | PURGE

Accenture Software Engineer / Developer Algorithm - 0of 0 votes

AnswersGiven a rectangular grid of N*M (1-based indexing) in which their are k monsters on k different cells.Now we need to answer Q queries in which we will be given lowest row number(L) and highest row number(H) we need to tell maximum area of rectangle between those rows that don't have a monster.(Here area of rectangle means count of cells only)

- justhack4fun688 in India

Example : Say we have a grid of 4 * 5 (mean n=4 and m=5) and monsters are located on 7(=k) cells which are (1,3) , (1,4) , (2,1) , (2,4) , (3,2) , (4,1) , (4,2) and let we have 1 query in which L=3 and H=4 then the maximum area is 6 here.

Now if the queries are very large say 10^6.Then how to tackle this problem.Is their any dynamic approach or so for doing it?| Report Duplicate | Flag | PURGE

Adobe Software Development Manager - 1of 1 vote

AnswersGiven an array A of n numbers we can perform 3 operations on its array elements.Their are n operations in total and ith operation is to be applied on elements from ith index to last element of the array.

- justhack4fun688 in United States

1.Reverse(R) : Reverse the elements from A[i..n]

2.Add(A) : Add X to each element from A[i..n]

3.Multiply(M) : Multiply Y to each element from A[i..n]

Note : In 2nd and 3rd operation all calculations done modulo Z.

I need to find final array after nth operation is done.

EXAMPLE : Say n=3 and array has 3 elements [1,1,1] and lets X=2 ,Y=3 , Z=1000 .If sequence of operation is ARM which means 1st operation is Add,2nd operation is Reverse and 3rd one is Multiply.Then resultant array after final operation will be [3,3,9].

I was needed to calculate this array in efficient manner in c++/java| Report Duplicate | Flag | PURGE

Flipkart Software Analyst Algorithm - -1of 3 votes

AnswersGiven an undirected graph with n vertices and m edges. How to check for perfect matching in the graph.(Perfect matching means each vertex has degree 1).Provide a code in c++.

- justhack4fun688 in United States| Report Duplicate | Flag | PURGE

Adobe Software Development Manager Algorithm - 0of 0 votes

AnswersCalculate number of DISTINCT palindromic substrings in a string with help of suffix array or a trie.

- justhack4fun688 in India

Like if aba is string the their are 3 distinct palindromic subsrings:{a,aba,b}| Report Duplicate | Flag | PURGE

Amazon Software Engineer / Developer Algorithm - 0of 0 votes

AnswersI want to calculate number of DISTINCT palindromic substrings in a string.How to do it?

- justhack4fun688 in United States

Like if aba is string the their are 3 distinct palindromic subsrings:{a,aba,b}

length of string could be 10^5 range.So i dont think O(n^2) solution will work.So interviewer wanted some better algorithm.| Report Duplicate | Flag | PURGE

- -1of 1 vote

AnswersI want to calculate number of DISTINCT palindromic substrings in a string.How to do it?

- justhack4fun688 in India

Like if aba is string the their are 3 distinct palindromic subsrings:{a,aba,b}

length of string could be 10^5 range.So i dont think O(n^2) solution will work.So the interviewer required some better algorithm.But i know only O(n^2) one.| Report Duplicate | Flag | PURGE

Adobe Software Engineer / Developer Algorithm

- 0 Answers
**Distinct palindromic count**I want to calculate number of DISTINCT palindromic substrings in a string.How to do it?

- justhack4fun688 December 11, 2013

Like if aba is string the their are 3 distinct palindromic subsrings:{a,aba,b}

length of string could be 10^5 range.So i dont think O(n^2) solution will work.So plz help| Flag | PURGE

@Hector But i have large numebr of queries.If i am gonna do it as maximum sum in 2d array then its time complexity will be very large as for each query i need to calculate maximum array.Moreover how u are sure that maximum array will not have any 0/-1(acc to you) in it?Please read question carefully before answering it

- justhack4fun688 January 09, 2014@Ininiaa I am not saying about this.i am talking about if (op==A) {add+=X;}

if (op==M) {mul*=Y; add*=Y;}

Here there is no mod operation

@Ininiaa and wht about avoiding overflow?

- justhack4fun688 January 05, 2014@Ininiaa Why u set swap_ptr to 2 here?And how are you sure that on your first step the add and mult will not overflow as the caluclation can go upto 10^18.

- justhack4fun688 January 05, 2014@Ininiaa Could you provide code in c++/java.?Thanx in advance

- justhack4fun688 January 05, 2014@glebtstepanov1992 Length of sequence is also n(=length of array).And how to do compute blocks as for ith operation we need to change elements from i to n. rather than all elements of array.

- justhack4fun688 January 05, 2014@Ehsan Their can be multiple edges also in the graph and initially graph need not have all vertices with degree 1.I need to tell can their be perfect matching in a graph after removal of some of its edges.

- justhack4fun688 January 04, 2014@saurabh So finding perfect matching itself means that can we delete some edges from our given graph so that each node has degree 1.I need to find this in short

- justhack4fun688 January 03, 2014I think you are wrong.Consider the undirected graph with 4 vertices and 6 edges say (1,2),(1,3),(1,4),(2,3),(2,4),(3,4) .According to u it dont haveperfect matching.But in actual it has.

- justhack4fun688 January 03, 2014Perhaps a piece of code might be helpful.Their are some sort of ambiguties

- justhack4fun688 January 03, 2014will it provide maximum count?or sorting on basis of end time will provide maximum?

- justhack4fun688 January 03, 2014@Diego Giagio YA. i know it..its O(n^2). Now for a string of length 10^5 it will take huge memory.Dont u think so?

- justhack4fun688 December 16, 2013@leet coder could you provide a piece of code plz..

- justhack4fun688 December 16, 2013@Diego Giagio the code is better undoubtdly. but last problem is space.How much is its space complexity.? analyse it

- justhack4fun688 December 16, 2013@Diego Giagio What is complexity of your purposed algorithm?

- justhack4fun688 December 15, 2013@Elad Your algorithm seems right.But tooo slow for larger strings.

- justhack4fun688 December 15, 2013@Diego Giagio sorry to say but still wrong for strings like "aaaa".

- justhack4fun688 December 15, 2013@Diego Giagio It still give wrong answer for string "abba"

- justhack4fun688 December 15, 2013@ajeet ur code give 4 as result on "diaid" but answer should be 5 : {d,i,a,iai,diaid}

- justhack4fun688 December 12, 2013Your code gives one palindromic substring for "aa" but in actual their are two :a,aa

- justhack4fun688 December 12, 2013Your code gives {aba,a,a} as result.Had you checked it out?

- justhack4fun688 December 12, 2013I had gone through this.But not able to modify it to count distinct palindromes.Could you do that plz?

- justhack4fun688 December 12, 2013Could u plz provide me code to implement Manacher algorithm to count distinct palindromes. I need it

- justhack4fun688 December 12, 2013could you plz provide your code in java..as i am a java coder

- justhack4fun688 December 12, 2013**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

Open Chat in New Window

@BigKdotAtTdot Could u please provide a code in c++ to do the same ?And yeah graph is undirected.

- justhack4fun688 March 10, 2014