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
Mask all odd bits with 10101010 in binary (which is 0xAA), then shift them left to put them in the even bits. Then, perform a similar operation for even bits. This takes a total 5 instructions.
public static int swapOddEvenBits(int x) {
return ( ((x & 0xaaaaaaaa) >> 1) | ((x & 0x55555555) << 1) );
}
@sneha: I think your logic is not correct. This will work only of the matrix has one row only.
If matrix has more than 1 ro, it will fail.
Check my code.
Suppose you want to make queue of length n
Take two stacks, Stack1 and Stack2 of length n each
-----------------------------------------------------------
1) Push -
Bottomline - Always push in Stack1.
IF Stack1 is full and Stack2 is not empty - Print Queue overflow
IF Stack1 is full and Stack2 is empty - Pop every item from Stack1 and push it in Stack2, till Stack1 is empty.
After that push new element on Stack1
2) Pop -
Bottomline - Always pop from Stack2
IF Stack2 is empty and Stack1 is empty - Print Queue Underflow.
IF Stack2 is empty and Stack1 is not empty- Pop every item from Stack1 and push it in Stack2.
Pop from Stack2.
Use circular buffer of length n, where each node stores one line. At the end of file. Print data in buffer line by line
- Nitin Gupta February 07, 2013@ruddermechanic : how many yrs exp do you have ?
- Nitin Gupta February 07, 2013subscribing to the thread
- Nitin Gupta February 07, 2013Find least common ancestor of two nodes, then you can find distance between them.
- Nitin Gupta February 07, 2013subscribing to thread
- Nitin Gupta February 07, 2013This is the problem of largest area histogram. Compute sum of rows by iterative deepening (row-wise), and for every 1-D array generated get largest area histogram for it.
Finally return the maximum.
----------------------------------------------------------
Program to find largest area of histogram.
int largestArea(int arr[], int len)
{
int area[len]; //initialize it to 0
int n, i, t;
stack<int> St; //include stack for using this #include<stack>
bool done;
for (i=0; i<len; i++)
{
while (!St.empty())
{
if(arr[i] <= arr[St.top()])
{
St.pop();
}
else
break;
}
if(St.empty())
t = -1;
else
t = St.top();
//Calculating Li
area[i] = i - t - 1;
St.push(i);
}
//clearing stack for finding Ri
while (!St.empty())
St.pop();
for (i=len-1; i>=0; i--)
{
while (!St.empty())
{
if(arr[i] <= arr[St.top()])
{
St.pop();
}
else
break;
}
if(St.empty())
t = len;
else
t = St.top();
//calculating Ri, after this step area[i] = Li + Ri
area[i] += t - i -1;
St.push(i);
}
int max = 0;
//Calculating Area[i] and find max Area
for (i=0; i<len; i++)
{
area[i] = arr[i] * (area[i] + 1);
if (area[i] > max)
max = area[i];
}
return max;
}
----------------------------------------------------
Program to get 1-D array by summing each row every time.
---------------------------------------------------------
#define ROW 10
#define COL 10
int find_max_matrix(int A[ROW][COL])
{
int i, j;
int max, cur_max;
cur_max = 0;
//Calculate Auxilary matrix
for (i=1; i<ROW; i++)
for(j=0; j<COL; j++)
{
if(A[i][j] == 1)
A[i][j] = A[i-1][j] + 1;
}
//Calculate maximum area in S for each row
for (i=0; i<ROW; i++)
{
max = largestArea(A[i], COL);
if (max > cur_max)
cur_max = max;
}
//Regenerate Oriignal matrix
for (i=ROW-1; i>0; i--)
for(j=0; j<COL; j++)
{
if(A[i][j])
A[i][j] = A[i][j] - A[i-1][j];
}
return cur_max;
}
Guys instead of pasting code here, please discuss algorithms and techniques you used, because that will be more helpful to all of us. I know this can be done, its not that tough question.
Just that I was not able to do it in 100 min (time given by palantir).
I just wanted to know different approaches to solve this question.
My Solution. Though I was not able to complete in 100 min. Wasted a golden opportunity.
-----------------------------
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.StringTokenizer;
import java.util.TreeMap;
import javax.swing.text.html.HTMLDocument.Iterator;
class Result{
int value;
char tag;
Result next;
public Result(int value){
this.value = value;
this.next = null;
}
}
public class Solution {
static int dimension;
static Result land[][];
static List<Integer> list;
public static Result calculateMinimum(Result i, Result j){
Result min = null;
if(i.value < j.value){
min = i;
} else {
min = j;
}
return min;
}
public static Result calculateMinimum(Result i, Result j, Result k) {
Result min = null;
if(i.value < j.value && i.value < k.value){
min = i;
}
if(j.value < i.value && j.value < k.value){
min = j;
}
if(k.value < i.value && k.value < j.value){
min = k;
}
return min;
}
public static Result calculateMinimum(Result i, Result j, Result k, Result l){
Result min = null;
if(i.value < j.value && i.value < k.value && i.value < l.value){
min = i;
}
if(j.value < i.value && j.value < k.value && j.value < l.value){
min = j;
}
if(k.value < i.value && k.value < j.value && k.value < l.value){
min = k;
}
if(l.value < i.value && l.value < j.value && l.value < k.value){
min = l;
}
return min;
}
public static void findBasin(){
if(dimension == 1){
System.out.print(1);
return;
}
char start = 'A';
for(int row = 0; row < dimension; row++){
for(int col = 0; col < dimension; col++){
Result min = null;
if(row - 1 < 0){
if(col - 1 < 0){
min = calculateMinimum(land[row][col + 1], land[row + 1][col]);
} else if(col + 1 >= dimension){
min = calculateMinimum(land[row][col - 1], land[row + 1][col]);
} else {
min = calculateMinimum(land[row][col - 1], land[row][col + 1], land[row + 1][col]);
}
} else if(row + 1 >= dimension){
if(col - 1 < 0){
min = calculateMinimum(land[row][col + 1], land[row - 1][col]);
} else if(col + 1 >= dimension){
min = calculateMinimum(land[row][col - 1], land[row - 1][col]);
} else {
min = calculateMinimum(land[row][col - 1], land[row][col + 1], land[row - 1][col]);
}
} else {
if(col - 1 < 0){
min = calculateMinimum(land[row][col + 1], land[row - 1][col], land[row + 1][col]);
} else if(col + 1 >= dimension){
min = calculateMinimum(land[row][col - 1], land[row - 1][col], land[row + 1][col]);
} else {
min = calculateMinimum(land[row][col - 1], land[row][col + 1], land[row - 1][col], land[row + 1][col]);
}
}
if(min.value > land[row][col].value){
land[row][col].next = null;
land[row][col].tag = start;
start += 1;
} else {
if(min.next == null){
land[row][col].next = min;
} else {
land[row][col].next = min.next;
}
}
}
}
for(int row = 0; row < dimension; row++){
for(int col = 0; col < dimension; col++){
Result temp = land[row][col];
while(temp.next != null){
temp = temp.next;
}
land[row][col].tag = temp.tag;
}
}
Map<Character, Integer> map = new HashMap<Character, Integer>();
for(int row = 0; row < dimension; row++){
for(int col = 0; col < dimension; col++){
if(map.size() > 0){
if(map.containsKey(land[row][col].tag)){
map.put(land[row][col].tag, map.get(land[row][col].tag) + 1);
} else {
map.put(land[row][col].tag, 1);
}
} else {
map.put(land[row][col].tag, 1);
}
}
}
Collection<Integer> values = map.values();
list = new ArrayList<Integer>(values);
Collections.sort(list);
Collections.reverse(list);
for(Integer i : list){
System.out.print(i + " ");
}
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
dimension = Integer.parseInt(br.readLine());
land = new Result[dimension][dimension];
for(int i = 0; i < dimension; i++){
String line = br.readLine();
int j = 0;
StringTokenizer st = new StringTokenizer(line);
while(st.hasMoreTokens()){
int no = Integer.parseInt(st.nextToken());
//System.out.println(no);
Result temp = new Result(no);
land[i][j] = temp;
j++;
}
j = 0;
}
findBasin();
}
}
/* 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;
}
}
Just to get mailers about this problem :-)
- Nitin Gupta January 29, 2013you can tweak the code to store root value while returning. Its simple
- Nitin Gupta January 28, 2013@komal: see me solution
- Nitin Gupta January 28, 2013Your code have many bugs. Also I think your code will loop infinitely. As both functions are calling each other.
- Nitin Gupta January 26, 2013I guess we have to maintain max-heap of words used in as tags according to their frequency.
- Nitin Gupta January 26, 2013Call below function for each row of matrix
int reverse(int row[])
{
int end = sizeof(row)/sizeof(int) - 1;
int start = 0;
int temp;
while(start < end)
{
temp = row[start];
row[start] = row[end];
row[end] = temp;
start++;
end--;
}
}
int maxHeight(struct node* root)
{
if(root == NULL)
{
return 0;
}
int lHeight = maxHeight(root->left);
int rHeight = maxHeight(root->right);
return (1 + (lHeight > rHeight ? lHeight : rHeight));
}
int max(int a, int b)
{
return (a > b ? a : b);
}
int maxTreeWalk(struct node* root)
{
if(root == NULL)
{
return 0;
}
int lHeight = maxHeight(root->left);
int rHeight = maxHeight(root->right);
int lDiameter = maxTreeWalk(root->left);
int rDiameter = maxTreeWalk(root->right);
return max(lHeight + rHeight + 1, max(lDiameter, rDiameter));
}
His solution is correct.
- Nitin Gupta January 24, 2013@gen-y-s : Thanks for pointing out mistakes. Edited the function again. However 3rd issue is not addressed yet.
I can think of workaround like exiting when we find kthlargest, but that is not recommended using in the program.
Yeah ! Solution is violating rules. But, I could not figure out how to do within restrictions.
@francisco.gutierrez.91: Can you give some idea/hint of your algorithm, so that we can get some direction.
Given List = 1->2->3->4->5->NULL
(I am only showing next pointer here, but you will get the idea)
Step 1 - Push a new node after every node
List - 1->1->2->2->3->3->4->4->5->5->->NULL
(Here first 1 is from old list, second 1 is new node we appended)
Step 2 - Do as following for each node.
node->next->random = node->random->next;
Step 3 - At the end just pop out newly added nodes.
and make old list's last node's next as NULL
Comments Welcome
In any way your code is incorrect.
Figure out why ?
:P
I understood like this :-
If a binary tree is given, convert it into a binary tree where each node is the sum of its childrens.
---------------------------
Input
1
/ \
3 4
/ \
5 6
-------------------------------
Output
18
/ \
11 0
/ \
0 0
@cyrus: I don't know which logic you are following. But only leaf node will become 0 not internal nodes.
Go through my code again for better understanding.
I think we can do it by reverse inorder traversal
/* Function for reverse inorder */
int data;
void revInorder(struct node* root, int kthLargest)
{
static int count = 0;
if(root == NULL)
{
return;
}
revInorder(root->right, kthLargest);
count++;
if(count == kthLargest)
{
data = root->data;
return;
}
revInorder(root->left, kthLargest);
}
int sumUp(struct node* root)
{
if(root == NULL) return 0;
int curr = root->data;
int left = sumUp(root->left);
int right = sumUp(root->right);
root->data = left + right;
return (curr + root->data);
}
I guess we have to build max-heap for getting max selling product.
- Nitin Gupta January 23, 2013Sry, don't know python. Better give algo for your solution, instead of coding it.
- Nitin Gupta January 22, 2013Yes, you are correct. Even question sounds incomplete and can be interpreted in two ways, where other is finding the merging(intersection) point in two list, as the algo given by Anonymous.
This question is ambiguous and better to have discussion with interviewer to clarify a bit. May be interviewer deliberately did not revealed much details hoping that candidate will ask them, just to see his/her problem solving skills.
:-)
@will_in_seattle : Do we need to care about duplicates ?
I guess not. Because while taking intersection or union, the result is a set. As set does not contains duplicates, so there is no need to check for duplicates.
Comments pls
" traverse two lists to check their common data and store them in a new array"
How will you traverse then, traversing will take O(n^2) here in your case. As you have to compare each element of list 1 to each element of list2
The question is not clear itself. First I also thought of same thing.
But the question can be to find intersection of elements.
For. ex. -
List 1 - {14,56,2,78,90}
List 2 - {15,10,56,36,2, 80,65}
We have to return 56 and 2
---------------------
I don't think here we need to find merging point of two list.
If it is so, then your solution is correct.
@yingsun1228 : Why you need sorting ?
1) Make a hashmap/hashset with one list.
2) Now traverse second list and check if hashmap/hashset contains that element. If it contains then print it, otherwise move on.
Yes. log n seems to be impossible....
Simple logic is - you have to visit each node at least once to check for its value.
Why you need extra parameter for base. Its well known that if a number starts with '0x' or 'x', it is hex number and if it starts with '0' it is octal representation of number.
- Nitin Gupta January 18, 2013@limca500ml :- This question is too easy to qualify as Amazon Interview questions. And if the interviewer ask these easy questions then it means they will show no mercy to your solution. So you have to write perfect code. By perfect, I mean no bug, all testcases handled.
Your solution will fail in following condition :-
1.) If string denotes negative number i.e. "-12345".
2.) If string is in hexadecimal i.e. "0xFF" or "xFF".
3.) If string is in octal i.e. "013".
Some other invalid test cases can be.
1.) If string is like "--12"
2.) If string is like "-12-3"
3.) If string is contains only characters "abcde".
4.) If string is null.
P.S. - Also you can handle integer overflow.
Thanks,
Comments are welcome
I think your solution is wrong.
Lets suppose
a[] = {1,9,15}
b[] = {2,5,7}
Here K = 3
So answer should be (1, 7)
While your solution will return (15,7), if I am not wrong.
Oh really sorry, I forgot the condition 0 <= i <= j <= k
We can use this condition to reduce time complexity.
Will update the code later.
Thanks
Sorry for inconvinience
If I am getting question right, you mean that of all the K*K pairs generated by both arrays, where one element is from array A and other element is from array B, we have to find Kth smallest pair.
---------------------------------
(Make maxheap of size K.)
For each pair generated by arrays,calculate a + b,
If a + b is less than top of maxheap then replace it with top and heapify.
else ignore it.
At the end, top of the maxheap will give kth smallest a+b. If you want you can also store index numbers of elements.
Time Complexity - O(n*n logn)
Space Complexity - O(k)
The idea is to check for each given node in tree about whether it lies left or right of a given node.
-------------------------------------------------------------------------
struct node{
int data;
struct node* left;
struct node* right;
};
int isInTree(struct node* root, int node)
{
if(root == NULL)
{
return 0;
}
if(root->data == node)
{
return 1;
}
return (isInTree(root->left, node) || isInTree(root->right, node));
}
int findLCA(struct node* root, int node1, int node2)
{
if(root == NULL)
{
return 0;
}
int isNode1InLeft = isInTree(root->left, node1);
int isNode2InLeft = isInTree(root->left, node2);
if(isNode1InLeft != isNode2InLeft)
{
return root;
}
return (isNode1InLeft ? findLCA(root->left, node1, node2) : findLCA(root->right, node1, node2));
}
your answer is correct
- Nitin Gupta January 15, 2013@anish and @gocool:-
Question clearly says that exactly one integer occurs odd number of times.
@anish and @gocool: All three integers in your test case occurred odd number of times.
As it seems to me, question itself is ambiguous. What is meant by first 100 large numbers. As per my understanding, it should be find 100 large numbers.
So we can create min heap of 100 elements size. As soon you receive number from the stream, put it in heap and heapify.
XOR all numbers.
Result is the required number
Make min heap of 100 elements.
Whenever new incoming number is less than the top of heap ignore it.
Otherwise replace top with this new number and bubble down this number to its correct position by calling heapify.
Yes, you are correct. This problem is similar to coin change problem, where we have unlimited supply of coins of value 1, 2, 3 and we have to find total number of ways to make sum as 'n'.
First thought that came to my mind
:-)
me too :-)
- Nitin Gupta January 04, 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 ...
I think it would be top-down only. I will post my solution after sometime.
- Nitin Gupta February 16, 2013