admin管理员组文章数量:1582682
- develop a fresh algorithm, solve real problems
- 45 minutes, one problem
- false negative are acceptable
- relative comparison
- hard questions are not bad
- screening interview
- on-site 3-6 interview
- Delays can and do happen.
- Microsoft/Amazon/Google/Apple/Facebook(Meta)/Palantir
- Why work for Microsoft?
- bar raiser, percent correct
- enthusiastic endorser
- system design and architecture
Arrays and Strings
- HashTable, ArrayList & Resizable arrays, StringBuilder
ASCII is used for representing 128 English characters in the form of numbers, with each letter being assigned to a specific number in the range 0 to 127.
Unicode and ASCII are the most popular character encoding standards that are currently being used all over the world. Unicode is the universal character encoding used to process, store and facilitate the interchange of text data in any language while ASCII is used for the representation of text such as symbols, letters, digits, etc. in computers.
Unicode can be defined with different character encoding like UTF-8, UTF-16, UTF-32, etc. Among these UTF-8 is the most popular as it used in over 90% of websites on the World Wide Web as well as on most modern Operating systems like Windows.
387. First Unique Character in a String
class Solution {
public:
int firstUniqChar(string s) {
map<char,int> charMap;
for (auto c: s) {
// auto it = charMap.find(s[i]);
// if (it == charMap.end()) {
// charMap.insert(it, pair<char,int>(s[i], 1));
// } else {
// charMap.at(s[i]) += 1;
// }
charMap[c]++;
}
for (int i = 0; i < s.size(); i++) {
if (charMap[s[i]] == 1) {
return i;
}
}
return -1;
}
};
最简单的map,key直接是char就可以了,不用index了
345. Reverse Vowels of a String
class Solution {
public:
string reverseVowels(string s) {
int begin = 0, end = s.size();
do {
begin = s.find_first_of("aeiouAEIOU", begin);
end = s.find_last_of("aeiouAEIOU", end);
if (begin < end) {
swap(s[begin], s[end]);
begin++;
end--;
}
} while (begin < end);
return s;
}
};
541. Reverse String II
class Solution {
public:
string reverse(string s, int begin, int end) {
for (int i = 0; i <= (end-begin)/2; i++) {
swap(s[begin+i], s[end-i]);
}
return s;
}
string reverseStr(string s, int k) {
int begin = 0;
while (begin < s.size() - 1) {
int end = begin + k - 1;
if (end < s.size()) {
s = reverse(s, begin, end);
} else {
s = reverse(s, begin, s.size()-1);
}
begin += k + k;
}
return s;
}
};
557. Reverse Words in a String III
class Solution {
public:
string reverseString(string s, int b, int e) {
for (int i = 0; i <= (e-b)/2; i++) {
swap(s[b+i], s[e-i]);
}
return s;
}
string reverseWords(string s) {
int i = 0;
int n = s.size();
while (i < n) {
int j = i;
for (; j < n; j++) {
if (s[j] == ' ') {
break;
}
}
// s[j] == [ ]
s = reverseString(s, i, j-1);
i = j + 1;
}
return s;
}
};
Linked List
- runner
- recursive, iterative
203. Remove Linked List Elements
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
if (head == nullptr) {
return nullptr;
}
if (head->val == val) {
return removeElements(head->next, val);
} else {
ListNode* cur = head -> next;
head->next = removeElements(cur, val);
}
return head;
}
};
237. Delete Node in a Linked List
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
void deleteNode(ListNode* node) {
ListNode* p = node->next;
node->val = p->val;
node->next = p->next;
p = p -> next;
}
};
2095. Delete the Middle Node of a Linked List
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* deleteMiddle(ListNode* head) {
if (head->next == nullptr) {
return nullptr;
}
int counter = 0;
ListNode* p = head;
while (p != nullptr) {
counter++;
p = p->next;
}
int mid = counter / 2;
p = head;
while (mid--) {
p = p->next;
}
ListNode* q = p->next;
if (q != nullptr) {
p->val = q->val;
p->next = q->next;
} else { // only two nodes
head->next = nullptr;
}
return head;
}
};
/*
// Definition for a Node.
class Node {
public:
int val;
vector<Node*> neighbors;
Node() {
val = 0;
neighbors = vector<Node*>();
}
Node(int _val) {
val = _val;
neighbors = vector<Node*>();
}
Node(int _val, vector<Node*> _neighbors) {
val = _val;
neighbors = _neighbors;
}
};
*/
class Solution {
public:
Node* clone_rec(Node* node, unordered_map<Node*, Node*>& completed_nodes) {
if (node == nullptr) {
return nullptr;
}
Node* pNew = new Node(node->val);
completed_nodes[node] = pNew;
for (auto p: node->neighbors) {
auto iter = completed_nodes.find(p);
if (iter == completed_nodes.end()) {
// not found
pNew->neighbors.push_back(clone_rec(p, completed_nodes));
} else {
pNew->neighbors.push_back(iter->second);
}
}
return pNew;
}
Node* cloneGraph(Node* node) {
unordered_map<Node*, Node*> completed_nodes;
return clone_rec(node, completed_nodes);
}
};
19. Remove Nth Node From End of List
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
int counter = 0;
ListNode* p = head;
while (p != nullptr) {
p = p->next;
counter++;
}
int num = counter - n - 1;
p = head;
if (num == -1) {
return head->next;
}
while (num--) {
p = p->next;
}
p->next = p->next->next;
return head;
}
};
本文标签: 题记codinginterviewpreCracking
版权声明:本文标题:C++ 刷题记录 No.2 + Cracking the Coding Interview (Pre & Array and String & Linked Lists) 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/dongtai/1727896036a1136800.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论