Table Of Contents
- Introduction
- Install the LeetCode Extension in VS Code
- Configure the LeetCode Extension
- Add Jest-based TDD Support
- Select a Problem
- Anatomy of the Generated File
- The Initial Attempt
- The Second Attempt
- The Final Attempt
- Conclusion
Introduction
Recently I attended an in-person interview. In the coding challenge part I was asked to solve the Anagram problem. Although the problem doesn't look tricky, I was under the self-imposed pressure of needing to solve it quickly. I intuitively chose an algorithm which checks whether every character in the first word also appears in the second one and vice versa. I did realize it has bugs. I tried to save it but failed because at the moment was I in a state of panic. When I got back home, suddenly I thought shouldn't sort-and-match be a solution? What a shame! I could have performed better.
The root cause of my failure is that I didn't catch the essentials of the problem. I need to practice. It's well-known that the leetcode.com is a platform where developers can learn and practice variety of algorithms. What's more, the leetcode.com provides an extension for VS Code so that we can solve LeetCode problems without leaving VS Code. From now on I am going to talk about the experience of using TypeScript and TDD to solve a LeetCode problem in VS Code.
Install the LeetCode Extension in VS Code
Open the Extensions panel in VS Code, find the LeetCode extension and install it. After installation, open the LeetCode panel, login to leetcode.com with our own account. We will see a navigation tree in the panel that helps us select a problem. Right clicking on a problem brings a context menu through which we can preview the problem and create a file to work on the problem.
At present, there is a technical problem that prevents users from logging into the leetcode.com. However, the workaround is given in the extension's home page.
Configure the LeetCode Extension
The LeetCode extension guides user to configure the default language and the workspace folder. These two settings can also be changed in LeetCode extension's settings page (On Mac: Code > Preferences > settings, input LeetCode in the search box to see the settings). Make sure typescript is selected as the default language.
Add Jest-based TDD Support
- Run
yarn initin the LeetCode workspace folder to initialize the project. - Run
yarn add -D @types/jest jest typescript ts-jestto install the dependencies. The ts-jest is A TypeScript preprocessor with source map support for Jest that lets you use Jest to test projects written in TypeScript. -
Add the jest.config.js file in the LeetCode workspace folder with the following content:
module.exports = { preset: 'ts-jest', testEnvironment: 'node', }; Add
"test:watch": "jest --watchAll"to the scripts filed in the package.json file.
Select a Problem
As you know, I just started to work on LeetCode. So, following the predefined order makes sense. I selected the [2] Add Two Numbers problem. Its difficulty level is medium. Operating on linked lists is its key point.
Anatomy of the Generated File
Let's have a look at the content of the generated file for the selected problem:
/*
* @lc app=leetcode id=2 lang=typescript
*
* [2] Add Two Numbers
*/
// @lc code=start
/**
* Definition for singly-linked list.
* class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
* }
*/
function addTwoNumbers(l1: ListNode | null, l2: ListNode | null): ListNode | null {
};
// @lc code=end
After a few trials, the following features about the file are found:
- The file is not a node or ES6 module because there are no statements to import modules and export values in it.
- The name of the file can be changed, however, the id in the comment is immutable.
- The leetcode.com runtime only cares about the content in the section demarcated by
// @lc code=startand// @lc code=end. The main(addTwoNumbers) and helper functions must be put in this section. The import and export statements, types and classes coming from leetcode.com runtime should be put outside of the section. If these rules are not followed, the leetcode.com runtime will report compilation errors when the file is submitted. - The ListNode class used in the main function's parameters comes from the leetcode.com runtime. Our local environment doesn't have it. However, its definition is shown in the comment of the main function.
In order to use this file in our local environment, we need to do the following things:
- Export the addTwoNumbers function, so the file turns to a ES6 module.
- Extract the ListNode class from the comment and export it.
The adjusted file looks like:
export class ListNode {
val: number;
next: ListNode | null;
constructor(val?: number, next?: ListNode | null) {
this.val = val === undefined ? 0 : val;
this.next = next === undefined ? null : next;
}
}
/*
* @lc app=leetcode id=2 lang=typescript
*
* [2] Add Two Numbers
*/
// @lc code=start
/**
* Definition for singly-linked list.
* class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
* }
*/
function addTwoNumbers(
l1: ListNode | null,
l2: ListNode | null
): ListNode | null {
}
// @lc code=end
export default addTwoNumbers;
Now we can use TDD to drive our implementation.
The Initial Attempt
Algorithm
Convert the two linked lists to two numbers, add the numbers to get a sum, convert the sum back to a linked list.
Test cases
- toNumber: a function that converts a linked list to a number.
- fromNumber: a function that converts a number to a linked list.
import addTwoNumbers, {
ListNode,
toNumber,
fromNumber,
} from "./2.add-two-numbers";
describe("convert a number to a linked list", () => {
test("0 to 0", () => {
const l: ListNode = fromNumber(0);
expect(l.val).toBe(0);
expect(l.next).toBeNull();
});
test("123 to 3 > 2 > 1", () => {
const l: ListNode = fromNumber(123);
expect(l.val).toBe(3);
expect(l.next.val).toBe(2);
expect(l.next.next.val).toBe(1);
expect(l.next.next.next).toBeNull();
});
});
describe("Convert a linked list to a number", () => {
test("0 to 0", () => {
const l: ListNode = new ListNode(0, null);
expect(toNumber(l)).toBe(0);
});
test("3 > 2 > 1 to 123", () => {
const l: ListNode = new ListNode(
3,
new ListNode(2, new ListNode(1, null))
);
expect(toNumber(l)).toBe(123);
});
});
describe("Add two numbers", () => {
test("Example 1", () => {
const l1 = new ListNode(2, new ListNode(4, new ListNode(3, null)));
const l2 = new ListNode(5, new ListNode(6, new ListNode(4, null)));
const s = addTwoNumbers(l1, l2);
expect(toNumber(s)).toBe(807);
});
test("Example 2", () => {
const l1 = new ListNode(0, null);
const l2 = new ListNode(0, null);
const s = addTwoNumbers(l1, l2);
expect(toNumber(s)).toBe(0);
});
test("Example 3", () => {
const l1 = new ListNode(
9,
new ListNode(
9,
new ListNode(
9,
new ListNode(
9,
new ListNode(9, new ListNode(9, new ListNode(9, null)))
)
)
)
);
const l2 = new ListNode(
9,
new ListNode(9, new ListNode(9, new ListNode(9, null)))
);
const s = addTwoNumbers(l1, l2);
expect(toNumber(s)).toBe(10009998);
});
});
Implementation
export class ListNode {
val: number;
next: ListNode | null;
constructor(val?: number, next?: ListNode | null) {
this.val = val === undefined ? 0 : val;
this.next = next === undefined ? null : next;
}
}
/*
* @lc app=leetcode id=2 lang=typescript
*
* [2] Add Two Numbers
*/
// @lc code=start
function toNumber(l: ListNode): number {
let num = 0;
let currentNode = l;
let exponent = 0;
while (currentNode) {
num += currentNode.val * Math.pow(10, exponent++);
currentNode = currentNode.next;
}
return num;
}
function fromNumber(num: number): ListNode {
const numStr = String(num);
let headNode: ListNode = null;
for (let i = 0; i < numStr.length; i++) {
const digit = parseInt(numStr.charAt(i), 10);
const node = new ListNode(digit);
node.next = headNode;
headNode = node;
}
return headNode;
}
/**
* Definition for singly-linked list.
* class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
* }
*/
function addTwoNumbers(
l1: ListNode | null,
l2: ListNode | null
): ListNode | null {
const num1 = toNumber(l1);
const num2 = toNumber(l2);
const s = num1 + num2;
return fromNumber(s);
}
// @lc code=end
export default addTwoNumbers;
export { toNumber, fromNumber };
Result
Run yarn run test:watch. All local test cases passed. So far so good. How will leetcode.com evaluate this solution? Let's submit it. Gotchas! The 1565 of 1568 test cases passed. 3 test cases failed!
Obviously the number represented by the first linked list is too big to be handled by the algorithm. A possible solution could be using BigInt instead of Number in the toNumber and fromNumber functions. However, BigInt is a feature of ES2020, using it in leetcode.com runtime could bring other problems. A more flexible algorithm is required.
The Second Attempt
Algorithm
Convert the two linked lists to two arrays, calculate the the array for the sum by iteratively adding the digits from the two arrays in the same position, convert the array for the sum to a linked list.
Test cases
- fromArray: a function that converts an array of number to a linked list.
- toArray: a function that converts a linked list to an array of number.
- Because of fromArray and toArray, writing test cases becomes easier.
- The failed test case in the initial attempt has been added.
import addTwoNumbers, {
ListNode,
fromArray,
toArray,
} from "./2.add-two-numbers";
describe("convert an array to a linked list", () => {
test("[0] to 0", () => {
const l: ListNode = fromArray([0]);
expect(l.val).toBe(0);
expect(l.next).toBeNull();
});
test("[2, 4, 3] to 2 > 4 > 3", () => {
const l: ListNode = fromArray([2, 4, 3]);
expect(l.val).toBe(2);
expect(l.next.val).toBe(4);
expect(l.next.next.val).toBe(3);
expect(l.next.next.next).toBeNull();
});
});
describe("convert a linked list to an array", () => {
test("0 to [0]", () => {
const array = [0];
const l: ListNode = fromArray(array);
expect(toArray(l)).toEqual(array);
});
test("2 > 4 > 3 to [2, 4, 3]", () => {
const array = [2, 4, 3];
const l: ListNode = fromArray(array);
expect(toArray(l)).toEqual(array);
});
});
describe("Add two numbers", () => {
test("Example 1", () => {
const l1 = fromArray([2, 4, 3]);
const l2 = fromArray([5, 6, 4]);
const s = addTwoNumbers(l1, l2);
expect(toArray(s)).toEqual([7, 0, 8]);
});
test("Example 2", () => {
const l1 = new ListNode(0, null);
const l2 = new ListNode(0, null);
const s = addTwoNumbers(l1, l2);
expect(toArray(s)).toEqual([0]);
});
test("Example 3", () => {
const l1 = fromArray([9, 9, 9, 9, 9, 9, 9]);
const l2 = fromArray([9, 9, 9, 9]);
const s = addTwoNumbers(l1, l2);
expect(toArray(s)).toEqual([8, 9, 9, 9, 0, 0, 0, 1]);
});
test("case 1566", () => {
const l1 = fromArray([
1,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
1,
]);
const l2 = fromArray([5, 6, 4]);
const s = addTwoNumbers(l1, l2);
expect(toArray(s)).toEqual([
6,
6,
4,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
1,
]);
});
});
Implementation
export class ListNode {
val: number;
next: ListNode | null;
constructor(val?: number, next?: ListNode | null) {
this.val = val === undefined ? 0 : val;
this.next = next === undefined ? null : next;
}
}
/*
* @lc app=leetcode id=2 lang=typescript
*
* [2] Add Two Numbers
*/
// @lc code=start
function fromArray(array: number[]): ListNode {
let headNode: ListNode = null;
for (let i = array.length - 1; i > -1; i--) {
const node = new ListNode(array[i], headNode);
headNode = node;
}
return headNode;
}
function toArray(l: ListNode): number[] {
const array = [];
let currentNode = l;
while (currentNode) {
array.push(currentNode.val);
currentNode = currentNode.next;
}
return array;
}
/**
* Definition for singly-linked list.
* class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
* }
*/
function addTwoNumbers(
l1: ListNode | null,
l2: ListNode | null
): ListNode | null {
const array1 = toArray(l1);
const array2 = toArray(l2);
const augend = array1.length >= array2.length ? array1 : array2;
const addend = array1.length >= array2.length ? array2 : array1;
const sum = [];
let carry = 0;
for (let i = 0; i < augend.length; i++) {
const augendDigit = augend[i];
const addendDigit = i in addend ? addend[i] : 0;
const digitSum = augendDigit + addendDigit + carry;
const sumDigit = digitSum % 10;
carry = Math.floor(digitSum / 10);
sum.push(sumDigit);
}
if (carry !== 0) {
sum.push(carry);
}
return fromArray(sum);
}
// @lc code=end
export default addTwoNumbers;
export { fromArray, toArray };
Result
Run yarn run test:watch. All local test cases passed. So far so good. How will leetcode.com evaluate this solution? Let's submit it. All remote test cases passed. Hooray!
Usually I will stop here because the algorithm seems to work well. However, the performance indicators show that the algorithm doesn't perform well in terms of the memory usage. Yes, I think it is caused by converting the linked lists into arrays and vice versa. How about accessing the digit in the list node directly?
The Final Attempt
Algorithm
Basically, the algorithm is the same as the one used in the second attempt, the only difference is that the list nodes are accessed directly.
Test cases
We didn't add any new functionalities in this attempt. So, the test cases keep the same as the ones used in the second attempt.
Implementation
Although the toArray and fromArray functions are not used in the algorithm, the are convenient for writing test cases, so they are retained but moved outside of the LeetCode code section.
export class ListNode {
val: number;
next: ListNode | null;
constructor(val?: number, next?: ListNode | null) {
this.val = val === undefined ? 0 : val;
this.next = next === undefined ? null : next;
}
}
/*
* @lc app=leetcode id=2 lang=typescript
*
* [2] Add Two Numbers
*/
// @lc code=start
/**
* Definition for singly-linked list.
* class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
* }
*/
type Pointer = {
l1CurrentNode: ListNode;
l2CurrentNode: ListNode;
carry: number;
};
function addTwoNumbers(
l1: ListNode | null,
l2: ListNode | null
): ListNode | null {
const p: Pointer = {
l1CurrentNode: l1,
l2CurrentNode: l2,
carry: 0,
};
const sumList = new ListNode();
let slCurrentNode: ListNode = null;
while (p.l1CurrentNode || p.l2CurrentNode) {
if (!slCurrentNode) {
slCurrentNode = sumList;
} else {
slCurrentNode.next = new ListNode();
slCurrentNode = slCurrentNode.next;
}
const augendDigit = p.l1CurrentNode?.val ?? 0;
const addendDigit = p.l2CurrentNode?.val ?? 0;
const digitSum = augendDigit + addendDigit + p.carry;
const sumDigit = digitSum % 10;
slCurrentNode.val = sumDigit;
p.l1CurrentNode = p.l1CurrentNode?.next;
p.l2CurrentNode = p.l2CurrentNode?.next;
p.carry = Math.floor(digitSum / 10);
}
if (p.carry !== 0) {
slCurrentNode.next = new ListNode(p.carry);
slCurrentNode = slCurrentNode.next;
}
return sumList;
}
// @lc code=end
export default addTwoNumbers;
export function fromArray(array: number[]): ListNode {
let headNode: ListNode = null;
for (let i = array.length - 1; i > -1; i--) {
const node = new ListNode(array[i], headNode);
headNode = node;
}
return headNode;
}
export function toArray(l: ListNode): number[] {
const array = [];
let currentNode = l;
while (currentNode) {
array.push(currentNode.val);
currentNode = currentNode.next;
}
return array;
}
Result
The performance in terms of the memory usage improved a lot!
Conclusion
There are 1700+ problems on leetcode.com. The number is intimidating. The process of seeking the most suitable solution to a specific problem is both time-consuming and brain-consuming. However, the good result from the submission is encouraging. LeetCode extension for VS Code is a productivity tool, however, with the help of TDD, the experience can be better.
As to the performance indictors, don't take "Your runtime beats *% of typescript submissions" seriously. Sometimes the percentage is high, sometimes it is low. I think it may be affected by the load of the leetcode.com runtime. Try to submit code several times, if it keeps being low then the algorithm may need to be improved. The memory usage indicator is relatively stable and can be used to assess the level of memory usage of the algorithm.
Top comments (0)