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
In telephonic interview, there is enough time for 3 questions to be answered including code for an above average candidate.
- Nitin Gupta November 08, 2012Map<String, String> memoized;
String SegmentString(String input, Set<String> dict) {
if (dict.isWord(input)) return input;
if (memoized.containsKey(input) {
return memoized.get(input);
}
int len = input.length();
for (int i = 1; i < len; i++) {
String prefix = input.substring(0, i);
if (dict.isWord(prefix)) {
String suffix = input.substring(i, len);
String segSuffix = SegmentString(suffix, dict);
if (segSuffix != null) {
return prefix + " " + segSuffix;
}
}
memoized.put(input, null);
return null;
}
Time complexity : O(n^2) Supposing that substring operation only requires constant time.
- Nitin Gupta November 08, 2012@anish: I think you are wrong. How it will skip if condition which is checking for > 20 for the first time.
- Nitin Gupta November 05, 2012@anish: Ok lets walk through the code.
Call McNuggets(33)
Then it will substract 20 from it.
Call McNuggets(13)
Then it will substract 9 from it.
Call McNuggets(4)
Then it will return false.
@anish : I think you replied on wrong post. See for which solution I commented.
- Nitin Gupta November 05, 2012I think that's what Bucket Sort does.
- Nitin Gupta November 04, 2012@anish : I can still see that it is failing for 33. Check once again.
- Nitin Gupta November 04, 2012@Vinod: Why are you posting without running some test cases on your code. Your code fails for even basic cases leave trickier cases aside.
Check your code with n = 33 (20*0 + 9*3 + 6*1)
I think this problem is similar to Minimum Coin Problem. Given set of coin values. Find minimum no of coins required for a sum. This can be solved easily by dynamic programming.
Code goes like this.
int min(int n)
{
int packages[] = {1,9,20};
int size = sizeof(packages)/ sizeof(int);
int sum[n+1] = {INT_MAX};
for(int sum_counter = 1; sum_counter < n+1; sum_counter++)
{
for(int coin_counter = 0; coin_counter < size; coin_counter++)
{
if(packages[coin_counter] <= sum_counter &&
sum[sum_counter - packages[coin_counter]] < sum[sum_counter])
{
sum[sum_counter] = sum[sum_counter - packages[coin_counter]] + 1;
}
}
}
return sum[n];
}
The above code is is for Minimum Coin problem. We have to modify it to handle case where it is not possible and also I have replaced 6 by 1 so that index does not goes out of bound for above program.
Its 12 am. Feeling sleepy.
Just Give a thought to this approach.
Tell me if I am wrong.
This was my answer. He was satisfied with this.
int convert(int x)
{
int c = n;
c = c << 8 | n;
c = c << 16 | c;
return c;
}
This problem can be easily solved by slightly modifying "Largest Area of Histogram problem".
- Nitin Gupta November 02, 2012What if there is a constraint that we cannot modify original link list. Its always better not to modify original data as far as possible.
- Nitin Gupta November 02, 2012@sastry.soft - Its simple, for each node we are checking data of all subsequent nodes (see two while loops) hence complexity is O9n^2).
But if we go deeper and link list contains many duplicates then the size of link list will be decremented each time and complexity will be less than O(n^2).
But in worst case i.e. there are no duplicates it will be O(n^2)
If we are allowed to use extra space then we can use hashmap. This way it is simple on pass traversal.
Time Complexity = O(n)
Space Complexity = O(n)
----------------------------------------------------------
Without using any extra space.
Time Complexity = O(n^2)
Space Complexity = O(1)
struct node * removeDuplicates(struct node * head)
{
struct node* slow = head, fast;
while(slow != NULL)
{
fast = slow;
while(fast->next != NULL)
{
if(slow->data == fast.next.data)
{
fast->next = fast->next->next;
}
else
{
fast = fast->next;
}
}
slow = slow->next;
}
return head;
}
@Anonymous: Your solution does not work. Check this...
If Matrix is
1 4
6 2
5 3
Then
rows = {1,0,0}
cols = {1,0}
and your condition check fails.
Rope is best DS. Refer to wikipedia article.
- Nitin Gupta October 29, 2012ok. Dou you work or student ??
- Nitin Gupta October 29, 2012@eugene: you also contested there ??
- Nitin Gupta October 29, 2012@rs :- This is interview street codesprint question.
- Nitin Gupta October 29, 2012In one of my comment, I have written that I asked interviewer that whether co-ordinates of points are given or not. He said NO. So we can't use this approach.
- Nitin Gupta October 09, 2012@Anonymous :- From where did you get this idea "in cuboid all sides are equal". I learnt this property for cubes only. Anyway, I asked interviewer if co-ordinates are given or not. He told me nothing is given. If co-ordinates along with length,breadth and hight of cuboid would have been given then no need to use 6 pointers here, we can traverse simply by comparing co-ordinates moving accordingly.
Comments please.
I thought it as graph problem. Can you explain a bit more ?
- Nitin Gupta October 08, 2012I asked him whether x,y,z co-ordinates of vertex are given or not. He told nothing is given.
Anyway I came up with this data structure (6-ary tree like).
struct node{
int point[3];
struct node* east;
struct node* west;
struct node* north;
struct node* south;
struct node* top;
struct node* bottom;
}
Then told him that to search for a node we can do BFS. However he was not satisfied. He was asking me to improve it.
I could not come up with better DS.
What I was lacking ??
@tom.thkwok - I think i got your point this algo will return same no if input is itself palindrome..so instead of checking for <= check only for < and handle = case differently.
Case 1 - if number is of even length
If R = reverse of L. Increment L by 1. R = reverse of L. Print no.
Case 2 - If number is of odd length
If R = reverse of L.
If M < 9
Increment M. Print no.
else
M = 0, Increment L by 1. R = reverse of L. Print no.
----------------------
But interviewer did not present this counter example and at that time it did not came up in my mind. He was giving no hint of what he wanted and where I was wrong. At least one counter example would have served better.
I think here interviewer is not talking in conventional sense...3 and 2 are adjacent, 3 & 4 are not adjacent.
@DashDash- is this interview question ?? I also gave interview of Adobe at bangalore for Live cycle team.
My Interviewer was dumb as few months back someone posted same experience with some Adobe interviewer.
------------------------------
Regarding question - I think that this question is either very easy because if array only has positive numbers. Then only 2 sub-arrays we have to compare. One is, sum for all the elements at odd position and other is, sum for all the elements at even position. If adjacent here does not mean in conventional sense.
I did this algo -
Case 1 - Number length is even
Step 1 - Divide number in two equal halfs. Call left one as L, right one as R.
Step 2 - Check if R <= reverse of L. If it is put R = reverse of L. Print number
Step 3 - else if R > reverse of L. Increment L by 1. Make R = reverse of L. Print number.
Case 2 - Number is of odd length
Step 1 - Divide number in 3 parts call them as L (Left), M (Middle), R (Right) . M will always have single integer.
Step 2 - Check if R is <= reverse of L. Make R = reverse of L. Print number.
Step 3 - else if R > reverse of L.
Step 4 - check if M < 9
Step 5 - M++. Make R = reverse of L. Print number.
Step 6 - else Make M = 0, Increment L by 1. Make R = reverse of L. Print number.
---------------------------------------
But interviewer seems to be un-satisfied. What is wrong in this algo. I could not find anything wrong in this.
@Susheel - I think you are wrong. Even if two rectangles have same x1 and x2, they can still be non-intersecting based on their y co-ordinate.
For ex.
Rectangles with bottom left (BL) and top right (TR) co-ordinate.
Rectangle 1 - BL = (3,1) TR = (6,4)
Rectangle 2 - BL = (3, 5) TR = (6, 8)
As you see both rectangles have same x co-ordinates but still if you draw them on cartesian-plane, they will be non-intersecting.
Why everybody is assuming that there are only 2 rectangles already drawn on the screen.
- Nitin Gupta October 06, 2012I don't know python, so finding it difficult to understand. Can you transform it in c,c++ or java....
- Nitin Gupta October 06, 2012I cannot figure out how can we determine the correct half order by just comparing it with first and last element of that half.
- Nitin Gupta October 05, 2012Sivabasava - Can you explain your algorithm ?
- Nitin Gupta October 05, 2012Explain a bit more
- Nitin Gupta October 05, 2012First look says it will not work.
Explain a more with some example.
I don't think normal Binary search will work in this case either you have to modify it or you cannot use binary search(simple one).
Can you explain your methodology ??
Pivot is first element of array
- Nitin Gupta October 05, 2012Question continued :-
For example if in a particular order, the teams appeared as T1, T2, T3, T4 … then team T1 had lost to T2, T2 had lost to T3, and T3 had lost to T4… It may be possible that T3 lost to T1 .. but that need not be taken into consideration while writing the order. Only the neighboring elements should be such that the element on the left has lost to the element on the right.
How will you write the teams in this order? Write a code for it
Make all the necessary assumptions you need to solve the problem.
@Vitlay - was it asked in tech interview ??
I hv given written of Adobe for MTS on 25th Aug. Still got no result of that. Mailed them twice. One out of office reply came from HR mentioning "University recruiting is keeping me busy. Please expect a delay in reply."
Do Adobe informs about result, if candidate could not clear it ??
@Anonymous: Yes, he looks like amateur, seeing his code and his algo.
- Nitin Gupta September 05, 2012string largestPal(string input_str)
{
string isPal = "";
string largest = "";
int j, k;
for(int i = 0; i < input_str.length() - 1; ++i)
{
k = i + 1;
j = i - 1;
// starting a new interation
// check to see if even pal
if(j >= 0 && k < input_str.length()) {
if(input_str[i] == input_str[j])
j--;
else if(input_str[i] == input_str[j]) {
k++;
}
}
while(j >= 0 && k < input_str.length())
{
if(input_str[j] != input_str[k])
break;
else
{
j--;
k++;
}
isPal = input_str.substr(j + 1, k - j - 1);
if(isPal.length() > largest.length()) {
largest = isPal;
}
}
}
return largest;
}
Sum of two bits can be obtained by performing XOR (^) of the two bits. Carry bit can be obtained by performing AND (&) of two bits.
Above is simple Half Adder logic that can be used to add 2 single bits. We can extend this logic for integers. If x and y don’t have set bits at same position(s), then bitwise XOR (^) of x and y gives the sum of x and y. To incorporate common set bits also, bitwise AND (&) is used. Bitwise AND of x and y gives all carry bits. We calculate (x & y) << 1 and add it to x ^ y to get the required result.
#include<stdio.h>
int Add(int x, int y)
{
// Iterate till there is no carry
while (y != 0)
{
// carry now contains common set bits of x and y
int carry = x & y;
// Sum of bits of x and y where at least one of the bits is not set
x = x ^ y;
// Carry is shifted by one so that adding it to x gives the required sum
y = carry << 1;
}
return x;
}
int main()
{
printf("%d", Add(15, 32));
return 0;
}
Following is recursive implementation for the same approach.
int Add(int x, int y)
{
if (y == 0)
return x;
else
return Add( x ^ y, (x & y) << 1);
}
Not in any company. It is programming challenge on interview street.
- Nitin Gupta August 21, 2012Why ? We have to minimize no of candies and question only says about higher rating nothing about equal and less rating.
P.S. - I have solved it. Its accepted :-)
No.
These are ratings of student which can be same. I have taken above example. First read the question carefully, then you will get it. I can't understand where I have given NULL candy to some student.
@Shivam Maharshi : Again read the example test case.
Candies are given as follows:
1 - 1
2 - 2
2 - 1
Hope it clarifies your confusion
@Sandeep : 2nd test case is failing for my code.
My algo : I am counting total length of decreasing ratings till some greater rating is encountered. Then doing sum to n terms where n will be decreasinglength.
Can u find out error in my code. Thanks for the help
#include<stdio.h>
int main(void)
{
int totalCandies = 0;
int lastGivenCandy = 0;
int noOfStudents;
int decreasingLength = 0;
int rating1 = -100, rating2 = -101, flag = 0;
scanf("%d", &noOfStudents);
while(noOfStudents > 0)
{
if(flag == 0)
{
scanf("%d", &rating2);
noOfStudents--;
}
if(rating1 < 0)
{
lastGivenCandy = 1;
totalCandies += lastGivenCandy;
decreasingLength = 1;
flag = 1;
}
do
{
if(flag == 2)
{
rating1 = rating2;
scanf("%d", &rating2);
noOfStudents--;
if(rating2 > rating1)
{
if(decreasingLength > 1)
{
if(lastGivenCandy > decreasingLength)
{
decreasingLength -= 1;
}
else
{
totalCandies -= lastGivenCandy;
}
totalCandies += ((decreasingLength * (decreasingLength + 1)) / 2);
lastGivenCandy = 1;
}
lastGivenCandy++;
totalCandies += lastGivenCandy;
decreasingLength = 1;
}
else
{
decreasingLength++;
}
}
}while(rating2 <= rating1 && noOfStudents > 0);
rating1 = rating2;
flag = 2;
if(decreasingLength > 1)
{
if(lastGivenCandy > decreasingLength)
{
decreasingLength -= 1;
}
else
{
totalCandies -= lastGivenCandy;
}
totalCandies += ((decreasingLength * (decreasingLength + 1)) / 2);
lastGivenCandy = 1;
}
}
printf("%d",totalCandies);
return 0;
}
Anonymous : This problem is not part of any ongoing contest. This is just a practice problem at interview street.
- Nitin Gupta August 15, 2012@All : Guys I don't think that sorting and then distributing will give correct answer. Consider following example.
4,3,4 - requires 5 (2+1+2) candies.
As you have said after sorting
3,4,4 - It requires 4 (1+2+1) candies.
The correct answer is 5.
I think this problem can only be solved by using recursion or dynamic programming.
Malluce - You cannot change order of students as you will get wrong result.
Ex :
4,3,4 - requires 5 (2+1+2) candies.
As you have said after sorting
3,4,4 - It requires 4 (1+2+1) candies.
The correct answer is 5.
Malluce - For sorting it would require space to store all the students' ratings. As you know N can be 10^5. I think there should be more efficient code if we use Dynamic Programming.
- Nitin Gupta August 15, 2012
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 ...
@Anoymous: You seems correct.
- Nitin Gupta November 08, 2012