Hello world! Sorry didn't publish anything since long, I am lazy and you know it.
Anyways, due to our performance at ICPC Asia regionals at Amritapuri, I got an internship offer from Directi (big deal :) ). As a part of the interview procedure I had to give a phone interview totally based on Algos. I was asked following 2 questions:
1. Given a number, find the smallest number larger than the given number and consists of the same
digits as the given number.
i.e if input = 123 then the answer would be 132
Soln - Start from the last digit, move till u find a digit smaller than the last digit and then place the last
digit in front of the found digit and then sort the digits present on it's right hand side.
2. Given an array ,for all members x find a number y such that:
y<x and pos(y) < pos(x) and pos(y) is closest to pos(x) [pos(x)=position of x in the array]
i.e given 1,2,5,3,4 answer will be 2:1, 5:2, 3:2, 4:3
Soln: Stack comes in handy over here.
Place the first number in stack.
Now for every member check the top of the stack. If it is smaller, then the number is your
answer, or else, pop the top and again check.
Once, you find your answer, push the current number also in the stack.
Tweet
Anyways, due to our performance at ICPC Asia regionals at Amritapuri, I got an internship offer from Directi (big deal :) ). As a part of the interview procedure I had to give a phone interview totally based on Algos. I was asked following 2 questions:
1. Given a number, find the smallest number larger than the given number and consists of the same
digits as the given number.
i.e if input = 123 then the answer would be 132
Soln - Start from the last digit, move till u find a digit smaller than the last digit and then place the last
digit in front of the found digit and then sort the digits present on it's right hand side.
2. Given an array ,for all members x find a number y such that:
y<x and pos(y) < pos(x) and pos(y) is closest to pos(x) [pos(x)=position of x in the array]
i.e given 1,2,5,3,4 answer will be 2:1, 5:2, 3:2, 4:3
Soln: Stack comes in handy over here.
Place the first number in stack.
Now for every member check the top of the stack. If it is smaller, then the number is your
answer, or else, pop the top and again check.
Once, you find your answer, push the current number also in the stack.
Tweet
Yeah, finally a new post after such a long time ;-)
ReplyDeletebtw main point is "Did you get the intern???"
I didn't get it. Don't know the reason
Delete@nimit shah: you did the first in O(n+nlogn) where n is number of digits. It would have been O(n) only if in place of sorting part you would have swapped the last digit from left greater than your found digit .
ReplyDeleteSorting the digits helps to make sure that the new found number is smallest possible.
DeleteConsider the case:
Delete123654 - The answer should be 124356
- Your answer: 124653