fork(5) download
copy 
  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
copy 
Standard input is empty
stdout
copy 
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!