Microsoft Interview Question Software Engineer / Developers
Country: United States
@Loler , can you please help me to understand and provide any pseudo code, Thanks in advance
We can actually improve the bounds to guaranteed O(n) instead of expected O(n) by noting that the sum is bounded between -n and n. We can just use an array instead of a hash table.
consider the list: 0,1,1,1,0,0,0,1
Your algo gives count[0]=3
but in reality it is 4 i.e. (0,1),(1,6),(3,4) and (6,7).
Am I misunderstanding something?
@alex: I don't understand your question. Can you please elaborate?
btw, I ran the above code on your input and the algorithm gives a value of (8,8) for total_count and max_len and that matches the brute force value. (Of course, both the methods could have bugs...)
I guess the number of subarrays with number of 0s equal to number of 1s is proportional to n^2. How is it feasible to find all such subarrays in less than O(n^2) time.
Example test case: 01010101010101
I think for the second part you can follow this approach but for finding the first part you can't iterate all the subarrays in O(n).
I thought of this same approach too. I will write here why I did so that it helps others think of it this way if they can't think of another more efficient approach. Basically, the running sum with hashtable approach seems to work for most problems where sum of a sub-array is desired. Here the sum of the sub-array is 0 considering zeroes as -1s and ones as 1s.
for the second part I think we can do following
traverse from left to right: and store the longest,second longest,third longest lengths of zeros and one in an array...if required we can store start and end index of all the lengths.
Then we can compare the arrays and determine the max sub sequence of zeros and ones
Please correct me if I am wrong
Well for the second part, replace all 0s by -1, now this problem reduced to finding the longest size subarray with sum=0. We can use a hashmap to keep track of cumulative sums and easily find that in O(n) time.
However we can't do better than O(n^2) for solving first part because in worst number of subarrays with equal no of 0s and 1s could be proportional to n^2. Consider this test case: 0101010101.
Sounds like a typical DP problem.
Let sums[i][j] be the accumulated sum from position i to j inclusive in the given sequence where for '0' we add -1 to the sum and for '1' we add 1.
The problem can be degraded to find all the accumulated sum in sums array that equals 0.
While printing out all possible solutions we can find the maximum.
Program runs in O(n^2)
class Program
{
static void Main(string[] args)
{
Longest("01100011");
Console.ReadLine();
}
static void Longest(string s)
{
if (string.IsNullOrEmpty(s)) return;
var sums = new int[s.Length, s.Length];
for (int i = 0; i < s.Length; i++)
{
for (int j = i; j < s.Length; j++)
{
if (i == j)
{
sums[i, j] = (s[i] == '0') ? -1 : 1;
}
else
{
sums[i, j] = sums[i, j - 1] + ((s[j] == '0') ? -1 : 1);
}
}
}
int max = 0, maxStart = 0, maxEnd = 0;
for (int i = 0; i < s.Length; i++)
{
for (int j = i; j < s.Length; j++)
{
if (sums[i, j] == 0)
{
for (int k = i; k <= j; k++)
{
Console.Write(s[k]);
}
Console.WriteLine();
if (j - i + 1 > max)
{
max = j - i + 1;
maxStart = i;
maxEnd = j;
}
}
}
}
Console.WriteLine("Max is:");
for (int k = maxStart; k <= maxEnd; k++)
{
Console.Write(s[k]);
}
}
}
import java.util.*;
public class Maxlen01 {
public static void main(String[] args) {
boolean b=false;
int a[]=new int[20];
int n,nof1=0,nof0=0;
int max=0,equal=0,c=0;
Scanner sc=new Scanner(System.in);
System.out.print("enter the length of the 0s and 1s");
n=sc.nextInt();
System.out.print("enter the oreder of the 0s and 1s");
for(int i=0;i<n;i++)
{
a[i]=sc.nextInt();
}
if(a[0]==0)
nof0++;
else
nof1++;
System.out.print("entry1");
for(int i=1;i<n;i++)
{
if(a[i]==0)
nof0++;
else
nof1++;
if(nof0==nof1)
{
b=true;
equal++;
if(max<nof0)
max=nof0;
}
if(a[i]!=a[i+1])
c++;
if(b || c==2)
{ b=false;
nof0=0;
nof1=0;
c=0;
}
}
System.out.println("no of equal lent 0s and 1s:"+equal);
System.out.println("max lent 0s and 1s:"+max);
}
}
sample o/p:enter the length of the 0s and 1s6
enter the oreder of the 0s and 1s0 1 0 0 1 1
entry1no of equal lent 0s and 1s:2
max lent 0s and 1s:2
o/p2:enter the length of the 0s and 1s14
enter the oreder of the 0s and 1s1 1 0 0 1 1 1 0 0 0 1 1 0 0
entry1no of equal lent 0s and 1s:3
max lent 0s and 1s:3
If it is subsequence the solution is simple as suggested by loler in his comment but if u meant subarray then i think u can use Kadane's algo with little modification.Add 1 to the sum if u find a 1 and substract 1 if u find a zero.Maintain a count and left index of current sum for the length of subarray and keep checking if the sum is zero.
Memoization can be used, time and space complexity O(n^2), n= len(sequnce).
public class Main {
private static int[] sequence = {1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 0, 0, 1};
/* on index i, j lets store #ones - nr zeros between position i and j */
private static int [][] diff = new int[sequence.length][sequence.length];
static int longestI = -1;
static int longestJ = -1;
static int longestLength = 0;
private static void evaluateSequecen(int i, int j) {
if (diff[i][j] == 0) {
System.out.printf("Subsequence with the same number of cell is from i = %d to i=%d (", i, j);
for (int k = i; k <= j; k ++) {
System.out.printf("%d,", sequence[k]);
}
System.out.printf(")\n");
if (j - i > longestLength) {
longestLength = j- i; longestI = i; longestJ = j;
}
}
}
public static void main(String[] args) {
int nrOnes = 0;
int nrZeros = 0;
/* lets do first row manualy */
for (int j = 0; j < sequence.length; j ++) {
if (sequence[j] == 0) {
nrZeros ++;
} else{
nrOnes ++;
}
diff[0][j] = nrOnes - nrZeros;
evaluateSequecen(0, j);
}
/* use memoidation tofill rest of the table */
for (int i = 1; i < sequence.length; i++) {
for (int j = i; j< sequence.length; j++) {
diff[i][j] = diff[i-1][j] - diff[i-1][i-1];
evaluateSequecen(i, j);
}
}
System.out.printf("Longest subsequence found on position from %d to %d", longestI, longestJ);
}
}
1. all the subsequences where number of 0s = number of 1s
2. max length subsequence where number of 0s = number of 1s
example : 0 1 1 1 0 1 0 1 1 0 1 0 0 1 1 0 0 0 1
these are the steps of dry running
1] 0 1 1 1 0 1 0 1 1 0 1 0 0 1 1 0 0 0 1
01, 011101011010011000
2] 1 1 0 1 0 1 1 0 1 0 0 1 1 0 0 0 1
nil
3]1 1 0 1 0 1 1 0 1 0 0 1 1 0 0 0 1
1 1 0 1 0 1 1 0 1 0 0 1 1 0 0 0
4] 1 0 1 0 1 1 0 1 0 0 1 1 0 0 0 1
1 0 1 0 1 1 0 1 0 0
1 0 1 0 1 1 0 1 0 0 1 1 0 0
1 0 1 0 1 1 0 1 0 0 1 1 0 0 0 1
5] 0 1 0 1 1 0 1 0 0 1 1 0 0 0 1
0 1 0 1 1 0
0 1 0 1 1 0 1 0 0 1
0 1 0 1 1 0 1 0 0 1 1 0
6] 1 0 1 1 0 1 0 0 1 1 0 0 0 1
1 0 1 1 0 1 0 0
1 0 1 1 0 1 0 0 1 1 0
void findtheLargestSequence()
{
int a[] = {0, 1, 1, 1, 0, 1, 0 ,1, 1, 0 ,1, 0, 0 ,1, 1, 0, 0 ,0 ,1 };
int length = sizeof(a)/sizeof(a[0]);
int maxcount = 0,Zeros_count,OnesCount,start = 0,end = 0;
for(int i = 0; i < length; i ++)
{
Zeros_count = 0; OnesCount= 0;
for(int j = i ; j < length; j++)
{
if(a[j]== 0) Zeros_count++;
if(a[j]==1) OnesCount++;
if(Zeros_count== OnesCount)
{
int count = j-i ;
if(count>maxcount)
{
maxcount = count; start = i; end = j;
}
}
}
}
printf("the longest o's and 1's sequence is :" );
for(int i = start ; i < end ; i++)
{
printf("%d",a[i]);
}
}
void subprint(char* A, int s, int e){
cout << endl << "{ ";
for (int i = s; i < e+1; i++){
cout << A[i] << ",";
}
cout << "}";
};
void oneequalzero(){
char *A = "10101100110101100110101";
int a = strlen(A);
int thissum = 0;
int sum = 0;
int start = 0;
int end = 0;
int gstart = 0;
int gend = 0;
for (int i = 0; i < a; i++){
thissum = 0;
start = i;
//gstart = i;
for (int j = i; j < a; j++){
if (A[j] == '1'){
thissum++;
end = j;
//gend = j;
}
else if (A[j] == '0'){
thissum--;
end = j;
//gend = j;
}
if (!thissum){
subprint(A, start, end);
cout << "S:" << start << " E:" << end <<endl;
if ((j - i)>sum){
gstart = i;
gend = j;
sum = gend - gstart;
}
}
}
}
subprint(A, gstart, gend);
cout << "GS:" << gstart << " GE:" << gend << endl;
};
Assuming by subsequence you actually meant _subarray_, an O(n) time algorithm is possible.
Traverse the array from left to right, and maintain a running sum of number of ones - number of zeroes.
You also have a hashtable keyed on the running sum, and which contains information regarding the number of times that running sum appears, and also the leftmost index for which that sum appears.
Note: Even though the code uses hashtable below, as Eugene pointed out, since the running_sum is between -n and n, we can always use an array, guaranteeing O(1) lookups.
Using this structure, we can compute the answers for both 1 and 2.
For instance, to compute the number, we check if the running sum appeared before. If it appeared k times before, then we get k new sub-arrays with equal number of zeroes and ones.
The max length uses the left most such idx.
Here is sample code in python (with random test cases). The O(n) method is named equal_count.
def equal_count(lst): bits = [-1,1] counts = {0: (1,-1)} run_sum, total_count, max_len = 0,0,0 cur_idx = -1 for bit in lst: cur_idx += 1 run_sum += bits[bit] if run_sum in counts: c, idx = counts[run_sum] total_count += c if cur_idx - idx > max_len: max_len = cur_idx - idx counts[run_sum] = c+1, idx else: counts[run_sum] = 1, cur_idx return total_count, max_len def equal_count_brute(lst): n = len(lst) total_count, max_len = 0,0 for i in range(0,n): for j in range(i+1, n+1): count = sum (map (lambda x: -1 if x == 0 else 1, lst[i:j])) if count == 0: total_count += 1 if j-i > max_len: max_len = j-i return total_count, max_len def main(): lsts = [[0], [1], [1,1], [1,0], [1,0,1],[1,0,0,1], [0,1,0,1,0,1]] for lst in lsts: print equal_count(lst), equal_count_brute(lst) if __name__ == "__main__": main()If you actually meant _subsequence_, then I suppose the problem is easier and more mathematical than programming.
- Loler March 05, 2013Count the number of zeroes, and number of ones. Find the number of ways to pick r zeroes and r ones, and add up over possible r. The largest r (or rather 2r) will you give you the max length subsequence.