I appeared for the Amazon SDE-I FTE (Full-Time Equivalent) hiring process through my college campus in March 2021. The process began with an online coding round, followed by three rounds of virtual interviews.

Online Coding Round: Approximately 40 candidates were shortlisted from the online coding round for the interview process, which was held the following week.

In the online coding round, two questions were asked (different questions for different candidates): one was a bit tricky, and the other was easier. I did not complete either question successfully. For the first question, I passed about 8 out of 13 total test cases. For the second, I passed only 2 out of 9.

I thought I had no chance of qualifying, but when the shortlist was published, I was surprised to find myself high up on the list. I later learned that the developers who create these questions thoroughly review your code to determine if you used the correct logic, or at least a close approximation.

Given a string S of distinct characters of size N and their corresponding frequencies f[], where character S[i] has frequency f[i]. Your task is to build the Huffman tree and print all the Huffman codes in preorder traversal of the tree.

Note:

• While merging, if two nodes have the same value, the node that occurs first will be taken on the left of the binary tree, and the other one to the right.
• Otherwise, the node with the less value will be taken on the left of the subtree, and the other one to the right.