fork(5) download 
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4.  
  5. namespace Interview_ArithmeticSequence
  6. {
  7.     class Program
  8.     {
  9.         internal class Pair
  10.         {
  11.             public int First { get; set; }
  12.             public int Second { get; set; }
  13.         }
  14.  
  15.         public static int GetMaxLengthOfArithmeticSequence(int[] numbers)
  16.         {
  17.             Array.Sort(numbers);
  18.             var hashTable = BuildHashTable(numbers);
  19.             return Analyze(hashTable, numbers.Length);
  20.         }
  21.  
  22.         private static Dictionary<int, List<Pair>> BuildHashTable(int[] numbers)
  23.         {
  24.             var hashTable = new Dictionary<int, List<Pair>>();
  25.             for(int i = 0; i < numbers.Length; ++i)
  26.             {
  27.                 for(int j = i + 1; j < numbers.Length; ++j)
  28.                 {
  29.                     Pair pair = new Pair
  30.                     {
  31.                         First = i,
  32.                         Second = j
  33.                     };
  34.  
  35.                     int diff = numbers[j] - numbers[i];
  36.                     if(hashTable.Keys.Contains(diff))
  37.                     {
  38.                         hashTable[diff].Add(pair);
  39.                     }
  40.                     else
  41.                     {
  42.                         List<Pair> newValue = new List<Pair>();
  43.                         newValue.Add(pair);
  44.                         hashTable[diff] = newValue;
  45.                     }
  46.                 }
  47.             }
  48.  
  49.             return hashTable;
  50.         }
  51.  
  52.         private static int Analyze(Dictionary<int, List<Pair>> hashTable, int lengthOfNumbers)
  53.         {
  54.             int maxLength = 0;
  55.             foreach(var key in hashTable.Keys)
  56.             {
  57.                 int[] lengths = new int[lengthOfNumbers];
  58.                 for (int i = 0; i < lengthOfNumbers; ++i)
  59.                 {
  60.                     lengths[i] = 1;
  61.                 }
  62.  
  63.                 foreach(Pair pair in hashTable[key])
  64.                 {
  65.                     lengths[pair.Second] = lengths[pair.First] + 1;
  66.                 }
  67.  
  68.                 foreach(var length in lengths)
  69.                 {
  70.                     if(length > maxLength)
  71.                     {
  72.                         maxLength = length;
  73.                     }
  74.                 }
  75.             }
  76.  
  77.             return maxLength;
  78.         }
  79.  
  80.         private static void Test(string testName, int[] numbers, int expected)
  81.         {
  82.             if(GetMaxLengthOfArithmeticSequence(numbers) == expected)
  83.             {
  84.                 Console.WriteLine(string.Format("{0} passed.", testName));
  85.             }
  86.             else
  87.             {
  88.                 Console.WriteLine(string.Format("{0} FAILED.", testName));
  89.             }
  90.         }
  91.  
  92.         private static void Test1()
  93.         {
  94.             int[] numbers = { 1, 3, 2, 4, 8, 5, 7, 9, 11 };
  95.             int expected = 6;
  96.             Test("test1", numbers, expected);
  97.         }
  98.  
  99.         private static void Test2()
  100.         {
  101.             int[] numbers = { 1, 2, 3, 4, 5, 6 };
  102.             int expected = 6;
  103.             Test("test2", numbers, expected);
  104.         }
  105.  
  106.         private static void Test3()
  107.         {
  108.             int[] numbers = { 5, 4, 3, 2, 1 };
  109.             int expected = 5;
  110.             Test("test3", numbers, expected);
  111.         }
  112.  
  113.         private static void Test4()
  114.         {
  115.             int[] numbers = { 3, 3, 3, 3 };
  116.             int expected = 4;
  117.             Test("test4", numbers, expected);
  118.         }
  119.  
  120.         private static void Test5()
  121.         {
  122.             int[] numbers = { 3, 2, 1, 3, 7, 10, 3, 6, 9, 3 };
  123.             int expected = 4;
  124.             Test("test5", numbers, expected);
  125.         }
  126.  
  127.         private static void Test6()
  128.         {
  129.             int[] numbers = { 8, 3, 0, 5, 4, 9, 2 };
  130.             int expected = 4;
  131.             Test("test6", numbers, expected);
  132.         }
  133.  
  134.         private static void Test7()
  135.         {
  136.             int[] numbers = { 3, 2, 1, 3, 4, 5, 3, 6, 9, 3 };
  137.             int expected = 6;
  138.             Test("test7", numbers, expected);
  139.         }
  140.  
  141.         private static void Test8()
  142.         {
  143.             int[] numbers = { 2, 10, 3, 6, 4, 5, 8, 9 };
  144.             int expected = 5;
  145.             Test("test8", numbers, expected);
  146.         }
  147.  
  148.         private static void Test9()
  149.         {
  150.             int[] numbers = { 1, 6, 3, 5, 9, 7 };
  151.             int expected = 5;
  152.             Test("test9", numbers, expected);
  153.         }
  154.  
  155.         static void Main(string[] args)
  156.         {
  157.             Test1();
  158.             Test2();
  159.             Test3();
  160.             Test4();
  161.             Test5();
  162.             Test6();
  163.             Test7();
  164.             Test8();
  165.             Test9();
  166.         }
  167.     }
  168. }
  169.  
Success #stdin #stdout 0.05s 34032KB
comments (?)
stdin 
Standard input is empty
stdout 
test1 passed.
test2 passed.
test3 passed.
test4 passed.
test5 passed.
test6 passed.
test7 passed.
test8 passed.
test9 passed.
https://ideone.com/lEqNm3
Get the max length of an Arithmetic Sequence out of an array (No order limitation)
language:
C# (gmcs 5.20.1)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!