Interview Question

Country: India
Interview Type: Written Test

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

step 1: Convert this string to list of the substrings of size x
step 2: sort individual substring characters make things better use only unique characters from each substring so that duplicate number generation can be avoided
step 3: generate n th string from all these substrings, i.e. generate N the set in the cartesian product of these substring characters.

package com.practice.algo;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;

public class KthNumberInSorted {

  private static List<Integer> getNthNumber(List<List<Integer>> lists, int n) {
    int lSize = lists.size();
    int[] mul = new int[lSize];
    mul[lSize - 1] = 1;
    for (int i = lSize - 2; i >= 0; i--) {
      mul[i] = mul[i + 1] * lists.get(i + 1).size();
    List<Integer> l = new ArrayList<>();
    n -= 1;
    for (int i = 0; i < lSize; i++) {
      int r = n / mul[i];
      n = n - r * mul[i];
    return l;

  private static String getNthNumber(String s, int x, int k) {
    List<Integer> l = new ArrayList<>();
    for (int i = 0; i < s.length(); i++) {
      l.add(s.charAt(i) - '0');
    List<List<Integer>> listOfLists = new ArrayList<>();
    int start = 0;
    while (start < s.length()) {
      int end = Math.min(s.length(), start + x);
      // make it unique
      List<Integer> list = new ArrayList<>(new HashSet<>(l.subList(start, end)));
      start = end;
    StringBuilder stringBuilder = new StringBuilder();
    for (Integer i : getNthNumber(listOfLists, k)) {
    return stringBuilder.toString();

  public static void main(String[] args) {
    System.out.println(getNthNumber("1234567891", 5, 3));
    System.out.println(getNthNumber("123456789", 3, 3));


- xyz September 16, 2019 | Flag Reply

Add a Comment

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.


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


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