fork(3) 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
stdin
Standard input is empty
stdout
test1 passed.
test2 passed.
test3 passed.
test4 passed.
test5 passed.
test6 passed.
test7 passed.
test8 passed.
test9 passed.