Problem You are given a binary tree in which each node contains a value. Design an algorithm to print all paths which sum up to that value. Note that it can be any path in the tree – it does not have to start at the root. Examples Example 1: 10 / \ 7 15 / \ / \ 8 9 11 1 ...
Problem Implement a function to check if a tree is balanced. Definition Height-balanced binary tree: is defined as a binary tree in which the depth of the two sub-trees of every node never differ by more than 1. Examples Example 1 3 / \ 9 20 / \ 15 7 ...
Problem Given that integers are read from a data stream. Find median of elements read so for in efficient way. OR Numbers are randomly generated and passed to a method. Write a program to find and maintain the median value as new values are generated. OR You are given a stream of numbers which can be positive or negative. You are required to provide an operation FIND MEDIAN..which when invoked should be able return the median of the numbers in stream(in say O(1) time) ...
Problem Write a method to shuffle a deck of cards. It must be a perfect shuffle – in other words, each 52! permutations of the deck has to be equally likely. Assume that you are given a random number generator which is perfect. OR How can you shuffle an array in O(n) time and O(1) space? For example, if input is an array of (1, 2, 3, 4, 5), one of the output can be (5, 4, 3, 2, 1) or (4, 2, 3, 1, 5). ...
Problem The Fibonacci Numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is, Sequence is defined as, $$ F_{0} = 0 $$ and $$ F_{1} = 1 $$ and $$ F_{n} = F_{n-1} + F_{n-2} $$ Given n, calculate F(n). Examples Example 1: Input : n = 2 Output : 1 ...
Problem Write a method to generate a random number between 1 and 7, given a method that generates a random number between 1 and 5. (i.e., implement rand7() using rand5()). OR Using a function rand5() that returns an integer from 1 to 5 (inclusive) with uniform probability, implement a function rand7() that returns an integer from 1 to 7 (inclusive). Solution This appear to be one of those probabilistic analysis questions. You should be familiar with the concept of expected value, as it could be extremely helpful in probabilistic analysis. ...
Problem Given a Binary tree where each node has an extra field (node * next), write a function that puts the inorder successor of that node in the next pointer. struct node { int val; struct node * left; struct node * right; struct node * next; } ...
Reverse Words in a String 2 Problem Given an input string, reverse the string word by word. A word is defined as a sequence of non-space characters. The input string does not contain leading or trailing spaces and the words are always separated by a single space. Follow up Could you do it in-place without allocating extra space? Examples Example 1: Input: s = "the sky is blue" Output: "blue is sky the" ...
Problem You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise). Another way to ask the same problem Given an image represented by an NxN matrix, where each pixel in the image is 4 bytes, write a method to rotate the image by 90 degrees. Can you do this in place? Examples Example 1: ...
Problem You are given two linked lists representing two non-negative numbers. Problem 1 - The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list. Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 0 -> 8 ...