CareerCup

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);
			}
			map.get(curr.val).add(i);
			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; }
	}

}

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;
        }
        hashSet.Add( curr.Value );

        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 ) {
            tmp.Add( curr );
            curr = curr.Next;
            continue;
        } 
        if ( list1.Count >= list2.Count ) {
            list2.Clear();
            list2.Add( curr );
            tmp = list2;
        } else {
            list1.Clear();
            list1.Add( curr );
            tmp = list1;
        }
        curr = curr.Next;
    }
    if ( list2.Count == 0 ) { return new List<Node>(); }
    return list1.Count >= list2.Count ? list1 : list2;
}

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

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);
	}
}

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);
	}
}

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);
}
}

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);
}
}

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);
	}
}

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));

}

I guess this is the easiest way:

int count = 0;
vector<int>arr1;
struct node *temp = head;
while(temp->next!=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

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:
        nodes.add(root)
        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

If 3 belongs to the sequence return sequence length :)

if 3 belongs to the sequence return sequences length -1

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) {
System.out.print(head.val + "->");
head = head.next;
}
}

public static ListNode findPath(ListNode head, int target) {
if (head == null)
return head;
while (true) {
if (head.next.val == target)
break;
head = head.next;
}
ListNode p = head.next;
head.next = null;
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;
}