## ALgeek

BAN USER- 0of 0 votes

AnswersGive a rectangular matrix(order mxn), each cell having only 0's or 1's, find the largest rectangular sub-matrix with equal number of 0's and 1's in it. O(m^2 n^2) solution possible... More time efficient algorithm required... Is O(mn) possible?

- ALgeek in India| Report Duplicate | Flag | PURGE

Amazon Software Engineer / Developer Algorithm - 0of 0 votes

AnswersThe maximum suffix of a string is the lexicographically largest suffix of the string. The maximum

- ALgeek in India

suffix problem is to find the maximum suffix of a given string. Linear time algorithm required.| Report Duplicate | Flag | PURGE

Google Software Engineer / Developer Algorithm - 1of 1 vote

AnswersYou are given n dices each with heads numbered from 1 to m. You are to throw the n dices and note down the sum of the numbers on each of the n dices. You'll be give a number x and its a win if the sum obtained is greater than x. The problem is the find out the winning probability given n, m and x.

- ALgeek in India

Note 1<=n<=100,

1<=m<=10,

m<=x<=n*m.| Report Duplicate | Flag | PURGE

Google Software Engineer / Developer Algorithm - 0of 2 votes

AnswersFor a stream of insertions and deletions, recall that x[j] = #insertions - #deletions of element j.

- ALgeek in India

Given such a stream satisfying x[j] >= 0 for all elements j, let

A = { j : x[j] > 0 }

Determining whether A is empty is easy: just check if the sum of all x[j]'s equals 0 (which is easily doable in a stream).

Problem: devise a small memory streaming algorithm to determine if |A| = 1.

Extensions: What about higher sizes of A? What if the promise is not satisfied and we define A to be the set of j's with x[j] not equal to 0.| Report Duplicate | Flag | PURGE

Google Software Engineer / Developer - 0of 0 votes

AnswersAlgorithm to output for a length m of a number stream, the value of the element j appearing in the stream for which freq[j]>m/2 with space complexity O(1) and time complexity O(m). Dont need to worry about the case when there are no elements with freq > m/2.

- ALgeek in India

The question in simpler terms:

In a collection of 'M' elements, some elements are repeated. Find the element which occurred at least M/2 times.| Report Duplicate | Flag | PURGE

Google Software Engineer / Developer

Rep**clarasbarr**, Korean Air Change Flight at Adap.tvI am ClaraBarr from California USA. Writes and records various different genres for television, film and other artists.Wrote several ...

Rep**thelmasaraht**, Applications Developer at Accolite softwareA child protection social worker is responsible for a variety of services designed to help families and children in a ...

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

Open Chat in New Window

Also note that if the input is not a string but a tree kind of structure(may be a n-ary tree), then inorder traversal would suffice.

- ALgeek November 26, 2012