CareerCup

Hi,

I recently attended a walk-in for Software development Engineer (SDE- 1) at Amazon, Bangalore.
Here is my experience of Amazon interview.
As I was from the same city, there was no phone interview. I have listed down all questions that I remember.
Round 1: Data Structures, Algorithms and coding (1 hour)
Interviewer just started off with questions without introduction and stuff.
1) Given a singly linked list, swap every 2 nodes, for odd number of input; retain the last node as it is.
Eg: Input: 5 13 15 18 20 11 6 7
Output: 13 5 18 15 11 20 7 6
I was asked to write the code straight-away.
Wrote the same, verified boundary cases and discussed.

2) Given a binary search tree, find the number of pairs where sum of 2 nodes’ values equal to k
Eg:
1
2 3
4 5 7
Say k=7, output =2 ( 2+5, 3+4)
Suggested an approach where I’d use inorder traversal of this,
Then interviewer asked me to solve the simplified problem, find k in sorted array instead of tree.
Got solution for this one, to have 2 pointers at each end, and traverse accordingly.
I was asked the approach for extending same to BST.
Then, I implemented the same for BST using stack.

Round 2: Data Structures, Algorithms and coding (1 hour)
1) Given input as k sorted array, generate a single sorted list as output.
Eg:
Array1: 1 5 8 9 11 ….
Array2: 2 12 24 44 …..
.
.
Array k: 3 15 79 115 ….
Output: Array1: 1 2 3 5 8 9 11 12 15 ….
Discussed the approach, and complexity, then wrote the code for the same.

2) Given a function isGreater, compare user defined objects and then return the object that is greater than all other objects.
Twist: obj1 > obj2 and obj2 > obj3 does not mean obj1>obj3
I asked for the use case for the same, as I was not convinced with the problem.
He gave an example of games/ 1 team winning another.
Discussed the approach and then wrote the code.

3) Given an input sentence, output the non repeated words in the sentence.

4) How are maps implemented?
Interviewer then clarified my questions about Amazon.
Both first and second rounds were at similar difficulty level.
If the interview feedback was bad for any of these, the candidate was eliminated. If at least 1 of these went well and other “not sure”, then too candidate is called for next rounds.


Round 3: Hiring Manager round (1 hour 40 minutes)

Discussed on my current roles and responsibilities
why do you want to join to Amazon?
What are your accomplishments in your role so far?
What are the things that you’re not good at and need to improve?
Serialization of Binary tree. Given 1 traversal is it possible to re-construct the binary tree.
Write code to reconstruct the tree given any 2 traversals.
I took in-order and post-order traversal, discussed the approach and wrote recursive solution.
Was then asked the approach for iterative.
Round4: Culture Fit Round
This surprisingly had a data structure question first.

1) Given a n (large number) lists of customers who visited n webpages on n (large number) days, design a data structure to get customers who have visited the website on exactly "k" days and should have visited at least "m" distinct pages altogether.
Was then asked to improvise the solution as much as possible

2) Details on my previous project and job profile

3) Challenging situation faced

4) Why should we hire you?
Then, he answered some of my questions.


Round5: Coding, Algorithm and data structures (Technical round with a senior developer )
Started with questions straight away

1) Least common ancestor of a binary tree (Solution and Code)

2) Given a 2 dimensional array sorted vertically and horizontally, search for an element and return true if the element is present. (Algorithm, Code and Complexity)
Example
1 5 13 29
11 16 25 38
45 49 52 57
51 54 59 66

3) Something on count sort.

4) Print binary tree in zig-zag order..

5) Gold box problem (Approach)
There are ‘n’ gold boxes placed in a row, each having different number of gold coins.
2 players play a game, where the motive is to collect the maximum number of gold coins. Each player can see how many coins are present in each box, but can get a box from either end only, on his turn.
Design a strategy such that Player1 wins (Assuming both players play smartly)

I got the hiring call after couple of days, after my last round of interview. They said feedback was very positive and they’re happy to hire me.

------------------------------------------------------------------
The books “Cracking the Coding interview” and “The Google Resume” are written very well and helped in my preparation for the interview. Thank you CareerCup !!

Did any of you attempt an online test given by Amazon for SDE/SDET position here in US?
If yes, then how was the test? What should I prepare before attempting the test?

can anyone give one test case which my program give wrong answer my code http://ideone.com/psN07u.
this code find two disjoint subarray and their maximum difference.

How to read a large file efficiently in java ?

Dear Student programmers,

Enter the OGC Student Map App Challenge!

Last month the not-for-profit Open Geospatial Consortium announced (http://www.opengeospatial.org/pressroom/pressreleases/1816) the OGC Student Map App Challenge, sponsored by Google, an OGC Principal Member. This is a programming contest for students who have programming skills and an interest in maps and location services. We are now making a last call for registrations, which are due by June 15. See registration details at http://appchallenge.opengeospatial.org/rules.html. Apps are to be submitted by July 15, 2013.

Awards include a Nexus tablet, an all expenses paid trip to an OGC Technical Committee (TC) meeting in a distant city (Frascati, Italy in September; Bombay, India in December; or a 2014 location to be announced soon) and a two-year OGC membership (http://www.opengeospatial.org/ogc/join/value) for your college or university.

Register now and become part of the exciting international OGC community that's making "where" information in integral part of the global Internet!


Thank you!

Hi guys
Can someone help me with the current Market compensation for a Tech Lead (Mainframe) with 5.5 years of experience with a MNC ?

I want to know if I am getting underpaid.

Thanks !

We are conducting a Hiring Event in Hyderabad at the earliest. Interested!! - Do drop in your CVs ASAP to avecdce@gmai.com

Responsibilities
The Acrobat product development team identifies key product imperatives, conceptualizes compelling document solutions and delivers the capability in newer Acrobat and Reader releases.

As a part of this team, you will work on newer Acrobat / Reader releases on the desktop or on Acrobat integration with SaaS services or on Windows Store Apps, and work on areas such as:
Build the next generation of document creation tools
Design and build next generation of document processing tools to extract, index and search document content
Develop advanced document reconstruction algorithms for document editing, PDF Export
Develop document and image processing algorithms for creating next generation of document scanning and OCR tools
Develop next generation of intuitive and powerful document reviews, commenting and approval solutions
Develop new document protection and signing technologies
Work on Windows Store apps for Adobe PDF workflows
Architect and implement application sandboxing techniques by leveraging Windows security model and implementing processes that execute within very restrictive environments
Develop new frameworks that integrate desktop applications with SaaS services, all mostly architected cross-platform to work on multiple platforms, on devices and as services as a part of this award-winning product suite.
Requirements
1 - 8 years of hands on design / development experience
B.Tech / M.tech in computer science and engineering from a premier institute
Good understanding of object oriented design and knowledge of product life cycles and associated issues
Technical depth in operating systems, computer architecture and OS internals
Proficient in C++, data structures and algorithms
Solid programming/debugging/troubleshooting skills in system / application level
Skills in analyzing software performance and benchmarking.
Ability to work independently with strong problem solving skills
Knowledge of product life cycles is a plus

. How many comparisons are required to sort an array of length 5 if a straight selection sort is used and the array is already sorted in the opposite order?
a)0
b)1
c)15
d)20

Adobe India is hiring :
1. Engineering “Developer” positions (C/C++, Java)
2. Member Technical staff and Computer Scientists with 1 to 8 years of experience in product development with B. Tech / M. Tech in Computer Science & Engineering from a premier institute
What we need :
- B. Tech / M. Tech in Computer Science & Engineering from a premier institute.
- Minimum 1 to 8 years of hands on design / development experience.
- Excellent Credentials / Product Development Exposure.
- Good understanding of object oriented design and knowledge of product life cycles and associated issues.- Knowledge of application development on multiple platforms including various flavors of Windows and Mac.
- Should have excellent computer science fundamentals and a good understanding of architecture, design and performance.
- Must have excellent written and verbal communication skills.
Mail To: avecdce@gmail.com

I hear that TRIE is becoming a popular interview Q but don't see any good questions\solutions posted here. Yes, I searched with the keyword TRIE and the results weren't very promising.

Can you please point me to some good resources for TRIE (not wikipedia please...)

Thank you in anticipation.

why is c++ a system programing language while java not

Is there anyone who has given APIGEE interview for SDET ?

please reply if anyone has given . I didn't get any question for APIGEE

Need algorithm
i m having a file without space, symbols and numbers. so it will be having only characters without space and any symbols. now i want valid words from that file which will be check with dictionary and If word are valid then i want to calculate its value according to game u may know Word Scramble.

Hi Guys,
I'm sure you know this, but it's annoying.
I cannot tap on a question or any item and open it up to see the proposed solutions under iOS. Tried with Safari and Chrome and it's the same lack of luck

Brain teaser 6.4!

The solution to this on page 146 is incorrect. They state that if nobody else has a hat, then you have a hat. True. If another person has a hat, there will never be a way for you to know if you have a hat or not. C could equal 1 as the problem did not specify what would happen once all hats were removed. There is no signal to let the guys know that there are no more hats, thus no way for any person to know whether they can go into the water or not.

Hi All,

I have received following two offers:

1. SDET II at Microsoft (Seattle Area, WA)
2. Senior Software Dev Eng at Yahoo (Bay Area, CA)

Compensation is almost same (factoring in the state taxes in CA). The most confusing thing is the "TEST" part in MSFT offer. I have always been a developer.

Moreover I have always worked in C++ before. The position at MSFT will require me to work in C# and Yahoo is C++/Java.

Kindly advice.

#include<stdio.h>
char *cat(char *d,char *s)
{char *t=d;

while(*d)
d++;

d=s;
return t;
}




int main()
{
char dest[100] = "geeksfor";
char *src = "geeks";

printf(" %s ",cat(dest, src));
getchar();
}

This is my implementation of strcat func.Please xplain why its not working?

What's the difference between this 2 method,
which one is better?
1.
char[] s_array = s.toCharArray();
for(char C : s_array)
letters[c]++;

2.
for(int i=0; i< s.length(); i++){
int c = s.charAt(i);
letters[c]++;
}


------------------
Sample solution:



public boolean permutation(String s, String t){
if(s.length() != t.length()) return false;

int[] letters = new int[256];

char[] s_array = s.toCharArray();
for(char C : s_array)
letters[c]++;

for(int i=0; i<t.length(); i++){
int c = (int) t.charAt(i);
if(--letters[c] < 0)
return false;
}
}

The Government of Byteland has decide to issue new currency notes with special protection features to so as to commemorate a great mathematician.

It has decided to issue notes summing up to N and all the sums from 1 to N should only made by selecting some of the notes in only one unique way.

With n = 5 the sets {1,1,1,1,1}, {1,2,2}, {1,1,3} are valid. Invalid sets are

-{1,1,1,2} because 2 can be made by {1,1} and {2}and also 3 by {1,1,1} and {1,2}

-{1,2,4} because all from 1 to 5 can be uniquely made but the sum is not 5.

Input

First line contains T(1<=T<=1000) the number of test cases. Each test case contains a integer N (<=10^9) in one line.
Output

Output the solution of each test case on a line.
Example

Input:
2
10
1000


Output:
1
13

How to print extended ASCII characters in C/C++ ?