Interview Question
Country: United States
static String[] lexicoGraphicalOrder(int N, int[] query){
StringBuilder sb = new StringBuilder();
for(int i=1; i<=N; i++){
sb.append(String.valueOf(i)+",");
}
String[] nums = sb.substring(0, sb.length()-1).split(",");
Arrays.sort(nums);
String[] res = new String[query.length];
int i=0;
for(int n:query){
res[i] = nums[n];
i++;
}
return res;
}
1 fill an array list with the increasing numbers 1-N
2 sort the array list with compare lambda expression
the comparison is to be done after converting the num to a value between 0-9
eg 1 10 ...19 all produce 1 only rearrange when nums produce negative
2 and 11 will be compared as 1-2 will produce -1 and so swapped
public static void main(String[] args) {
ArrayList<Integer> list = new ArrayList<>();
System.out.print("Enter the size : ");
Scanner in = new Scanner(System.in);
int n = in.nextInt();
for (int i = 1; i <= n; i++) {
list.add(i);
}
// sort using num converted to 0-9
list.sort((o1, o2) -> {
while (o1 > 9) o1 /= 10;
while (o2 > 9) o2 /= 10;
return o1 - o2;
});
System.out.println("The list is : " + list.toString());
int t;
do {
System.out.print("Enter the index you want to get <negative num to exit> : ");
t = in.nextInt();
if (t >= 0 && t < n)
System.out.println("The Queried num is " + list.get(t));
else System.out.println("Error : Index out of bounds");
} while (t >= 0);
}
Generate next element in the sequence based on the previous element. This way we don't need to store the sequence and meet the memory requirements.
def find(query, n):
ans = []
query = sorted(query)
qi = 0
z = 1
for zi in xrange(n):
if query[qi] == zi:
ans += [z]
qi += 1
if qi == len(query):
break
if z*10 <= n:
z *= 10
elif z%10 != 9 and z+1 <= n:
z += 1
else:
z /= 10
while z%10 == 9:
z /= 10
z += 1
return ans
print find([1,4], 12)
- Anonymous November 07, 2018