1. Several forms of interview tearing code:
1. Platform class
Go to the interviewer on the platform given by the interviewer, on which you can write code, debug and run. Some of these platforms have written function frameworks, and some are whiteboards. You need to write all the content yourself
2. Own IDE
The interviewer asks the candidate to open their own ide and share the desktop for writing. This kind of must write all the input and output by themselves.
3. Request to complete the test cases
Some interviewers, such as those from Microsoft, may ask you to design as comprehensive a test case as possible after you write the code to test the code you wrote.
2.1 input
1)cin
Cin is a standard input stream object in C++. The two usages of cin are listed below, read in individually, and read in batches
The principle of cin, in simple terms, is that there is a buffer. The data input by our keyboard will be stored in the buffer first, and the data can be read from the buffer with cin.
- cin can continuously read data from the keyboard
- cin uses spaces, tab s, and newlines as separators
- cin starts reading from the first non-whitespace character until it encounters a delimiter and ends reading
// Usage 1, read in single data
int num;
cin >> num;
cout << num << endl; // output the integer num read in
// Usage 2, read in multiple data in batches
vector<int> nums(5);
for (int i = 0; i < nums.size(); i++) {
cin >> nums[i];
}
// output read array
for (int i = 0; i < nums.size(); i++) {
cout << nums[i] << " ";
}
2)getline()
From the attention of cin, it can also be seen that when there is a space in the middle of the string we require to read, cin will not read the entire string. At this time, the getline() function can be used to solve it.
- When using the getline() function, you need to include the header file
- The getline() function will read a line, the read string includes spaces, and ends with a newline character
string s; getline(cin, s); // output the read string cout << s << endl;
3)getchar()
This function will read a character from the buffer, often used to determine whether to wrap
char ch; ch = getchar(); // output the characters read cout << ch << endl;
2.2 Output
On the output side, we mainly introduce a function, which is the most used cout. It should be noted that if the endl object is output, a newline character will be output, similar to \n.
string s = "hello, Irray~"; // see how they differ cout << "hello, Irray~"; cout << s << endl;
Of course, there are more than these input and output functions in C++. Other input functions include scanf(), cin.get(), etc., and output functions also include printf(), clog, cerr, etc., depending on the specific usage scenario. , select a specific input and output function.
3. Case
(1) One-dimensional array
This type of input, each element is an int or char, there are two common cases:
1. Fixed number
Input format:
3 1 2 3 or 3 1 2 3
Parse:
For the first group, 3 in the first line is the number of integers, and the second line is three integers separated by spaces, so cin can be used to read
For the second group, 3 in the first line is the number of integers, and the data after the space is three integers separated by spaces, so cin can be used to read
For such problems, you can create a vector first, set the size to a given value, and then loop through the for loop to input
Answer:
int n;
cin >> n; // Read 3, indicating that the size of the array is 3
vector<int> nums(n); // Create a vector<int> of size 3
for (int i = 0; i < n; i++) {
cin >> nums[i];
}
// Verify whether the read is successful
for (int i = 0; i < nums.size(); i++) {
cout << nums[i] << " ";
}
cout << end
2. Unfixed number
Input format:
1 2 3 4
Parse:
The input data is four integers separated by spaces, and the number of integers is not specified, so you can use a while loop combined with cin to deal with this problem.
Answer:
vector<int> nums;
int num;
while (cin >> num) {
nums.push_back(num);
// Read a newline character, terminate the loop
if (getchar() == '\n') {
break;
}
}
// Verify whether the read is successful
for (int i = 0; i < nums.size(); i++) {
cout << nums[i] << " ";
}
cout << endl;
(2) Two-dimensional array
In addition to the most basic input of a one-dimensional array, the input of a two-dimensional array will also be examined, especially in the dfs and dp types of topics.
There are two main ways to create a two-dimensional array:
1. Normal mode
Input format:
2 3 1 2 3 1 2 3
Parse:
The 2 in the first row means that the data is 2 rows, and the 3 means that the data is 3 columns. Therefore, according to the first row, it can be concluded that the input data is a two-dimensional array with 2 rows and 3 columns. The next 6 numbers are 2x3 two-dimensional arrays separated by spaces and newlines, so they can be processed with for loops and cin
Answer:
int m; // Rows received
int n; // Receive columns
cin >> m >> n;
vector<vector<int>> matrix(m, vector<int>(n));
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
cin >> matrix[i][j];
}
}
// Verify whether the read is successful
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
cout << matrix[i][j] << " ";
}
cout << endl;
}
2. Each line of data is an integer separated by commas
Input format:
2 3 1,2,3 1,2,3
Parse:
The 2 in the first row means that the data is 2 rows, and the 3 means that the data is 3 columns. Therefore, according to the first row, it can be concluded that the input data is a two-dimensional array with 2 rows and 3 columns. The next 2 lines are a string, each integer is separated by a comma. Here, the method of reading in strings is adopted, and the read in strings are separated by commas.
Answer:
int m; // Rows received
int n; // Receive columns
cin >> m >> n;
vector<vector<int>> matrix(m);
for (int i = 0; i < m; i++) {
// read string
string s;
getline(cin, s);
// Separate the read strings into vector<int> by commas
vector<int> vec;
int p = 0;
for (int q = 0; q < s.size(); q++) {
p = q;
while (s[p] != ',' && p < s.size()) {
p++;
}
string tmp = s.substr(q, p - q);
vec.push_back(stoi(tmp));
q = p;
}
//write matrix
matrix[i] = vec;
vec.clear();
}
// Verify whether the read is successful
for (int i = 0; i < matrix.size(); i++) {
for (int j = 0; j < matrix[i].size(); j++) {
cout << matrix[i][j] << " ";
}
cout << endl;
}
(3) String
1. Single String
Input format:
abc
Parse:
Just use cin to read in
Answer:
string s; cin >> s; // Verify whether the read is successful cout << s << endl;
2. A given number of strings
Input format:
3 abc ab a
Parse:
The 3 in the first line means that there are 3 strings, followed by 3 strings separated by spaces, which can be read by using for loop and cin
Answer:
int n;
cin >> n; // Read 3, indicating that the size of the string array is 3
vector<string> strings(n); // Create a vector<string> of size 3
for (int i = 0; i < n; i++) {
cin >> strings[i];
}
// Verify whether the read is successful
for (int i = 0; i < strings.size(); i++) {
cout << strings[i] << " ";
}
cout << endl;
3. Unspecified number of multiple strings
Input format:
abc ab a d
Parse:
Enter several strings separated by spaces.
Answer:
vector<string> strings;
string str;
while (cin >> str) {
strings.push_back(str);
// Read a newline character, terminate the loop
if (getchar() == '\n') {
break;
}
}
// Verify whether the read is successful
for (int i = 0; i < strings.size(); i++) {
cout << strings[i] << " ";
}
cout << endl;
4. String to integer array
Input format:
11,22,3,4
Parse:
The input is a complete string, and the content of the string is an array separated by commas. You can read the complete string first, and then separate it by commas
Answer:
vector<int> vec;
// read string
string s;
getline(cin, s);
// Separate the read strings into vector<int> by commas
int p = 0;
for (int q = 0; q < s.size(); q++) {
p = q;
while (s[p] != ',' && p < s.size()) {
p++;
}
string tmp = s.substr(q, p - q);
vec.push_back(stoi(tmp));
q = p;
}
// Verify whether the read is successful
for (int i = 0; i < vec.size(); i++) {
cout << vec[i] << " ";
}
cout << endl;
4.ACM mode practice platform
In addition to actual combat in the written test, you can also practice on the Niu Ke platform: https://ac.nowcoder.com/acm/contest/5652
There are also many special ACM mode algorithm questions on Niuke.
A) I don't know how many groups: A+B (1)
#include <iostream>
using namespace std;
int main() {
int a,b;
while (cin >> a >> b) {
cout << a + b << endl;
}
return 0;
}
B) Number of known input groups: A+B (2)
#include<iostream>
using namespace std;
int main(){
int t;
cin>>t;
int a,b;
while(cin>>a>>b){
cout<<a+b<<endl;
}
return 0;
}
C) Unknown multiple groups + end condition + 0 end: A+B (3)
#include<iostream>
using namespace std;
int main(){
int a,b;
while(cin>>a>>b){
if(a==0&&b==0){
break;
}
cout<<a+b<<endl;
}
return 0;
}
D) Unknown multiple groups + given n data within the group: A+B (4)
#include<iostream>
#include<string>
using namespace std;
int main(){
int n;
while(cin>>n&&n!=0){
int temp=0,sum=0;
while(getchar()!='\n'){
cin>>temp;
sum+=temp;
}
cout<<sum<<endl;
}
return 0;
}
E)t group input + given n data in the group: A+B (5)
#include<iostream>
#include<string>
using namespace std;
int main(){
int t;
cin>>t;
int n;
while(cin>>n&&n!=0){
int temp=0,sum=0;
while(getchar()!='\n'){
cin>>temp;
sum+=temp;
}
cout<<sum<<endl;
}
return 0;
}
F) Unknown multiple groups + n data within the group: A+B (6)
#include<iostream>
#include<string>
using namespace std;
int main(){
int n;
while(cin>>n&&n!=0){
int temp=0,sum=0;
while(getchar()!='\n'){
cin>>temp;
sum+=temp;
}
cout<<sum<<endl;
}
return 0;
}
G) Unknown multiple groups + unknown numbers separated by spaces: A+B (7)
#include<iostream>
#include<string>
using namespace std;
int main(){
int cur;
int sum=0;
while(cin>>cur){
sum+=cur;
if(getchar()=='\n'){
cout<<sum<<endl;
sum=0;
}
}
return 0;
}
H) Strings separated by n spaces: string sorting (1)
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;
int main(){
int n;
cin>>n;
vector<string>v(n);
string temp;
for(int i=0;i<n;i++){
cin>>v[i];
}
sort(v.begin(),v.end());
for(auto &i:v){
cout<<i<<" ";
}
return 0;
}
I) Unknown characters separated by multiple lines + spaces in the line: string sorting (2)
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
void print(vector<string>&v){
for(auto &i:v){
cout<<i<<" ";
}
cout<<endl;
}
int main(){
vector<string>v;
string s;
while(cin>>s){
v.push_back(s);
//if(cin.get() == '\n')
if(getchar()=='\n'){
sort(v.begin(),v.end());
print(v);
v.clear();
}
}
return 0;
}
J) Unknown multiple lines + separated by commas: string sorting (3)
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
void print(vector<string>&strs){
for (int i=0; i<strs.size(); ++i){
if (i==0) cout << strs[0];
else cout<<","<< strs[i];
}
cout<<endl;
}
int main(){
string str;
vector<string> strs;
string cur;
while (cin>>str){
for(int i=0; i<str.size(); ++i){
if (str[i]!=','){
cur += str[i];
}
else{
strs.emplace_back(cur);
cur.clear();
}
}
strs.emplace_back(cur);
cur.clear();
sort(strs.begin(),strs.end());
print(strs);
strs.clear();
}
return 0;
}
K) Self-test local pass submission is 0
#include<iostream>
using namespace std;
int main(){
long a,b;
while(cin>>a>>b){
cout<<a+b<<endl;
}
return 0;
}
5. Definition of common data structures
In the ACM mode, the definitions of data structures such as linked lists and binary trees also need to be defined by themselves. Next, the definitions, input and output of the two are given.
The code is given directly here, presumably everyone knows the data structure well.
1. Linked list
#include <iostream>
using namespace std;
// Linked list definition, and give two constructors with parameters
struct ListNode{
int val;
ListNode* next;
ListNode(int _val) :val(_val), next(nullptr) {}
ListNode(int _val, ListNode* _next) :val(_val), next(_next) {}
};
int main(){
// According to the input of the console, create a singly linked list
ListNode* LHead = new ListNode(-1);
ListNode* pre = LHead;
ListNode* cur = nullptr;
int num;
while (cin >> num){
// For simplicity, set it to -1 to exit, and it can be optimized later. Here is just an example
if (num == -1) break;
cur = new ListNode(num);
pre->next = cur;
pre = cur;
}
cur = LHead->next;
// Output the value of the singly linked list
while (cur){
cout << cur->val << " ";
cur = cur->next;
}
cout << endl;
return 0;
}
2. Binary tree
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
//define tree node
struct TreeNode{
int val;
TreeNode* left;
TreeNode* right;
TreeNode() :val(0), left(nullptr), right(nullptr) {}
TreeNode(int _val) :val(_val), left(nullptr), right(nullptr) {}
TreeNode(int _val, TreeNode* _left, TreeNode* _right) :val(0), left(_left), right(_right) {}
};
//Generate a tree from an array
TreeNode* buildTree(const vector<int>& v){
vector<TreeNode*> vTree(v.size(), nullptr);
TreeNode* root = nullptr;
for (int i = 0; i < v.size(); i++){
TreeNode* node = nullptr;
if (v[i] != -1){
node = new TreeNode(v[i]);
}
vTree[i] = node;
}
root = vTree[0];
for (int i = 0; 2 * i + 2 < v.size(); i++){
if (vTree[i] != nullptr){
vTree[i]->left = vTree[2 * i + 1];
vTree[i]->right = vTree[2 * i + 2];
}
}
return root;
}
//Traverse and print according to the order of the root node of the binary tree
void printBinaryTree(TreeNode* root){
if (root == nullptr) return;
vector<vector<int>> ans;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()){
int size = q.size();
vector<int> path;
for (int i = 0; i < size; i++){
TreeNode* node = q.front();
q.pop();
if (node == nullptr){
path.push_back(-1);
}
else{
path.push_back(node->val);
q.push(node->left);
q.push(node->right);
}
}
ans.push_back(path);
}
for (int i = 0; i < ans.size(); i++){
for (int j = 0; j < ans[i].size(); j++){
cout << ans[i][j] << " ";
}
cout << endl;
}
return;
}
int main(){
// verify
vector<int> v = { 4,1,6,0,2,5,7,-1,-1,-1,3,-1,-1,-1,8 };
TreeNode* root = buildTree(v);
printBinaryTree(root);
return 0;
}