SDE1 Interview Questions
- 0of 0 votes
AnswersExplain some of the text encoding types and advantages/disadvantages of each.
- Gaile January 31, 2014 in United States| Report Duplicate | Flag | PURGE
Apple SDE1 - 0of 0 votes
AnswersIf your browser crashes, how would you debug it only using the command line?
- Gaile January 31, 2014 in United States| Report Duplicate | Flag | PURGE
Apple SDE1 - 0of 0 votes
AnswersThere are 3 ants at 3 corners of an equilateral triangle they randomly start moving towards another corner what is the probability that they do not collide? Follow up: Suppose if all ants go in same direction(say ant 1 travels from point A to B, ant 2 from B to C and ant 3 from C to A. Either all ant travels in clockwise or anti clockwise) when will they collide
- Gaile January 31, 2014 in United States| Report Duplicate | Flag | PURGE
Apple SDE1 - 0of 0 votes
Answersdesign an iterator over a LinkedList of LinkedList's
- Gaile January 31, 2014 in United States| Report Duplicate | Flag | PURGE
Apple SDE1 - 0of 0 votes
AnswersHow will you sort 1 billion integers stored in an array?
- Gaile January 31, 2014 in United States| Report Duplicate | Flag | PURGE
Apple SDE1 - 1of 1 vote
AnswersHaving two distinct very large ordered array of values, find the mean value(not median) of the two arrays.
- Gaile January 31, 2014 in United States| Report Duplicate | Flag | PURGE
Apple SDE1 - 2of 2 votes
AnswersYou have a 100 coins laying flat on a table, each with a head side and a tail side. 10 of them are heads up, 90 are tails up. You can't feel, see or in any other way find out which side is up. Split the coins into two piles such that there are the same number of heads in each pile.
- Gaile January 31, 2014 in United States| Report Duplicate | Flag | PURGE
Apple SDE1 - 0of 0 votes
AnswersModel an elevator.
- Gaile January 31, 2014 in United States| Report Duplicate | Flag | PURGE
Apple SDE1 - 1of 1 vote
AnswersImplement an iterator for a binary search tree that will iterate the nodes by value in ascending order
- Gaile January 31, 2014 in United States| Report Duplicate | Flag | PURGE
Apple SDE1 - 2of 2 votes
AnswersLucky numbers are those numbers which contain only "4" and/or "5". For example 4, 5, 44, 54,55,444 are lucky numbers while 457, 987 ,154 are not.
- sunny.010203045 January 29, 2014 in India
Lucky number sequence is one in which all lucky numbers exist in increasing order for example 4,5,44,45,54,55,444,445,454,455...
Now we concatenate all the lucky numbers (in ascending order) to make a lucky string "4544455455444445454455..."
Given n, your task is to find the nth digit of the lucky string. If the digit is 4 then you have to print "Hacker" else you have to print "Earth".
Input:
first line contain number of test cases T , next T line contain a single interger n.
Output:
For each test case print "Hacker"(without quotes) if nth digit of lucky string is "4" else print "Earth"(without quotes) if nth digit of lucky string is "5".
Constraints:
1<=t<=10^5
1<=n<=10^15| Report Duplicate | Flag | PURGE
Amazon SDE1 - 1of 1 vote
AnswersProblem Statement
- sunny.010203045 January 29, 2014 in India
There are three types of tickets and stations available in CodeCountry A, B and C. Tickets of type A can only be bought at stations of type A and end at a station of type B. Tickets of type B can only be bought at stations of type B and end at a station of type C. Similarly, tickets of type C can only be bought at stations of type C and end at a station of type A. Also, you can only travel from station i to station j if j > i, i.e. you can only move forward and if the ticket type bought at station i ends at station j.
The cost of a ticket is j x j if you travel a distance of j. For example if you start at Station 3 and end at station 5 the cost is 2 x 2=4.
Now, you want to travel from Station 1 to Station N using trains in CodeCountry. You are given the type of each station. Output the minimum cost of the journey.
Note that station N will also have a type and you must reach it using a ticket of compatible type. Output -1 if it is not possible to reach from station 1 to station N
Input Format
The first line contains the number of test cases T. This is followed by T lines one for each test case.
Each test case consists of a string representing the types of each station. The i-th character of the string represents the i-th station's type.
Output Format
Output the minimum cost of the journey, one line per test case.
Constraints
The number of test cases is atmost 50.
There will be atleast 2 stations and atmost 15 stations.
The first station (station 1) is always of type A.| Report Duplicate | Flag | PURGE
Amazon SDE1 - -1of 1 vote
AnswersBy mistake I wrote the following program and it compiles and runs without any error in gcc compiler. enter code here
- Amit January 28, 2014 in India
#include<stdio.h>
#include<stdlib.h>
int main()
{
int i,**data;
data=(int **)malloc(sizeof(int)*1000000);
for(i=0;i<1000000;i++)
data[i]=(int *)malloc(sizeof(int)*1000000);
printf("done\n");
return 0;
}
But I don't understand how is it allocating an array of 1000000*1000000 bytes,almost equivalent to 1TB??| Report Duplicate | Flag | PURGE
SDE1 C - 0of 0 votes
AnswersYou have a plain with lots of rectangles on it, find out how many of them intersect
- Madan January 28, 2014 in United States| Report Duplicate | Flag | PURGE
Google SDE1 - 2of 2 votes
AnswersSort a list of numbers in which each number is at a distance k from its actual position
- Madan January 28, 2014 in United States| Report Duplicate | Flag | PURGE
Google SDE1 - 0of 0 votes
AnswersStore a set of sudden-death tournament results in a compact format (eg. a bit array) and a set of predicted match results (also in a bit array). Score the predictions, giving one point per correctly guessed match, without unpacking the bit array into a more convenient format (ie. you have to traverse the tree in-place).
- Madan January 28, 2014 in United States| Report Duplicate | Flag | PURGE
Google SDE1 - 0of 0 votes
AnswersImplement a simple regex parser which, given a string and a pattern, returns a boolean indicating whether the input matches the pattern. By simple, we mean that the regex can only contain special character: * (star), . (dot), + (plus). The star means what you'd expect, that there will be zero or more of previous character in that place in the pattern. The dot means any character for that position. The plus means one or more of previous character in that place in the pattern.
- Madan January 28, 2014 in United States| Report Duplicate | Flag | PURGE
Google SDE1 - 0of 0 votes
Answers1. find all the combinations of a string in lowercase and uppercase. For example, string "ab" -> "ab", "Ab", "aB", "AB". So, you will have 2^n (n = number of chars in the string) output strings. The goal is for you to test each of these string and see if it match a hidden string.
- Madan January 28, 2014 in United States| Report Duplicate | Flag | PURGE
Google SDE1 - 0of 0 votes
Answerint[] first = {3}; // size 1
- Madan January 28, 2014 in United States
int[] second = new int[3]; // size 3
second[0] = 2;
second[1] = 4; //2,4
Second array has enough space to hold all elements of first and second array, where both the arrays are merged. Now write code to have first array into second.
The following Cracking the coding interview code doesn't work.
public static int[] merge2(int[] first, int[] second){
int lastA = first.length-1; //0
int lastB = second.length-1; //2
int indexMerge = (lastA + lastB);
while(lastA >= 0 && lastB >= 0){
if(first[lastA] > second[lastB]){
second[indexMerge] = first[lastA];
indexMerge--;
lastA--;
}else{
second[indexMerge] = second[lastB];
indexMerge--;
lastB--;
}
}
while(lastA >= 0){
second[indexMerge] = first[lastA];
indexMerge--;
lastA--;
}
return second;
}| Report Duplicate | Flag | PURGE
Google SDE1 - 0of 2 votes
AnswersYou are given an array A with elements 0 to n-1, numbers can be repeated in the array. Create n sets where
- sunny.010203045 January 27, 2014 in United States
S[i]={a[i],a[a[i]],a[a[a[i]]]…}. Set has all elements unique. Find the size of the largest set.
Input:
First line contains n, size of the array. n<1000
Next lines contains n numbers, each element of the array
Output
Prints one number: Size of the largest set.
Sample Test Case:
Input: {3,1,2,0}
Output: 2
Explanation:
Four possible sets are
{3,0},{1},{2}{0,3}| Report Duplicate | Flag | PURGE
Amazon SDE1 - 0of 0 votes
AnswersGiven an array of integers. Remove minimum number of elements from the array such that the largest and the smallest number does not differ by more than two times.In other words if x is the minimum of the remaining elements in the array and y is the maximum than y<=2x.
- sunny.010203045 January 27, 2014 in United States
Find the minimum number of numbers that has to be removed from the array so that the largest and the smallest number differed in no more than two times.
Input:
First line contains n(2<=n<=10^5), the size of the array
Second line contains n integers, the elements of the array.
Output:
Single integer - the minimum number of elements to be removed from the array.
Sample Test Case:
Input: {4,5,3,8,3,7}
Output: 2
Note: In the above sample you can remove the fourth and the sixth measurement results (values 8 and 7). Then the maximum of the remaining values will be 5, and the minimum one will be 3. Or else, you can remove the third and fifth results (both equal 3). After that the largest remaining result will be 8, and the smallest one will be 4.
You do not need to write full code. Just fill out the given function.| Report Duplicate | Flag | PURGE
Amazon SDE1 - 1of 1 vote
AnswersYou are given a 2-Dimensional array with M rows and N columns. You are initially positioned at (0,0) which is the top-left cell in the array. You are allowed to move either right or downwards. The array is filled with 1's and 0's. A 1 indicates that you can move through that cell, a 0 indicates that you cannot move through the cell. Given a function numberOfPaths which takes in the above 2-D array, return the number of paths from the top-left cell to the bottom-right cell (i.e. (0,0) to (M-1,N-1)).
- Madan January 27, 2014 in United States| Report Duplicate | Flag | PURGE
Google SDE1 - -1of 1 vote
Answersyou have a array which says the order of alphabets say [abcdef....z]. now use this array to sort, constraint is 'a' can be swapped one time 'b' two times, and for sorting you can use only swap.
- sameer.careercup January 26, 2014 in India| Report Duplicate | Flag | PURGE
Amazon SDE1 - -1of 1 vote
Answeryou have n different array, all are sorted. form one array of size n whose range is min. meaning in resultant array diff of a[0] to a[n-1] is min.
- sameer.careercup January 26, 2014 in India| Report Duplicate | Flag | PURGE
Amazon SDE1 - 0of 2 votes
AnswersSuppose there is array contains 100 unsorted elements ...say a[1] to a[100].
- Ruhan January 25, 2014 in India
find out the minimum and maximum value in the range of a[25] to a[75].| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - -1of 1 vote
AnswersConsider in Java arraylist we have mix of int, double, float, string, etc. How will you find if a given index of arraylist have string. No need to worry about generics and type safe.
- Madan January 23, 2014 in United States| Report Duplicate | Flag | PURGE
Google SDE1 - 3of 3 votes
AnswersConsider the following array {1,2,3,4,5,2,5,4,4};
In the above array, index 4 could be considered as breaking point where summation of 0 to 4 in the array is equal to summation of 5 to end of array. We need to find the breaking point for the given array. I solved this. But follow up was for this array{1,0,-1,-1,1};
. Mathematically the later array's breaking point is 2.
- Madan January 23, 2014 in United States| Report Duplicate | Flag | PURGE
Google SDE1 - 2of 2 votes
AnswersThere is a large file( 1TB) containinig braces. Question is to check for their balance. I said will use a counter, will increment on an open brace and decrement on an close brace. If counter goes negative or counter is non zero at the end of the file, braces are not balanced. Otherwise balanced. Followup question was to make this process parallel ( meaning to see if this problem can be solved through parallelism, like dividing the the problem into sub problem....) Remember the file is very large.
- gns January 23, 2014 in India| Report Duplicate | Flag | PURGE
Amazon SDE1 Problem Solving - 0of 0 votes
AnswersGiven a tree, generate all paths. Note : all paths..not just the ones starting from root
- anon123 January 22, 2014 in United States| Report Duplicate | Flag | PURGE
Amazon SDE1 - 1of 1 vote
AnswersImplement a function which returns list of all nodes in a binary tree having a given number of leaves, say k . Also mention complexity.
- batradiva January 22, 2014 in India| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 0of 0 votes
AnswersHow do you add two numbers that are larger/longer than Integer datatype? I said I would use BigInteger , then he asked how will you add if the number is larger than BigInteger?
- Madan January 16, 2014 in United States| Report Duplicate | Flag | PURGE
Google SDE1