Archive for the ‘Adobe’ Category

Q. There are k sorted lists and we have to merge them to make a single sorted list in best time.

A. I used min heap of size k to contain one element of each list. Each node of heap also contains the id of the list it belongs to.

  • Pick out first element of each list and push it into heap.
  • Take the minimum element out of the heap. Record the list it belongs to say list j.
  • Push the next element from list j back into heap.
  • Repeat the operation till all elements are parsed.

If all lists are of length n, each element has to pushed into heap at some point.

Complexity for pushing the element is logk in heap.

Overall complexity will be O(nk logk).

Q. Given a number, you have to compute nearest palindrome number. This palindrome number should be greater than given number.

A. Calculate the number of digits and get the most significant half out of it. For example, most significant first half of 2345 will be 23. Most significant first half of 45436 will be 454.

  • If number of digits are even, flip the most significant first half towards lower significant half that makes the palindrome. If the palindrome is smaller than the original, add one to the most significant half and then flip it over. Example, number -2345, most significant half -23, first candidate palindrome – 2332. Since, this is less than 2345, we add 1 to most significant half which makes it 24. Our next candidate for palindrome becomes 2445.
  • If number of digits are odd, we should not flip the middle one. For example, 45436, most significant digits will be 454 and our candidate for palindrome will be 45454. Since, it is greater than original, we’ll keep this as answer.
  • In case, adding one adds another digit to the number, we have to switch the process as per new number of digits.