SDE1 Interview Questions
- -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 September 27, 2013 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 - 3of 5 votes
AnswersGiven an n X n matrix, find all elements which are zero, when found set all the elements in that row and column to zero.
- akula.maheshk September 24, 2013 in United States| Report Duplicate | Flag | PURGE
Microsoft SDE1 Algorithm - 0of 2 votes
Answersgiven a array of digits. print all combination of of these i.e all no formed by these.
- Abhi September 23, 2013 in India
repetition allowed.
and then for modification:
repetition not allowed
example:
i/p:
arr={2,3,4}
o/p:
(without repetition)
234
243
324
342
423
432| Report Duplicate | Flag | PURGE
Cadence Inc SDE1 Algorithm - -1of 1 vote
AnswersGiven a positive int "N". and an array of numbers ranging from 0-9 (say array name is arr).
- Abhi September 23, 2013 in India
print all numbers from 0 to N which include any number from "arr".
example:
i/p: N=20
arr={2,3}
o/p: 2,3,12,13,20| Report Duplicate | Flag | PURGE
Cadence Inc SDE1 Algorithm Coding - -1of 1 vote
AnswersGiven a list of 'N' coins, their values being in an array A[], return the minimum number of coins required to sum to 'S' (you can use as many coins you want). If it's not possible to sum to 'S', return -1
- pirate September 14, 2013 in India
Input #01:
Coin denominations: { 5,5,5,5,5 }
Required sum (S): 11
Output #01:
-1| Report Duplicate | Flag | PURGE
Amazon SDE1 - 0of 0 votes
AnswersImplement a Boolean vector: T, F, F, T, F, … with the following operations:
- adi September 13, 2013 in United States
append(boolean b)
boolean get(int index)
set(int index, boolean b)
int length()
Restriction: no Java collections classes
What if you knew the vector has 99.99% T and only 0.01% False. How would you change the approach?| Report Duplicate | Flag | PURGE
Google SDE1 Java - 2of 2 votes
AnswersGiven 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.
- blackfever September 03, 2013 in India
Was then asked to improvise the solution as much as possible| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 0of 0 votes
AnswersMultiply two linked list represented as linked list and return result as linked list.
- ninja August 31, 2013 in United States| Report Duplicate | Flag | PURGE
SDE1 - 5of 7 votes
AnswersWhat is the minimum representation in bits of two positions on an 8x8 chessboard?
- pretonesio August 28, 2013 in United States for Outlook| Report Duplicate | Flag | PURGE
Microsoft SDE1 Brain Teasers - 1of 1 vote
AnswerImplement cache with proper synchronization.
- nr August 21, 2013 in United States| Report Duplicate | Flag | PURGE
American Airlines SDE1 - 0of 4 votes
AnswersWrite code to reconstruct the tree from given any 2 traversals.Do it iteratively.
- nishu August 14, 2013 in India| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - -2of 8 votes
Answersits easy but still!!
find the largest subarray with equal number of 0's and 1's.
example 001010101
output:8
- viva August 14, 2013 in United Statesint subarray(int arr[],int n) { int count=0; for(int i=0;i<n;i++) { if(a[i]==0) count++; else count--; } if(count==0) return n; else { if(count>0) return n-count; else return n+count; } }
| Report Duplicate | Flag | PURGE
Groupon SDE1 Data Structures - -3of 3 votes
AnswersRequirements:
- MrA August 07, 2013 in United States
1>client should be able to create shapes like circle, square , rectangle..etc,. Also framework should be able to add some more shapes later.
2> client should be able to calculate areas of each shapes
3> should have collection where all shapes are stored and should be able to sort on the area of the shapes| Report Duplicate | Flag | PURGE
Amazon SDE1 Object Oriented Design - 0of 0 votes
Answersn1 pairs of “{} ” brackets
- nishu August 03, 2013 in India
n2 pairs of “[] ” brackets
n3 pairs of “() ” brackets
find the all valid combinations of all the pairs.| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 0of 0 votes
Answersnegate each bit of 32 bit integer. I answered with XOR with FFFF but interviewer asked will ~(number) work? I answered as no.
- gaurav.2897 July 30, 2013 in India
I executed this piece of code
int x=8;
int k=~(x);
printf(%d",k)
output: 9
x=1000
~(x) =9 how?| Report Duplicate | Flag | PURGE
McAfee SDE1 C - -6of 6 votes
AnswersThere are three persons A,B,C .A shots the target 6 times out of 7 shots .B shots 4 out of 5 shots .Then what is the probability of hitting the target twice when 2 persons are selected at random.
- siddharthjain July 29, 2013 in India| Report Duplicate | Flag | PURGE
Amazon SDE1 Probability - 0of 0 votes
Answerswrite a code to find the equilibrium position of the array.
- gaurav.2897 July 25, 2013 in India
given an array: 3,-3,8,6,-1,-5
equilibrium position should be 2(element 8) sum of lower index(3+-3)=sum of higher index(6+(-1)+(-5))| Report Duplicate | Flag | PURGE
Amazon SDE1 C - 4of 4 votes
AnswersYou are having a 500 MB RAM and you have a program which uses malloc to allocate 600 MB memory . What will happen , will it be allocated using the concept of virtual memory or not , if yes how?
- P3A July 23, 2013 in India| Report Duplicate | Flag | PURGE
Yahoo SDE1 Operating System - 3of 5 votes
AnswersThere are N(0 to N-1) players each having at Max 'M' (0 to M-1) number of followers. You have to select minimum number of players so that the total followers must be equal to a given number 'K'.
I/P would be like,
first line contain N, M, K followed by N lines containing string of 0 or 1 s.t. for i'th line if j'th char is 1 it means j'th person follows player 'i'
For. eg.
- P3A July 18, 2013 in India3 6 5 111100 000100 000010 ans=2 ( select 0th and 2nd )
| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 11of 13 votes
AnswersThere are some glasses with equal volume 1 litre. The glasses kept as follows
1 2 3 4 5 6 7 8 9 10
You can put water to only top glass. If you put more than 1 litre water to 1st glass, water overflow and fill equally both 2nd and 3rd glass. Glass 5 will get water from both 2nd glass and 3rd glass and so on..
- Vin July 17, 2013 in India
If you have X litre of water and you put that water in top glass, so tell me how much water contained by jth glass in ith row.
Example. If you will put 2 litre on top.
1st – 1 litre
2nd – 1/2 litre
3rd - 1/| Report Duplicate | Flag | PURGE
Amazon SDE1 - 2of 2 votes
AnswersWAP to create a mirror of a binary tree. Extend the code or write a new code if not possible to do mirroring at alternate levels . Here in the second part , if the two trees are placed in front of each other , then odd levels should be exact mirror as a whole and even levels should be exactly same . Then write the iterative version for the above codes.
- Kavish Dwivedi July 15, 2013 in India for Bangalore| Report Duplicate | Flag | PURGE
Amazon SDE1 Trees and Graphs - 23of 23 votes
AnswersYou are given an array of n integers which can contain integers from 1 to n only . Some elements can be repeated multiple times and some other elements can be absent from the array . Write a running code on paper which takes O(1) space apart from the input array and O(n) time to print which elements are not present in the array and the count of every element which is there in the array along with the element number .
- Kavish Dwivedi July 15, 2013 in India for Bangalore
NOTE: The array isn't necessarily sorted.| Report Duplicate | Flag | PURGE
Amazon SDE1 Arrays - 0of 4 votes
AnswersWrite a method in your preferred language that given an array of n points on a plane specified by their (x,y) coordinates, and an angular size α, returns the direction β at which a beam of size α centered at the origin of the coordinate system would enclose the most number of points from the array. The direction of the beam can be represented by an angle β as shown in the illustration below.
- shylaja23 July 13, 2013 in United States
Tip: The function arctan(y/x) returns the angle of a point.
In the illustration below, the blue dots represent points from the array and the grey beam represents the beam of size α pointed in a direction β where it happens to enclose three points.| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 0of 4 votes
AnswersConstruct a BST from inorder and preorder traversal string. Write code for it.
- yolo July 11, 2013 in India| Report Duplicate | Flag | PURGE
Amazon SDE1 Trees and Graphs - -11of 11 votes
AnswersGiven a tree, verify if it contains a subtree.
- yolo July 11, 2013 in India| Report Duplicate | Flag | PURGE
Amazon SDE1 Trees and Graphs - 0of 2 votes
AnswersGiven a maze that contains floor plan with rooms.
- yolo July 11, 2013 in India
For example, consider a n*m matrix where each block represent a room.
You can move up-down and left-right from one room to another. But there are some rooms where there no door to one or more side of the wall.
some rooms are bathrooms.
Given a room location, return the nearest bathroom.
Start by writing method signature. Interviewer said that :)
It was bar raiser round.| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 5of 7 votes
AnswersDelete last node from the linked list. First node pointer is not given.
- yolo July 11, 2013 in India
I told him its not possible in conventional linked list.
He asked me what if we can add some more data in node.
Data should not be a pointer to previous node i.e., it should still be singly linked list.| Report Duplicate | Flag | PURGE
Amazon SDE1 Linked Lists