Interview Question 4

Sep 16, 2022

Consider the following ten-digit number:
\( 7~1~0~6~4~1~9~9~0~2\). You should remove three of the digits so as to get the largest possible seven digit number. As a first step, you may want to try to delete two digits from the following five digit number to get the largest possible three digit number:
\(7~1~9~3~4\).
Now consider the more general question when you are given an \(n\) digit number and asked to delete \(k < n\) out of the \(n\) digits, so as to leave the largest possible \(n - k\) digit number. Explain your general strategy. Evaluate the number of steps requried to perform your strategy and try to minimise this number as much as you can.

This question was used in CS interviews at Lady Margaret Hall in December 2018.

Tags: oxford, cs, maths, interview

Respond to this

4 responses

  x = num
  x = array_of_digits(num)
  y = sort(x)
  loop through x, k times:
    pick the first k elements in y, and delete them from x, left to right
  return x with k elements removed.

JD – September 16th, 2022

 Dynamic programming.
 Let D be the n-digit number.
 MaxNumber(D, n, k) = max_{i <= n, D' is D without ith digit} 
 MaxNumber(D', n-1, k-1)
 MaxNumber(D, n, 0) = D

anon – November 25th, 2022

make 10 queues for digits 0-9 and store positions of digits. find the first position of largest digit, pop everything with a position prior to it, rinse and repeat. time complexity is O(n)

alexandros – December 4th, 2022
Assuming that the order of the letters, except those deleted, is unchangeable.

1.(a) 934

(b) 7649902
1. General strategy: Consider the first (k - 1) digits of n. Take the (first if several equal) largest of these to start the new number and remove all numbers before it from original list. Now consider the new list starting from index 1 (assuming zero-indexed). Keep doing the same steps over and over for appropriate new n and k values on the new sublists until reaching an answer of desired length.
This strategy needs a maximum of (n-k) recursions/searches like this since the worst-case scenario is that no digits are eliminated each run for k runs. Therefore, it feels pretty efficient. To make it even more efficient, could store the results of previous searches/sorts and only re-sort the new digits that need consideration in the next recursion and beyond.
Jay – November 13th, 2023