title: How to instruct longest palindrome from a list of numbers?
body: <p>I am trying to solve a question which says that we need to write a function in which given a list of numbers, we need to find the longest palindrome that we can from given only the numbers in the list.</p>
  <p>For eg:</p>
  <p>If the given list is : [3,47,6,6,5,6,15,22,1,6,15]</p>
  <p>The longest palindrome that we can return is one of length 9, such as [6,15,6,3,47,3,6,15,6].</p>
  <p>Additionally, we have the following constraints:</p>
  <p>One can only use an array queue, array stack, and a chaining hashmap, and the list we are supposed to return, and the function must run in linear time. And we can use only constant additional space.</p>
  <p>My approach was the following:</p>
  <p>Since a palindrome can be formed if have an even number of certain characters, we can iterate over all the elements in the list, and store in a chaining hash map, the number of times each number appears in the list. This should take O(N) time since each lookup in the chaining hash map takes constant time, and iterating over the list takes linear time.</p>
  <p>Then we can iterate over all the numbers in the chaining hash map, to see which numbers appear an even number of times, and accordingly, just make a palindrome. In the worst case, this will take a O(n) linear time.</p>
  <p>Now there are two things I am wondering:</p>
  <ol>
  <li><p>How should I make the actual palindrome? Like how do I use the data structures that I am being allowed to use in order to make a palindrome? I am thinking that since the queue is a LIFO data structure, for each number that occurs an even number of times, we add it once to the queue and once to the stack, and so on and so forth. And finally, we can just dequeue everything from the queue, and pop once from the stack, and then add it to the list!</p>
  </li>
  <li><p>It seems that with my approach, it is taking me two linear runs to solve the question. I am wondering if there is a faster way to do this.</p>
  </li>
  </ol>
  <p>Any and all help will be appreciated. Thanks!</p>