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