Easy Flashcards
Given a 32-bit signed integer, reverse digits of an integer.
check return 0 part
Given an array, rotate the array to the right by k steps, where k is non-negative.
Take care of–>
k=k%nums.length
and
nums.length - 1
Given two binary trees, write a function to check if they are the same or not.
recursion
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
Time complexity : O(n) We traverse the list containing n elements only once. Each look up in the table costs only O(1) time.
Space complexity : O(n)
how to find if key is present in map or not
map.containsKey(key)
how to create and initialize array
int[] ret = new int [] {m.get(target- nums[i]), i};
int[] ret = new int [] {a, b};
How to throw invalid argument exeption
throw new IllegalArgumentException(“No two sum solution”);
Given a non-empty array of digits representing a non-negative integer, plus one to the integer.
pass by value n reference in java
pass by value- for all java primitive data types like int, float, boolean
pass by reference- for all non primitive data types like arrays, stack, etc
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
Maintain two stacks.
Given a linked list, determine if it has a cycle in it.
Time complexity : O(n)
Space complexity : O(1)
Given a string containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[’ and ‘]’, determine if the input string is valid.
public boolean isValid(String s) {
Stack<character> stack = new Stack<character>();</character></character>
for (char c : s.toCharArray()) {
if (c == ‘(‘)
stack.push(‘)’);
else if (c == ‘{‘)
stack.push(‘}’);
else if (c == ‘[’)
stack.push(‘]’);
else if (stack.isEmpty() || stack.pop() != c) return false;
}
return stack.isEmpty();
}
Time complexity : O(n)
push and pop operations on a stack take O(1) time.
Space complexity :O(n)
in the worst case, we will end up pushing all the brackets onto the stack. e.g. ((((((((((.
Remove Duplicates from Sorted Array
Given nums = [0,0,1,1,1,2,2,3,3,4], Your function should return length = 5, with the first five elements of nums being modified to 0, 1, 2, 3, and 4 respectively. It doesn’t matter what values are set beyond the returned length.
Time complextiy : O(n). Assume that n is the length of array. Each of i and j traverses at most n steps.
Space complexity : O(1).
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.
Time complexity should be O(n)
space O(1)
Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4
Time complexity : O(n + m)
Space complexity : O(1)
——————————————recursion——————————
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if(l1 == null) return l2;
if(l2 == null) return l1;
if(l1.val < l2.val){
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else{
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
Space complexity : O(n + m)
Time complexity : O(n + m)
Move Zeroes
Input: [0,1,0,3,12]
Output: [1,3,12,0,0]
Space Complexity : O(1)
Time Complexity: O(n)
Invert Binary Tree
Since each node in the tree is visited only once, the time complexity is O(n), where n is the number of nodes in the tree.
Because of recursion,O(h) function calls will be placed on the stack in the worst case, where h is the height of the tree. Because h∈O(n), the space complexity is O(n)
Given a stream of integers and a window size, calculate the moving average of all integers in the sliding window.
Example:
MovingAverage m = new MovingAverage(3);
m. next(1) = 1
m. next(10) = (1 + 10) / 2
m. next(3) = (1 + 10 + 3) / 3
m. next(5) = (10 + 3 + 5) / 3
Design a logger system that receive stream of messages along with its timestamps, each message should be printed if and only if it is not printed in the last 10 seconds.
Logger logger = new Logger();
// logging string “foo” at timestamp 1 logger.shouldPrintMessage(1, “foo”); returns true;
// logging string “bar” at timestamp 2 logger.shouldPrintMessage(2,”bar”); returns true;
// logging string “foo” at timestamp 3 logger.shouldPrintMessage(3,”foo”); returns false;
// logging string “bar” at timestamp 8 logger.shouldPrintMessage(8,”bar”); returns false;
// logging string “foo” at timestamp 10 logger.shouldPrintMessage(10,”foo”); returns false;
// logging string “foo” at timestamp 11 logger.shouldPrintMessage(11,”foo”); returns true;
We want to use quad trees to store an N x N boolean grid. Each cell in the grid can only be true or false. The root node represents the whole grid. For each node, it will be subdivided into four children nodes until the values in the region it represents are all the same.
Each node has another two boolean attributes : isLeaf and val. isLeaf is true if and only if the node is a leaf node. The val attribute for a leaf node contains the value of the region it represents.
Your task is to use a quad tree to represent a given grid.
class Node {
public boolean val;
public boolean isLeaf;
public Node topLeft;
public Node topRight;
public Node bottomLeft;
public Node bottomRight;
public Node() {}
public Node(boolean _val,boolean _isLeaf,Node _topLeft,Node _topRight,Node _bottomLeft,Node _bottomRight) {
val = _val;
isLeaf = _isLeaf;
topLeft = _topLeft;
topRight = _topRight;
bottomLeft = _bottomLeft;
bottomRight = _bottomRight;
}
};
Pascal’s Triangle
Given a non-negative integer numRows, generate the first numRows of Pascal’s triangle.
