# Prepare for Software Engineer test and interviews

## What are good learning resources to help me prepare for test and interviews?

We recommend going through TopCoder educational website. We also recommend reading some of these books, although they by far exceed the knowledge needed for passing the test:

• "Introduction to algorithms" by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein
• "Algorithms" by Robert Sedgewick and Kevin Wayne
• "Introduction to Algorithms: A creative approach" by Udi Manber
• "Algoritmi i strukture podataka" by Milo Tomašević
• "Algoritmi" lectures at MATF Belgrade by Miodrag Živković"

### Can you give me some advice on preparing myself for the test?

Focus on concepts rather than on a form of an algorithm you learn. Try solving the problem by yourself before reading the entire algorithm from these books. Understanding the essentials of algorithms helps you in better understanding how the author originally came up with a particular algorithm and more importantly it improves your ability to come up with new algorithms.

### What are the areas we can expect on the entrance test? Should I learn AVL trees?

Understanding and solving problems on the test requires university level knowledge in algorithms/programming. You should understand the concepts of algorithm complexity and at least know about sorting, binary search, dynamic programming, recursion, and divide-and-conquer techniques. There is no need to learn complex algorithms for the test. If you do know some of the more advanced algorithms we will definitely enjoy discussing them during interviews.

There are usually 4 programming problems on the test.

Here are some examples:

Two strings A and B are isomorphic if there exists character mapping which replaces characters from A to get B. Rules for character mapping are:

• all occurrences of one character (e.g. ‘x’) must be replaced with the same character (e.g. ‘y’)
• no two different characters may map to the same character
• a character may map to itself

Write a function that returns true if provided strings are isomorphic, otherwise false:

bool AreStringsIsomorphic(char* a, char* b)

The strings are NULL-terminated, with characters from lower case English alphabet ‘a’ – ‘z’.

Examples:

A = “brain”, B = “space”true
A = “noon”, B = “feet”false
A = “aab”, B = “ccd”false

You are given an array of integers, denoted with a of length m, where first number in array is odd and the last number is even. You need to write a function

TreeNode generateTree(int m, int* a)

that will create a N-ary tree from this array with the following properties:

• Leaf nodes of the tree are even numbers and inner nodes are odd numbers
• Pre order traversal of the tree is equal to the original array

If there are multiple solutions (trees which satisfy above properties) return any of them. N could be any integer number. Tree node is represented as

{
int value;
TreeNode* sibling; // Pointer to the next sibling, or NULL if next sibling does not exist
TreeNode* firstChild; // Pointer to the first child, or NULL if this is leaf
};

sibling and firstChild should be set to NULL if corresponding nodes don’t exist.

Examples:

m=9
a = 3, 1, 4, 48, 2, 5, 3, 6, 18

Given image is showing one possible solution. Gray nodes are inner nodes of a tree and they have odd values inside. Leaf nodes (the ones that don’t have child nodes) are white and they have even values. Dotted lines represent sibling pointers and children pointers are represented with full lines.

Tree pre-order: Display the data part of the root (current node). After that, recursively call traversals for root children in given order: traverse the first child subtree by recursively calling the pre-order function; traverse the second child subtree by recursively calling the pre-order function; etc.

Pre-order: F, B, A, D, C, E, G, I, H.

You are given an array a of length n = 2m. Write a function that finds length of the minimal period T of array a.

int MinPeriod(int * a, int n)

Number T is a period of array a, if repeating first T elements of array a several times gives exactly array a, without any extra elements.

Examples:

n = 8 4
a = {2, 5, 3, 4, 2, 5, 3, 4}
n = 8 8
a = {2, 5, 3, 2, 5, 3, 2, 5}

Single linked lists contain nodes which have a data field as well as a 'next' field, which points to the next node in list of nodes.

Node is defined as

{
char data;
Node* next;
};

Last node in list has next pointer equal to NULL.

Write a function

void reverseNodes(Node** head, int indexA, int indexB)

which should reverse order of nodes in list, starting from node on position indexA until node on position indexB.

Head node is on position 1.

Examples:

‘a’ -> ‘c’ -> ‘x’ -> ‘q’ -> ‘e’ -> ‘2’
indexA = 2‘a’ -> ‘q’ -> ‘x’ -> ‘c’ -> ‘e’ -> ‘2’
indexB = 4