- Published on
four interview questions
- Authors
- Name
- light-city
Come on, let's solve four interview questions together
Table of Contents
1. Introduction
Below are four interview questions from a certain large company.
- Maximum Subarray
- Deep Copy Linked List with Random Pointers
- Count the number of 1s in a 32-bit integer
- Big Number Multiplication
This section focuses on the ideas and implementations of these four questions, and corresponding problems have been found on Nowcoder and LeetCode. All code in this article has passed the online judge (OJ).
2. Maximum Subarray
Problem Description:
Given a sequence of K integers { N1, N2, ..., NK }, any continuous subsequence can be represented as { Ni, Ni+1, ..., Nj }, where 1 <= i <= j <= K. The maximum continuous subsequence is the one with the largest sum of elements, for example, for the sequence -2, its maximum continuous subsequence is 13, and the maximum sum is 20. Now an additional requirement is to output the first and last elements of this subsequence.
Input Description:
The test input contains several test cases, each consisting of 2 lines. The first line gives a positive integer K (K < 10000), and the second line gives K integers separated by spaces. When K is 0, the input ends, and this case is not processed.
Output Description:
For each test case, output the maximum sum, the first, and the last element of the maximum continuous subsequence on one line, separated by spaces. If there are multiple maximum continuous subsequences, output the one with the smallest indices (as in the second and third cases of the input example). If all K elements are negative, then define the maximum sum as 0 and output the first and last elements of the entire sequence.
Test your code:
Solution:
The problem simplifies to finding the longest, continuous subsequence and returning the left and right endpoints. When there are multiple results, return the endpoints of the first subsequence.
The problem states that if all K elements are negative, the maximum sum is defined as 0, and the left and right boundaries are the first and last elements of the sequence, respectively. When the current element is negative, the maximum sum at the current position is 0. When updating the maximum sum, update both left and right boundaries. The state equation is: dp[k] = dp[k-1] + v[k]. If dp[k] <= 0, then dp[k] is 0.
Implementation:
int main() {
int n;
cin >> n;
if (n == 0) {
cout << 0 << " " << 0 << " " << 0 << endl;
return 0;
}
vector<int> v(n);
for (int i = 0; i < n; i++)
cin >> v[i];
vector<int> dp(n);
// Check if all elements are less than or equal to 0
bool flag = false;
for (int i = 0; i < n; i++) {
if (v[i] > 0) {
flag = true;
break;
}
}
// If all elements are less than or equal to 0, the sum is 0, and the left and right boundaries are the first and last elements
if (!flag) {
cout << 0 << " " << v[0] << " " << v[v.size() - 1] << endl;
return 0;
}
int i = 0, j = 0, max_res = -1;
// Initialize dp
if (v[0] <= 0) {
dp[0] = 0;
i++; // Start from the next position
} else {
dp[0] = v[0];
max_res = dp[0]; // Update the maximum sum
i = 0; // Start from 0
}
// Record the first minimum lower bound
int min_i;
for (int k = 1; k < n; k++) {
dp[k] = dp[k - 1] + v[k];
if (dp[k] <= 0) {
dp[k] = 0;
i = k + 1;
}
// Since we need to output the first minimum lower and upper bounds, we cannot use the equal sign
if (dp[k] > max_res) {
j = k;
min_i = i;
max_res = dp[k];
}
}
cout << max_res << " " << v[min_i] << " " << v[j] << endl;
}
3. Deep Copy Linked List with Random Pointers
Problem Description:
Please implement the copyRandomList function to copy a complex linked list. In a complex linked list, each node has a next pointer pointing to the next node and a random pointer pointing to any node in the list or null.
Example 1:
Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]] Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]
Solution:
This problem involves many knowledge points, including linked lists, graph, and tree traversal.
How is it related to graphs and trees? It's simple. With the addition of the random pointer, you can consider a node containing both next and random pointers as a node in a tree with two children. This leads to tree traversal. When the random forms a loop, it forms a graph. Thus, this problem covers various knowledge points and has a broad scope.
Test your code:
Implementation:
1. DFS Method
class Solution {
private:
// oldNode:newNode
map<Node *, Node *> m; // Handle loops
public:
Node *copyRandomList(Node *head) {
if (head == NULL) return NULL;
if (m.count(head) > 0) return m[head];
Node *cloneNode = new Node(head->val);
m[head] = cloneNode;
cloneNode->next = copyRandomList(head->next);
cloneNode->random = copyRandomList(head->random);
return clone
Node;
}
};
2. BFS Method
class Solution {
private:
// oldNode:newNode
map<Node *, Node *> m; // Handle loops
public:
Node *copyRandomList(Node *head) {
if (!head) return NULL;
queue<Node *> q;
q.push(head);
Node *cloneNode = new Node(head->val);
m[head] = cloneNode;
while (!q.empty()) {
Node *cur = q.front();
q.pop();
// If cur->next has not been copied
if (cur->next && m.count(cur->next) == 0) {
m[cur->next] = new Node(cur->next->val);
q.push(cur->next);
}
// If cur->random has not been copied
if (cur->random && m.count(cur->random) == 0) {
m[cur->random] = new Node(cur->random->val);
q.push(cur->random);
}
m[cur]->next = m[cur->next];
m[cur]->random = m[cur->random];
}
return cloneNode;
}
};
3. Iterative Method
class Solution {
private:
// oldNode:newNode
map<Node *, Node *> m; // Handle loops
public:
Node *copyRandomList(Node *head) {
Node *oldHead = head;
Node *cloneNode = NULL;
while (oldHead) {
cloneNode = get(oldHead);
cloneNode->next = get(oldHead->next);
cloneNode->random = get(oldHead->random);
oldHead = oldHead->next;
cloneNode = cloneNode->next;
}
return m[head];
}
Node *get(Node *oldNode) {
if (!oldNode) return NULL;
Node *cloneNode;
if (m.count(oldNode) > 0) cloneNode = m[oldNode];
else {
cloneNode = new Node(oldNode->val);
m[oldNode] = cloneNode;
}
return cloneNode;
}
};
4. Iterative Method (Optimized)
class Solution {
public:
Node *copyRandomList(Node *head) {
if (head == NULL) return NULL;
Node *p = head;
// Build a new list with alternating old and new nodes
while (p) {
Node *newNode = new Node(p->val);
newNode->next = p->next;
p->next = newNode;
p = newNode->next;
}
p = head;
// Connect random pointers: A->A'->B->B'->NULL
while (p) {
p->next->random = p->random ? p->random->next : NULL;
p = p->next->next;
}
Node *oldHead = head;
Node *newHead = head->next, *q = newHead;
p = oldHead;
// Break the old and new lists
while (p) {
p->next = p->next->next;
q->next = q->next ? q->next->next : NULL;
p = p->next;
q = q->next;
}
return newHead;
}
};
4. Count the Number of 1s in a 32-bit Integer
Problem Description:
Please implement a function that takes an integer as input and outputs the number of 1s in its binary representation. For example, if 9 is represented in binary as 1001, there are 2 1s. Therefore, if the input is 9, the function outputs 2.
Example 1:
Input: 00000000000000000000000000001011 Output: 3 Explanation: The input binary string 00000000000000000000000000001011 has a total of three '1' bits.
Solution:
Method 1: Easy way, not recommended in interviews.
class Solution {
public:
int hammingWeight(uint32_t n) {
int count=0;
while(n!=0) {
if((1&n)==1) count++;
n/=2;
}
return count;
}
};
Method 2: In the case where n/=2 is replaced by bit operation n>>1, there may be problems. Analysis: For negative numbers, the highest bit is 1. Negative numbers are stored in two's complement in the computer. When shifting right, the sign bit remains unchanged. If the sign bit 1 is shifted right, it may eventually become all 1, resulting in an infinite loop. To eliminate the impact of negative numbers, perform a bitwise AND with 0xffffffff. After ANDing with 0xffffffff, n is a positive number, just like the two's complement of a negative number.
class Solution {
public:
int hammingWeight(uint32_t n) {
int count=0;
if(n<0) n = n&0xffffffff;
while(n!=0) {
count+=1&n;
n=n>>1;
}
return count;
}
};
Method 3: If there is no shift operation, there is no problem mentioned above. Therefore, you can use the n&(n-1) method, which removes one 1 each time.
class Solution {
public:
int hammingWeight(uint32_t n) {
int count=0;
while(n!=0) {
count++;
n=n&(n-1);
}
return count;
}
};
Method 4: To determine if a number is a power of 2:
bool powerof2(int n)
{
return ((n & (n-1)) == 0);
}
5. Big Number Multiplication
Problem Description:
Implement big number multiplication. The input consists of two strings, such as n1 = '340282366920938463463374607431768211456' n2 = '340282366920938463463374607431768211456' The output should be '115792089237316195423570985008687907853269984665640564039457584007913129639936' Requirements: Do not use built-in language support for big number multiplication; validate input strings.
Solution:
During an interview, when given the task of big number multiplication, you should think about converting it into a string for processing!
For strings, you need to handle some special conditions, such as when one of the factors is empty or zero. In such cases, the result is zero, and for other cases, use the vertical method for multiplying two numbers.
In the specific implementation process, pay attention to several points:
- The number of digits in the multiplication result does not exceed the sum of the two digits
- The number of the current bit is equal to the number of the current bit + multiplication result + carry
- The current number of reserved digits is the number of the current digit and modulo 10
- The carry of the current bit is the result of dividing the number of the current bit by 10