Problem Given a positive integer num, write a function which returns True if num is a perfect square else False. Follow up: Do not use any built-in library function such as sqrt. Examples Example 1: Input: num = 16 Output: true Example 2: Input: num = 14 Output: false ...
Problem Suppose you are at a party with n people (labeled from 0 to n - 1) and among them, there may exist one celebrity. The definition of a celebrity is that all the other n - 1 people know him/her but he/she does not know any of them. Now you want to find out who the celebrity is or verify that there is not one. The only thing you are allowed to do is to ask questions like: “Hi, A. Do you know B?” to get information of whether A knows B. You need to find out the celebrity (or verify there is not one) by asking as few questions as possible (in the asymptotic sense). ...
Problem Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. An input string is valid if: Open brackets must be closed by the same type of brackets. Open brackets must be closed in the correct order. Every close bracket has a corresponding open bracket of the same type. Examples Example 1: ...
Problem Given a linked list, in addition to the next pointer, each node has a child pointer that can point to a separate list. With the head node, flatten the list to a single-level linked list. Examples Example 1: Input: head = [1, [2, [5, 6] ], 3, 4] 1 -> 2 -> 3 -> 4 | 5 -> 6 Output: 1 -> 2 -> 3 -> 4 -> 5 -> 6 ...
Problem Given an array nums of size n, return the majority element. The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array. Definition Majority Element: If an element appears more than n/2 times in array where n is the size of the array. Examples int [] arrA = {1,3,5,5,5,5,4,1,5}; Output: Element appearing more than n/2 times: 5 int []arrA = {1,2,3,4}; Output: No element appearing more than n/2 times ...
Problem The API: int read4(char *buf) reads 4 characters at a time from a file. The return value is the actual number of characters read. For example, it returns 3 if there is only 3 characters left in the file. By using the read4 API, implement the function int read(char *buf, int n) that reads n characters from the file. Examples Example 1 Input: "filetestbuffer" read(6) read(5) read(4) read(3) read(2) read(1) read(10) Output: 6, buf = "filete" 5, buf = "stbuf" 3, buf = "fer" 0, buf = "" 0, buf = "" 0, buf = "" 0, buf = "" ...
Problem Given a file and assume that you can only read the file using a given method read4, implement a method to read n characters. Method read4: The API read4 reads 4 consecutive characters from the file, then writes those characters into the buffer array buf. The return value is the number of actual characters read. Note that read4() has its own file pointer, much like FILE *fp in C. ...
Problem A message containing letters from A-Z can be encoded into numbers using the following mapping: 'A' -> 1 'B' -> 2 ... 'Z' -> 26 To decode an encoded message, all the digits must be grouped then mapped back into letters using the reverse of the mapping above (there may be multiple ways). For example, "11106" can be mapped into: ...
Problem Given an integer array nums that may contain duplicates, return all possible subsets (the power set). The solution set must not contain duplicate subsets. Return the solution in any order. Examples Example 1: Input: nums = [1,2,2] Output: [ [],[1],[1,2],[1,2,2],[2],[2,2] ] Example 2: Input: nums = [0] Output: [ [],[0] ] ...
Problem Given an unsorted integer array, find the first missing positive integer. Follow up You have to find the smallest positive number missing from the array in O(n) time using constant extra space. You can modify the original array. Examples Example 1: Input: nums = [1,2,0] Output: 3 ...