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
