Problem You are given an m x n integer array grid. There is a robot initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m-1][n-1]). The robot can only move either down or right at any point in time. An obstacle and space are marked as 1 or 0 respectively in grid. A path that the robot takes cannot include any square that is an obstacle. ...
Problem Suppose a sorted array is rotated at some pivot unknown to you beforehand. (i.e., [0, 1, 2, 4, 5, 6, 7] might become [4, 5, 6, 7, 0, 1, 2]). You are given a target value to search. If found in the array return its index, otherwise return -1. You may assume no duplicate exists in the array. Follow up: what if duplicates are allowed? ...
Problem Write a function that takes a string as input and returns the string reversed. Examples Example 1: Given s = "hello", return "olleh". Given s = “kodeknight” , return “thginkedok“. Solution Method 0 - Iterative, Not in Place In Java, string is immutable. So, cannot do in place!. public String reverseString(String s) { int n = s.length; char[] reversed = s.toCharArray(); return reverse(reversed); } ...
Problem Given two sorted integer arrays A and B, merge B into A as one sorted array. Note: You may assume that A has enough space to hold additional elements from B. The number of elements initialized in A and B are m and n respectively. Similar Problem You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively. ...
Problem Design a method to find the frequency of occurrences of any given word in a book. Examples Example 1: Input: BookFrequency(String text) text = the day is sunny the the the sunny is is Input: getFrequency("the") Output: 4 Input: getFrequency("is") Output: 3 ...
Problem An array A[1..n] contains all the integers from 0 to n except for one number which is missing. In this problem, we cannot access an entire integer in A with a single operation. The elements of A are represented in binary, and the only operation we can use to access them is ”fetch the jth bit of A[i]”, which takes constant time. Write code to find the missing integer. Can you do it in O(n) time? ...
Problem Given a linked list, remove the nth node from the end of list and return its head. Examples Example 1: Input: head = [1,2,3,4,5], n = 2 Output: [1,2,3,5] Explanation: Given linked list 1->2->3->4->5 and n = 2, the result is 1->2->3->5. ...
Problem Given two strings s and t, return true if t is an anagram of s, and false otherwise. OR WAP to find out if 2 strings are anagrams or not. Anagram Definition Examples Example 1: Input: s = "anagram", t = "nagaram" Output: true Example 2: Input: s = "rat", t = "car" Output: false ...
Problem Explain what the following code does: ((n & (n-1)) == 0). Solution When we have A & B == 0, it means that A and B have no common 1s, i.e. any two bits at the same positions of A and B are either different from each other, or two 0s. It works because a binary power of two is of the form 1000…000 and subtracting one will give you 111…111. Then, when you AND those together, you get zero, such as with: ...
Problem Design a stack that supports push, pop, top, and retrieving the minimum element in constant time. Implement the MinStack class: MinStack() initializes the stack object. void push(int val) pushes the element val onto the stack. void pop() removes the element on the top of the stack. int top() gets the top element of the stack. int getMin() retrieves the minimum element in the stack. You must implement a solution with O(1) aka constant time complexity for each function. ...