Amazon telephonic interview ques

1. Write an efficient algo to find longest recurring substring in a string e.g. in banana, it would be 'ana'


Ans : We can use suffix trees to implement this. I will post the exact solution soon

2. Write a function to find intersection of two strings. i.e. characters common to the strings.

For this, the most efficient solution would be to use 26 bits .. one for each character and put zero in all and then wen u encounter a character, just make the corresponding bit 1. For this, we ll need to traverse both the strings only once ands the extra memory that would be required would only be 26 bits :) O(n) solution

Clock Angle Problem : Amazon Ques

Clock angle problems relate two different measurements - angles and time. To answer the problem the relationship between the time shown (or an elapsed time) and the position of the hands (as given by an angle) has to be found.
A general approach to such problems is to consider the rate of change of the angle in degrees per minute. The hour hand of a normal 12-hour analogue clock turns 360 degrees in 12 hours. This is equivalent to 360 degrees in 720 minutes or 0.5 degrees per minute. The minute hand turns 360 degrees in 60 minutes or 6 degrees per minute.

Equation for the degrees on the hour hand

(0.5 degrees per minute on the hour hand) * (the time on the hour hand * 60 minutes per hour) + (0.5 degrees per minute on the minute hand) * (the time on the minute hand)

Equation for the degrees on the minute hand

(6 degrees per minute on the minute hand) * (the time on the minute hand)

'Example: The time is 5:24'
The degree on the hour hand is (0.5*5*60)+(0.5*24)=162 degrees
It could be also calculated as
Hour hand angle = total minutes / 2
In this case Hour hand angle = total minutes / 2 = ( (total hours * 60) + (total minutes) ) / 2 = ( (5 * 60) + 24 ) / 2 = 162 degrees
The degrees on the minute hand is 6*24=144 degrees

Minute handl angle = minutes * 6
Equation for the degrees between the hands

The angle between the hands can also be found using the formula cos-1(cos(5.5x)), where x=the number of minutes past noon. This will always give an angle between 0 and 180 degrees.

'Example: The time is 1:35'

1:35 is 1(60)+35=95 minutes past noon.
cos-1(cos(5.5*95))=cos-1(cos(522.5))=cos-1(-.95372)=162.5 degrees between the hands
Angle=mod(60H-11M)/2
where H= hours and M=minutes

When are hour and minute hands of a clock superimposed?

Hour and Minute hands are superimposed only when angle between them are 0. If hour and minute hands are superimposed at time h:m
0.5*60*h + 0.5*m = 6*m
m=(30/5.5)*h
for h varies from 0...11, clock hands are superimposed at 1:05.4545,2:10.90...12:00.