Amazon Software Engineer interview questions

On-campus recruitment: A 1.5Hr test consisting of MCQ's and 2coding questions. Followed by a tech interview. b)First Interview Q1) Given a sorted array of zeros and ones, find the number of zeros in the array.A: First I told him the brute force approach, he asked of time complexity then how is it O(n)then I told him we could use binary search, explained how, then I was asked to write code.there was a bug pointing which he gave me a test case, which I then rectified.Time complexity was asked and how was it O(logn)? Q2) Given a sorted array of integers, find the number of times a given number K occurs in the array. A: Use binary search on both sides and add, average time complexity came out to be O(n). Both left and right halves were to be checked only when key==mid.Time of round : 15-20 mins c)Second Interview Q1) Given a number n, the number of open paranthesis find number of all possible valid pattern of pairs of pranthesis. eg. n=2 (()) , ()() A: Used backtracking. -What all subjects you have studied? -C , DS, OS. Q2) Questions on OS- -How does a process start -diff b/w process program -what does running a process mean -what gets loaded on memory when a program is run -from where and how memory is allocated during runtime -what is system call -What all topics do you know in DS? - Stacks, Queues, Deque, trees. -Haven't you know graphs? - I know but not a very good grasp on it. Q3) Given a tree find shortest path between any two given nodes. A: Find nearest ancestor find heights from there, add them. He asked extra iterations for heights were required? Returned height while finding ancestor. Asked to code. Asked to explain the code, then dry run for any test case. A bug was found and corrected.

I applied during career fair and was contacted for a back-to-back interview on campus. I had a very short notice. The two interviewers asked both behavioral and technical questions. Technical questions involved mainly data structure problems.