Example: [10, 4, -2, 7, 8, -1, -5] Maximum average of continuous elements 7+8=15/2 =7.5
Showing posts with label Google Interview. Show all posts
Showing posts with label Google Interview. Show all posts
Saturday, December 10, 2011
Thursday, December 8, 2011
Wednesday, December 7, 2011
Find The Largest Binary Search Tree in GIven Tree . Its Should be the Subtree.
Very Faq. Asked Question All Tech Giants :) Will Post The Solution Soon :) Meanwhile You Can Try & Post the approach .
Prerequisite : Most Efficient Solution to Check if Given Tree is BST or not ? !st Try it or Search Archives :)
Basic Idea :
Traverse the tree. From each node to the parent, return the following
set of values.
1) If BST, size of the current BST or -1 if the tree is not.
2) Minval & Maxval of the subtree and maxbstsize seen so far (
probably using references)
So in each node check the following:
set of values.
1) If BST, size of the current BST or -1 if the tree is not.
2) Minval & Maxval of the subtree and maxbstsize seen so far (
probably using references)
So in each node check the following:
If( leftmax < node->data && node->data < rightmin) // Means it is a BST { new size = rightsize+leftsize+1 update size if greater than max return size } else { return -1; }
Working Code:
/* Largest Binary search tree inside a binary tree -- O(n)*/
#include <stdlib.h>
#include <stdio.h>
using namespace std;
struct node
{
int data;
struct node* left;
struct node* right;
};
struct node* insert_bst(struct node* root, int num){
if(root == NULL){
root = (struct node*)malloc(sizeof(struct node));
root->data = num;
root->left = NULL;
root->right = NULL;
return root;
}else{
if(num == root->data){
return root;
}
if(num > root->data){
root->right=insert_bst(root->right,num);
}else{
root->left=insert_bst(root->left,num);
}
}
return root;
}
void inorder_traverse(struct node* root){
if(root == NULL) return;
inorder_traverse(root->left);
printf("%d ",root->data);
inorder_traverse(root->right);
}
struct node* bst_root = NULL;
int getmaxbst(struct node* root, int& subtreemin, int &subtreemax, int& max)
{
if(root == NULL) return 0;
int leftsubtreemin = -32767, rightsubtreemin = -32767;
int leftsubtreemax = 32767, rightsubtreemax = 32767;
int x,y;
x = getmaxbst(root->left, leftsubtreemin, leftsubtreemax, max);
y = getmaxbst(root->right, rightsubtreemin, rightsubtreemax, max);
if(x==-1 || y ==-1)
return -1;
if(x==0) { leftsubtreemax = root->data; leftsubtreemin = root->data;}
if(y==0) { rightsubtreemin = root->data; rightsubtreemax = root->data;}
if(root->data < leftsubtreemax ||
root->data > rightsubtreemin){
return -1;
}
subtreemin = leftsubtreemin;
subtreemax = rightsubtreemax;
if(x+y+1 > max){
max = x+y+1;
bst_root = root;
}
return x+y+1;
}
int main()
{
struct node* root=NULL;
root=insert_bst(root,5);
root=insert_bst(root,3);
root=insert_bst(root,9);
root=insert_bst(root,7);
root=insert_bst(root,4);
root=insert_bst(root,1);
root=insert_bst(root,14);
root=insert_bst(root,11);
root->data = 0;
int a,b,c,max=-32767;
c = getmaxbst(root,a,b,max);
printf("\nmax is %d\n",max);
inorder_traverse(bst_root);
return 1;
}
TC O(N)
SC O(1)
Labels:Data
Adobe Question
,
Amazon Interview
,
Google Interview
,
Trees
Wednesday, November 30, 2011
Tuesday, November 29, 2011
Devise an algorithm for maximizing the sum of the randomly selected elements from the k subarrays. Basically means that we will want to split the array in such way such that the sum of all the expected values for the elements selected from each subarray is maximum.
You have an array with *n* elements. The elements are either 0 or 1. You
want to *split the array into kcontiguous subarrays*. The size of each
subarray can vary between ceil(n/2k) and floor(3n/2k). You can assume that
k << n. After you split the array into k subarrays. One element of each
subarray will be randomly selected.
Devise an algorithm for maximizing the sum of the randomly selected
elements from the k subarrays. Basically means that we will want to split
the array in such way such that the sum of all the expected values for the
elements selected from each subarray is maximum.
You can assume that n is a power of 2.
Example:
Array: [0,0,1,1,0,0,1,1,0,1,1,0]
n = 12
k = 3
Size of subarrays can be: 2,3,4,5,6
Possible subarrays [0,0,1] [1,0,0,1] [1,0,1,1,0]
Expected Value of the sum of the elements randomly selected from the
subarrays: 1/3 + 2/4 + 3/5 = 43/30 ~ 1.4333333
Optimal split: [0,0,1,1,0,0][1,1][0,1,1,0]
Expected value of optimal split: 1/3 + 1 + 1/2 = 11/6 ~ 1.83333333
Source -> http://stackoverflow.com/ questions/8189334/google- combinatorial-optimization- interview-problm
want to *split the array into kcontiguous subarrays*. The size of each
subarray can vary between ceil(n/2k) and floor(3n/2k). You can assume that
k << n. After you split the array into k subarrays. One element of each
subarray will be randomly selected.
Devise an algorithm for maximizing the sum of the randomly selected
elements from the k subarrays. Basically means that we will want to split
the array in such way such that the sum of all the expected values for the
elements selected from each subarray is maximum.
You can assume that n is a power of 2.
Example:
Array: [0,0,1,1,0,0,1,1,0,1,1,0]
n = 12
k = 3
Size of subarrays can be: 2,3,4,5,6
Possible subarrays [0,0,1] [1,0,0,1] [1,0,1,1,0]
Expected Value of the sum of the elements randomly selected from the
subarrays: 1/3 + 2/4 + 3/5 = 43/30 ~ 1.4333333
Optimal split: [0,0,1,1,0,0][1,1][0,1,1,0]
Expected value of optimal split: 1/3 + 1 + 1/2 = 11/6 ~ 1.83333333
Source -> http://stackoverflow.com/
Labels:Data
Facebook Interview
,
Google Interview
Saturday, November 26, 2011
Sunday, November 20, 2011
Devise a small memory streaming algorithm to determine if |A| = 1.
For a stream of insertions and deletions, recall that x[j] = #insertions - #deletions of element j.
Given such a stream satisfying x[j] >= 0 for all elements j, let
A = { j : x[j] > 0 }
Determining whether A is empty is easy: just check if the sum of all x[j]'s equals 0 (which is easily doable in a stream).
Problem: devise a small memory streaming algorithm to determine if |A| = 1.
Extensions: What about higher sizes of A? What if the promise is not satisfied and we define A to be the set of j's with x[j] not equal to 0.
Labels:Data
Google Interview
Saturday, November 19, 2011
Given a string of lowercase characters, reorder them such that the same characters are at least distance d from each other.
Input: { a, b, b }, distance = 2
Output: { b, a, b }
Labels:Data
Google Interview
Tuesday, November 15, 2011
Given Table of Cities , Find Minimum Number of Hopes Required to Fly From One to Other City
There is a very Primitive Database and it has a table say "Travel". The content of table is as follows:
Source | Dest
--------------
Sea | LA
LA | FL
LA | MA
FL | Sea
Sea | FL
--------------
Sea | LA
LA | FL
LA | MA
FL | Sea
Sea | FL
The ask is to find out all routes between (Sea) to (FL) with mininum hop.
the Result would be:
1. Sea -> FL
2. Sea -> LA - > FL
the Result would be:
1. Sea -> FL
2. Sea -> LA - > FL
You have to write a Middle tier function to achieve above result. You can assume there is DBAPI that return the Destination city if you provide the source city.
Labels:Data
Amazon Interview
,
DirectI Interview
,
Dynamic Programming
,
Facebook Interview
,
Google Interview
,
Microsoft Interview
,
Recursion
Thursday, October 20, 2011
Given two bst, print the output that would come if two bsts are merged and then an inorder traversal is performed. Of, course you can't merge trees here.
PS:Heard From One of The My Friend :
Labels:Data
Amazon Interview
,
Google Interview
Provide an efficient algorithm to solve the question "Can I buy N items?
A shop sells an item in packets of 6, 9, and 17. A customer can buy any number of packets, but a packet cannot be broken up. Provide an efficient algorithm to solve the question "Can I buy N items?". For example, is it possible to buy 29 items? What about 19? Your algorithm simply needs to return true or false.
Labels:Data
Coin Change
,
DirectI Interview
,
Dynamic Programming
,
Facebook Interview
,
Google Interview
,
Knapsack
Design Data Structure For Students-Courses Realtionship
In a university, students can enroll in different courses. A student may enroll for more than one course. Both students and courses can be identified by IDs given to them. Design a data structure to store students, courses, and the student-course relationships. You can use arrays, lists, stacks, trees, graphs, etc. or come up with your own data structures. Give the running times, in Big O notation, for the following operations for your data structure and justify the answers: a) Return all students in a list. b) Return all courses in a list. c) Return all courses in a list for a given student. d) Return all students in a list for a given course.
Labels:Data
Amazon Interview
,
Data Structures
,
DirectI Interview
,
Facebook Interview
,
Google Interview
Wednesday, September 14, 2011
Monday, September 5, 2011
Find the smallest number expressible as the sum of cubes of two numbers in two different ways. Indeed, 10^3 + 9^3 =12^3+1^3=1729 , Do It Efficiently
Problem:
A mathematician G. H. Hardy was on his way to visit his collaborator S. Ramanujan an who was in the hospital. Hardy remarked to Ramanujan that he traveled in taxi cab number 1729 which seemed a dull one and he hoped it was not a bad omen. To this, Ramanujan replied that 1729 was a very interesting number-it was the smallest number expressible as the sum of cubes of two numbers in two different ways. Indeed,
103 + 93 =123 + 1 3 二1729.
Hint: This problem is very similar to another very popular problem that is asked in interviews. You are given a η ×η matrix in which both rows and columns are sorted in ascending order and you are supposed
to find a given number in the matrix.
Algorithm:
In this case, we are essentially looking for an implicit matrix A such that A(i,j) =i^3十j^3. In our case, the matrix will have n^1/3 rows and columns and this matrix of size n^1/3 * n^1/3 we try to search k=i^3+j^3 isn't it ans algorithms for searching for a number in such a matrix that are linear in the number of rows.
One approach is to start by comparing x to An,1. If x = An ,l , stop.Otherwise, there are two cases:
- x < A1,n in which case x is less than element at Column n at 1,n position. which mean we can escape whole row itself . we decrement column pointer to left.e.g. previous column.
- x > A1,n , in which case if x > a[1][n] is greater than it will be greater then all elements in Row 1.. we increment the row pointer to next row.
Efficient Solution:
Here is the Pseudo Code For The Same.
int IsNumberEqualstoSumeTwoCubes(int n)
{
int row=Ceil(Pow(n,1/3));// Pow Has Complexity of O(logn) Ceil(1729)=577
int column=row;
int i=0;int j=column;
while(i<row && j>=0)
{
int m=i*i*i+j*j*j;
if(m==n)
return 1; // print i^3 and j^3 these are two such numbers
else if ( m < n)
i++;
else
j--;
}
return 0; //such number DNE
}
Complexity Analysis:
In either case, we have a matrix with η fewer elements to search. In each iteration, we remove a row or a column, which means we inspect 2η-1 elements.
We claim that our algorithm that solves the matrix search problem will have to compare x with each of the 2n-l elements shown (i.e the diagonal elements (in case of column element matching )and the elements immediately below them (in case of row elements matching )and this is obvious just draw a diagram in which both row & column are in sorted order & try to run the above algorithm ).
Call these elemmts the # elements..
Comparing x with any other elements in matrix does not eliminate the any of the # elements.we can easily Proof this by Contradiction:Suppose X algorithm doesn't compare x with any of the above # elements.
then we could make that element x ( instead of x-1 got to prev. column or x+1 go to next row.).hence we will get wrong result.
Above Algorithm Really Requires Deep Understanding of Young_tableau :)
Time Complexity O(row+column)=O(N^1/3+N^1/3)=O(2*N^1/3)=O(N^1/3)
Space Complexity O(1)
Labels:Data
Facebook Interview
,
Google Interview
,
Hardy Number
Subscribe to:
Posts
(
Atom
)