this repo will contain a combination of uni assignments, interview questions, online problem solving contests, etc..
sumOfStr.cpp
testsumofstr.cpp
Given two non-negative integers,
num1
andnum2
represented >as string, return the sum ofnum1
andnum2
as a string.You must solve the problem without using any built-in library for >handling large integers (such as BigInteger). You must also not >convert the inputs to integers directly.
- solved.
- tested with Googletest.
- Runtime: 0 ms.
- Memory: 6.8 MB.
- Language: C++.
https://leetcode.com/problems/add-strings/
Given an array of intervals where
intervals[i]
=[starti, endi]
, Select the maximum number of activities that can be performed by a single person, assuming that a person can only work on a single activity at a given day.
- solved.
- tested with Googletest.
- Runtime: less than 1 s.
- Language: C++.
Given two strings
text1
andtext2
, return the length of their >longest common subsequence. If there is no common >subsequence, return0
.A subsequence of a string is a new string generated from the >original string with some characters (can be none) deleted >without changing the relative order of the remaining characters.
For example, "ace" is a subsequence of "abcde".
A common subsequence of two strings is a subsequence that is >common to both strings.
- solved.
- tested with Googletest.
- Runtime: 8 ms.
- Memory: 10.5 MB.
- Language: C++.
Math , String, Simulation.
On an infinite plane, a robot initially stands at
(0, 0)
and >facesnorth
. The robot can receive one of three instructions:
- "G": go straight 1 unit;
- "L": turn 90 degrees to the left;
- "R": turn 90 degrees to the right.
The robot performs the instructions given in order, and repeats >them forever.
Return
true
if and only if there exists a circle in the plane >such that the robot never leaves the circle.
- solved.
- tested with Googletest.
- Runtime: 0 ms, faster than 100.00% of C++ online submissions for Robot Bounded In Circle.
- Memory Usage: 6.2 MB, less than 48.40% of C++ online submissions for Robot Bounded In Circle.
- Language: C++.
Greedy , Heap(Priority Queue).
There are
n
different online courses numbered from1
ton
. You are given an arraycourses
wherecourses[i] = [durationi, lastDayi]
indicate that the ith course should be taken continuously fordurationi
days and must be finished before or onlastDayi
.You will start on the 1st day and you cannot take two or more courses simultaneously.
Return the maximum number of courses that you can take.
- solved.
- tested with Googletest.
- Runtime: 1036 ms.
- Memory Usage: 84.1 MB.
- Language: C++.
Math , String, Bit Manipulation, Simulation.
Given two binary strings
a
andb
, return their sum as a binary string.
- solved.
- tested with Googletest.
- Runtime: 3 ms. faster than 68.05% of C++ online submissions for Add Binary.
- Memory Usage: 8.5 MB.
- Language: C++.
Array, Sorting.
Given an array
nums
withn
objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue.We will use the integers
0
,1
, and2
to represent the color red, white, and blue, respectively.You must solve this problem without using the library's sort function.
- solved.
- tested with Googletest.
- Runtime: 0 ms, faster than 100.00% of C++ online submissions for Sort Colors.
- Memory Usage: 8.4 MB.
- Language: C++.
Binary Tree, Depth-first-search.
You are given the
root
of a binary tree where each node has a value0
>or1
. Each root-to-leaf path represents a binary number starting with >the most significant bit.
- For example, if the path is
0 -> 1 -> 1 -> 0 -> 1
, then this could >represent01101
in binary, which is13
.For all leaves in the tree, consider the numbers represented by the path >from the root to that leaf. Return the sum of these numbers.
The test cases are generated so that the answer fits in a 32-bits integer.
- solved.
- tested with Googletest.
- Runtime: 8 ms, faster than 53.68% of C++ online submissions for Sum of Root To Leaf Binary Numbers.
- Memory Usage: 20.4 MB.
- Language: C++.
Linear time sorting, Counting sort.
Sort the given array of non-negative integers
nums
in linear-time complexityO(n)
and linear spaceO(n)
.
- Solved.
- tested on randomly generated arrays with Googletest.
- Runtime for 1 array of size
$10^{7}$ = 25.04 s. - Runtime for 1 array of size
$10^{5}$ = 0.26 s. - Language: C++.
Array, Binary Search, Divide-And-Conquer.
Given two sorted arrays
nums1
andnums2
of sizem
andn
respectively, return the median of the two sorted arrays.The overall run time complexity should be
O(log (m+n))
.
- In progress.
- testing with Googletest.
- Language: C++.
Given an array of integers
nums
and an integertarget
, return indices of the two numbers such that they add up totarget
. You may assume that each input would have exactly one solution, and you may not use the same element twice. You can return the answer in any order.
- Time Complexity:
$O(n^{2})$ - Spacial Complexity:
$O(1)$ - tested with Googletest.
- Runtime: 605 ms, faster than 17.41% of C++ online submissions for Two Sum.
- Memory Usage: 10 MB, less than 94.82% of C++ online submissions for Two Sum.
- Language: C++.
- Time Complexity:
$O(n)$ - Spacial Complexity:
$O(n)$ - tested with Googletest.
- Runtime: 19 ms, faster than 58.92% of C++ online submissions for Two Sum.
- Memory Usage: 11 MB, less than 23.81% of C++ online submissions for Two Sum.
- Language: C++.
Given four integer arrays
nums1
,nums2
,nums3
, andnums4
all of lengthn
, return the number of tuples(i, j, k, l)
such that:
0 <= i, j, k, l < n
nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0
- Time Complexity:
$O(n^{4})$ - Spacial Complexity:
$O(1)$ - tested with Googletest.
- Language: C++.
- Time Complexity:
$O(n^{2})$ - Spacial Complexity:
$O(n^{2})$ - tested with Googletest.
- Runtime: 575 ms ms.
- Memory Usage: 25 MB.
- Language: C++.
You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.
Suppose you have
n
versions[1, 2, ..., n]
and you want to find out the first bad one, which causes all the following ones to be bad.You are given an API
bool
isBadVersion(version)
which returns whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.
- Time Complexity:
$O(\lg(n))$ - Spacial Complexity:
$O(\lg(n))$ - tested with Googletest.
- Runtime: 0 ms.
- Memory Usage: 6.1 MB.
- Language: C++.