sprateek1990
BAN USER- 0of 0 votes
AnswersGiven a string having a number:
- sprateek1990 in United States
"625626628"
Here the substrings are in consecutive order except for 1 substring which is missing. Find the missing substring.
Test cases:
"1235678" -> 4 is missing
"9979981000" -> 999 is missing
"624625627" -> 626 is missing| Report Duplicate | Flag | PURGE
Amazon SDE1 - 0of 0 votes
AnswerBox stacking problem with boxes having k dimension, find max height of stack
- sprateek1990 in India| Report Duplicate | Flag | PURGE
Amazon Java Developer
Hi,
My first solution was that we check till len/2,but clearly he was looking for more optimised approach.
hi,
The numbers are positive, sequence increases by 1 only, missing number can be anywhere, substrings can be of different length(2nd last test case).
Hi,
Thanks for posting a solution, what i perceive is ur checking for each substring starting from length 1 ? can u think of a more optimised solution? What I suggested in interview was we break down the string in factors of total length from len/2 to 1. Then he gave me the test case of 9979981000 so I checked for factors of length and prime numbers till len/2 .
so for 9979981000, i check for substrings of length 5,3,2,1.
sorry posted again by mistake
- sprateek1990 September 29, 2014can we get better time complexity...in place and better than On^2
- sprateek1990 April 19, 2012
Hi pradeep
- sprateek1990 January 21, 2015Thanks for writing a perfectly working code, but can u plz specify where have u achieved optimization?
thanks...