I had this problem at my test, but i don't know how to "think the problem", neither this type of problems with efficient execution time..
Number x is called "sufix" for y, only if y is obtained from x by adding at least one digit to the left of the number. Example: 502 is sufix for 11502 because if u add "11" in front of "502" you get number "11502". A text file contain an array of numbers, max 1.000.000.000 numbers, each number must be from 0, to 1.000.000.000. Display on the screen, strictly ascending, each number from array, which belong from [100 to 999] and it is a sufix for at least one number from the array. If the array doesn't contain a sufix number, display on the screen message "No sufix number". The algorithm must be efficient at execution time.
If we have this array "11502 49 54321 6149 76149 123 123 502 4321 321 321", the result must be "321 502"
Create an array has_suffix with entries of 1000 boolean elements, and set each element to False.
Iterate over each line. For each number i in a line, if it is over 999, find the last three digits i_, and set has_suffix[i_] = True
If you run into 2199, set has_suffix[199] = True. For example:
If you run into 132, ignore it.
If you run into 23, ignore it.
Create an array suffix with entries of 1000 boolean elements, and each element set to False.
Iterate again over each line. For each number i in a line, if it is between 100 and 999 and has_suffix[i] == True, set suffix[i] = True.For example:
If you run into 2199, ignore it.
If you run into 23, ignore it.
If you run in 132, check has_suffix[132]. If it is True, then set suffix[132] = True.
Iterate over the entries of suffix from 100 to 999, and print out the indices of the entries that are True. For example,
True are 321 and 502, then print "321" and "502".