Uber | OA Coding Questions and Solutions | Set - 29 | 2022

Question

For proper oa or interview experiences list of all top tech companies visit :

https://oa.desiqna.in

https://interview.desiqna.in

 

 

Answer 1

You are given a binary string (containing character 0 and 1 only) s of length n. You task is to convert all the 1s in this string to 0. To do this you can do the following :
First choose an integer K and then perform the following operation any number of times :

 

• Choose any substring of this string such that length of substring is greater than or equal to K and change all 0s to 1 and all 1s to 0 in that substring i.e. for a substring [L,R] (R-L+1>=K) in s, for each i such that L<=i<=R, if si is 0 make it 1 and if it is 1 make it 0.
  Find the maximum integer K less than or equal to n that we can choose such that it is possible to convert the string to all 0s using above method.
  Constraints
  1<=n<=100000
  Examples
  Input : 101
  Output : 2
  Explanation : If we choose K = 2, we can convert the string to all 0s by following way
• choose substring [0,1] = "10", then s becomes 011
• now choose substring [1,2] = "11", then s becomes 000
  It is the maximum K as we can not convert the sting to all 0s by choosing K = 3.
  Input : 10000
  Output : 4
  Explanation : We can choose K = 4 and convert the following way
• Choose substring [0,4] = "10000", the s becomes 01111
• Choose substring [1,4] = "1111", then s becomes 00000
  Input/Output
• [execution time limit] 4 seconds (py3)
• [input] string s
  given binary string
• [output] integer
  Output the maximum K such that it is possible to convert s to all 0s by the operation.

Answer 2

Seems to be a variation of https://leetcode.com/problems/minimum-number-of-k-consecutive-bit-flips/ where instead of making all 1 we are making all 0. Further, we are not given K in OA problem, So, naively we will need to iterate over all possible values of K, giving us a O(N^2) algorithm.