Power of 3 problem
Problem Write function to determine if given unsigned 32-bit number is a power of 3 int is_power_of_3(uint32_t n)
Posts
Reading integer streams and return N th order statistics
Problem Imagine you are reading in a stream of integers. Periodically, you wish to be able to look up the rank of a number x (the number of values less than or equal to x). Implement the data structures and algorithms to support these operations. The following methods need to be implemented. // method to take new number x void track(int x); // method to return the number of values that are less than or equal to x (not including x itself) int get_rank(int x); Example: Stream (in order of appearance): 5, 1, 4, 4, 5, 9, 7, 13, 3 get_rank(1) = 0 get_rank(3) = 1 get_rank(4) = 3
Finding the element in the M X N matrix sorted in ascending order
Problem Given an M $\times$ N matrix in which each row and each column are sorted in ascending order, write a method to find an element.
Finding the string in the sorted array of strings with empty strings
Problem Given a sorted array of strings that is interspersed with empty strings, write a method to find the location of a given string. Example input: find "ball" in {"at", "", "", "","ball", "", "", "car", "", "". "dad", "",""} Output: 4
Finding the magic index in array, A
Problem A magic index in an array A [0. . .n-1] is defined to be an index such that A[i] = i. Given a sorted array of distinct integers, write a method to find a magic index, if one exists, in array A. FOLLOW UP What if the values are not distinct?
Count the number of occurrences in a sorted array [reviewed]
Problem Given a sorted array arr[] and a number x, write a function that counts the occurrences of x in arr[]. Expected time complexity is $O(Log N)$ For example, given array, {8,8,8,9,9,11,15,16,16,16}, the occurrence of 8 should be 3.
Checking if a given tree is Binary search tree - no parent pointer[reviewed]
Problem Your are given the pointer to the root of the tree, with nodes having the following structure. struct node { node * left; node * right; int value; }; You algorithm should find out whether the given tree is BST (Binary search tree or not)
Find the combination of numbers making triangle [reviewed]
Problem Find all triangle combination from a given array of integers. For example, given array of integers, {8,7,3,2,5,6,1,4}, your algorithm should produce list of combinations that makes triangle.
Searching number in the circular array [reviewed]
Problem Given the circular array of sorted values, search the specified value. For example, A = { 4,5,6, 1,2,3}, target = 1; output = true Your algorithm should be better than O(N).
Finding H-index
Problem Find h-index given array of numbers. For more information about h-index, check out the following link. https://en.wikipedia.org/wiki/H-index The idea is that you need to find the last value in the array where the value is larger than its index. For example, Say Scientist A has 5 publications with the following citation count. Publications = {10, 8, 5, 4, 3}. In this case, the h-index is 4 since 4 whose index is 3 is the last value which value is larger than its index.
Local MinMax problem [reviewed]
Problem Given the list of numbers, find the local min or local max Local max or min is the number that exists between the first and last number. For example, 1 , 2 , 3 , 4 , 3 , 2 => local max exists, which is 4 1 , 2 , 3 , 4 , 5 , 6 , 7 => No local max or local min exists 5 , 4 , 3 , 2 , 1 => No local max or local min exists 9 , 8 , 7 , 6 , 5 , 6 , 7 , 8 , 9 => local min exists, which is 5. Challenging part is that your problem should run faster than O(N).