Amazon Interview Question SDE1s
Country: United States
Interview Type: Written Test
/**
*
* @param arc sorted the array
* @param angular
* @return sub-array which contains the max elements in the array
*/
public static Queue<Integer> getMaxIntArr(int[] arc , int angular){
Queue<Integer> tempQue = new LinkedList<Integer>();
Queue<Integer> resultQue = new LinkedList<Integer>();
tempQue.add(arc[0]);
for(int i=1 ; i < arc.length ; i++){
if(getTempQueArcTotal(tempQue) <= angular){
tempQue.add(arc[i]);
if(resultQue.size() < tempQue.size()){
resultQue.clear();
resultQue.addAll(tempQue);
}
if(getTempQueArcTotal(tempQue) > angular){
resultQue.remove(arc[i]);
}
}
while(getTempQueArcTotal(tempQue) > angular){
tempQue.remove();
}
}
return resultQue;
}
/**
* @description get the sum angular in the queque
* @param que
* @return
*/
public static int getTempQueArcTotal(Queue<Integer> que){
Queue<Integer> tempQ = new LinkedList<Integer>();
tempQ.addAll(que);
int result = 0;
int temp = tempQ.remove();
while(!tempQ.isEmpty()){
result+=tempQ.peek() - temp;
temp = tempQ.remove();
}
return result;
}
may be this is more than O(n).
You can first calculate all the polar angles (btw by arctan2, not arctan ;)) then sort them, then do a "slide window" scan like this: you keep a pointer to the left boundary and a pointer to the right boundary of a region whose opening angle is less than alpha. If the opening angle is less than alpha, increase the right pointer, otherwise increase the left pointer, and keep track of the max number of elements inclosed in this process. The angle of the point pointed by the left pointer in the final max-including cone is your beta.
1. Have a method angleFromOrigin(int x, int y) or (Point p) that returns the angle from whatever axis you choose. (if you pass in 3, 4 it will return 30 degrees or whatever). This will allow you to order them from their angle from a given axis.
2. Iterate through the points and put the result in a List<PointWithAngle>
PointWithAngle {
Point p;
int angleFromAxis;
}
3. Sort the list based on angleFromAxis.
4. Find the largest subset that has a difference less than the alpha angle.
This can be done by having a two index system that runs along the array and increments when the points are outside the alpha angle.
5. Return the last point in the subset's angle (if your reference axis is the beta angle's axis).
Hope that makes sense,
Initializing list by running through points: O(n)
Sorting list: O(nlogn)
Finding the largest subset: O(n)
Runtime: O(nlogn)
For example if the list of angles corresponding to points was:
30,35,40,75,110,135,140,175
and your alpha angle was 30
you would return 30,35,40 since that was the largest subset that didn't exceed the alpha angle
This is exactly what I thought and here is the implementation of this idea in Visual Basic.
''' 1. Creating an encapusation of information about point
Public Class Point
Private mvarX As Double
Public Property X() As Double
Get
Return mvarX
End Get
Set(ByVal value As Double)
mvarX = value
End Set
End Property
Private mvarY As Double
Public Property Y() As Double
Get
Return mvarY
End Get
Set(ByVal value As Double)
mvarY = value
End Set
End Property
Sub New(x As Double, y As Double)
Me.X = x
Me.Y = y
End Sub
End Class
Public Class Calculate
Dim srtArry As New SortedList()
Dim Alpha As New Double
Dim maxAry As New Dictionary(Of Double, Integer)
''' 2. Creating instances of Point class
Sub New(ByVal Arry As List(Of Point), ByVal alpha As Double)
Me.Alpha = alpha
If Arry.Count > 0 Then
For Each i As Point In Arry
Dim angl As Double = (ArcTan(i))
If (srtArry.ContainsKey(angl)) Then
srtArry(angl) = srtArry(angl) + 1
Else
srtArry.Add(angl, 1)
End If
Next
RunProgram()
Else
Console.WriteLine("No points given!")
End If
End Sub
Private Sub RunProgram()
Dim maxPtsCnt As Integer = GetMaxPtsCnt()
For j As Integer = 0 To maxAry.Count - 1
Console.WriteLine("Beta angle can take value " & maxAry.ElementAt(j).Key * (180 / Math.PI) & " to get " & maxAry.ElementAt(j).Value & " points in region")
Next
End Sub
Private Function GetMaxPtsCnt() As Integer
Dim max As Integer = 0
Dim tmp As Integer = 0
Dim cnt As Integer = 0
For i As Integer = 0 To (srtArry.Count - 1)
Dim currentAngle As Double = srtArry.GetKey(i)
Dim tmpAngle As Double = srtArry.GetKey(tmp)
' Calculating number of max points covered by tmpAngle
'*****************************************************
'---***If currentAngle lies outside the beam formed by tmpAngle and Alpha***
While (tmpAngle + Alpha < currentAngle)
'---***Check if cnt is the new max ***
FinalizeAngle(max, tmp, tmpAngle, cnt)
tmp = tmp + 1
'---***If all Angles in srtArry are calculated exit loop***
If tmp = srtArry.Count Then Exit For
'---***next angle in srtArry after tmpAngle***
tmpAngle = srtArry.GetKey(tmp)
cnt = cnt - srtArry.Item(srtArry.GetKey(tmp - 1))
End While
'---***If currentAngle lies in the beam formed by tmpAngle and Alpha***
If tmpAngle + Alpha >= currentAngle Then
cnt = cnt + srtArry.Item(srtArry.GetKey(i))
'---***If tmpAngle + Alpha is greater than maximum of all angles i.e. (i = srtArray.Count - 1 && tmpAngle + Alpha > currentAngle)***
If i = srtArry.Count - 1 Then
'---***Loop all angles before currentAngle if tmpAngle beam overflows to FirstQuadrant***
If tmpAngle + Alpha - (2 * Math.PI) >= 0 Then LoopAgain(cnt, tmpAngle)
'---***Check if tmpAngle cnt is the new max***
FinalizeAngle(max, tmp, tmpAngle, cnt)
'---***If all Angles in srtArry are not calculated yet***
If tmp < i Then
'---***Restart for loop from tmp + 1 (Next i increments value)***
i = tmp
'---***Since tmpAngle is finalized, next angle in srtArry after tmpAngle***
tmp = tmp + 1
cnt = 0
End If
End If
End If
Next i
Return max
End Function
''' Utility Function1 : Find angle of given point
Private Function ArcTan(ByVal pt As Point) As Double
Dim Beta As Double = 0
If pt.X >= 0 And pt.Y < 0 Then
Beta = Math.Atan(pt.Y / pt.X) + (2 * Math.PI)
ElseIf pt.X < 0 And pt.Y >= 0 Then
Beta = Math.Atan(pt.Y / pt.X) + Math.PI
ElseIf pt.X < 0 And pt.Y <= 0 Then
Beta = Math.Atan(pt.Y / pt.X) + Math.PI
Else
Beta = Math.Atan(pt.Y / pt.X)
End If
Console.WriteLine("( " & pt.X & "," & pt.Y & ")" & " Angle : " & Beta * 180 / Math.PI)
Return Beta
End Function
''' Utility Function2 : Decide if Angle should be added into an array of closest points.
Private Sub FinalizeAngle(ByRef max As Integer, tmp As Integer, tmpAngle As Double, cnt As Integer)
If max < cnt Then
max = cnt
maxAry.Clear()
maxAry.Add(tmpAngle, cnt)
ElseIf max = cnt Then
If maxAry.ContainsKey(tmpAngle) Then
maxAry.Item(tmpAngle) = maxAry(tmpAngle) + 1
Else
maxAry.Add(tmpAngle, cnt)
End If
End If
End Sub
''' Utility Function3: I doubt if this is the culprit which increased time complexity of my
'''program. Loop function that loops through all points within alpha range but lies beyond
'''4th quadrant.
Private Sub LoopAgain(ByRef cnt As Integer, tmpAngle As Double)
Dim TmpLowAngle As Double = tmpAngle + Alpha - 2 * Math.PI
For j As Integer = 0 To srtArry.Count - 1
Dim currentAngle2 As Double = srtArry.GetKey(j)
If TmpLowAngle - currentAngle2 >= 0 Then
cnt = cnt + srtArry.Item(srtArry.GetKey(j))
Else
Exit For
End If
Next
End Sub
''' Initializing some examples
<Extension()>
Sub Add(ByVal list As List(Of Point), ByVal X As Double, ByVal Y As Double)
list.Add(New Point(X, Y))
End Sub
Sub Main()
'''Dim pts As New List(Of Point) From {{-2, 0}, {-2, 2}, {-2, 0.5}, {2, -1}, {2, 0}, {2, -0.5}, {-2, 0}}
Dim pts As New List(Of Point) From {{0, 2}, {-2, 2}, {0, -2}, {2, -2}, {2, 0}, {5, 0.25}, {5, 0.15}}
'''Dim pts As New List(Of Point) From {{0, 5}, {-3, 3}, {-5, 0}, {4, -2}, {3, -3}, {5, 0.25}}
Dim obj1 As New Calculate(pts, 45.0 * (Math.PI / 180))
Console.ReadLine()
End Sub
I was asked to write a program that has time complexity not more than O(n) after sorting O(n^2)
- shylaja23 July 13, 2013