Java Interview Questions
interview questions shared by candidates
Java Interview Questions
Intern at Facebook was asked...
Given an array of randomly arranged lower case letters, uppercase letters, and numbers, sort the array such that all lower case letters come before all uppercase letters, come before all numbers. The classes of characters do not need to be in order in their respective sections. 7 Answersimport java.util.Arrays; public class SortLowerUpperAndNumbers { static Character array[] = new Character[] { 'B', 'g', '3', 'a'}; public static void main(String[] args) { Arrays.sort(array, (Character o1, Character o2) -> o2 - o1); for (int i = 0; i < array.length; i++) { System.out.println(array[i]); } } } ArrayList newArr = new ArrayList(); for x in oldArr if x is lowercase newArr.add(x) for x in oldArr if x is uppercase newArr.add( x) for x in oldArr if x is number newArr.add( x) An O(n) solution To clarify, the solution to such a problem should run in linear time and use constant space. So the first two solutions, while presumably valid, are not quite doing enough Show More Responses Is it like the dutch national flag problem? Using Dutch Flag problem, in where clause I can use 2 Hash Set which contains only lower case letters and upper case letters respectively. Then implementing HashSet.contains(value) in Switch statement cases and rest swapping values based upon it. Solution in java: Arrays.sort(arr, Collections.reverseOrder()); i = j = 0 for j in range(0,len(arr)): if arr[j] != 0: if (i < j): temp = arr[i] arr[i] = arr[j] arr[j] = temp i += 1 |
Software Engineer at Dropbox was asked...
Find all duplicate files by content in your filesystem. 7 AnswersYou'll probably have to define few heuristics, such as md5sum, sha1sum, instead of byte comparison. It's actually a software design problem. Your solution needs to be tackle a couple of problems: obtaining a list of all the files in the file system (e.g. via DFS), binning the lists into possible matches, repeat via swappable heuristics until your certainty is 100%. (eg size 1st, md5 2nd, byte stream 3rd) To anonymous: If that was a software design problem, why doing it as phone screening & via coderpad.io? That's kinda stretching it a bit thin, don't you think so? It doesn't seem the proper place to work with I/O, neither brainstorm like a white-board... Most of phone screens via coderpad.io are self contained to make sure the candidate knows how to code, then bring onsite for a more in-depth discussion. Show More Responses get all files via dfs. group files by file size. then compare each file to other files in its group, reading one byte at a time. if one byte is different from rest, remove it from group. files with same byte are in subgroups. read next byte until eof. remove subgroups of size 1 - these files are not duplicates. remaining subgroups consist of duplicate files. Doing MD5 or SHA1 would involve reading large files which is slow, and collisions if file sizes are > 2^256 size for ex if using sha 256-bit. Do you know what 2^256 is called in terms of bytes, like KB, MB etc.? Can you have a file size bigger than that? Collisions can happen even if the file size is much smaller, but I don't think a file bigger than 2^256 bytes is going to be a problem. I'm curious, because I just got this question in an interview and got entirely stuck towards the end of the problem when trying to determine actual file equality. Tree traversal and whatnot is no big deal, but is there a "right" answer here in terms of being able to compare arbitrarily large files for equality? I got this question too and I think I did well, considering I had no clue about anything related to this question. Fairly matured interviewer quickly understood that the question got me out of surprised and have 2 java API's .. listAllFile(String path) and isDir(String path). What I did is wrote 2 functions. 1> Arraylist getAllFile(String path); // This is DFS and returns all path.. took me like 2 mins, Interviewer wanna know how would I traverse, i didnt even mention its just came outta fly and I said recursively traverse... I think my dumbness here reflected as this to be a very "minor" things for me. 2>ArrayList> Compare(ArrayList files); // This required a considerable amount of work, I used SHA1 for hashing, HashMap for storing... Interviewer got a lotta info about me in here, coz I know deep level details about how file encoding works, its just not binary byte by byte comparion as someone wrote above... coz .png / .jpg of the same file will have 2 different byte value... this is where Interviewer was kinda caught by surprised, coz I think he haven't got to that detailed. Finally he will ask you to print the duplicate only files, which is just another API.. fairly easy. Overall, I would say coderpad.io sucks... No intelligence, no help.. Intellegence show dump things.. I was totally turned off. Interviwer was late by 6 minutes but I was able to finish task within 50 minutes, considering the technical discussion, coding of 2 diff algorithm, I feel... it was worth to call a good but complex question as phone interview |
Engineering at Facebook was asked...
Write a C function to define strstr(char *haystack, char * needle) to return the first occurrence of needle in haystack. Code must compile and execute. 7 AnswersI wrote the necessary C code and didn't struggle much on code development as this is a common question. Can't guarantee that my code would compile and run as I didn't get a scope to run the code using a compiler. Not sure how picky they are about this matter. I wrote this in 15 mins, after being out of touch with C for 2-3 years. It compiles. Just in case someone needs it: int strstr(char *haystack, char * needle) { int i=0,j=0; int here=0; while(1){ if(needle[i]==haystack[j]){ if(here==0) here=j; i++;j++; if(i>=strlen(needle)){ return here; } if(j>=strlen(haystack)){ return -1; } } else{ j++;i=0;here=0; } } } in Java: static int indexOf(String main, String search){ int index = 0; for(int i = 0; i <= (main.length()-search.length()); i++){ if(main.substring(i, i+search.length()).equals(search)){ index = i+1; break; } } return index; } Show More Responses Wrong answer... int strstr(String haystack, String needle) { if (haystack == null || needle == null || haystack.equals("") || needle.equals("") || needle.length() > haystack.length()) return -1; int position = -1; int j = 0; for (int i = 0; i 0){ i--; j = 0; position = -1; } } return position; } I was asked about this question yesterday but it took me too long since I was nervous. But actually it is simple def strStr(self, haystack, needle): """ :type haystack: str :type needle: str :rtype: int """ len_needle = len(needle) len_haystack = len(haystack) start = 0 while ((start+len_needle) <= len_haystack): if haystack[start:start+len_needle] == needle: return start else: start += 1 return -1 #include #include #include int main(void) { char input_string[100] = "/bin/mydir/product/2020/05/bin/linux64/xyz"; char needle[10] = "/bin/"; char *firstOccurrence; firstOccurrence = strstr(input_string,needle); printf("First occurrence of the string '/bin/' is : %s\n",firstOccurrence); int i = 0, j = 0; while(input_string[i] != '\0'){ if(((input_string[i] == '/') && (input_string[i+1] == 'b') && (input_string[i+2] == 'i') && (input_string[i+3] == 'n') && (input_string[i+4] == '/') )== 1){ j = i; } i++; } printf("Last occurrence of string '/bin/' starts at position %d and the string is : ", j); while(input_string[j] != '\0'){ printf("%c",input_string[j]); j++;; } return 0; } OUTPUT: First occurrence of the string '/bin/' is : /bin/mydir/product/2020/05/bin/linux64/xyz Last occurrence of string '/bin/' starts at position 26 and the string is : /bin/linux64/xyz #include #include #include int main(void) { char input_string[100] = "/bin/mydir/product/2020/05/bin/linux64/xyz"; char needle[10] = "/bin/"; char *firstOccurrence; firstOccurrence = strstr(input_string,needle); printf("First occurrence of the string '/bin/' is : %s\n",firstOccurrence); int i = 0, j = 0; while(input_string[i] != '\0'){ if(((input_string[i] == '/') && (input_string[i+1] == 'b') && (input_string[i+2] == 'i') && (input_string[i+3] == 'n') && (input_string[i+4] == '/') )== 1){ j = i; } i++; } printf("Last occurrence of string '/bin/' starts at position %d and the string is : ", j); while(input_string[j] != '\0'){ printf("%c",input_string[j]); j++;; } return 0; } First occurrence of the string '/bin/' is : /bin/mydir/product/2020/05/bin/linux64/xyz Last occurrence of string '/bin/' starts at position 26 and the string is : /bin/linux64/xyz |
Software Engineer at Google was asked...
1. mutable, non mutable classes in Java 2. declaring constants in Java 3. x^y algorithm and its optimization. 4. second largest number from Binary Tree 7 AnswersFor #4, is it possible the question was "how to find the second largest number in a Binary Search Tree"? If so, it can be done in O(log n) by starting at the root node, traversing right repeatedly until you reach a leaf node, and then returning the parent of that last node. If its just some random binary tree without any ordering, you'd have to traverse the whole tree. For #4, is it possible the question was "how to find the second largest number in a Binary Search Tree"? If so, it can be done in O(log n) by starting at the root node, traversing right repeatedly until you reach a leaf node, and then returning the parent of that last node. If its just some random binary tree without any ordering, you'd have to traverse the whole tree. Method1: Do a in order tree walk and return the last but one element. O(n) Method2: We can go the right sub-tree repeatedly until next is null. Then return the parent. O(logn) Show More Responses 1.) Langauge trivia up for interpretation. For immutable classes, you can declare fields final (so noone can change your data), you can declare the class itself final (so noone can subclass you). 2.) static final whatever is a constant, optimized by the JVM at compile time 3.) Optimizing an exponential algorithm's tricky depending on what you're doing. I'd look for memoization to reduce the amount of work you're doing - an really slow algorithm likely includes massive amounts of rework (e.g. naive Fibonacci). 4.) Go right until you can't go right anymore (find the greatest node). If there is a left node (e.g. greatest -> left != null), go left once and then go right again until you can't go right anymore, and that node will be the second largest. If there is no left node, greatest -> parent is the second largest. Code for the last question in java with a recursive function: public static Integer getSecondLargest(Node root) { if (root == null) { return null; } Integer currentSecondLargest = null; if (root.myRight != null) { currentSecondLargest = root.myValue; Integer contenderFromRightSubTree = getSecondLargest(root.myRight); if (contenderFromRightSubTree != null) { currentSecondLargest = contenderFromRightSubTree; } } else if (root.myRight != null) { currentSecondLargest = root.myLeftmyValue; } return currentSecondLargest; } For 3, There is an algorithm described here that can be done in O(n^1.59) time: http://www.cs.berkeley.edu/~vazirani/algorithms/chap2.pdf public int findTreeSecLargest(Node root) { int count = 0; if (root != null) { // last right left return 1; // second return 2; count = 1 + findTreeSecLargest(root.right); } // second node of the last right node if (count == 2) { System.out.println("sec large " + root.x); } return count; } |
Software Development Engineer at Amazon was asked...
Coding Challenge 3) You are given a linkedlist with next and arbitary pointers. Create a new linkedlist similar to the given linkedlist. You need to create a code for deep copy of a linkedlist. 8 AnswersUse a hash map to make a connection between the original list and the new list. ListNode* deepCopy(ListNode *head){ if(head == NULL) return NULL; ListNode* hd= new ListNode(head->label); unordered_map table; table[head] = hd; ListNode *p1 = head->next, p2 = hd; while(p1){ p2->next = new ListNode (p1->label); p2 = p2->next; table[p1] = p2; p1 = p1->next; } p1 = head; while(p1){ table[p1]->random = table[p1->random]; p1 = p1->next; } return hd; } Can you provide java implementation? Java version of the given solution above. (This is just a translation of the C/C++ solution above. I have not analyzed the solution in any way.) ListNode deepCopy(ListNode head) { if (head == null) { return null; } ListNode hd = new ListNode(head.label); Map table = new HashMap(); table.put(head, hd); ListNode p1 = head.next, p2 = hd; while(p1 != null) { p2.next = new ListNode(p1.label); p2 = p2.next; table.put(p1, p2); p1 = p1.next; } p1 = head; while (p1 != null) { table.get(p1).random = table.get(p1.random); p1 = p1.next; } return hd; } Show More Responses Dude its a non optimal solution. Do in one iteration please Nikhil can you share the code to do in one iteration without changing the source linkedlist? I think you can treat this like a cyclic map with 2 child nodes per node, and do a depth first search and keep track of nodes that have already been "seen" public static Node deepCopy(Node n) { if (n== null) return null; return deepCopy(n, new HashMap()); } public static Node deepCopy(Node n, Map seen){ if (node == null) return null; if (seen.contains(n)) return seen.get(n); Node tmp = new Node(); tmp.next = deepCopy(n.next, seen); tmp.rand = deepCopy(n.rand, seen); seen.put(n, tmp); return tmp; } Deep copy => modifying one of the objects does not change the data on the other object. You could always provide copy constructors for the object in the list and the node in order to handle deep copy of data Cannot remember the Java syntax so here is come code: class CA { public CA(CA obj) { // do a deep copy of an object by providing a copy constructor } Node node { CA data; Node next; public Node(Node nd) { data = new CA(nd.data); next = null; } } List list { Node head; void Add(Node n) { //code to add to the list } } List copyList(List list) { List copyList = new List(); Node n = list.head; while(n != null) { Node newNode = new Node(n); copyList.add(newNode); n = n.next; } return copyList; } One or more comments have been removed. |
Software Development Engineer at Amazon was asked...
How would you find the pairs of numbers that added to some specific number in an array. 7 Answersi program in java..so i will talk from the arrayLists perspective. suppose we want to find out a+b = 123; for(int i=0; i2000 records.but below that, sorting and above operation is efficient. you must play with different possibilities. Your answer (using arrayList.indexOf(...)) is worse than sorting. Sorting is O(log n), finding an item in an unsorted array using ArrayList.indexOf is O(n). Given an unsorted array input (e.g. int[] input), sort it using Array.sort(input) ... this is O(log n). Start at input[0] of the sorted array and calculate it's complementary value. Go to the end of the array and iterate backwards until you find the complementary value or less. If it's less repeat for input[1] and iterate backwards from the previous last item ... keep going. This is at worst proportional to n/2, ie O(n). I realize I wasn't totally clear in my first paragraph ... searching for the complementary value of one item is O(n), but you have to the search for (at worst) every item, so your solution is O(n^2). Show More Responses Duh - sorting is O(nlog n) ... Using hashing, this can be done in O(N). store the n/2 mod i in the corresponding hash bucket. Now check the each hash bucket and you are done. sort the array (o(n(log(n)) and take two pointers at both the ends say p1 and p2 if p1+ p2 move the pointer p2 by 1 and add to check if (p1+p2) > n -> move the pointer p1 by 1 and add to check if (p1+p2) = n ->print the pair [traversal takes o(n)] finally thus can be done in o(n) I will not waste o(nlogn) in sorting the array. Instead assuming that the sum we looking for is k, i will divide the array into 2 arrays. First array will contain all values which are less than k/2 Second array will contain all values > k/2 This is bcoz in a sum if one number is less than k/2, the other has to be larger. I will iterate over the smaller array of the 2 since they would rarely be equal. For each x in array 1, i will find the k-x in array 2. Complexity will be O(n). |
Software Engineer at Yelp was asked...
Main Technical Question: Write a function that takes as input an array of words input => ['cat', 'star', 'act', 'god', 'arts', 'dog', 'rats'] and returns a sorted array output => ['cat', 'act', 'god', 'dog', 'start', 'arts', 'rats'] 6 Answershttp://stackoverflow.com/questions/15045640/how-to-check-if-two-words-are-anagrams-in-java Below is a pythonic implementation of the same, assumption is we are allowed to built-in sorted method. words = ['cat', 'star', 'act', 'god', 'arts', 'dog', 'rats'] print sorted(words,key=lambda x:sorted(x)) Below is a pythonic implementation of the same, assumption is we are allowed to built-in sorted method. words = ['cat', 'star', 'act', 'god', 'arts', 'dog', 'rats'] print sorted(words,key=lambda x:sorted(x)) Show More Responses Follow senthill comment, I think they need another step of sorting based on the length. words = ['cat', 'star', 'act', 'god', 'arts', 'dog', 'rats'] words = sorted(words,key=lambda x:sorted(x)) sorted(words, key=lambda x:len(x)) public static void insertionSort(String[] arr) { for(int i=1;i arr[j+1].length()) { String temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; } } return arr; } import java.util.ArrayList; import java.util.Arrays; import java.util.HashMap; import java.util.Iterator; import java.util.Set; public class Anagrams_Yelp { public Anagrams_Yelp() { String[] words = {"masterschool","cat", "star", "act", "god", "arts", "dog", "rats","schoolmaster"}; printAnagramsTogether(words); } private void printAnagramsTogether(String[] words) { ArrayList finalList = new ArrayList(); HashMap> map = new HashMap>(); for (int i = 0; i list = map.get(myString); list.add(str); map.put(myString, list); }else{ ArrayList list = new ArrayList(); list.add(str); map.put(myString, list); } } Set keySet = map.keySet(); Iterator objIterator = keySet.iterator(); while(objIterator.hasNext()){ ArrayList list = map.get(objIterator.next()); finalList.addAll(list); } int i = 0; while(i |
QA Engineer at Salesforce was asked...
Another question was: what's the difference between an abstract class and an interface. Can a class inherit both from an abstract class and an interface at the same time? 6 AnswersThe answer is yes in C++ but no in Java. Uh, this question is as dumb as the first answer. A Java class can extend at most one class, and implement one or more interfaces. A combination of the above is allowed. I agree with the 2nd post Show More Responses Yes, In java class can`t have more than one super class but it can extend a super class and implement interface at one time. See this for differences between abstract class and interface, the first part of the question: http://www.interview-questions-java.com/abstract-class-interface.htm Difference between interface and abstract is , abstract can contain both abstract and non-abstract that is concrete methods, but interface has only all abstract methods....and i agree with ans 2 |
Java Programmer at Barclays was asked...
Assume there is a method provided getNextperson() which gives Person objects which have comparable interface implemented, now read from a file records and sort it and give first 1000 records, write code on the paper 7 Answersmaybe use tree data structure tree data structure ? i hope u meant to say "TreeSet"; but the question doesnt say that getNextPerson() will be unique. So let us not bank on treeSet. So just add them on to a arrayList and do a Collections.sort(arrayList); The question is actually quite simple since you were given that Comparable interface is already implemented (eg, public int compareTo(Object o) method is overridden in Person object). First step, 'read from a file all records' and store each Person object returned by getNextPerson() in List records = new ArrayList(). Next step, call Collections.sort(records) to sort (by criteria specified in compareTo() method, such as Last and First name, or any other meaningful parameter). Final step, 'give first 1000 records' -- either by iterating over first 1000 (checking size() >= 1000) or by returning the list consisting of only 1000 records (either copy into a new list with size 1000 or by using removeRange method in ArrayList. Show More Responses How would you read a 2GB file and put in a arraylist and then sort it? assuming memory constraint Use a heap based data structure(min or max) to keep replacing the root once you have a 1000 records. java priority queue. Using heap is the rightapproach. Array list approach wont work if the file is so huge. Implementing heap using array to store the top 1000 records. (note: since the person implements comparable, we just have to compare the new person with root node i.e index 0 in heap. if root is already greater than new person, just skip the new person else add it as root and call heapify). Finally we can call the Arrays.sort on heap and return the result. One or more comments have been removed. |
Software Engineer at Tripadvisor was asked...
Given four coins that could have any value (i.e. $.17, $.07, $.05, $.01), come up with an algorithm that figures out the fewest number of coins to get that value. 6 AnswersBuild a tree where the root node value is the amount you are trying to solve. Off of that node make a new node for for the amount with the value of each coin subtracted off. Do this recursively until until all solutions are found then do a breadth first search until you get to a leaf. for each coin x=value of coin int q=x/25 int d=(x%25)/10 int n=((x%25)%10)/5 int p=((x%25)%10)%5 return (q+d+n+p) Sorry. My description was a little ambiguous. I didn't mean using a quarter, dime, nickel, and penny. The coins themselves could have arbitrary values. For example, Coin A is worth 16 cents, Coin B is worth 9 cents, coin C is worth 4 cents, and coin D is worth 1 cent. Now using coins A, B, C, and D, find the fewest amount of coins to get to value X. Now the typical reaction is to subtract the largest coin from the total until the total is less then the value of that coin, repeat with the next smallest coin, and so on and count up the coins (like how the previous poster solved it). But that solution doesn't always work. Given the coin values described above, get the fewest coins for value X=18. This algorithm would result in 1 coin A and 2 coin Ds for a total of three coins but the correct answer is 2 coin Bs. The original solution with the tree and breadth first search is the way to get this answer. Show More Responses I think use dynamic programming to solve this problem is quite easy. In Java: static int pickCoins(int valueIn, int[] coinsIn) { if (valueIn == 0) return 0; int num = 0; Set first = new HashSet(), second = new HashSet(), temp; first.add(valueIn); while (!first.isEmpty()) { num++; for (int i : first) { for (int j : coinsIn) { if (i-j == 0) return num; else if (i-j > 0) second.add(i-j); } // for-coinsIn } //for-first // swap first and second temp = second; first.clear(); second = first; first = temp; } //while return -1; } //pickCoins() public static int totalNum(int valueIn, int[] coinsIn){ Arrays.sort(coinsIn); int num = 0; for(int i = (coinsIn.length-1); i >= 0; i--){ num += valueIn/coinsIn[i]; valueIn = valueIn % coinsIn[i]; if (valueIn == 0) return num; } return -1; } From main: int[] coins = { 1, 7, 5, 11 }; int amount = 100;// $1 tatalNum(amount, coins) |