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
Its Dutch national flag problem.
void sort(int *arr, int len) {
int low, mid, high;
for(low = mid = 0, high = len - 1; mid < high; ) {
arr[mid] == 1 ? swap(&arr[mid++], arr[low++]) : arr[mid] == 2 ? mid++ : swap(&arr[mid], &arr[high--]);
}
}
Sorry, I didn't understand you. What do you want to say.
- Nitin Gupta May 16, 2013void arrange(int array[]){
int len = sizeof(array)/ sizeof(array[0]);
int low, mid;
for(low = mid = 0; mid < len; ) {
array[mid] == 0 ? swap(&array[low++], &array[mid++]) : mid++;
}
}
It is bad answer. You are using extra memory. What if you have to do that in-place.
See my answer below
Guys, What's the fuss ??
Check my solution below...upvote it.
:-)
I think you have to use min priority queue or min heap.
- Nitin Gupta May 15, 2013Find the 3 largest number in array viz. n1 > n2 > n3 and 2 smallest number in array viz m1 < m2.
The largest product will be either n1 * n2 * n3 or n1 * m1 * m2
Take care of 0
This is tree diameter problem.
Idea is max distance will be in left subtree or in right subtree or it will pass through root.
We can do it recursively.
int height(struct node* root) {
if(root == NULL) {
return 0;
}
int leftHeight = height(root->left);
int rightHeight = height(root->right);
if(leftHeight > rightHeight) {
return leftHeight + 1;
} else {
return rightHeight + 1;
}
}
int diameter(struct node* root) {
if(root == NULL) {
return 0;
}
int lHeight = height(root->left);
int rHeight = height(root->right);
int lDiameter = diameter(root->left);
int rDiameter = diameter(root->right);
return max(lHeight + rHeight + 1, max(lDiameter, rDiameter));
}
@eugene.yaravoi :- In my initial days, I never cared about integer overflow condition. My sole purpose used to be just solve the problem. So, yes I also had made this mistake in my college days. But, later on, I learned that overflow cases can occur. So, now I've become more attentive on these kind of details also.
@ gunsnroses23k :- You should never calculate mid like above.
Consider a scenario where low = 5, high = 7.
Note that these are numerals above are representing index of array not elements of array.
Ideally - our mid should be index no 6
But according to your code, it would be 1, which is wrong.
Now you can calculate mid like this
mid = (low + high) / 2
You will get correct answer which is 6. But this can fail when the sum of low and high exceeds the integer limit defined for that data type in that language.
So, the correct way is
mid = low + (high - low) / 2
Ya it is integer overflow case.
Instead one should do like
low + (high - low) / 2
Because it is a straight Binary Search question which is basic algorithm that first year students study in their college and a company of eBay's repute asking it, without any twist in words or twist in application of binary search.
So, I was shocked.
Are you joking ???
Ebay asked this question ???
Though questions does not seems clear to me. I assume that you want to convert one string to another by rotating it.
In this case append first string with itself and find index of start of the second string in it. That is the no of shifts required.
@eugene.yarovoi: In worst case it will be O(n), but in average case it will be O(log n).
- Nitin Gupta May 04, 2013It would be fun, if the problem would have been like this
A[1] <= A[2] <= ..... <= A[n]
Then it would have become more complex because of duplicates.
/* This function returns the leftmost child of nodes at the same level as p.
This function is used to getNExt right of p's right child
If right child of is NULL then this can also be sued for the left child */
struct node *getNextRight(struct node *p)
{
struct node *temp = p->nextRight;
/* Traverse nodes at p's level and find and return
the first node's first child */
while (temp != NULL)
{
if (temp->left != NULL)
return temp->left;
if (temp->right != NULL)
return temp->right;
temp = temp->nextRight;
}
// If all the nodes at p's level are leaf nodes then return NULL
return NULL;
}
/* Sets nextRight of all nodes of a tree with root as p */
void connect(struct node* p)
{
struct node *temp;
if (!p)
return;
// Set nextRight for root
p->nextRight = NULL;
// set nextRight of all levels one by one
while (p != NULL)
{
struct node *q = p;
/* Connect all childrem nodes of p and children nodes of all other nodes
at same level as p */
while (q != NULL)
{
// Set the nextRight pointer for p's left child
if (q->left)
{
// If q has right child, then right child is nextRight of
// p and we also need to set nextRight of right child
if (q->right)
q->left->nextRight = q->right;
else
q->left->nextRight = getNextRight(q);
}
if (q->right)
q->right->nextRight = getNextRight(q);
// Set nextRight for other nodes in pre order fashion
q = q->nextRight;
}
// start from the first node of next level
if (p->left)
p = p->left;
else if (p->right)
p = p->right;
else
p = getNextRight(p);
}
}
I think function will take only 'A' and 'N' as input. If this is the case then it is simple.
Sort the Array [O(nlogn)]
Put one pointer at the beginning and one pointer at the end.
Now add cubes of two numbers pointed by two pointers.
If sum is greater than 'A', then move last pointer one step towards left side.
If sum is smaller than 'A', then move first pointer one step towards right side.
Otherwise, you will have one pair.
But my concern is there will only be one pair if all numbers are positive as given in question.
bool match(char *first, char * second)
{
// If we reach at the end of both strings, we are done
if (*first == '\0' && *second == '\0')
return true;
// Make sure that the characters after '*' are present in second string.
// This function assumes that the first string will not contain two
// consecutive '*'
if (*first == '*' && *(first+1) != '\0' && *second == '\0')
return false;
// If the first string contains '?', or current characters of both
// strings match
if (*first == '?' || *first == *second)
return match(first+1, second+1);
// If there is *, then there are two possibilities
// a) We consider current character of second string
// b) We ignore current character of second string.
if (*first == '*')
return match(first+1, second) || match(first, second+1);
return false;
}
There is recursion in method2.
- Nitin Gupta April 20, 2013@Neha: You are wrong. Integer is of 4 bytes. So it can hold upto 32 bit info.
- Nitin Gupta April 15, 2013@hraha123: And still you made mistake. Find and correct it.
- Nitin Gupta April 09, 2013KMP
- Nitin Gupta March 21, 2013In case of two missing numbers, you are taking product. I think it is wrong as it will produce wrong result if our final product goes out of bound of integers. (Integer Overflow)
- Nitin Gupta March 21, 2013void print(int N)
{
int arr[N];
arr[0] = 1;
int i = 0, j = 0, k = 1;
int numJ, numI;
int num;
for(int count = 1; count < N; )
{
numI = arr[i] * 2;
numJ = arr[j] * 5;
if(numI < numJ)
{
num = numI;
i++;
}
else
{
num = numJ;
j++;
}
if(num > arr[k-1])
{
arr[k] = num;
k++;
count++;
}
}
for(int counter = 0; counter < N; counter++)
{
printf("%d ", arr[counter]);
}
}
Above answer is posted by me.
- Nitin Gupta March 20, 2013Ok.
If you look closely then you can see that, we are adding and removing each element in the deque, exactly once. So, it will be O(n)
The element which is repeated more than half times is also called as majority element which can be found by Moore's Voting algorithm.
This is a two step process.
1. Get an element occurring most of the time in the array. This phase will make sure that if there is a majority element then it will return that only.
2. Check if the element obtained from above step is majority element.
------------------------------------------------------------------------------------------------
/* Function to find the candidate for Majority */
int findCandidate(int a[], int size)
{
int maj_index = 0, count = 1;
int i;
for(i = 1; i < size; i++)
{
if(a[maj_index] == a[i])
count++;
else
count--;
if(count == 0)
{
maj_index = i;
count = 1;
}
}
return a[maj_index];
}
/* Function to check if the candidate occurs more than n/2 times */
bool isMajority(int a[], int size, int cand)
{
int i, count = 0;
for (i = 0; i < size; i++)
if(a[i] == cand)
count++;
if (count > size/2)
return 1;
else
return 0;
}
I do not think that there is any complex thing to explain in my code.
I am using a deque whose front will always contain maximum element.
First I am putting first K element's index in my deque along with the condition such that, If coming element is less than last element of deque then there is no need to store its index.
Then in second while loop, I am checking if current maximum goes out of the window or not.
Third while loop is similar to first one.
I don't know what is difficult to understand in this code. People wants everything to be served to them ready to eat. Please apply your mind to understand the code by running over some example. This is how you will grow.
Downvoting just for fun is not good for such a great platform provided to us.
Why my answer is downvoted?
- Nitin Gupta March 19, 2013This can be done in O(n) using a deque whose front will always hold maximum in current window. Space Complexity - O(k)
------------------------------------------------------------------------------------------------------------
void maxInWindow(int* arr, int k)
{
std::deque<int> Qi(k);
int i;
for(i = 0; i < k; i++)
{
while(!Qi.empty() && arr[i] >= arr[Qi.back()])
{
Qi.pop_back();
}
Qi.push_back(i);
}
for( ; i < length; i++)
{
std::cout << arr[Qi.front()] << std::endl;
while(!Qi.empty() && i - k >= Qi.front())
{
Qi.pop_front();
}
while(!Qi.empty() && arr[i] >= arr[Qi.back()])
{
Qi.pop_back();
}
Qi.push_back(i);
}
std::cout << arr[Qi.front()] << std::endl;
}
Is it not a deadlock problem.
Use Banker's Algorithm. It does exactly this thing
Its time complexity is exponential.
Also if I am understanding your logic, there is one bug.
Second instance of "part_sum += a[cur];"
should not be there.
Who said to remove constants. Use look up table.
- Nitin Gupta March 14, 2013Time complexity can be reduced.
Yes the problem is different but it can be modified.
www[dot]geeksforgeeks[dot]org/tug-of-war/
- Nitin Gupta March 14, 2013:)
- Nitin Gupta March 09, 2013Trick is to start from end.
- Nitin Gupta March 09, 2013KMP
- Nitin Gupta March 06, 2013So you started reading cracking the coding interview :P
- Nitin Gupta March 05, 2013The trick is to start from the end.
- Nitin Gupta March 04, 2013We have to return level with maximum number of node. In other words we have to find width of the tree. Traverse the tree in pre-order fashion.
int getMax(int count[], int n)
{
int max = arr[0];
int i;
for (i = 0; i < n; i++)
{
if (arr[i] > max)
max = arr[i];
}
return max;
}
int getMaxWidthRecur(struct node* root, count, level)
{
if(root == NULL)
{
return 0;
}
count[level]++;
getMaxWidthRecur(root->left, count, level + 1);
getMaxWidthRecur(root->right, count, level + 1);
}
int getMaxWidth(struct node* root)
{
int height = getHeight(root);
int* count = (int *) calloc(sizeof(int), height);
int level = 0;
getMaxWidthRecur(root, count, level);
return getMax(count, height);
}
@beg: Total no of paths will be stored in our static variable total_ways.
- Nitin Gupta February 18, 2013It can be solved with dynamic programming. Assuming that you can move either right or down which can be a good point to discuss with interviewer. Also this is recursive solution.
Suppose you are at position N, M you can come to it either by N-1, M or by N, M-1. This way we can work upwards to find total no of ways.
static int total_ways = 0;
class Point{
int x,
int y,
Point(int a, int b)
{
x = a;
y = b;
}
boolean getPath(int x, int y, ArrayList<Point> path, Hashtable<Point, Boolean> cache)
{
Point p = new Point(x, y);
if(cache.containsKey(p))
{
return cache.get(p);
}
path.add(p);
if(x == 0 && y == 0)
{
total_ways++;
return true;
}
boolean success = false;
if(x >= 1 && isFree(x - 1, y)
{
success = getPath(x - 1, y, path, cache);
}
if(!success && y >= 1 && isFree(x, y - 1))
{
success = getPath(x, y - 1, path, cache);
}
if(!success)
{
path.remove(p);
}
cache.put(path, success);
return success;
}
Its a knapsack problem where we have to minimize value instead of maximizing it.
0-1 knapsack problem - If it is mandatory to pick all books of given price.
Fractional knapsack problem - If it is allowed to pick any quantity of books of given price.
This is very good point to discuss with your interviewer.
This can be done using quick sort.
Randomly pick one player (A) then place players who lost to A at right hand side and players who won to A at left hand side.
Repeat above step. At the end we will get the result.
Comments welcome
/* Given a stream of numbers and index, find the digit at that index
* e.g. 01234567891011121314 index = 15, answer is 1 (of 12)
*/
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<math.h>
/* Function to find number of digits */
int findNoOfDigits(int* index)
{
int no_of_digits = 1;
if(*index <= 10)
{
return no_of_digits;
}
int num = 90;
int temp = *index - 10;
*index = temp;
while(temp > 0)
{
no_of_digits++;
temp -= (num * no_of_digits);
if(temp < 0)
{
break;
}
*index = temp;
num *= 10;
}
return no_of_digits;
}
/* Function to find value at some position */
int position(int index)
{
int no_of_digits = findNoOfDigits(&index);
printf("%d %d\n", no_of_digits, index);
if(no_of_digits == 1)
{
return index - 1;
}
else
{
int temp = no_of_digits - 1;
int num = pow(10, temp);
int rem = index % no_of_digits;
int quotient = index / no_of_digits;
num += quotient;
if(rem == 0)
{
return (num % 10);
}
else
{
int digit;
int count = no_of_digits + 1 - rem;
while(count > 0)
{
count--;
digit = num % 10;
num = num / 10;
}
return digit;
}
}
}
/* Main driver function */
int main(void)
{
int index;
scanf("%d", &index);
printf("\n");
printf("%d",position(index));
getch();
return 0;
}
Can you explain the logic ?
- Nitin Gupta February 16, 2013How about using KMP for each pattern.
- Nitin Gupta February 16, 2013If the path can start anywhere. In that case, we can make a small modification. On every node, we look up to see if we have found the sum.
When we recurse through each node n, we pass the functin the full path from root to n.This function then adds the nodes along the path in reverse order from n to root. When the sum of each subpath equals sum, then we print the path.
void findSumUtil(Treenode node, int sum, int[] path, int level)
{
if(node == null)
{
return;
}
path[level] = node.data;
int t = 0;
for(int i = level; i >= 0; i--)
{
t += path[i];
if(t == sum)
{
print(path, i, level);
}
findSumUtil(node.left, sum, path, level + 1);
findSumUtil(node.right, sum, path, level + 1);
path[level] = Integer.MIN_VALUE;
}
void findSum(Treenode node, int sum)
{
int depth = depth(node);
int[] path = new int[depth];
findSumUtil(node, sum, path, 0);
}
void print(int[] path, int start; int end)
{
for(int i = start; i <= end; i++)
{
printf("%d ", path[i]);
}
}
int depth(Treenode node)
{
if(node == NULL)
{
return 0;
}
else
{
return (1 + Math.max(depth(node.left), depth(node.right));
}
}
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 ...
So, what is problem in my code?
- Nitin Gupta May 24, 2013