Nitin Gupta
BAN USER
- 4of 4 votes
AnswersGiven an array of integers and a number. WAP to find the pairs which sum of upto given number.
- Nitin Gupta in India for Cloud & Enterprise team
I solved it. Then he asked about writing test cases for this function.
I wrote below test cases
1.) All the elements should be number.
2.) Length of array should not be 0.
3.) Array itself should not be null.
4.) Given number, arrayLength can be represented by 32bits or 64 bits.
5.) number should not be negative.
6.) Input does not has pair, It should return false
7.) Input has pair, It should return true
8.) Input has all negative values and pair exists, then function should return true
9.) Input has all negative values and pair does not exists, function should return false
He told that he is looking for more test cases. Can you guys think of some more complex test cases.| Report Duplicate | Flag | PURGE
Microsoft SDE-2 Algorithm Arrays C++ Data Structures - 0of 0 votes
AnswersIn a Formula-1 challenge, there are n teams numbered 1 to n. Each team has a car and a driver. Car’s specification are as follows:
- Nitin Gupta in India
– Top speed: (150 + 10 * i) km per hour
– Acceleration: (2 * i) meter per second square.
– Handling factor (hf) = 0.8
– Nitro : Increases the speed to double or top speed, whichever is less. Can be used only once.
Here i is the team number.
The cars line up for the race. The start line for (i + 1)th car is 200 * i meters behind the ith car.
All of them start at the same time and try to attain their top speed. A re-assessment of the positions is done every 2 seconds(So even if the car has crossed the finish line in between, you’ll get to know after 2 seconds). During this assessment, each driver checks if there is any car within 10 meters of his car, his speed reduces to: hf * (speed at that moment). Also, if the driver notices that he is the last one on the race, he uses ‘nitro’.
Taking the number of teams and length of track as the input, Calculate the final speeds and the corresponding completion times.| Report Duplicate | Flag | PURGE
Google SDE1 Algorithm Arrays Data Structures Java Object Oriented Design - 0of 0 votes
AnswersUpdate to careercup android app
- Nitin Gupta in India
I gave one update to careercup app.
Now you can get the right questions which you want to focus on.
https://play.google.com/store/apps/details?id=com.careercup
Install it from here to know more.
P.S. - It is free and available throughout the world. Also write reviews, feature requests, and give ratings
Thanks Guys| Report Duplicate | Flag | PURGE
- 1of 3 votes
AnswersNew CareerCup Android App!!!
- Nitin Gupta in United States
Hey Guys,
Lately I was trying to get android app for this website and no single app was good enough for me.
So I thought of developing it myself. After 2 weekends of work I released first version of the app. With lot more new features lined up.
Please download it here
https://play.google.com/store/apps/details?id=com.careercup
and give your reviews and ratings.
Thanks| Report Duplicate | Flag | PURGE
A9 SDE1 - 0of 0 votes
AnswersWrite printf method.
- Nitin Gupta in India| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 1of 1 vote
AnswersWhich is best Merge Sort or QuickSort?
- Nitin Gupta in India
Why and How?| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - -5of 7 votes
AnswersGiven a matrix of size M X N containing all 0's, and a co-ordinate (i, j) in the matrix.
You have to fill the matrix with L shape block (made by 3 blocks, each block is having 1) except the given co-ordinate.1 1 1 1 1 1 1 1 1 1 1 1
Note - L shaped block can be rotated, so finally there will be 4 orientation for L shape block.
- Nitin Gupta in United States for AppStore
You can assume that solution always exists.
Later on he changed matrix to N X N where N = 2^n.| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 1of 9 votes
AnswersGiven one egg and a building with infinite number of floors. Find out minimum number of throws at which (least) floor egg will break, if thrown?
- Nitin Gupta in India for Illustrator
I said we have to start at floor 1 and keep incrementing and testing by moving 1 floor up. Then he said optimize it by minimizing no of throws. I could not find more optimal way. I told him that I know with problem with 2 eggs and finite floor building.
Then, he told me that now lets there are 2 eggs and infinite floor building, find minimum no if throws required to find least floor at which egg breaks.
I still could not do that for infinite floors.| Report Duplicate | Flag | PURGE
Adobe Member Technical Staff Brain Teasers - -2of 2 votes
AnswersGiven 2 arrays with numbers, multiply the numbers with corresponding indexes and return the sum of all the products.
- Nitin Gupta in India for WebStore
Twist :- When one array gets consumed then start with its first element again.
A : 1,2,3,4,5
B : 2,1
Output: 24 (1*2 + 2*1 + 3*2 + 4*1 + 5*2)| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - -1of 3 votes
AnswersPrint N numbers of form 2^i.5^j in increasing order for all i >= 0 , j >= 0 ?
- Nitin Gupta in India for WebStore
Example : - 1,2,4,5,8,10,16,20.....| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 1of 5 votes
AnswersBelow question was asked in online coding exam for Palantir Technology, Palo Alto, CA. Time given was 100 min. I could not complete it by the time.
- Nitin Gupta in United States
-----------------------------
A group of farmers has some elevation data, and we’re going to help them understand how rainfall flows over their farmland.
We’ll represent the land as a two-dimensional array of altitudes and use the following model, based on the idea that water flows downhill:
If a cell’s four neighboring cells all have higher altitudes, we call this cell a sink; water collects in sinks.
Otherwise, water will flow to the neighboring cell with the lowest altitude. If a cell is not a sink, you may assume it has a unique lowest neighbor and that this neighbor will be lower than the cell.
Cells that drain into the same sink – directly or indirectly – are said to be part of the same basin.
Your challenge is to partition the map into basins. In particular, given a map of elevations, your code should partition the map into basins and output the sizes of the basins, in descending order.
Assume the elevation maps are square. Input will begin with a line with one integer, S, the height (and width) of the map. The next S lines will each contain a row of the map, each with S integers – the elevations of the S cells in the row. Some farmers have small land plots such as the examples below, while some have larger plots. However, in no case will a farmer have a plot of land larger than S = 5000.
Your code should output a space-separated list of the basin sizes, in descending order. (Trailing spaces are ignored.)
While correctness and performance are the most important parts of this problem, a human will be reading your solution, so please make an effort to submit clean, readable code. In particular, do not write code as if you were solving a problem for a competition.
A few examples are below.
Input:
3
1 5 2
2 4 7
3 6 9
Output:
7 2
The basins, labeled with A’s and B’s, are:
A A B
A A B
A A A
Input:
1
10
Output:
1
There is only one basin in this case.
Input:
5
1 0 2 5 8
2 3 4 7 9
3 5 7 8 9
1 2 5 4 2
3 3 5 2 1
Output:
11 7 7
The basins, labeled with A’s, B’s, and C’s, are:
A A A A A
A A A A A
B B A C C
B B B C C
B B C C C
Input:
4
0 2 1 3
2 1 0 4
3 3 3 3
5 5 2 1
Output:
7 5 4
The basins, labeled with A’s, B’s, and C’s, are:
A A B B
A B B B
A B B C
A C C C| Report Duplicate | Flag | PURGE
Palantir Technology Front-end Software Engineer Algorithm - -1of 3 votes
AnswersGiven a number x = 0x25. Convert it into y = 0x25252525.
- Nitin Gupta in India| Report Duplicate | Flag | PURGE
Adobe Member Technical Staff Algorithm Bit Manipulation C Coding - -1of 1 vote
AnswersWe have a long chain of cuboids in all the six directions (six faces). One start node is given and one end node is given. Give a data structure to represent this also search for the given node from start node.
- Nitin Gupta in India for Live Cycle| Report Duplicate | Flag | PURGE
Adobe Member Technical Staff Algorithm Data Structures - -1of 1 vote
AnswersGiven a number, find next higher palindrome number that comes after this number. Give algorithm.
- Nitin Gupta in United States for Live Cycle| Report Duplicate | Flag | PURGE
Adobe Member Technical Staff Algorithm - -1of 1 vote
AnswersWrite a code to generate Pascals triangle of any level.
- Nitin Gupta in India| Report Duplicate | Flag | PURGE
Adobe MTS Algorithm Data Structures - 0of 2 votes
AnswersI have a list of N teams T1, T2, T3 … Tn. Each of these teams has played a match against every other team. I have a function displayResult(Team T1, Team T2), it returns the team which won the match between any two given teams T1 and T2.
- Nitin Gupta in India
I have to write the teams in an order such the (n-1)th team (in the order) had lost to the nth team which in turn had lost to (n+1)th team..Write Code| Report Duplicate | Flag | PURGE
Adobe MTS SDE1 Algorithm Data Structures - -1of 1 vote
AnswersGiven a sorted but rotated array. Find the pivot.
- Nitin Gupta in India| Report Duplicate | Flag | PURGE
Adobe MTS Algorithm Arrays Data Structures - 0of 0 votes
AnswersAlice is a kindergarden teacher. She wants to give some candies to the children in her class. All the children sit in a line and each of them has a rating score according to his or her usual performance. Alice wants to give at least 1 candy for each child.Children get jealous of their immediate neighbors, so if two children sit next to each other then the one with the higher rating must get more candies. Alice wants to save money, so she wants to minimize the total number of candies.
- Nitin Gupta in India| Report Duplicate | Flag | PURGE
Algorithm Data Structures - 3of 3 votes
AnswersQ1.- Written exam (Amazon, Bangalore)
- Nitin Gupta in India
Given a singly link list and a number 'K', swap the Kth node from the start with the Kth node from the last. Check all the edge cases.
Sample Input: 1->2->3->4->5->6->7->8 and K = 3
Sample Output : 1->2->6->4->5->3->7->8
Sample Input: 1->2->3->4->5->6->7->8 and K = 10
Sample Output: print error "LIST IS OF LESSER SIZE".| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm C C# C++ Coding Data Structures Java Linked Lists - 0of 0 votes
AnswersQ2. F2F Round-1, Amazon(Bangalore)
- Nitin Gupta in India
Given an array of integers having the property that first that array is strictly increasing then it is strictly decreasing, You have to search for a given number.
Constraint: Minimize the complexity| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm Arrays C C# C++ Coding Data Structures Java - 0of 0 votes
AnswersQ1. F2F Round 1 Amazon(Bangalore)
- Nitin Gupta in India
Given a character array as input. Array contains only three types of characters 'R', 'G' and 'B'. Sort the array such that all 'R's comes before 'G's and all 'G's comes before 'B's.
Constraint :- No extra space allowed(except O(1) space like variables) and minimize the time complexity.
You can only traverse the array once.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm Arrays C C# C++ Coding Data Structures Java Sorting - 0of 0 votes
AnswersQ4. Written Exam Amazon(Bangalore)
- Nitin Gupta in India
Given an array of integers A[1....n-1] where 'N' is the length of array A[ ]. Construct an array B such that B[i] = min(A[i], A[i+1], ......., A[i-K+1]), where K will be given.
Array B will have N-K+1 elements.
Constraint: Extra space allowed O(K) and time complexity allowed O(N.K) or lower.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm Arrays C C# C++ Coding Data Structures Java Sorting - 1of 1 vote
AnswersQ3. Written Exam Amazon(Bangalore)
- Nitin Gupta in India
Given a singly linked list which may or may not contain loop and loop may or may not start from the head node. Count the number of elements in the linked list.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm C C# C++ Coding Data Structures Java Linked Lists - 0of 0 votes
AnswersQ2. Written Exam Amazon(Bangalore)
- Nitin Gupta in India
Given a number in the form of string. Output the binary equivalent of that number.
Sample Input: "8.5"
Sample Output: 1000.1
Sample Input: "12.34.23"
Sample Output: "ERROR"| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm C C# C++ Coding Java Math & Computation - 0of 0 votes
AnswersQ2. F2F Round-1, Amazon(Bangalore)
- Nitin Gupta in India
Given an array of integers having the property that first that array is strictly increasing then it is strictly decreasing, You have to search for a given number.
Constraint: Minimize the complexity| Report Duplicate | Flag | PURGE
Algorithm - 0of 0 votes
AnswerQ1. F2F Round 1 Amazon(Bangalore)
- Nitin Gupta in India
Given a character array as input. Array contains only three types of characters 'R', 'G' and 'B'. Sort the array such that all 'R's comes before 'G's and all 'G's comes before 'B's.
Constraint :- No extra space allowed(except O(1) space like variables) and minimize the time complexity.
You can only traverse the array once.| Report Duplicate | Flag | PURGE
Algorithm - 0of 0 votes
AnswersQ4. Written Exam Amazon(Bangalore)
- Nitin Gupta in India
Given an array of integers A[1....n-1] where 'N' is the length of array A[ ]. Construct an array B such that B[i] = min(A[i], A[i+1], ......., A[i-K+1]), where K will be given.
Array B will have N-K+1 elements.
Constraint: Extra space allowed O(K) and time complexity allowed O(N.K) or lower.| Report Duplicate | Flag | PURGE
Algorithm - 0of 0 votes
AnswersQ1.- Written exam (Amazon, Bangalore)
- Nitin Gupta in India
Given a singly link list and a number 'K', swap the Kth node from the start with the Kth node from the last. Check all the edge cases.
Sample Input: 1->2->3->4->5->6->7->8 and K = 3
Sample Output : 1->2->6->4->5->3->7->8
Sample Input: 1->2->3->4->5->6->7->8 and K = 10
Sample Output: print error "LIST IS OF LESSER SIZE".| Report Duplicate | Flag | PURGE
Algorithm
4 Answers Adobe Software Engineer Profile for White Box Testing
Hi All,
- Nitin Gupta May 15, 2012
I want to know that how good is this profile for Software Engineer. Currently I am working in Samsung, Bangalore as Software Engineer. I want to grow as Software Developer in some very good company like Amazon, Google, Microsoft, Adobe etc.
Though the company is Adobe and profile is Software Engineer but it is creating doubt in my mind as they have written White Box testing in the mail. Please find the below mail as received by me from Adobe. Kindly enlighten me keeping my career prospect in mind. Should I take it or not??
------------------------------------------------------------
Mail From Adobe
------------------------------------------------------------
For white box testers for our Product Adobe Flash Professionals. The profile requires coding, scripting and automation experience. The candidate will be designated as Software Engineer and will be responsible for testing of Adobe products. We're looking for an individual with excellent programming and communication skills.
Requirements:
1. Hands on C++ programming.
2. Should have expertise in scripting - JavaScript and/or Action Script. Experience in Flex/Flash technologies will be preferred.
3. Strong Windows and OS fundamentals. Mac OS experience will be an added advantage.
4. Exposure in writing full test frameworks would be a definite advantage
5. Should have excellent bug writing skills often suggesting the technical solutions to the issues.
6. People with experience in Automation tools like Silk Test will be preferred.
7. This person should be capable of working independently and collaboratively with a team.
8. B.E/B.Tech/M tech/MCA with 0 to 4 years' experience in testing Desktop and Enterprise/Cloud Products.
9. Excellent verbal and written communication skills.
Any help will be appreciated.
Thanks| Flag | PURGE
Create a directed graph and apply Topological Sorting.
- Nitin Gupta May 18, 2015It is quite clear in the question that number of teams and track length is input to the function. So, you can take any value for input parameters.
- Nitin Gupta May 07, 2015Thanks Sumit.
Please download and use the app and encourage others too. Also give your valuable suggestions and feedback for the app.
Sadly, no....but i will try to learn iOS development first.
- Nitin Gupta February 22, 2015Test
- Nitin Gupta February 14, 2015Take XOR of all the numbers of array. Resulting number in XOR is the answer.
- Nitin Gupta February 20, 2014void merge(int a[], int begin, int n) {
int p1 = begin;
int p2 = begin + n;
int b = a[p2];
for(int i = p2-1; i > p1; i--) {
a[i+1] = a[i];
}
a[begin + 1] = b;
merge(a, begin + 3, n-1);
}
It seems to be subset-sum problem.
Find a subset with sum of elements half of total sum of array.
1.) Sort the array.
2.) Starting from second element, swap 2nd and 3rd element, 4th and 5th element and so on.
For getting holes info, you need to look at each point. So the best solution is O(n^2). DFS will give O(n^2) only.
Any new approach is welcome.
It was asked in Amazon Ninja Coder 2013.
Please refrain from posting questions for ongoing competition.
Now the competition is over. I will answer this.
I used recursive approach to solve this.
First mark the matrix with barren land as 0 and holes as 1.
Then check recursively for holes using DFS.
Let me know if you guys want working code.
I think anotherguy's algo is correct.
@anonymous - Below is solution for your test case .
l = {0,4,4,6,6,6,6,6,6,6}
r = {6,6,6,6,6,6,6,6,6,0}
ans = {0,3,0,2,5,0,3,5,2,0}
Total water stored = 15
This question was asked in Topcoder SRM 592
- Nitin Gupta October 24, 2013ya
- Nitin Gupta October 14, 2013I think this problem is not asked by FB, but it is asked in Illuminati Hiring Challenge that ended today on HackerRank.com. Only the words have been changed, problem seems to be exactly what was asked there.
- Nitin Gupta October 14, 2013void braces(int open, int close, string str) {
if(open == 0 && close == 0) {
cout << str << endl;
}
if(open > 0) {
braces(open-1, close+1, str + "{");
}
if(close > 0) {
braces(open, close-1, str + "}");
}
}
int main() {
int n;
cout << "Please enter number of braces : ";
cin >> n;
int open = n, close = 0;
braces(open, close, "{");
return 0;
}
@anish[1] - Yes you can start from anywhere. When did I said that you have to start from middle ?
You have to fill whole matrix with L shaped blocks such that only that cell remains unfilled whose co-ordinate is given.
It was asked to me in second face to face.
What is absurd in question ?
No its not knight movement because knight goes 2 step forward then 1 step left or right.
Here its one step forward and then 1 step left or right.
I gave divide and conquer solution. But I don't think divide and conquer is correct.
For Ex. In the last recursive call we will have 2 X 2 matrix where we can fill only 3 block, which is not correct as we have to fill all blocks except i,j
There must be some DP solution.
You are only taking a case where all negative numbers come first followed by 0 and positive numbers, while in question it is not mentioned. So, array can have negative and positive numbers dispersed randomly.
- Nitin Gupta September 08, 2013Geet :- DLL means doubly linked list. What you are saying will be true for circular doubly linked list.
In DLL, previous pointer of first node points to null. While in circular DLL it points to tail.
So you have traverse all along the way to tail.
As this is binary tree, so we have to sort array in descending order and treat this array like we have stored max-heap. So this will be complete binary tree which is left aligned.
Then calculate tree weight.
It is simple
If the question really asks for intersection of lines (as line extends to infinity both ways), then we just have to compare their slope. If slope is equal they will never intersect aka parallel otherwise they will overlap at some point.
But, I think question would be for intersection of line segment (both endpoints of line segment are fixed).
This can be done in O(n). Will post my algo, when I will be free.
- Nitin Gupta July 30, 2013I could not understand why will you pick 'a' as it is not present in input string 'bcd' ?
- Nitin Gupta July 30, 2013Min Coin Problem
- Nitin Gupta July 30, 2013int findMaxSum(int arr[], int n)
{
int incl = arr[0];
int excl, excl_new;
for(int i = 1; i < n; i++)
{
excl_new = incl > excl ? incl : excl;
incl = excl + arr[i];
excl = excl_new;
}
return (incl > excl ? incl : excl);
}
How can you say that doubling floors each time is optimal solution ??
We can triple floors each time also...
For finite floors we can do load balancing as you have described...
but for infinite floors how can we do load balancing ?
what will be the optimized number of throws??
- Nitin Gupta July 19, 2013Its a 0-1 knapsack problem. We have to minimize number of people given a total number of followers.
- Nitin Gupta July 19, 2013// Program to find the amount of water in jth glass of ith row
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// Returns the amount of water in jth glass of ith row
float findWater(int i, int j, float X)
{
// A row number i has maximum i columns. So input column number must
// be less than i
if (j > i)
{
printf("Incorrect Input\n");
exit(0);
}
// There will be i*(i+1)/2 glasses till ith row (including ith row)
float glass[i * (i + 1) / 2];
// Initialize all glasses as empty
memset(glass, 0, sizeof(glass));
// Put all water in first glass
int index = 0;
glass[index] = X;
// Now let the water flow to the downward glassses till the
// amount of water X is not 0 and row number is less than or
// equal to i (given row)
for (int row = 1; row <= i && X !=0.0; ++row)
{
// Fill glasses in a given row. Number of columns in a row
// is equal to row number
for (int col = 1; col <= row; ++col, ++index)
{
// Get the water from current glass
X = glass[index];
// Keep the amount less than or equal to
// capacity in current glass
glass[index] = (X >= 1.0f) ? 1.0f : X;
// Get the remaining amount
X = (X >= 1.0f) ? (X - 1) : 0.0f;
// Distribute the remaining amount to the down two glasses
glass[index + row] += X / 2;
glass[index + row + 1] += X / 2;
}
}
// The index of jth glass in ith row will be i*(i-1)/2 + j - 1
return glass[i*(i-1)/2 + j - 1];
}
// Driver program to test above function
int main()
{
int i = 2, j = 2;
float X = 2.0; // Total amount of water
printf("Amount of water in jth glass of ith row is: %f",
findWater(i, j, X));
return 0;
}
They are asking for maximum path not minimum path.
- Nitin Gupta July 11, 2013typedef unordered_map<Node *, Node *> Map;
Node *clone(Node *graph) {
if (!graph) return NULL;
Map map;
queue<Node *> q;
q.push(graph);
Node *graphCopy = new Node();
map[graph] = graphCopy;
while (!q.empty()) {
Node *node = q.front();
q.pop();
int n = node->neighbors.size();
for (int i = 0; i < n; i++) {
Node *neighbor = node->neighbors[i];
// no copy exists
if (map.find(neighbor) == map.end()) {
Node *p = new Node();
map[node]->neighbors.push_back(p);
map[neighbor] = p;
q.push(neighbor);
} else { // a copy already exists
map[node]->neighbors.push_back(map[neighbor]);
}
}
}
return graphCopy;
}
HackerRank ongoing challenge question.
- Nitin Gupta July 08, 2013We can solve this using Dynamic Programming which will take O(n^2) space and will have time complexity of O(n^2) where n is length of string.
However, it can be solved without Dynamic Programming. So, time complexity will be O(n^2) but in constant space.
int longestPalindromicSubstring(char* str)
{
int len = strlen(str);
int maxLength = 1;
int start = 0;
int low, high;
for(int i = 1; i < len; i++)
{
// Find longest even length palindrome with
// center points as i-1 and i
low = i-1;
high = i;
while(low >= 0 && high < len && str[low] == str[high])
{
if(high - low + 1 > maxLength)
{
start = low;
maxLength = high - low + 1;
}
low--;
high++;
}
// Find longest odd length palindrom with
// center point as i
low = i-1;
high = i+1;
while(low >= 0 && high < len && str[low] == str[high])
{
if(high - low + 1 > maxLength)
{
start = low;
maxLength = high - low + 1;
}
low--;
high++;
}
}
printf("Longest Palindromic Substring is: ");
for(int i = start; i <= start + maxLength - 1; i++)
{
printf("%c", str[i]);
}
return maxLength;
}
Method 1 - Simple but Inefficient. Time Complexity is O(n^2)
Start from root and do an inorder traversal of the tree. For each node N, check whether the subtree rooted with N is BST or not. If BST, then return size of the subtree rooted with N. Else, recur down the left and right subtrees and return the maximum of values returned by left and right subtrees.
int largestBST(struct node *root)
{
if (isBST(root))
return size(root);
else
return max(largestBST(root->left), largestBST(root->right));
}
Method 2 - Efficient
Traverse tree in bottom up manner and pass information like size of BST if it is BST when you recurse back.
/* Returns size of the largest BST subtree in a Binary Tree
(efficient version). */
int largestBST(struct node* node)
{
// Set the initial values for calling largestBSTUtil()
int min = INT_MAX; // For minimum value in right subtree
int max = INT_MIN; // For maximum value in left subtree
int max_size = 0; // For size of the largest BST
bool is_bst = 0;
largestBSTUtil(node, &min, &max, &max_size, &is_bst);
return max_size;
}
/* largestBSTUtil() updates *max_size_ref for the size of the largest BST
subtree. Also, if the tree rooted with node is non-empty and a BST,
then returns size of the tree. Otherwise returns 0.*/
int largestBSTUtil(struct node* node, int *min_ref, int *max_ref,
int *max_size_ref, bool *is_bst_ref)
{
/* Base Case */
if (node == NULL)
{
*is_bst_ref = 1; // An empty tree is BST
return 0; // Size of the BST is 0
}
int min = INT_MAX;
/* A flag variable for left subtree property
i.e., max(root->left) < root->data */
bool left_flag = false;
/* A flag variable for right subtree property
i.e., min(root->right) > root->data */
bool right_flag = false;
int ls, rs; // To store sizes of left and right subtrees
/* Following tasks are done by recursive call for left subtree
a) Get the maximum value in left subtree (Stored in *max_ref)
b) Check whether Left Subtree is BST or not (Stored in *is_bst_ref)
c) Get the size of maximum size BST in left subtree (updates *max_size) */
*max_ref = INT_MIN;
ls = largestBSTUtil(node->left, min_ref, max_ref, max_size_ref, is_bst_ref);
if (*is_bst_ref == 1 && node->data > *max_ref)
left_flag = true;
/* Before updating *min_ref, store the min value in left subtree. So that we
have the correct minimum value for this subtree */
min = *min_ref;
/* The following recursive call does similar (similar to left subtree)
task for right subtree */
*min_ref = INT_MAX;
rs = largestBSTUtil(node->right, min_ref, max_ref, max_size_ref, is_bst_ref);
if (*is_bst_ref == 1 && node->data < *min_ref)
right_flag = true;
// Update min and max values for the parent recursive calls
if (min < *min_ref)
*min_ref = min;
if (node->data < *min_ref) // For leaf nodes
*min_ref = node->data;
if (node->data > *max_ref)
*max_ref = node->data;
/* If both left and right subtrees are BST. And left and right
subtree properties hold for this node, then this tree is BST.
So return the size of this tree */
if(left_flag && right_flag)
{
if (ls + rs + 1 > *max_size_ref)
*max_size_ref = ls + rs + 1;
return ls + rs + 1;
}
else
{
//Since this subtree is not BST, set is_bst flag for parent calls
*is_bst_ref = 0;
return 0;
}
}
1.) Put all characters string2 in a stack.
2.) Then start traversing string1 in reverse order
2.1) If currect character matches with top of stack then pop it from stack.
3.) After traversing string1 fully, If stack is empty then return true else return false
I think BFS or DFS will work.
- Nitin Gupta June 18, 2013Anonymous (Question Poster) - How many years of experience you have??
- Nitin Gupta June 14, 2013use bit vector of 95000. He was looking for bit array at that time.
- Nitin Gupta June 09, 2013Yes, in case of all negative numbers we need special check here.
- Nitin Gupta June 06, 2013See my solution above.
- Nitin Gupta June 06, 2013Another very good approach
int maximumSum(int arr[])
{
int size = sizeof(arr)/sizeof(arr[0]);
int incl = arr[0];
int excl = 0, excl_new;
for(int i = 1; i < size; i++)
{
excl_new = incl > excl ? incl : excl;
incl = excl + arr[i]; // sum including current element
excl = excl_new; // sum excluding current element
}
return (incl > excl ? incl : excl);
}
Explain your code. What is temp? How it will be constructed?
- Nitin Gupta May 29, 2013As per your answer O(log n) + O(n) = O(n).
Mine is giving O(log n) because after finding index of key, I am again doing binary search on left part to find first occurrence. However, you are doing it linear search on the left part.
Your complexity will be O(n). It can be solved in O(log n)
- Nitin Gupta May 27, 2013int binarySearch(int arr[], int start, int end, int key)
{
if(end < start) return -1;
int mid = start + (end - start) / 2;
if(arr[mid] == key)
{
int leftIndex = binarySearch(arr, start, mid - 1, key);
return (leftIndex == -1 ? mid : leftIndex);
}
else if(arr[mid] > key)
{
return binarySearch(arr, start, mid - 1, key);
}
else
{
return binarySearch(arr, mid + 1, end, key);
}
}
Your code will not give first occurrence of given number.
- Nitin Gupta May 27, 2013
RepSpent high school summers donating toy monkeys in Minneapolis, MN. At the moment I'm building glue in Edison, NJ ...
Repryandchinkle, Android Engineer at ABC TECH SUPPORT
I was born in Northridge USA, I like photography, I have wide photos collection of wildlife. I have many religious ...
RepShayneLJohnson, Scientific Officer at Cerberus Capital
I'm Shayne and I have a history of sensitivities that range from dietary issues to skin care and other ...
Repjuanitajboon, Applications Developer at 247quickbookshelp
Hi everyone, I am from Pelham. I currently work in the Hechinger as Cashier.I like to do creative things ...
RepDedicated administrative assistant with years of experience managing large and small offices. I have worked with numerous branches,including payroll ...
Repsalinagray, Development Support Engineer at Atmel
Hi I am Salina Gray,I live in Texas and work as a Design Team Member. I am new to ...
RepHello, I am Sherri from Orangeburg. I am working as a Nurse in Kleinhans Hospital. I like painting, reading, and ...
Repjonesreina93, Hawaiian airlines reservations at American Airlines
Hello, I am currently working at the airport as an air hostess, and my responsibility are Check tickets and assisted ...
Repharrylseay, Aghori Mahakal Tantrik at ASAPInfosystemsPvtLtd
I am Harry and I live in the USA but basically I am from Bangor. I live my life very ...
RepHi, I am Alisa from Southfield, USA, I am working as a Toolmaker in an Audio-Visions company. I am also ...
Repnancyhfloress, Computer Scientist at AMD
Hey there, I’m Nancy. I’m a small business owner living in Sunrise, FL 33323. I am a fan ...
RepDiscover the cheapest packers and movers in Gurgaon at best price with smooth and hassle free relocation. We provide truck ...
Reparlenekraft8, How to book a seat on Southwest airlines flight at Absolute Softech Ltd
I am a coding specialist from MD,USA.I’m indifferent to most items on the planet.Participated in creating ...
Repkevinlmoses, Animator at Accenture
I am Experienced Building Manager who is an expert in public and industrial safety with a preventative mindset against fire ...
Repomarcdei, Android Engineer at Abs india pvt. ltd.
I'm Omar. I am working as a Mail carrier in Manning's Cafeterias company. I love to learn and ...
Repjosephcday6, Android Engineer at Absolute Softech Ltd
I am SEO Executive in Elek-Tek company. I live in Morgantown USA. I won’t write any details about Best ...
RepAmberBrook, Animator at A9
Hi everyone, Done my master of arts in specialized journalism.Also an member of society of professional journalists since 2015 ...
Repmelissattaylor, AT&T Customer service email at Bankbazaar
Je suis membre participant du chapitre de Virginie de l'Association nationale du travail social. J'aime lire et écrire ...
Repnyladsomerville, abc
Want to purchase best quality silencer at affordable price manufactured by top most trusted brand Innovative Arms.
Contact Stonefirearms now!
Rephoychrista, Blockchain Developer at ASU
Worked with Clients to guide them through the event details about copier leasing companies and served as their personal coordinator ...
Repmelissamewingm, abc at ABC TECH SUPPORT
I am Melissa from Springdale. I function as an Auditing assistant in Bountiful Harvest Health Food Store. My solid interest ...
Repelisahbuff, Apple Phone Number available 24/7 for our Customers at Altera
I have previous work experience in a customer focused environment. I like to Enjoy my Free Time Playing football.I ...
Repclairetsmith49, AT&T Customer service email at ADP
Hello, I am Claire and work as a Human resources and I am responsible for recruiting, screening, interviewing and how ...
Repmarkemorgan007, Applications Developer at Big Fish
I am Mark From Fresno city in USA.I working as a tour guide and also help for make a ...
RepJerryesumrall777, Consultant at None
Hello Everyone, My name is Jerrye Sumrall and I am 34 years of age and I originate from Ocean city ...
RepLynnebailey3333, Systems Design Engineer at None
Hello Everyone, My name is Lynne Bailey from Phoenix, AZ I am an expert visual originator. I am working this ...
RepHenryMelvin, Korean Air Change Flight at AMD
Hello, everybody! My name is Henry,I am a picture-drawer.Art drawing & painting classes for adults, kids, teens.We have ...
Hint : Think binary search for the answer.
If you had a function bool isPossible which could tell you if its possible to paint the boards in time T or less.
Keep assigning boards to painter greedily till the time taken < mid. If you run out of painters, isPossible = false.
else isPossible = true.
- Nitin Gupta November 21, 2016