Interview Question


Country: India




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

def counter():
	str = '0010110100'
	
	length = 0
	ones = 0
	max = 0
	
	for c in str:
		if c == '1':
			length += 1
			ones += 1
		else:
			length = ones + 1
			ones = 0

		if length > max:
			max = length
			
	print(max)

- . August 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

My solution was to maintain two counts. The first is a hypothetical count (what would happen if I flipped that last '0') and another count that only keeps track of a chain of '1's.

When I encounter a new '0', I trash the hypothetical chain and replace it with the current chain of '1's.

O(n)

var str = '00101101110100';

var chain = [0, 0];
var position = 0;

var longest = {
    position: 0,
    length: 0
};

for (var i in str) {

    if (str[i] == '0') {

        //end the chain
        if (longest.length < chain[0]) {
            longest.position = position;
            longest.length = chain[0];
        }

        //start another
        position = i;
        chain[0] = chain[1] + 1;
        chain[1] = 0;
        continue;
    }

    chain[0]++;
    chain[1]++;
}

console.log(longest);

- John M August 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

can anyone tell me , In which language is the code written. I wanted to test the code on some different inputs .

Will this work for input "0111110"

- Greg August 29, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Greg

JavaScript, and yes.

- John M. December 01, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Although time contraint is more , this will do the job...

public class FlipZero {
	
	public static void main(String[] args) {
		
		//System.out.println(countMax("10011101111"));
		System.out.println(getFlipIndex("10111101101011101"));
	}
	
	
	static int getFlipIndex(String inp) {
		
		int len = inp.length();
		int max = 0;
		int index = 0;
		for(int i=0;i<len;i++) {
			
			if(inp.charAt(i) == '0'){
				
				int localMax = countMax(inp.substring(0, i)+"1"+inp.substring(i,len));
				if(localMax > max) {
					
					max = localMax;
					index = i;
				}
			}
		}
		
		
		
		return index+1;
	}
	static int countMax(String inp) {
		
		if(inp==null || inp.isEmpty())
			return -1;
		
		int len =  inp.length();
		int count = 0;
		for(int i=0;i<len;i++) {
			
			if(inp.charAt(i)=='1') {
				
				int localCount = 1;
				for(int j=i+1;j<len;j++) {
					
					if(inp.charAt(j)=='1')
						localCount++;
					else
						break;
					
				}
				
				if(localCount>count)
					count = localCount;
			}
		}
		
		return count;
	}

}

O/p : 7

- shukad333 August 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is a linear solution.
1. Have three variables. "start", "mid", and "end".
2. initialize "start" at 0. initialize "mid" at the index of the first "0" in the string (if the string has no '0's just return the size of the string), and initialize 'end' at the index of second '0' (or the size of the string if there is no second '0').
3. If you flip the '0' at "mid", you get a block of (end - start) '1's.
4. Now start becomes mid + 1, mid becomes end, and end becomes the index of the next '0'.
5. Keep doing thing while keeping track of the max block size until you run out of '0's.

Here is the algorithm in Java:

// I'm assuming that the input string only contains '0's and '1's.
int maxConsecutiveOnesAfterAtMostOneFlip(String s) {
  int maxBlockSize = 0;
  int start = 0;  // The first character of the block.
  int mid = s.indexOf('0');  // The first '0' of the block.
  if (mid == -1) {  // if the string is all '1's.
    return s.length();
  }
  int end = s.indexOf('0', mid + 1);  // The first '0' after the block.
  while (end != -1) {
    maxBlockSize = Math.max(maxBlockSize, end - start);
    start = mid + 1;
    mid = end;
    end = s.indexOf('0', mid + 1);
  }
  maxBlockSize = Math.max(maxBlockSize, s.length() - start);
  return maxBlockSize;
}

- djmclaugh August 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think the key here is to maintain the state of the all consecutive 1's to the left and right of each '0' as the string is iterated. Then, whenever a new '0' is encounter, sum the left and right counts of the previous '0' together and compare it against the best candidate found thus far. This can be accomplished in O(n) time.

/**
 * Find the best '0' bit to flip to create most consecutive 1 bits
 *
 * @param bits String containing either '0' or '1' chars
 */
public static void find_best_flip(String bits) {

        int left_cnt = 0;      // Count of consecutive 1's to the left of 0
        int right_cnt = 0;   // Count of consecutive 1's to the right of 0
        int total_cnt = 0;   // Count of consecutive 1's to the right AND left of 0
        int pos = -1;          // Position of most recent 0

        int longest = 0;        // Longest consecutive 1's
        int best_index = 0;     // Index of zero with longest stream when flipped

        // Loop through string once, tracking the most consecutive 1's as we go
        for(int i = 0; i < bits.length(); i++) {

                char bit = bits.charAt(i);
                if(bit == '0') {

                        // Previous stream ended, so compare against best
                        total_cnt = left_cnt + right_cnt;
                        if(total_cnt > longest) {
                                best_index = pos;
                                longest = total_cnt;
                        }

                        // New stream started; Right is new left
                        left_cnt = right_cnt;

                        // Add flipped bit
                        left_cnt++; 

                        right_cnt = 0;
                        pos = i;

                // Else, we encountered a '1', so increment counter
                } else {
                        right_cnt++;
                }
        }
        // Tally last set
        total_cnt = left_cnt + right_cnt;
        
       if(total_cnt > longest) {
                best_index = pos;
                longest = total_cnt;
        }

        if(best_index != -1) {
                System.out.println("Longest: " + longest);
                System.out.println("By replacing Index " + best_index + " with '1'");
        } else {
                System.out.println("No zero's found");
        }
}

For the string "0010110100" the output would be:

Longest: 4
By replacing Index 3 with '1'

- Thomas Mielke August 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

static int findLength(String s) {
int start = 0;
int end = 0;
int maxLength = 0;

// create a window with only one zero
while (end < s.length() && s.charAt(end) == '1')
end++;
end++;

// now shift window such that there can only be one zero
while (end < s.length()) {
// move end till second zero
while (end < s.length() && s.charAt(end) == '1')
end++;

// update maxLength with window length if window length is greater than maxLength
if (maxLength < end-start)
maxLength = end-start;

// now shift the whole window such that previous zero is out and the second zero is in
while (start < end && s.charAt(start) == '1')
start++;
start++;
end++;
}
return maxLength;
}

- Vnikku August 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

static int findLength(String s) {
		int start = 0;
		int end = 0;
		int maxLength = 0;

		// create a window with only one zero
		while (end < s.length() && s.charAt(end) == '1') 
			end++;
		end++;

		// now shift window such that there can only be one zero 
		while (end < s.length()) {
			// move end till second zero
			while (end < s.length() && s.charAt(end) == '1') 
				end++;

			// update maxLength with window length if window length is greater than maxLength 
			if (maxLength < end-start) 
				maxLength = end-start;

			// now shift the whole window such that previous zero is out and the second zero is in 
			while (start < end && s.charAt(start) == '1') 
				start++;
			start++;
			end++;
		}
		return maxLength;
	}

- Vnikku August 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Pretty easy question. It is just hard to think in those interviews sometimes.

- Jim August 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(n) solution:

size_t findLongestContiguousPattern(string& str, char c)
{
	size_t max = 0;
	int index = -1;
	size_t count = 0;
	for (size_t i = 0; i < str.size(); i++) {
		if (str[i] == c)
			count++;
		else {
			if (max < count) {
				max = count;
				if (i > 0 && str[i - 1] == c && str[i + 1] == c)
					index = i;
			} else
				count = 0;
		}
	}
	if (index > 0)
		str[index] = c;
	return index;
}

- Teh Kok How August 31, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1.Find the longest contiguous susbtring with maximum 1s, note down the starting index and length
2.Move to the left till you encounter a second zero.. check the length and index
3. Move to the right till you encounter a second zero.. check the length and index

- Neel August 31, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

assuming input string is not null and more than 3 chars and in the format of only 0 and 1,

 public static int FlipBit(string input)
        {
            int idx = 0;
            idx = input.LastIndexOf("101");

            if (idx > 0)
            {
                idx = idx + 1;                
            }
            return idx;
        }

- Anonymous August 27, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is wrong! Let input string be "111111110". Your code will return -1.

- Satsuma August 27, 2014 | Flag
Comment hidden because of low score. Click to expand.
-2
of 2 vote

assuming input string is not null and more than 3 chars and in the format of only 0 and 1,

 public static int FlipBit(string input)
        {
            int idx = 0;
            idx = input.LastIndexOf("101");

            if (idx > 0)
            {
                idx = idx + 1;                
            }
            return idx;
        }

- Anonymous August 27, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

Basic problem ( thanks for pointing the flaw out *Satsuma * :) )
One way of doing this is :-

def find_max_flipped(bit_string):
    partitions = bit_string.split('0')
    max_item = ''
    num = len(partitions)

    if num is 1:
        return ''
    if num is len(bit_string) + 1:
        return '0'

    for i in range(1, num):
        if partitions[i-1] is '' and partitions[i] is '':
            continue

        if partitions[i-1] is '' and partitions[i] is not '':
            if len(max_item) < partitions[i] + 1:
                max_item = '0' + partitions[i]

        if partitions[i-1] is not '' and partitions[i] is '':
            if len(max_item) < partitions[i-1] + 1:
                max_item = partitions[i-1] + '0'

        else:
            # They can be merged
            item = partitions[i-1] + '0' + partitions[i]
            if len(item) > max_item:
                max_item = item
    return max_item

3 Regex matches.

import re
import sys
'''
We note that the strings can be :
1+01+ ; then the max match wins anyways
1+0
0+1
'''


def find_max_len(regex, bit_string):
    res = re.findall(regex, bit_string)
    ret = ''
    for r in res:
        if len(r) > len(ret):
            ret = r
    return ret


def find_max_regex(bit_string):

    result = find_max_len('1+01+', bit_string)
    find10 = re.search('1+0', bit_string)
    find01 = re.search('01+', bit_string)
    if result != '':
        return result
    if find01 is not None:
        return find01.group()
    if find10 is not None:
        return find10.group()
    if '0' in bit_string:
        return '0'
    return ''


f = find_max_regex(sys.argv[1])
print(f)

- Darth Plaguies August 27, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

I believe you are not connecting your longest sequence from right and left by flipping 0 to 1 between two sequences, like in "1111110111111101"

- Satsuma August 27, 2014 | Flag
Comment hidden because of low score. Click to expand.
-2
of 2 vote

public int countToRight(String input, int start) {
     //find how many "1" in a row starting from start index
     if (!input)
           return 0;
     int len = input.length;
     if (start > len-1)
           return 0;
     int result = 0;
     for (int i=start; i<len; i++) {
          if (input.charAt[i] == '0')
               break;
          result++; 
     }
}
public int countToLeft(String input, int end) {
     //find how many "1" in a row starting left from end index
     if (!input || end<1)
           return 0;
     int result = 0;
     for (int i=end; i>-1; i--) {
          if (input.charAt[i] == '0')
               break;
          result++; 
     }
}
public int flipToOne(String input) {
     //first find max sequence of "1" 
     if (!input)
           return 0;
     int maxCount = 0;
     int start = input.indexOf("1");
     if (start<0)
         return 1;
     while (start < len-1) {
         int count = countToRight(input, start);
         if (count > maxCount) {
                 maxCount = count;
                 start = input.substring(start+maxCount+1);
         }
     }
     //now we need to check if there are "1" at +2 and -2 positions, so we can connect by flipping
     int maxCandidate = maxCount + 1;
     if (input.CharAt(start+2) =='1') {
           maxCandidate = maxCount + 1 + countToRight(input, start+2);
     }
     if (input.CharAt(start-2)=='1') {
           maxCandidate = max(maxCandidate, maxCount + 1 + countToLeft(input, start-2));
     }
     return maxCandidate;
}

- Satsuma August 27, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I'm not sure what you are doing, but you have an potential infinite loop here:

while (start < len-1) {
    int count = countToRight(input, start);
    if (count > maxCount) {
        maxCount = count;
        start = input.substring(start+maxCount+1);
    }
}

- Anonymous August 28, 2014 | Flag


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More