A modest interview guide: part 1

The post was prepared to help programmers in preparing for programming interviews. It covers all the main topics that, at a minimum, it is desirable to know before the interview. We used our own experience, experience and stories of colleagues, specialized literature.
Some of the topics discussed here may not be useful to some programmers at all, or they may be mandatory, you decide. My advice is to try as much as possible to study the topics / sections / aspects mentioned here.
And so, as a required knowledge:

• Data structures
• Algorithms and "concepts"
• Programming language

The list above, of course, does not oblige to know everything related to them; it is not even realistic. At least for novice programmers. There is a certain minimum that you definitely need to know according to the author and some fairly qualified interviewers.

Data structures

• Arrays and strings
• Related Lists
• Stack and queue
• Trees and graphs

Algorithms and "concepts"

• Sort and search
• Recursion
• Bit manipulation
• Object Oriented Design

Programming language

• Basic components
• “Homemade” implemented projects
• As much as possible

And now on the shelves, what, how and why?

Data structures

Arrays and strings

Questions giving a general idea of ​​the "situation":
" Implement a function that determines whether all characters that do not repeat in a given string ".
For simplicity, imagine that there is an ASCII character set (if not, you will need to change the size of the “container”, the logic will not change anyway).
')

bool are_unique_characters(const std::string& str) { std::vector<bool> char_set(256, false); for (int i = 0; i < str.size(); ++i) { int val = str.at(i); if (char_set[val]) { return false; } char_set[val] = true; } return true; } 

The complexity in this case is O (n), where n is the length of the input string. It is very important that during the interview you mention the complexity and be able to really / correctly calculate the complexity of some algorithm.
If we assume that the string consists only of characters from “a” to “z” (lowercase letters), then the following code would be a better solution, since you can do without a vector.

 bool are_unique_characters(const std::string& str) { int checker = 0; for (int i = 0; i < str.size(); ++i) { int val = str.at(i) - 'a'; if ((checker & (1 << val)) > 0) { return false; } checker |= (1 << val); } return true; } 

For reflection - a classic problem: “ Turn over the C-line (meaning that“ abcd ”is five characters, the fifth is the terminating null character '\ 0') ”.
Compare your decision with this and answer the question, why is your code better?

 void reverse_c_string(char* str) { char* end = str; char tmp; if (str) { while (*end) { ++end; } --end; while (str < end) { tmp = *str; *str++ = *end; *end-- = tmp; } } } 

As a homework, try to solve this puzzle: “ Given an image as an array of NxN, where each element is one pixel and each pixel weighs 4 bytes. Write a function that will turn the image 90 degrees . ”

Related Lists

Questions related to the lists, to put it mildly, quite general. The question can be from a simple “remove a node from a linked list” to more thought-straining. Remember, when you are asked about linked lists, specify which list in question it is - simply connected or doubly linked. You should know, again, necessarily how to create a list and how to remove a node from a single-linked list.

Examples of tasks:
" Write code that removes duplicate items from an unsorted linked list ."
Having

 struct list_node { int data; list_node* next; }; 

The decision will be (and yours?):

 void delete_duplicates(list_node* head) { if (NULL == head) { return; } list_node* previous = head; list_node* current = previous->next; while (NULL != current) { list_node* runner = head; while (runner != current) { if (runner->data == current->data) { list_node* tmp = current->next; previous->next = tmp; current = tmp; break; } runner = runner->next; } if (runner == current) { previous = current; current = current->next; } } } 

" Implement an algorithm that removes a node from the middle of a single-linked list; you only have access to this node ."
The solution is simple, but it is important to understand that the problem is not solved if the node to be deleted is the last node in the list and your interviewer wants to hear it.

 bool delete_node(list_node* nd) { if (NULL == nd || NULL == nd->next) { return false; // whatta..? } list_node* nxt = nd->next; nd->data = nxt->data; nd->next = nxt->next; return true; } 

Questions to think about, aka homework:
" You have two numbers represented as a linked list, where each node contains one digit. Numbers are stored in reverse order. Write a function that subtracts the sum of these numbers and returns as a linked list.
Example: for the numbers 295 and 513 in total we get 808.
Input: (5 -> 9 -> 2), (3 -> 1 -> 5)
Output: (8 -> 0 -> 8) ".

" Find the middle of the linked list ."

Stack and queue

The necessary knowledge is the ability to implement the stack and the queue. Be sure to check all input values ​​and “boundary cases” in the implemented class methods.

" Write a class my_queue that implements a queue using two stacks ."
" Below is the solution to the previous problem, what is wrong with this code? "

 template <typename T> class my_queue { private: std::stack<T> m_stack1; std::stack<T> m_stack2; int size() const { return m_stack1.size() + m_stack2.size(); } void add(const T& value) { m_stack1.push(value); } T peek() { if (!m_stack2.empty()) { return m_stack2.top(); } while (!m_stack1.empty()) { m_stack2.push(m_stack1.top()); m_stack1.pop(); } return m_stack2.top(); } T remove() { if (!m_stack2.empty()) { T tmp = m_stack2.top(); m_stack2.pop(); return tmp; } while (!m_stack1.empty()) { m_stack2.push(m_stack1.top()); m_stack1.pop(); } return m_stack2.top(); } }; 

For reflection:
" Write a program that sorts the stack in ascending order ."

Trees and graphs

Questions on trees and graphs are mostly “in” in the following forms:

• Implement the tree / find the node / delete the node / other important algorithms
• Implement a modified version of the known algorithm

It is strongly recommended that you thoroughly prepare for trees and graphs before the interview and remember - “not all binary trees are binary search trees”.
You should be able to easily implement the following algorithms:

• Direct tree traversal (pre-order)
• In-order bypass
• Reverse crawl (post-order)
• Insert node

Graph knowledge required:

• Depth First Search
• Search Breadth (Breadth First Search)

" Given an array sorted (in ascending order), write an algorithm that creates a minimum-height binary tree ."
Algorithm:

1. Insert into the tree the middle element of the array
2. Insert (in the left subtree) elements of the "left subarray"
3. Insert (in the right subtree) elements of the "right subarray"
4. And so recursively

 tree_node* add_to_tree(int arr[], int start, int end) { if (end < start) { return NULL; } int mid = (start + end) / 2; tree_node* n = new tree_node(arr[mid]); n->left = add_to_tree(arr, start, mid - 1); n->right = add_to_tree(arr, mid + 1, end); return n; } tree_node* create_min_BST(int arr[]) { //... SIZE   //... arr   return add_to_tree(arr, 0, SIZE - 1); } 

For reflection:
" Implement a non-recursive symmetrical tree walk ."

UPD : As Shedal noted, this guide is (mostly) for students / juniors.

UPD 2 : Part Two.