FastPrepK-Step Bit Flip with Retention
Problems/K-Step Bit Flip with Retention

K-Step Bit Flip with Retention

Cisco logoCisco● MediumFULLTIMEPHONE SCREEN

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: In a phone screen, the candidate got a binary string and a number k. They had to run k labeled steps. Each step keeps one position the same and flips all the others. The post gave the full rules and the results for k from 1 to 4 on the same starting string.

The report does not give any limits on the string length or on k. Here, the string has up to 10^4 characters and k can be as large as 10^9, so running every step one by one is too slow.

Our version is about 95% the same as the reported question.

You are given a binary string s and a positive integer k. Apply exactly k steps to s, one after another. The steps are labeled k, k - 1, k - 2, ..., 1. The first step has label k, and the last step has label 1.

A step with label v changes the current string in two parts:

  1. Choose the kept position:
    • If v is odd, it is the position of the leftmost '1'.
    • If v is even, it is the position of the leftmost '0'.
    • If the string has no character of that kind, it is the last position, s.length - 1.
  2. Flip every character except the one at the kept position. A '0' becomes '1', and a '1' becomes '0'. The kept character stays the same.

Positions are counted from 0. Return the string after all k steps.

Function

kStepBitFlip(s: String, k: int) → String

Examples

Example 1

s = "1010"k = 1return = "1101"

There is one step, with label 1. The label is odd, so the kept position is the leftmost '1', at index 0. Every other character flips, so "1010" becomes "1101".

Example 2

s = "1010"k = 2return = "1111"

The labels are 2, then 1.

  • Label 2 is even. The leftmost '0' is at index 1, so it is kept and the rest flip: "1010" becomes "0001".
  • Label 1 is odd. The leftmost '1' is at index 3, so it is kept: "0001" becomes "1111".

Example 3

s = "1010"k = 3return = "1110"

The labels are 3, 2, then 1.

  • Label 3 is odd. Keep index 0: "1010" becomes "1101".
  • Label 2 is even. Keep index 2, the leftmost '0': "1101" becomes "0000".
  • Label 1 is odd, but there is no '1'. Keep the last index, 3: "0000" becomes "1110".

Example 4

s = "1010"k = 4return = "1111"

The labels are 4, 3, 2, then 1.

  • Label 4 is even. Keep index 1: "1010" becomes "0001".
  • Label 3 is odd. Keep index 3, the only '1': "0001" becomes "1111".
  • Label 2 is even, but there is no '0'. Keep the last index, 3: "1111" becomes "0001".
  • Label 1 is odd. Keep index 3: "0001" becomes "1111".

Example 5

s = "001"k = 1000000000return = "111"

The first label, 10^9, is even. Keep index 0: "001" becomes "010".

The next label is odd. Keep index 1, the leftmost '1': "010" becomes "111".

From here on, every step keeps the last index. An even label finds no '0', and an odd label finds its leftmost '1' at index 2. So the string goes "111", "001", "111", "001", and so on. It is "111" after every even number of steps. 10^9 is even, so the answer is "111".

Constraints

  • 1 <= s.length <= 10^4
  • s contains only the characters '0' and '1'.
  • 1 <= k <= 10^9

More Cisco interview questions

  • Check if a String Is a PalindromePHONE SCREEN · Seen Nov 2026
  • Find Unique ElementsPHONE SCREEN · Seen Nov 2026
  • First Letter to Appear TwicePHONE SCREEN · Seen Nov 2026
  • Middle of a Linked ListPHONE SCREEN · Seen Nov 2026
  • Reverse a Linked ListPHONE SCREEN · Seen Nov 2026
  • Reverse a StringPHONE SCREEN · Seen Nov 2026
  • Valid ParenthesesPHONE SCREEN · Seen Nov 2026
  • Longest Non-Repeating SubstringPHONE SCREEN · Seen Jul 2026
  • Todo Task Manager OperationsONSITE INTERVIEW · Seen Oct 2026
  • Find the Duplicate Number Without Modifying the ArrayONSITE INTERVIEW · Seen Sep 2026

Similar questions at other companies

  • Business Account KYC Verification — Parts 1–5Stripe · PHONE SCREENStripe interview questions
  • Read Across Sound TracksAirbnb · PHONE SCREENAirbnb interview questions
  • Stateful Log Transform and SearchRippling · PHONE SCREEN · ONSITE INTERVIEWRippling interview questions
  • In-Memory Filesystem CommandsPerplexity AI · PHONE SCREEN · ONSITE INTERVIEWPerplexity AI interview questions
  • Elevator Scheduling SimulationOpenAI · PHONE SCREENOpenAI interview questions
  • File Storage ServiceCresta · PHONE SCREENCresta interview questions
  • String Interpolation with a Missing-Value ModeMongoDB · PHONE SCREENMongoDB interview questions
  • Dasher Pay with Store Waits and Peak HoursDoorDash · PHONE SCREENDoorDash interview questions
  • Return Every Matching DecryptionDuolingo · PHONE SCREENDuolingo interview questions
  • Fixed-Order Task Run Time With CooldownWaymo · PHONE SCREENWaymo interview questions
All Cisco interview questionsSee Cisco hiring insights
Saved
class Solution {
    public String kStepBitFlip(String s, int k) {
        // Write your code here.
    }
}
Checking account…