A blog dedicated to those who live, drink and eat Algorithms.
Monday, June 30, 2008
Hi There
This is the first non algo post from my side. If there are any good question which you think should be here kindly put a comment to this post along with your solution. We all can learn in this process.
There is a TV avid person. HE wants to spend his max time on TV. There are N channels with different program of different length and diff times. WAP so that the person cam spend his max time watching TV. Precondition: If that person watches a program, he watches it completely.
This can be thought of as, N-queues(N-channels) containing jobs of different lengths and a processor(the TV Avid person). The goal is to maximize the processors utilization. Standard problem. Isn't it? Use some good standard scheduling algorithm.
given a number lets say 94512(a random number here), give me an algorithm which gives me the next immediate largest number that contains all the digits from the given number
What is the efficient way to search for a string in a 2D array of characters [I mean a matrix of chars]. The letters in the word are adjacent and can be in any of the 8 adjacent cells
Ranganath: This is quite simple, you take the last digit and scan backwards through the number and insert it in front of the first number smaller than it. If there isn't one, we take the second from last number and do the same, scan backwards from it and look for any numbers smaller than it.
On that example, we take the 2 and insert it before the 1, to get 94521.
It is also clear that if the number is the highest possible given the digits, the algorithm will run through the entire number and terminate without making changes.
8 comments:
Question:
There is a TV avid person. HE wants to spend his max time on TV. There are N channels with different program of different length and diff times. WAP so that the person cam spend his max time watching TV.
Precondition: If that person watches a program, he watches it completely.
Ex:
Channel1: prog1 - 8:00- 8:30
prog2: 9:00 - 10:00
prog3: 10:15 - 12:00
channel2: prg1 - 8:15 - 10:00
prg2: 10:30 - 12:00
So in this case max time will be if he watches:
ch2/prg1 + ch1/prg3
Hi akash... nice to hear from you..
Can you provide more detail about the run time requirements and mode of inputs etc?
Since we are just discussing the also so that is not important...
This can be thought of as, N-queues(N-channels) containing jobs of different lengths and a processor(the TV Avid person). The goal is to maximize the processors utilization. Standard problem. Isn't it? Use some good standard scheduling algorithm.
given an array of N elements, find three numbers in the array whose sum is equal to a value K.
given a number lets say 94512(a random number here), give me an algorithm which gives me the next immediate largest number that contains all the digits from the given number
What is the efficient way to search for a string in a 2D array of characters [I mean a matrix of chars]. The letters in the word are adjacent and can be in any of the 8 adjacent cells
Ranganath:
This is quite simple, you take the last digit and scan backwards through the number and insert it in front of the first number smaller than it. If there isn't one, we take the second from last number and do the same, scan backwards from it and look for any numbers smaller than it.
On that example, we take the 2 and insert it before the 1, to get 94521.
It is also clear that if the number is the highest possible given the digits, the algorithm will run through the entire number and terminate without making changes.
Post a Comment