leetcode 232. Implement Queue using Stacks
Implement the following operations of a queue using stacks.
MyQueue queue = new MyQueue();
queue.push(1); queue.push(2);
queue.peek(); // returns 1 queue.pop(); // returns 1 queue.empty(); // returns false
class MyQueue {
private int front;
private Stack<Integer> s1;
private Stack<Integer> s2;
/** Initialize your data structure here. */
public MyQueue() {
s1 = new Stack<>();
s2 = new Stack<>();
}
/** Push element x to the back of queue. */
public void push(int x) {
if (s1.isEmpty()) {
front = x;
}
while (!s1.isEmpty()) {
s2.push(s1.pop());
}
s2.push(x);
while (!s2.isEmpty()) {
s1.push(s2.pop());
}
}
/** Removes the element from in front of queue and returns that element. */
public int pop() {
int pop = s1.pop();
if (!s1.isEmpty()) {
front = s1.peek();
}
return pop;
}
/** Get the front element. */
public int peek() {
return front;
}
/** Returns whether the queue is empty. */
public boolean empty() {
return s1.isEmpty();
}
}
push(): Time complextiy : O(N). Space complexity : O(N). pop(), empty(), peek(): Time complextiy : O(1). Space complexity : O(1).
Runtime: 45 ms, faster than 19.26% Memory Usage: 34.3 MB, less than 45.05%
class MyQueue {
private int front;
private Stack<Integer> s1;
private Stack<Integer> s2;
/** Initialize your data structure here. */
public MyQueue() {
s1 = new Stack<>();
s2 = new Stack<>();
}
/** Push element x to the back of queue. */
public void push(int x) {
if (s1.isEmpty()) {
front = x;
}
s1.push(x);
}
/** Removes the element from in front of queue and returns that element. */
public int pop() {
if (s2.isEmpty()) {
while (!s1.isEmpty()) {
s2.push(s1.pop());
}
}
int pop = s2.pop();
return pop;
}
/** Get the front element. */
public int peek() {
if (!s2.isEmpty()) {
return s2.peek();
}
return front;
}
/** Returns whether the queue is empty. */
public boolean empty() {
return s1.isEmpty() && s2.isEmpty();
}
}
push(): Time complextiy : O(1). Space complexity : O(N). empty(), peek(): Time complextiy : O(1). Space complexity : O(1). pop(): Time complextiy : Amortized O(1), Worst-case O(n). Space complexity : O(1).
Runtime: 1 ms, faster than 41.71% Memory Usage: 36.4 MB, less than 57.64%
This week the company has taught the concept of the microservice, I read this article to see how the main login function works. How We Solved Authentication and Authorization in Our Microservice Architecture
I want to share some skills about docker, this is the senior developer told me.
I read Learning From the Feynman Techniquethis week and want to share it.
Richard Feynman (1918–1988), an author, graphic novel hero, intellectual, philosopher, physicist, and No Ordinary Genius is considered to be one of the most important physicists of all time.
The Feynman technique for teaching and communication is a mental model (a breakdown of his personal thought process) to convey information using concise thoughts and simple language.
Identify the subject Write down everything you know about the topic. Each time you run into new sources of information, add them to the note.
Teach it to a child If you can teach a concept to a child, you’re way ahead of the game.
Identify your knowledge gaps This is the point where the real learning happens. What are you missing? What don’t you know?
Organize + simplify + Tell a story Start to tell your story. Piece together your notes and begin to spin a tale using concise explanations. Bring the most vital pieces of your knowledge about the topic together.
leetcode 234. Palindrome Linked List
Given a singly linked list, determine if it is a palindrome.
Input: 1->2 Output: false
Input: 1->2->2->1 Output: true
class Solution {
public boolean isPalindrome(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
if (fast != null) {
slow = slow.next;
}
slow = reverse(slow);
fast = head;
while (slow != null) {
if (fast.val != slow.val) {
return false;
}
fast = fast.next;
slow = slow.next;
}
return true;
}
public ListNode reverse(ListNode head) {
ListNode prev = null;
while (head != null) {
ListNode next = head.next;
head.next = prev;
prev = head;
head = next;
}
return prev;
}
}
Time complextiy : O(N). Assume that n is the length of LinkedList. Space complexity : O(1).
Runtime: 1 ms, faster than 97.34% % Memory Usage: 40.9 MB, less than 91.63%
I am learning web development now, and I know agentzh is the creator of openresty, I browsed the offical website and planed to try the tutorial next week.
When we use the computer in company, it is a good custom to configure the mirror and proxy to download the dependencies quickly.
This week I read an article about the basic architecture concepts that is valuable for knew web developer beginner.
The article is Web Architecture 101
leetcode 53. Maximum Subarray
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
Input: [-2,1,-3,4,-1,2,1,-5,4], Output: 6 Explanation: [4,-1,2,1] has the largest sum = 6.
class Solution {
public int maxSubArray(int[] nums) {
int result = 0;
int max = Integer.MIN_VALUE;
for (int i = 0; i < nums.length; i++) {
result += nums[i];
if (result > max) {
max = result;
}
if (result < 0) {
result = 0;
}
}
return max;
}
}
Time complextiy : O(N). Assume that n is the length of nums. Space complexity : O(1).
Runtime: 1 ms, faster than 94.43% Memory Usage: 38.7 MB, less than 45.76%
I am learning web development now, and I know agentzh is the creator of openresty, I browsed the offical website and planed to try the tutorial next week.
This week is a little busy, I just recommend a note app: EverNote
This week I will share some skills during interview, I think they are practial skills beacuse everyone wants to achieve dream offer.
Often, you’ll hear an interviewer ask this: “OK, I think that looks good. Now, how would you improve this code?” This is a killer question. Being able to come up with a working solution is the bare minimum to be considered for the position. These questions are basic competency tests. What separates the good candidates from great is the ability to think beyond what’s required.
Think about edge cases, scaling issues, problem areas. Always think one step ahead. If you’re using a recursive approach, what would happen if you have a large data set? If you’re using a hashing algorithm, how do you handle collisions? How likely is that to happen, and what’s the worst case scenario?
From an interviewer perspective, I’m not looking to check if you know what the right answer is. Yes, it is important that you can write a working solution, but it’s not the only thing.
More than that, I’m looking for how smart this person is, how the solution is derived, and what other creative solutions this person might be thinking about.
Many candidates jump head-first into a programming problem without putting further thought into simplifying the code. I used to be in this bunch and, admittedly, I still do it sometimes.
If you’re starting out on your job search, then the very first thing you should do is prepare a great resume. That’s the number one thing that is often overlooked by job seekers and, arguably, is the lowest hanging fruit.
Communicate as often as you need. I tried to communicate early and often. Whenever there was an issue, I would raise it with the interviewer and let them know. It helped me determine if I was heading in the right direction, and course-correct if I was not.
leetcode 189. Rotate Array
Given an array, rotate the array to the right by k steps, where k is non-negative.
Input: [1,2,3,4,5,6,7] and k = 3 Output: [5,6,7,1,2,3,4] Explanation: rotate 1 steps to the right: [7,1,2,3,4,5,6] rotate 2 steps to the right: [6,7,1,2,3,4,5] rotate 3 steps to the right: [5,6,7,1,2,3,4]
Input: [-1,-100,3,99] and k = 2 Output: [3,99,-1,-100] Explanation: rotate 1 steps to the right: [99,-1,-100,3] rotate 2 steps to the right: [3,99,-1,-100]
Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem. Could you do it in-place with O(1) extra space?
class Solution {
public void rotate(int[] nums, int k) {
int previous;
int temp;
for (int i = 0; i < k; i++) {
previous = nums[nums.length - 1];
for (int j = 0; j < nums.length; j++) {
temp = nums[j];
nums[j] = previous;
previous = temp;
}
}
}
}
Time complextiy : O(N*k). Assume that n is the length of nums, and k is the number of roatate tiems. Space complexity : O(1).
Runtime: 83 ms, faster than 19.76% Memory Usage: 37.2 MB, less than 57.19%
We use an extra array in which we place every element of the array at its correct position.
class Solution {
public void rotate(int[] nums, int k) {
int[] a = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
a[(i + k) % nums.length] = nums[i];
}
for (int i = 0; i < nums.length; i++) {
nums[i] = a[i];
}
}
}
Time complexity : O(n). One pass is used to put the numbers in the new array. And another pass to copy the new array to the original one. Space complexity : O(n). Another array of the same size is used.
Runtime: 1 ms, faster than 41.71% Memory Usage: 36.4 MB, less than 57.64%
class Solution {
public void rotate(int[] nums, int k) {
k = k % nums.length;
int count = 0;
for (int start = 0; count < nums.length; start++) {
int current = start;
int prev = nums[start];
do {
int next = (current + k) % nums.length;
int temp = nums[next];
nums[next] = prev;
prev = temp;
current = next;
count++;
} while (start != current);
}
}
}
Time complexity : O(n)O(n). Only one pass is used. Space complexity : O(1)O(1). Constant extra space is used.
Runtime: 0 ms, faster than 100.00% Memory Usage: 36.3 MB, less than 58.01%
I am learning web development now, and I know agentzh is the creator of openresty, I browsed the offical website and planed to try the tutorial next week.
I am learning python rege now, the following are some trips I have met with.
greedyHaRegex = re.compile(r’(Ha){3,5}’) mo1 = greedyHaRegex.search(‘HaHaHaHaHa’) mo1.group() ‘HaHaHaHaHa’
nongreedyHaRegex = re.compile(r’(Ha){3,5}?’) mo2 = nongreedyHaRegex.search(‘HaHaHaHaHa’) mo2.group() ‘HaHaHa’ ``` Note that the question mark can have two meanings in regular expressions: declaring a nongreedy match or flagging an optional group. These meanings are entirely unrelated.
phoneNumRegex = re.compile(r’\d\d\d-\d\d\d-\d\d\d\d’) # has no groups phoneNumRegex.findall(‘Cell: 415-555-9999 Work: 212-555-0000’) [‘415-555-9999’, ‘212-555-0000’]
phoneNumRegex = re.compile(r’(\d\d\d)-(\d\d\d)-(\d\d\d\d)’) # has groups phoneNumRegex.findall(‘Cell: 415-555-9999 Work: 212-555-0000’) [(‘415’, ‘555’, ‘9999’), (‘212’, ‘555’, ‘0000’)] ```
To summarize what the findall() method returns, remember the following:
When called on a regex with no groups, such as \d\d\d-\d\d\d-\d\d\d\d, the method findall() returns a list of string matches, such as [‘415-555-9999’, ‘212-555-0000’].
When called on a regex that has groups, such as (\d\d\d)-(\d\d\d)-(\d\ d\d\d), the method findall() returns a list of tuples of strings (one string for each group), such as [(‘415’, ‘555’, ‘9999’), (‘212’, ‘555’, ‘0000’)].
leetcode 119. Pascal’s Triangle II
Given a non-negative index k where k ≤ 33, return the kth index row of the Pascal’s triangle. Note that the row index starts from 0.
In Pascal’s triangle, each number is the sum of the two numbers directly above it.
Input: 3 Output: [1,3,3,1]
class Solution {
public List<Integer> getRow(int rowIndex) {
List<Integer> list = new ArrayList<>(rowIndex + 1);
if (rowIndex < 0) return list;
for (int i = 0; i <= rowIndex; i++) {
list.add(1);
}
for (int i = 2; i <= rowIndex; i++) {
for (int j = rowIndex - i + 1; j < rowIndex; j++) {
list.set(j, list.get(j) + list.get(j+1));
}
}
return list;
}
}
Time complextiy : O(N^2). Assume that n is the length of nums. Space complexity : O(n).
Runtime: 1 ms, faster than 84.92% Memory Usage: 32.6 MB
This week, I will share a blog of How I landed offers from Microsoft, Amazon, and Twitter without an Ivy League degree
Yes, this blog is so inspiring, the author did not graduate from an Ivy league school. He went to a community college in Idaho for two years, and then finished the CS degree in a small Catholic university. but we can see that the author is a skilled software engineer and so confident, these two points are so importamnt, and it is the foundation of all success.
There are some other components that help him make his own success.
Remember, Remember: the strong survives, the tough thrives.
I am learning python now, the following are some trips I have met with.
Remember that escape characters in Python use the backslash (). The string value ‘\n’ represents a single newline character, not a backslash followed by a lowercase n. You need to enter the escape character \ to print a single backslash. So ‘\n’ is the string that represents a backslash followed by a lowercase n. However, by putting an r before the first quote of the string value, you can mark the string as a raw string, which does not escape characters.
Since regular expressions frequently use backslashes in them, it is convenient to pass raw strings to the re.compile() function instead of typing extra backslashes. Typing r’\d\d\d-\d\d\d-\d\d\d\d’ is much easier than typing ‘\d\d\d-\d\d\d-\d\d\d\d’.
The | character is called a pipe. When both Batman and Tina Fey occur in the searched string, the first occurrence of matching text will be returned as the Match object.
>>> heroRegex = re.compile (r'Batman|Tina Fey')
>>> mo1 = heroRegex.search('Batman and Tina Fey.')
>>> mo1.group()
'Batman'
>>> mo2 = heroRegex.search('Tina Fey and Batman.')
>>> mo2.group()
'Tina Fey'
Up to now, I release that I have to improve my English, including writing, speaking, listening, reading. I have searched so many resources in the Internet, finally, I found an awesome answer about how to learn English.
There are three parts of the answer. First, why it is difficulty to learning English Grammar. English Grammar is the rules about how words change their forms and combine with other words to make a sentence. For most Chinese student, they spend several years to learn English grammar, but this is just waste time and worthless. Because we just accumulate and regurgitate fixed knowledge.
Secondly, how to learn English grammar?
Thirdly, learning resource.
leetcode35. Search Insert Position
Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You may assume no duplicates in the array.
Input: [1,3,5,6], 5 Output: 2
Input: [1,3,5,6], 2 Output: 1
Input: [1,3,5,6], 7 Output: 4
Input: [1,3,5,6], 0 Output: 0
The array is sorted, so it is satisfied with the condition of binary search.
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int low = 0;
int high = nums[1] -1;
while (low <= high){
int mid = low + (high-low) >> 1;
if (nums[mid] == target){
return mid;
}
if ( target > nums[mid] ) {
low = mid+1;
}else{
high = mid-1;
}
}
return low;
}
}
Time complextiy : O(logN). Assume that n is the length of nums. Space complexity : O(1).
Runtime: 0 ms Memory Usage: 39.6 MB
This week I read a blog – How I went from newbie to Software Engineer in 9 months while working full time, I am inspired by the author and I want to share some useful suggestion from it
Most of below advice are that I do not possess. I have to improve it.