Delete Node in a Linked List Link to original Problem on LeetCode
Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.
Given linked list – head = [4,5,1,9], which looks like following:
Example 1:
Input: head = [4,5,1,9], node = 5
Output: [4,1,9]
Explanation: You are given the second node with value 5, the linked list should become 4 -> 1 -> 9 after calling your function.
Move Zeroes Link to original Problem on LeetCode
Given an array nums, write a function to move all 0’s to the end of it while maintaining the relative order of the non-zero elements.
Example:
Input: [0,1,0,3,12] Output: [1,3,12,0,0]
Note:
You must do this in-place without making a copy of the array. Minimize the total number of operations.
Company: Amazon, Bloomberg, Paytm, Samsung
Solution:
Time Complexity: O(n) Space Complexity: O(1)
class Solution(object): def moveZeroes(self, nums): """ :type nums: List[int] :rtype: None Do not return anything, modify nums in-place instead.
Reverse Linked List Link to original Problem on LeetCode
Reverse a singly linked list.
Example:
Input: 1->2->3->4->5->NULL Output: 5->4->3->2->1->NULL
Follow up:
A linked list can be reversed either iteratively or recursively. Could you implement both?
Company: Adobe, Amazon, MakeMyTrip, Microsoft, Qualcomm, Samsung
Solution (Iterative):
Time Complexity: Space Complexity:
class Solution(object): def reverseList(self, head): """ :type head: ListNode :rtype: ListNode """ # Video Explanation: https://youtu.be/sYcOK51hl-A # Credit: mycodeschool prev = None curr = head while curr: next = curr.
Product of Array Except Self Link to original Problem on LeetCode
Given an array nums of n integers where n > 1, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].
Example:
Input: [1,2,3,4] Output: [24,12,8,6]
Note: Please solve it without division and in O(n).
Follow up: Could you solve it with constant space complexity? (The output array does not count as extra space for the purpose of space complexity analysis.
Maximum Depth of Binary Tree Link to original Problem on LeetCode
Given a binary tree, find its maximum depth.
The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
Note: A leaf is a node with no children.
Example:
Given binary tree [3,9,20,null,null,15,7],
return its depth = 3.
Company: Goldman Sachs, Facebook, Bloomberg, Microsoft
Solution (Iterative using breadth first search):
Single Number Link to original Problem on LeetCode
Given a non-empty array of integers, every element appears twice except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
Example 1:
Input: [2,2,1] Output: 1
Example 2:
Input: [4,1,2,1,2] Output: 4
Company: Amazon
Solution (Using HashMap):
Time Complexity: O(n) Space Complexity: O(n)
class Solution(object): def singleNumber(self, nums): """ :type nums: List[int] :rtype: int """ # Keep a dictionary count and at the end just check whether any number has a count of 1 numCount = {} for num in nums: numCount[num] = numCount.
