## Amazon Interview Question for Applications Developers

Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````import java.util.ArrayList;
import java.util.HashMap;

public class LongestSequenceCircular {

public static void main(String[] args) {
Node n = createList();

// First, find the length of the linked list
int length = length(n);
System.out.println("Max sequence length is " + findLongestSequenceLength(n, length));

}

public static int findLongestSequenceLength(Node n, int length) {
HashMap<Integer, ArrayList<Integer>> map = new HashMap<Integer, ArrayList<Integer>>();
Node curr = n;
// create a map between node value and list of indexes it appears
for (int i = 0; i < length; i++) {
if (!map.containsKey(curr.val)) {
ArrayList<Integer> arr = new ArrayList<Integer>();
map.put(curr.val, arr);
}
curr = curr.next;
}
int max = 0;
// find the longest sequence among all values in the map
for (Integer i : map.keySet()) {
if (map.get(i).size() == 1) continue; // just one occurrence of the value will not form a sequence
int maxLocal = findLongestSequenceForValue(map.get(i), length);
max = Math.max(max, maxLocal);
}
return max;
}

public static int findLongestSequenceForValue(ArrayList<Integer> arr, int maxLength) {
int max = 0;
// since indexes are in ascending order we can find the max sequence in this iteration
for (int i=0; i<arr.size() - 1; i++) {
int diff = arr.get(i+1) - arr.get(i);
max = Math.max(max, diff);
}
// also check sequence length in case we wrap to the beginning of the linked list
int finalDiff = maxLength - 1 - arr.get(arr.size() - 1) + arr.get(0);
return Math.max(max, finalDiff);
}

public static int length(Node n) {
if (n == null) return 0;
Node slow = n;
Node fast = n.next;
int result = 1;
while (fast != null) {
if (fast == slow) return result;
if (fast.next == slow) return result + 1;
slow = slow.next;
fast = fast.next.next;
result++;
}
return result;
}

public static Node createList() {
Node n = new Node(3);
n.next = new Node(8);
n.next.next = new Node(9);
n.next.next.next = new Node(7);
n.next.next.next.next = new Node(2);
n.next.next.next.next.next = new Node(1);
n.next.next.next.next.next.next = new Node(3);
n.next.next.next.next.next.next.next = new Node(4);
n.next.next.next.next.next.next.next.next = new Node(6);
n.next.next.next.next.next.next.next.next.next = n;
return n;
}

public static class Node
{
int val;
Node next;
public Node(int val) { this.val = val; }
}

}``````

Comment hidden because of low score. Click to expand.
0

I've got the same idea. Nice.

Comment hidden because of low score. Click to expand.
0
of 0 vote

c# implementation.

``````public static List<Node> GetLongestSequence( Node node ) {

var res = GetLongestForIthElement( node );
var hashSet = new HashSet<int>();
var self = node;
var curr = node.Next;
while ( curr != self ) {

if ( hashSet.Contains( curr.Value ) ) {
curr = curr.Next; continue;
}

var tmp = GetLongestForIthElement( curr );
if ( tmp.Count > res.Count ) {
res = tmp;
}
curr = curr.Next;
}
return res;
}

public static List<Node> GetLongestForIthElement( Node node )        {
var list1 = new List<Node> { node };
var list2 = new List<Node>();
var tmp = list1;
var N = node.Value;
var self = node;
var curr = node.Next;
while ( curr != self  ) {
if ( curr.Value != N ) {
curr = curr.Next;
continue;
}
if ( list1.Count >= list2.Count ) {
list2.Clear();
tmp = list2;
} else {
list1.Clear();
tmp = list1;
}
curr = curr.Next;
}
if ( list2.Count == 0 ) { return new List<Node>(); }
return list1.Count >= list2.Count ? list1 : list2;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

use hash table to store first and last occurrence. Time:O(n), space:0(n)

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````package fgiet;

public class t4 {

public static void main(String a[])
{
int ar[]={3,8,9,7,2,1,3,4,6,3,8},n,left=0,right=0,i,max=-12345,s=0,e=0;
n=11;
for(i=0;i<n;i++)
{left=i;
right=i+1;
while(right<n)
{

if(ar[left]!=ar[right])
{
System.out.println(left+" "+ right);
right++;
}
else
{

int r=right-left+1;
if(r>max)
{
s=left;
e=right;
max=r;
}
left=right;
right++;
}
}

}
System.out.println(s+" " +e +" "+ max);
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````package fgiet;

public class t4 {

public static void main(String a[])
{
int ar[]={3,8,9,7,2,1,3,4,6,3,8},n,left=0,right=0,i,max=-12345,s=0,e=0;
n=11;
for(i=0;i<n;i++)
{left=i;
right=i+1;
while(right<n)
{
if(ar[left]!=ar[right])
{
System.out.println(left+" "+ right);
right++;
}
else
{
int r=right-left+1;
if(r>max)
{
s=left;
e=right;
max=r;
}
left=right;
right++;
}}
}
System.out.println(s+" " +e +" "+ max);
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

package fgiet;

public class t4 {

public static void main(String a[])
{
int ar[]={3,8,9,7,2,1,3,4,6,3,8},n,left=0,right=0,i,max=-12345,s=0,e=0;
n=11;
for(i=0;i<n;i++)
{left=i;
right=i+1;
while(right<n)
{
if(ar[left]!=ar[right])
{
System.out.println(left+" "+ right);
right++;
}
else
{
int r=right-left+1;
if(r>max)
{
s=left;
e=right;
max=r;
}
left=right;
right++;
}}
}
System.out.println(s+" " +e +" "+ max);
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

package fgiet;

public class t4 {

public static void main(String a[])
{
int ar[]={3,8,9,7,2,1,3,4,6,3,8},n,left=0,right=0,i,max=-12345,s=0,e=0;
n=11;
for(i=0;i<n;i++)
{left=i;
right=i+1;
while(right<n)
{
if(ar[left]!=ar[right])
{
System.out.println(left+" "+ right);
right++;
}
else
{
int r=right-left+1;
if(r>max)
{
s=left;
e=right;
max=r;
}
left=right;
right++;
}}
}
System.out.println(s+" " +e +" "+ max);
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````package fgiet;
public class t4 {

public static void main(String a[])
{
int ar[]={3,8,9,7,2,1,3,4,6,3,8},n,left=0,right=0,i,max=-12345,s=0,e=0;
n=11;
for(i=0;i<n;i++)
{left=i;
right=i+1;
while(right<n)
{
if(ar[left]!=ar[right])
{
System.out.println(left+" "+ right);
right++;
}
else
{
int r=right-left+1;
if(r>max)
{
s=left;
e=right;
max=r;
}
left=right;
right++;
}}
}
System.out.println(s+" " +e +" "+ max);
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

we can override the equals method of node and add extra param to check existing hashcode and objection location and next object location matches.. example..

``````public class Node {

public int value;
public Node(int i){
this.value=i;
}
public Node nextNode;

public boolean equals(Node obj) {

return (super.equals(obj)&& obj.nextNode==nextNode);
}
public class SearchingElement {

public static void main(String[] args){
Node n = new Node(3);
Node n1= new Node(4);
n.nextNode=n1;
Node n2 = new Node(5);
n1.nextNode=n2;
Node n3 = new Node(3);
n2.nextNode=n3;
Node n4 = new Node(6);
n3.nextNode=n4;
Node n5 = new Node(7);
n4.nextNode=n5;
n5.nextNode= n;

Node temp=n;
do{
System.out.println(" "+temp.value);
temp=temp.nextNode;
}while(!temp.equals(n));``````

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

I guess this is the easiest way:

``````int count = 0;
vector<int>arr1;
struct node *temp = head;
if(temp->data ==3) arr1.push_back(count);
temp = temp->next;
count++;

}

for(int i=0;i<len(arr1);i++){
vector<int>arr2;
arr2.push_back(arr1[i+1]-arr[i]);

}``````

Now return the greatest in your arr2
That's it
Cheers

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````class Node(object):
def __init__(self,data):

self.key = data
self.next = None

def longestSequence(root):
nodes = set()
sequences = {}
completesequences = {}
flat = []
while root not in nodes:
flat.append(root)
root = root.next

for node in flat:

if node.key in sequences:
seq = sequences.pop(node.key)
size = len(seq)
elem = completesequences.get(size,[])
elem.append(seq)
completesequences[size] = elem
else:
sequences[node.key] =[]
for key in sequences:
el = sequences[key]
el.append(node.key)
sequences[key] = el

maximum = max(completesequences.keys())
return completesequences[maximum]

if __name__ == '__main__':
root = Node(3)
root.next = Node(8)
root.next.next = Node(9)
root.next.next.next = Node(7)
root.next.next.next.next = Node(2)
root.next.next.next.next.next = Node(1)
root.next.next.next.next.next.next = Node(3)
root.next.next.next.next.next.next.next = Node(4)
root.next.next.next.next.next.next.next = Node(6)
root.next.next.next.next.next.next.next = root
print longestSequence(root)
pass``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

If 3 belongs to the sequence return sequence length :)

Comment hidden because of low score. Click to expand.
-1
of 1 vote

``if 3 belongs to the sequence return sequences length -1``

Comment hidden because of low score. Click to expand.
-1
of 1 vote

public static void main(String[] args) {
ListNode n1 = new ListNode(3);
ListNode n2 = new ListNode(8);
ListNode n3 = new ListNode(9);
ListNode n4 = new ListNode(7);
ListNode n5 = new ListNode(2);
ListNode n6 = new ListNode(3);
ListNode n7 = new ListNode(4);
ListNode n8 = new ListNode(6);
n1.next = n2;
n2.next = n3;
n3.next = n4;
n4.next = n5;
n5.next = n6;
n6.next = n7;
n7.next = n8;
n8.next = n1;
ListNode head = findPath(n1, 8);
while (head != null) {
}
}

public static ListNode findPath(ListNode head, int target) {
if (head == null)
while (true) {
if (head.next.val == target)
break;
}
ListNode p = head.next;
ListNode res = new ListNode(0);
ListNode nexPossible = p;
int len = 1;
int start = 1;
int max = 0;
while (p.next != null) {
if (p.next.val == target) {
ListNode next = p.next;
p.next = null;
if (len - start + 1 >= max) {
res.next = nexPossible;
max = len - start + 1;
}
nexPossible = next;
p = next;
len++;
start = len;
} else {
p = p.next;
len++;
}
}
if (start == 1)
return null;
if (len - start + 1 >= max) {
res.next = nexPossible;
}
return res.next;
}

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.