DEV Community: Shirley

Reverse a Linked List - Leetcode

Shirley — Mon, 04 Jan 2021 23:10:05 +0000

I'm sure many of you have seen this problem: reverse a linked list. When you reverse a linked list, you are essentially reversing the direction the linked list goes from.
For example, if you have a linked list 1 -> 2 -> 3 -> 4, you want to make the linked list 1 <- 2 <- 3 <- 4.
To do this, you need a variable prev that you can set the previous value to.
Here's my code for this problem:

def reverseList(head):
        prev = None
        while head:
            temp = head
            head = head.next
            temp.next = prev
            prev = temp
        return prev

You first set the variable prev to None. Then you create a while loop that loops through head, which contains the first value of the linked list. You set a temp variable equal to the current node. Then you set the current node to the next node to progress through the linked list, while temp remains the current node. You set the next pointer of temp(current) equal to prev, which is at first None, but then it equals the current node afterwards. Then you repeat.
For example, using 1 -> 2 -> 3 -> 4
temp = 1
head = 2
prev = 1
temp = 2
head = 3
prev = 2
temp = 3
head = 4
prev = 3
And that's how you reverse the linked list.

Flattening a Multidimensional array and Summing up a multidimensional array

Shirley — Sun, 03 Jan 2021 17:01:04 +0000

I've encountered problems with multidimensional arrays and you need to use recursion to solve the problem. Here are two examples of such problems.

The first problem is summing the elements of the array, given a multidimensional array. For example, given

let arr = [1,[1,2,[3,4]]]

The sum would be 11.
Here is my code using recursion to solve the problem:

function sumArrays(arr) {
  let sum = 0;
  for (let i = 0; i < arr.length; i++) {
    if(Array.isArray(arr[i])){
      sum += sumArrays(arr[i]);
    } else {
      sum += arr[i];
    }
  }
  return sum;
}

First, instantiate a variable sum. Then loop through the array. Check whether arr[i] is an array using Array.isArray. If it is an array, call the function sumArrays on the element again and add the sum to the sum variable. If the element is not an array, simply add the element to the sum.
For example, the first element 1 is not an array so add 1 to sum, so sum is now 1. The second element [1,2,[3,4]] is an array, so call sumArrays on it. It will loop through the element and check each element in the array. 1, 2 are elements so add that to sum. [3,4] is array so loop through that again and add the elements to the sum.

The second example is using recursion to flatten a multidimensional array. You want a one dimensional array of all the elements in the multidimensional array. For example given

[1, [1, 2, [3, 4]]]

you want

[1,1,2,3,4]

Here's my code:

function flattenArray(arr) {
  return arr.reduce((acc, ele) => {
    return acc.concat(Array.isArray(ele) ? flattenArray(ele) : ele)
  }, [])
}

Here I'm using the reduce function to concat the elements of the array to the accumulator variable which starts as an empty array. In my reduce function, I concat the element to the accumlator array. I check whether the element is an array, if so, I call the function flattenArray on it recursively. If not, I just concat the element to the array.

I hope this clears up any confusion regarding recursion in multidimensional arrays. Hope this helped.

Remove Duplicates from Sorted Array - Leetcode

Shirley — Thu, 10 Sep 2020 17:53:24 +0000

Given a sorted array of numbers with duplicates, remove all duplicates from array, leaving one of each number. Return the length of the array.
For example:

input = [1,1,2,2,2,3,3]
output = [1,2,3]

This problem is relatively straightforward. If you want to accomplish it using O(n) time and 0(1) space, you want to use the two pointer method. I will instantiate two pointers, i and j, set to 0 and 1, respectively. I will use a while loop, and I will check whether the num with i index is equal to num with j index. If not, I increment both of them by 1. If they are equal, I pop out the number with j index.

def removeDuplicates(nums):
    i, j = 0, 1

    while j < len(nums):
        if nums[i] != nums[j]:
            i += 1
            j += 1
        elif nums[i] == nums[j]:
            nums.pop(j)
    return len(nums)

In javascript, it's similar:

function removeDuplicates(nums):
    let i = 0;
    let j = 1;
    while (j< nums.length) {
        if (nums[i] != nums[j]) {
            i+= 1;
            j+= 1;
     } else if (nums[i] == nums[j]) {
         nums.splice(j, 1);
}
    return nums.length;
}

In javascript function, I use splice instead of pop since javascript doesn't pop by index. Splice takes the element with the specified index, and if there's a 1 as parameter, it removes that element.

To Do List with React Hooks

Shirley — Thu, 10 Sep 2020 01:28:10 +0000

React Hooks was introduced in Feb 2019 when React 16.8 was shipped. It allowed developers to use state and lifecycle methods inside functional components instead of purely class based components. Today, I am going to make a to-do list using useState() and show you guys how to use the most basic React hook, useState().
To make a todo app, we need to make a state hook, todos. We will declare this hook inside our App functional component.

function App () {
   const [todos, setTodos] = React.useState("")
}

todos is the state variable, and setTodos is similar to this.setState where you can change the value of todos by setting setTodos equal to a value. You initialize the state by setting React.useState(""). If you want to set todos to a value, do this:

function App () {
   const [todos, setTodos] = React.useState([{text: "Do leetcode", isCompleted: false}])
}

This sets todos equal to an array containing an object with keys of text and isCompleted and values equal to the content of the key.
Next, we want to make a function that adds a new todo to the todos variable.

const addTodos = (text) => {
     const newTodos = [...todos, {text:text, isCompleted:false}]
     setTodos(newTodos);

   }

When you call setTodos, you set the todos variable equal to the newTodos variable.
Next, we want to have a function where we can cross an item off the list if it is completed. We use the isCompleted value in this case. We set the isCompleted property to equal true.

 const completeTodo = index => {
     const newTodos = [...todos];
     newTodos[index].isCompleted = true
     setTodos(newTodos)
   }

The completeTodo function takes in an index parameter, which is the index of the todo that we want to cross off the list.

Finally, we want to remove a Todo from the list. We create a function for that and use splice to remove the selected todo.

 const removeTodo = index => {
     const newTodos = [...todos];
     newTodos.splice(index, 1)
     setTodos(newTodos)
   }

Next, we want to create a form to input a todo and have it displayed on our list.

const TodoForm = ({addTodos}) => {
  const [value, setValue] = React.useState("")
  const handleSubmit=(e) => {
    e.preventDefault();
    if(!value) return;
    addTodos(value)
    setValue("")
  }
  return (
    <form onSubmit={handleSubmit}>
      <input className="input" type="text" value={value} placeholder="Add Todo" onChange={e => setValue(e.target.value)}/>
      <button type="submit">Add </button>
      </form>
  )
}

The Todo form takes in a props in the form of addTodos. It has a state variable of value, which is what we use for the input. We have a handleSubmit() function that called e.preventDefault() to prevent the default form submission, and inside it, it calls addTodos(value) and setValue to empty after adding the todo. In our return, we set onChange of input equal to an inline function that takes in event and calls setValue(e.target.value).

Finally, we want to display our Todos:

const Todo = ({ todo, index, completeTodo, removeTodo } ) => {
  return (
  <div className="todo" style={{ textDecoration: todo.isCompleted ? "line-through" : "" }}>
      {todo.text}
      <div>
      <button onClick={() => completeTodo(index)}> Complete </button>
      <button onClick={() => removeTodo(index)} > X </button> 
      </div>
    </div>)
}

The Todo function takes in todo props, index props, completeTodo props, and removeTodo props. If the todo's isCompleted property is true, there will be a line through the text. There will be two buttons, one for Completed, and one for removing the todo.
This is what the App function's return finally looks like:

return (
  <div className="app">
       <TodoForm addTodos={addTodos} />
    <div className="todo-list">
      {todos.map((todo, index) => (
        <Todo
          key={index}
          index={index}
          todo={todo}
          completeTodo={completeTodo}
          removeTodo={removeTodo}
        />
      ))}
    </div>
  </div>
);

It calls the Todo functional component as well as the TodoForm functional component.

That's it for the app! Hope you guys enjoyed it, and let me know what content you want me to post in the future!

Sum of Left Leaves - Leetcode

Shirley — Mon, 24 Aug 2020 18:30:33 +0000

Today's leetcode challenge was a binary tree question: sum all of the left leaves of a binary tree.

Find the sum of all left leaves in a given binary tree.

Example:

    3
   / \
  9  20
    /  \
   15   7

There are two left leaves in the binary tree, with values 9 and 15 respectively. Return 24.

My method was using dfs and recursion. I created a dfs function that had two parameters: a value for the node (root) and a boolean value for whether the node was left or not(left). Then I checked to see if the root had a left child or right child and if it was left. If true, I added the value of the node to a cache. I then used recursion to loop through all the left nodes and all the right nodes. In my main function, I set cache = [0] and called the dfs function with parameters of root, and False.

class Solution:
    def sumOfLeftLeaves(self, root: TreeNode) -> int:
        def dfs(root, left):
            if not root:
                return
            if left and not root.left and not root.right:
                cache[0] += root.val
            dfs(root.left, True)
            dfs(root.right, False)
        cache = [0]
        dfs(root, False)
        return cache[0]

Two Sum - Leetcode

Shirley — Mon, 24 Aug 2020 18:10:20 +0000

Today I'm going to go over three solutions to the popular leetcode question Two Sum.

The question is this: given an array of numbers and a target number, return the indices of two numbers that add up to the target number.

Solutions:

O(n^2) time, O(1) space We can use two for loops to loop through the array and find the indices of the two numbers that add up to the target number.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(len(nums)):
            for j in range(i+1, len(nums)):
                if nums[i] + nums[j] == target:
                    return [i, j]

O(n) time, O(n) space We can use a hash table to store the numbers as keys and the indices as values. Then we check to see if the difference (target - number) is in the hash table. If it is, return both the index of the number and the index of the difference.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        values = {}
        for i, num in enumerate(nums):
            diff = target - num
            if diff in values:
                return [i, values[diff]]
            values[num] = i
        return []

O(nlogn) time, O(1) space You can use the two pointer method. After sorting the array and creating an array of the numbers and their indices, create two pointers i and j where i = 0 and j = len(array)-1. If the sum is smaller than target, increment i, if larger, increment j. If equal, return the indices.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        i = 0
        j = len(nums) - 1
        sortedNums = sorted(zip(nums, range(len(nums))))
        while i < j:
            if sortedNums[i][0] + sortedNums[j][0] == target:
                return [sortedNums[i][1], sortedNums[j][1]]
            elif sortedNums[i][0] + sortedNums[j][0] < target:
                i += 1
            elif sortedNums[i][0] + sortedNums[j][0] > target:
                j -= 1

Remove Duplicates From Linked List - Cracking the Coding Interview, Leetcode

Shirley — Thu, 20 Aug 2020 20:30:05 +0000

This problem appears in both Cracking the Cracking Interview and Leetcode. The problem is this: given a linked list, delete duplicates such that each number appears only once.

For example:

input: 1 -> 1 -> 2
output: 1 -> 2

Here's a hint. Use a hashset to store your unique numbers in, and if the number exists already in the hashset, set the pointer of the previous node equal to the next node of current node.

class Node:
  self.data = data
  self.next = None

class Solution:
  def removeDuplicates(self, head:Node) -> Node:
      hashSet = set()
      node = head
      prev = None
      while node:
         if node.data not in hashSet:
            hashSet.add(node.data)
            prev = node
         else:
            prev.next = node.next
          node = node.next
      return head

Functional programming and pure functions

Shirley — Thu, 20 Aug 2020 20:12:15 +0000

I have had interviewers ask me what functional programming is. I have heard of the term but never known what it really was until recently.

Functional programming is characterized by pure, higher order functions and immutable data. It is a programming paradigm, meaning it is a way of thinking of software construction based on higher level principles. Imperative programming is focused on creating statements that instruct your program every step it needs to take or how to do something whereas declarative programming tells the program what to do.

Pure functions are functions that, given the same input, produces the same output and does not have observable side effects. They are predictable, independent (do not use values in surrounding environment), easy to reuse, simplify state management, and are easy to test.

The map method is a pure function.

A side effect manipulates the state of the program or has observable effects on the program. These include reassigning a new value to a variable, mutating an object. A function has side effects if it changes the external state.

This is an example of a side effect in a function:

let _id = 1
function uniqueId() {
id++;
}

Higher order functions are functions that return a function. First class functions are functions that are treated like a value and can be returned from a function, passed as an argument to a function, assigned as a variable method or stored in an array.

Difference between Shallow Copy and Deep Copy

Shirley — Thu, 20 Aug 2020 19:58:47 +0000

“Tell me, what is the difference between a shallow copy and a deep copy? And how can you make a deep copy of an object?”

This was a question I got in an interview for a full stack web developer position. I have never heard of the terms “shallow copy” and “deep copy” back then. But it’s absolutely essential that web developers and software engineers understand the difference between a shallow copy and a deep copy. Interviewers will mostly definitely ask you how you can make a deep copy. Here is what you need to know.

First, you need to understand that primitive values are passed by value, while objects and arrays are passed by reference. What do I mean by that? When you pass by value, you create a copy of the original value. When you pass by reference, you make an alias to the original. Objects are stored in memory using a reference value. The reference value is an address in memory where the object is located. When you make a shallow copy of an object, you copy the reference, not the object itself. The actual object isn’t copied.

So a shallow copy copies the reference, and a deep copy copies the actual value of the object. Here are four ways you can make a shallow copy:

Object assign() method. You can use Object.assign() to copy over all enumerable properties of an object to a new object. For example:

const obj = {firstName: "John", lastName:"Smith"};
const newObj = Object.assign({}, obj);

In this example, the newObj will contain the same properties and values as the original obj.

Spread operator. You can duplicate an array or an object by using the spread operator.

const arr = [1, 2, 3, 4];
const newArr = [...arr];
// newArr = [1, 2, 3, 4]

Slice method. You can clone an array by slicing it.

const arr = ["a", "b", "c"];
const newArr = arr.slice();
// newArr = ["a", "b", "c"]

Array.from() method.

const arr = [1, 2, 3];
const newArr = Array.from(arr);

Here are ways to make a deep copy:

Lodash. After importing Lodash, you can use their cloneDeep() method to make a deep copy.

import _ from "lodash"
const obj = {firstName:"John", lastName:"Smith"};
const newObj = _.cloneDeep(obj);

Ramda.

import R from "ramda"
const obj = {firstName:"John", lastName:"Smith"};
const newObj = R.clone(obj);

JSON.parse(JSON.stringify())

const obj = {firstName:"John", lastName:"Smith"};
const newObj = JSON.parse(JSON.stringify(obj));