Interview Question
Country: India
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);
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"
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
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;
}
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'
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;
}
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;
}
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;
}
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;
}
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)
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;
}
- . August 29, 2014