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.             var hashTable = BuildHashTable(numbers);
  18.             return Analyze(hashTable, numbers.Length);
  19.         }
  20.  
  21.         private static Dictionary<int, List<Pair>> BuildHashTable(int[] numbers)
  22.         {
  23.             var hashTable = new Dictionary<int, List<Pair>>();
  24.             for(int i = 0; i < numbers.Length; ++i)
  25.             {
  26.                 for(int j = i + 1; j < numbers.Length; ++j)
  27.                 {
  28.                     Pair pair = new Pair
  29.                     {
  30.                         First = i,
  31.                         Second = j
  32.                     };
  33.  
  34.                     int diff = numbers[j] - numbers[i];
  35.                     if(hashTable.Keys.Contains(diff))
  36.                     {
  37.                         hashTable[diff].Add(pair);
  38.                     }
  39.                     else
  40.                     {
  41.                         List<Pair> newValue = new List<Pair>();
  42.                         newValue.Add(pair);
  43.                         hashTable[diff] = newValue;
  44.                     }
  45.                 }
  46.             }
  47.  
  48.             return hashTable;
  49.         }
  50.  
  51.         private static int Analyze(Dictionary<int, List<Pair>> hashTable, int lengthOfNumbers)
  52.         {
  53.             int maxLength = 0;
  54.             foreach(var key in hashTable.Keys)
  55.             {
  56.                 int[] lengths = new int[lengthOfNumbers];
  57.                 for (int i = 0; i < lengthOfNumbers; ++i)
  58.                 {
  59.                     lengths[i] = 1;
  60.                 }
  61.  
  62.                 foreach(Pair pair in hashTable[key])
  63.                 {
  64.                     lengths[pair.Second] = lengths[pair.First] + 1;
  65.                 }
  66.  
  67.                 foreach(var length in lengths)
  68.                 {
  69.                     if(length > maxLength)
  70.                     {
  71.                         maxLength = length;
  72.                     }
  73.                 }
  74.             }
  75.  
  76.             return maxLength;
  77.         }
  78.  
  79.         private static void Test(string testName, int[] numbers, int expected)
  80.         {
  81.             if(GetMaxLengthOfArithmeticSequence(numbers) == expected)
  82.             {
  83.                 Console.WriteLine(string.Format("{0} passed.", testName));
  84.             }
  85.             else
  86.             {
  87.                 Console.WriteLine(string.Format("{0} FAILED.", testName));
  88.             }
  89.         }
  90.  
  91.         private static void Test1()
  92.         {
  93.             int[] numbers = { 1, 3, 2, 4, 5 };
  94.             int expected = 3;
  95.             Test("test1", numbers, expected);
  96.         }
  97.  
  98.         private static void Test2()
  99.         {
  100.             int[] numbers = { 1, 2, 3, 4, 5, 6 };
  101.             int expected = 6;
  102.             Test("test2", numbers, expected);
  103.         }
  104.  
  105.         private static void Test3()
  106.         {
  107.             int[] numbers = { 5, 4, 3, 2, 1 };
  108.             int expected = 5;
  109.             Test("test3", numbers, expected);
  110.         }
  111.  
  112.         private static void Test4()
  113.         {
  114.             int[] numbers = { 3, 3, 3, 3 };
  115.             int expected = 4;
  116.             Test("test4", numbers, expected);
  117.         }
  118.  
  119.         private static void Test5()
  120.         {
  121.             int[] numbers = { 1, 8, 3, 6, 5, 4, 7, 2, 9 };
  122.             int expected = 5;
  123.             Test("test5", numbers, expected);
  124.         }
  125.  
  126.         private static void Test6()
  127.         {
  128.             int[] numbers = { 8, 3, 6, 5, 4, 7, 2 };
  129.             int expected = 4;
  130.             Test("test6", numbers, expected);
  131.         }
  132.  
  133.         private static void Test7()
  134.         {
  135.             int[] numbers = { 2, 10, 3, 6, 4, 5, 8, 9 };
  136.             int expected = 4;
  137.             Test("test7", numbers, expected);
  138.         }
  139.  
  140.         static void Main(string[] args)
  141.         {
  142.             Test1();
  143.             Test2();
  144.             Test3();
  145.             Test4();
  146.             Test5();
  147.             Test6();
  148.             Test7();
  149.         }
  150.     }
  151. }
  152.  
Success #stdin #stdout 0.05s 34064KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
test1 passed.
test2 passed.
test3 passed.
test4 passed.
test5 passed.
test6 passed.
test7 passed.
https://ideone.com/jxRDkd
Get the max length of an Arithmetic Sequence out of an array
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!