Software development engineer intern Interview Questions
software development engineer intern interview questions shared by candidates
Top Interview Questions
What was one of your best achievements on a project in the past? 19 AnswersAnswered about a previous internship, mentioned scalability and had a small discussion on that. Were there any coding questions? And was this for an internship? There was a coding question. It was for the SDE summer internship. Show More Responses Sorry last question, how long did it take for them to give you a final phone interview. It's been 5 days now for me.should I follow up? From what i've heard and seen, just wait, following up will barely do you any good. Hey, I just have one question out of curiosity, was the second online assessment web-cam proctored? i heard amazon is changing their recruiting process. Many people complained that the online proctoring was an invasion of their privacy. I also had a second online assessment but it was not webcam proctored. I am assuming the recruiting process is now two online non webcam assessments then a final phone interview. My friend had that round of interviews with Amazon 2 weeks ago. if you dont mind, could you tell us the phone interview questions ? Can you describe your phone interview? Do you pick your lang? do they ask you concept questions? do you do a coding problem? etc... No that's cheating Who has their phone interviews soon? I still haven't gotten back with a scheduled phone interview after the second assessment. Anyone else know long the time gap was between the second assessment to final phone interview? I just finished the second online assessment today. Now waiting for their reply. How long did it take for them to get back to you after the second online assessment? It's been almost 2 months and I have not heard back. Show More Responses Took about 2 days. If you have a recruiter you should email them over that kind of a length. Anyone hear back? Its been 1 week now and I do not have a recruiter...How are we supposed to contact a recruiter when we do not have one. I just got my first logical question part, it says webcam should be enabled. Is there any place i can practice those from? Did you get the coding question correct for your phone interview? Has anyone gotten an offer or response yet after their phone interview I had mine last Thursday. If you had a phone interview in February and got an offer pls lmk One or more comments have been removed. |
To find and return the common node of two linked lists merged into a 'Y' shape. 13 Answershow did the two linked lists make their poses to merge into a 'Y' shape, one's head attached to the waist? please explain more to help understand the question The two linked lists were something like: 1->2->3->4->5 and 3->4->5->6->7->8. For a Y shaped like this: 1 -> 2 -> 3 -> 4 ->7 -> 8 -> 9 5 -> 6 -> 7 -> 8 -> 9 where the trunk portion is of constant length, it is easy. Get the length of the first list. In our case 7. Get the length of the second list: 5. Difference is 2. This has to come from the legs. So, walk the difference in the larger list. Now node1 points to 3. node 2 points to 5. Now, walk through the two lists until the next pointers are the same. Show More Responses @kvr what if the lists are 1-2-3-4-7-8-9 and 12-13-14-5-6-8-9 Can this be done using hash tables? Or is there anything more efficient? i think that kvr's answer is the best. @snv if the two lists are linked by the very last two nodes, then you would find out after you are checking the values of the second two last two nodes. you just got unlucky and basically have to check until the very end. so basically, as a diagram with your example, it would look like this 1 -2 -3 -4-7-8-9 x -x -x -x -x-o 12-13-14-5-6-8-9 (sorry about spacing) but because you know the difference in length is 0, you can start comparing the two lists of nodes one by one. from the very beginning. HASH TABLE seems the only efficient wt. 1. add each element's address (of the smallest list)and push it to the hash table. 2. start walking second list. 3. get element compar eits address with hash table if match is found in hash table, return 4. if list is not exhausted, go to step 2. 5. return NULL Hashtable is complete overkill. The point is to realize that the two linked lists have the same tail. That means if you traverse them with the same index but from the right you will eventually find the first similar node. It's almost as easy if the problem said the two linked lists had the same prefix, find the first node on which they split. Here you walk them with the same index from the left. First reverse both list and find point where both gets diverged For Y condition the list could be List 1: 1->2->3->4->5->6 List 2: 7->8->9->4->5->6 So reverse list would be 6->5->4->3->2->1 6->5->4->9->8->7 now compare two list and move forward the position where you find next node of both are different is the point of merging Some of the above will work for doubly linked list. If not, travel node by node simultaneously from each end. When one traversal ends and the postion of cursor at the traversal is the answer kvr's answer is good but I think it could be optimized better by using 2 stacks. Traverse both lists putting each value into 2 separate stacks. Then when both are fully traversed, the head of each stack will match. Pop one off each at a time till they don't match, return the last popped. But I suppose it comes down to where the first match is at. If its the beginning of the list, kvr's answer will be better, if its at the end or bottom half 2 stacks would be better. Let's say L1 is the list starting with the lower number, and L2 is the other Set X = Head of L1 Set Y = Head of L2 While X <= Y Set X = Next(L1) End While If (X==Y) Return X Else While Y<=X Set Y = Next(L2) End While If X==Y Return X End If End If Repeat until you reach the end of either list. |
Determine if an array from 1..n has a duplicate in constant time and space. 14 AnswersCorrect answer is to place each value in the array in its corresponding index (i.e. if array[x] = 3, put 3 into array[3]). If an index already contains its corresponding value, there's a duplicate. ^^ Sorry, that's linear time *and* at best linear space, you fail. What are the properties of an array that affect time complexity? Usually we're talking about the size of the array, N, such that linear time operations, O(N), are those that perform an operation on each of the elements in the array. However, an important thing to consider is that you can evaluate N (the size of the array) itself in constant time. The only way this can be done in constant time is if the input satisfies the precondition that "1..n" means there are no *missing* values in that range. In other words, such an array from "1..5" must contain at least one instance of the numbers 1, 2, 3, 4, and 5. With that precondition, you know that the length of the array will be 5 if no duplicates and greater than 5 if it does contain duplicates. Show More Responses SUM(array) - (N(N+1)/2) = missing number. @Facebook Intern: That wont help .. In case there are 2 duplicates this can be broken. {1, 1, 4, 4} I attach pseudo code here: FindDuplicate(A) i = A.length j = 1 count = 0 while j < i if A[--j] - j == 0 j++ else count++ return count count holds the number of duplicated items This cannot be done in linear time unless the data-structure used to hold the integers has a property that immediately flags duplicates upon insertion. For e.g. like in a Dictionary/HashMap. If an array has elements from 1 to n the size of the array will be n, thus if the size of the array is greater than n, there must exist a duplicate. I think they are just asking to determine if there is any duplicate number ir not. Its not mentioned to find out which number it is. So that we can find out by using sum of n numbers I think they are just asking to determine if there is any duplicate number ir not. Its not mentioned to find out which number it is. So that we can find out by using sum of n numbers They asked for constant time. So checking sum will not work. For zero indexed arrays, Check if arr[len(arr)-1] == len(arr) - 1. Obviously this can't be done with constant time or space. At best you could compute a solution in linear time. memoize/cache it once then you could return the solution in O(1) time for subsequent calls. Show More Responses I've seen this question posted several places as "Find if an array has duplicates, in constant O(1) space" but no restriction on time. If the array is not sorted, and there is no restriction on the actual values in each item, then there is no O(1) space and O(1) algo. if you sort the array, then you lose O(1) time and obviously can not detect duplicates even in a sorted array in constant time. If its like most other versions of this question, and its only O(1) space, then you could store the duplicate value in the array itself, overwriting earlier elements that you already scanned. You'd only need an index that points just past the last duplicate value written. But this is not constant time. One or more comments have been removed. |
I was asked two questions. Q 1. You are given two version numbers of a software, like Version 10.3.4 and Version 10.3.41. Write a program to find out which of the version numbers are the latest. If version 1 is latest output -1, if version number 2 is latest output +1 else output 0 if same version. Both the version numbers are taken as string. He also asks to make the program of minimum time complexity as we can. At the end he also asked the difference between an iterative program and one with recurrence and their advantages and disadvantages. Q 2. Given two files with a list of application IDs (or some kind of data) stored in them , write a program to compare the data in the two files and output all the common data found in each. What data structure would you use and why ? Give a minimum time and space complexity algorithm. Why did you choose the particular data Structure or algorithm ? 7 Answers1. This was a little tricky. You have to check for the decimal place in both the versions and then Store that part of the string till the decimal place in a temporary variable and then convert them to integer and check which one is greater. You have to keep on doing that till you reach the end of the version numbers or till when you find the answer 2. In the second question you can use Linked lists and then Binary Search Algorithm. The interviewer will ask you the reason for this. Why not just delimit the string with "." Then you'll have an array of string numbers. Then loop with the array from 0 -> n (depending on how many decimals there was) and compare. Return when one is greater than the other. You will have to check if you get a index out of bounds if one has more decimals than the other. Over all, that should be in n time. As for #2. HashTable it. Also n time. Show More Responses If you are using c++, can't you just use the "compare" method that is built into the string class? Maybe not the best solution... the time complexity is O(n). public static void main(String[] args) { String ver1 = "10.22.7.3"; String ver2 = "10.22.8.4.1"; String split1[] = ver1.split("\\."); String split2[] = ver2.split("\\."); int max = split1.length > split2.length ? split1.length : split2.length; for (int i = 0; i i) { System.out.println(+1); break; } else if (split2.length i) { System.out.println(-1); break; } else { if (Integer.parseInt(split1[i]) > Integer.parseInt(split2[i])) { System.out.println(-1); break; } else if (Integer.parseInt(split1[i]) < Integer .parseInt(split2[i])) { System.out.println(+1); break; } } } } String v1="10.3.4"; String v2="10.3.41; double v12=v1.parseDouble(); double v22=v2.parseDouble(); If(v12>v22) { System.out.print(-1);} else if(v22>v12) {System.out.print(1);} else{ System. out. print(0);} Q:2 List a= new LinkedList(); List b= new LinkedList(); while(a.hasNext()) { ( int =1; i |
To return the 'm' smallest numbers from a file of 'n' numbers 8 AnswersI would first create an array holding the first m values of the file, and sort. Then, each value I read from the file, I can compare the the last (largest) value in the array. If its smaller, do a binary search to find the correct spot in the array. Insert the number and shift everything behind it back by 1. Worst case runtime will be O(n lg m) Why cant we simply start with min=INT_MIN. Then, read first number from file, if lower, set min=that number. Seek next number and so on... We dont need to load the whole file. We will go to the disk often though. I will create a min heap with the given numbers and extract 'm' minimums from the heap which will get stored into the resultant array Show More Responses Anuj, Wont it take time of O((M+N)log N) @spammer, I think it's O(n+m*log n), since you can construct the min heap bottom-up and that only takes O(n) Why don't we just sort the array and return the first m numbers? Takes O(nlogn) for sorting and O(m) to return the first m numbers. Maintain a heap of m numbers and also track a variable which stores the current highest value. So as u go through the n numbers, if the number is higher than the current highest number, ignore it else insert it into the heap and set the current highest value to the newly inserted value One or more comments have been removed. |
Make a program that writes a Binary Search Tree to a file. Now create a program that reads those files and recreates a Binary Search Tree. 5 AnswersThe BST should be read in > and save each values into a file. Its important that the tree is parsed in preorder- or regenerating tree will give a completely different tree. The solution by Jeevan is perfect. Inorder/Postorder - it is not possible to reconstruct the tree. calling insert(node), for every node read from file will re-create the original tree. Here's a code to do it: __________________________________________ #include #include "math.h" using namespace std; class BinaryTree { public: BinaryTree::BinaryTree(int v) : value(v) {left = NULL; right = NULL;}; int value; BinaryTree *left; BinaryTree *right; }; void dfs(BinaryTree *root, FILE *fp) { fprintf(fp, "%d|", root->value); if(root->left == NULL) fprintf(fp, "N|"); else dfs(root->left, fp); if(root->right == NULL) fprintf(fp, "N|"); else dfs(root->right, fp); } void serializeTree(BinaryTree *root) { FILE *fp = fopen("tree_serialized.txt", "w"); dfs(root, fp); fclose(fp); } BinaryTree* dfs_r(FILE *fp) { fpos_t position; fgetpos (fp, &position); char isN; fscanf(fp, "%c|", &isN); if(isN != 'N') { fsetpos(fp, &position); // integer, this node exists int value; fscanf(fp, "%d|", &value); BinaryTree *newroot = new BinaryTree(value); newroot->left = dfs_r(fp); newroot->right = dfs_r(fp); return newroot; } else { // no children // NULL already set by constructor return NULL; } } BinaryTree *deSerializeTree() { FILE *fp = fopen("tree_serialized.txt", "r"); BinaryTree *newT = dfs_r(fp); fclose(fp); return newT; } int main() { // Construct a binary tree BinaryTree root(4); BinaryTree n2(2); BinaryTree n6(6); BinaryTree n1(1); BinaryTree n3(3); root.left = &n2; root.right = &n6; n2.left = &n1; n2.right = &n3; // Serialize and de-serialize it serializeTree(&root); BinaryTree *newRoot = deSerializeTree(); return 0; } Show More Responses Preorder and postOrder are both correct. /*Java Code for Question - preOrder traversal is the way to go!*/ import java.io.FileInputStream; import java.io.FileOutputStream; import java.io.ObjectInputStream; import java.io.ObjectOutputStream; import java.io.Serializable; import java.util.LinkedList; import java.util.List; public class SimpleBinarySearchTree> implements Serializable { /** * */ private static final long serialVersionUID = 1L; Node root; private class Node implements Serializable{ T data; Node left; Node right; public Node(T data){ this.data=data; left=null; right=null; } } public SimpleBinarySearchTree(){ } public void add(T data){ root=addhelp(root,data); } private Node addhelp(Node node,T data){ if(node == null){ node=new Node(data); return node; } else if(node.data.compareTo(data) > 0){ node.left=addhelp(node.left,data); } else{ node.right= addhelp(node.right,data); } return node; } public void printPreOrder(){ printhelp(root); } private void printhelp(Node node){ if (node !=null){ System.out.println(node.data); printhelp(node.left); printhelp(node.right); } } public List preOrder() { List list = new LinkedList(); return preOrder(list,root); } /** * Helper method to list out items in BST in preOrder traversal * @param list the list of the items so far in preOrder traversal * @param curr the curr node being checked * @return list of items in BST in preOrder traversal */ private List preOrder(List list,Node curr){ if (curr != null){ list.add(curr.data); preOrder(list,curr.left); preOrder(list,curr.right); } return list; } public static void main(String args[]){ SimpleBinarySearchTree tree= new SimpleBinarySearchTree(); tree.add(6); tree.add(2); tree.add(8); tree.add(1); tree.add(3); tree.add(5); tree.add(9); SimpleBinarySearchTree tree2=null; try{ FileOutputStream fout = new FileOutputStream("/Users/Ore/Desktop/tree.ser"); ObjectOutputStream oos = new ObjectOutputStream(fout); oos.writeObject(tree); oos.close(); System.out.println("Done"); }catch(Exception ex){ ex.printStackTrace(); } try{ FileInputStream fin = new FileInputStream("/Users/Ore/Desktop/tree.ser"); ObjectInputStream ois = new ObjectInputStream(fin); tree2 = (SimpleBinarySearchTree) ois.readObject(); }catch(Exception ex){ ex.printStackTrace(); } List list = new LinkedList(); list=tree2.preOrder(); SimpleBinarySearchTree tree3= new SimpleBinarySearchTree(); for(int i=0;i |
Given the head pointers to two linked lists of unknown length, find the node of intersection if they do intersect. 5 AnswersSuppose that the pointers are head1 and head2. Move head1 and increment a count1 till head1 reaches null. Move head2 and increment count2 till head2 reaches null. If head1 > head2 or head2 > head1, move the respective pointer to such a position in the linked list so that the length of the linked lists from there are equal. Then, start checking if both pointers point to the same node and incrementing both until that condition is met. If they do point to the same node at some point, that is the node of intersection. Otherwise, there is no intersection. I don't understand the interview candidate's solution. I don't think I will work properly. If the last 3rd node of List A and last node of List B intersects, this algorithm will not find the answer. My solutions: Suppose length of List A is m, length of List B is n, If space cost is more of a concern, do a O(n^2) search because it will cost constant space to find the intersect. (nested for loop) If time is more of a concern, 1. traverse through both list to figure out the length. Identify the smaller list(suppose it's list A). cost O(m+n). 2. traverse List A, build a binary search tree with the address of pointers of the list as payload O(m log(m)). 3. Traverse through list B and search the tree for each element in list B. if found, then it's the intersection.O(n log(m)). the general complexity is O(m+n+(m+n)log(m)) = O((m+n)log(m)). If we don't suppose A is the shorter, then the time complexity will be O((m+n)log(min(m,n))) pblm can be solved by making a circular linked list. Start with head1 and traverse thru the list and modify the lastnode.nxtptr -> head2 Now start with head2 and traverse. If you reach the head2 again then the list do intersect. Show More Responses Vijay has the best solution with linear time. Vijay's solution works great for finding out whether they intersect, but the question asks for finding the node of intersection. I think William's solution will work best for finding the node of intersection. The obvious one is an O(n^2) solution by traversing the first list with the nodes of the second list and doing a comparison. |
I signed NDA for online assessments. For the phone interview, questions about DS and string manipulation. Should be good if can solve medium level HackerRank or Leetcode problems. 7 Answershow long did it take you to hear back after the 2nd online assesment? how long did it take you to hear back after the 2nd online assesment? It took them around 2 weeks to come back to me for the phone interview. Show More Responses Hey Brother, Brilliant article, glad I slogged through the Amazon it seems that a whole lot of the details really come back to from my past project. AWS Tutorial I'm using CloudFormation and really enjoy it, but there are a couple of things which are lacking here. Maybe there are some reasons why they weren't implemented here, but. So, the first thing is variables which can be populated during stack creation. Here is an example of similar service from another cloud provider: Thanks a lot. This was a perfect step-by-step guide. Don’t think it could have been done better. Shukran, Radhey Szia, Grazie! Grazie! Grazie! Your blog is indeed quite interesting around Interview Question! I agree with you on lot of points! I'm a tutor at a college in NZ trying to use AWS educate to teach my students how to set up a webserver and your admin approval system that we use to confirm access to the students is broken. It also enables customers to reduce the administrative burdens of operating and scaling storage to AWS, AWS Training USA so they don’t have to worry about capacity planning, hardware provisioning, data replication, hardware failure detection and recovery, or time-consuming hardware migrations. Excellent tutorials - very easy to understand with all the details. I hope you will continue to provide more such tutorials. Regards, Kevin Hello Mate, Seems like I won the lottery here….This is a treasure box of blogs and your folks are like leprechauns! Phenomenal read on Interview Question. I would like to ask you about bandwidth between standard AWS and your AWS in China. (I read it is operated by your partner Sinnet.) Are there lags like standard connections to / from China passing through that Great Chinese Firewall? AWS Training THANK YOU!! This saved my butt today, I’m immensely grateful. Kind Regards, Radhey One or more comments have been removed. |
string compression: aaabbbbcc ->a3b4c2 5 AnswersJava code: private static String compressString(String input) { StringBuilder result = new StringBuilder(); char currentCharacter; int count; for(int i = 0; i < input.length(); i++) { currentCharacter = input.charAt(i); count = 1; while(i < input.length() - 1 && input.charAt(i + 1) == currentCharacter) { count++; i++; } result.append(currentCharacter); result.append(count); } return result.toString(); } //C++ using namepsace std; main(int argc, char** argv) { string input = "aaaabbccccddd"; string output; char lastchar = input[0]; int count = 0; for (int i = 0; i < input.size(); i++) { if (input[i] != lastchar || i == input.size() -1 ) { output += lastchar; output += count; count = 0; lastchar = input[i]; } count++; } } What is a character is repeated more than 10 times? aaa..14times..bbb.cc.. a14b3c3 - how do we decode it then? if we assume input string can contain only alphabets- then its fine. Show More Responses Make an array of size 256 for all ASCII characters. Iterate through string and increment each character that matches the array. Iterate through ASCII array and concatenate letters and element values I'd probably just use a hash map (in-order map just like C++'s map) and iterate through the string counting the number of occurrences of each character. Then, using the in-order property of the hash table, the string could then be printed out in the aforementioned format: aaabbbbcc ->a3b4c2. |
Write a program to find the square root of a double. 5 Answersuse binary search to narrow down the search space and keep multiplying the answer in each iteration by itself to check if it is equal to the double given. If it is lesser, move up the lower bound, else move down the upper bound. One easy to remember method that also has much better performance than binary searching for the result is the Babylonian Method. It is similar to Newton's method for finding derivatives. See the algorithm here: http://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Babylonian_method Also, combining this algorithm with the Rough Estimation also described on that page will compute the squareroot of most double numbers in less than 10 iterations. Is it too obvious to ask if you can do double^.5 ? Show More Responses I would respond by showing that I am thinking about the problem as it is defined, not by making assumtions about what is implied. This can result in product that does not meet the requirement specifications, which can be very costly: "What do you mean, a program or a function? A program would require input and output mechanisms to make it meaningful, but makes it pretty usesless as a job assessment question. A function makes more sense in this context. " There's a variation of the problem which says "find the square root of a double up to the third decimal digit". I'd just multiply the original number by 10^position (meaning, for 3 digit accuracy it'd be 10^3) and ran a simple loop to find the closest integer. As soon as i*i > 10^position * number, you can return (i-1)/10^position. It's hella slow and unimaginative, but it works and you won't sound like you knew this problem ahead of time (if you come up with a Babylonian solution). |
See Interview Questions for Similar Jobs
- Software Development Engineer
- Software Engineer
- Intern
- Software Engineer Intern
- Software Developer
- Software Development Engineer I
- Software Engineering Intern
- Software Development Engineer In Test
- Senior Software Engineer
- Software Engineering
- Technology Analyst
- Applications Support Engineer
- Java Developer
- Software Development Engineer II