Forward Deployed Engineer Interview Questions
498
Forward Deployed Engineer interview questions shared by candidates
Merging of Sets: Sets Users which reference other user groups.
6 AnswersMax sum subsequence of an array
4 Answers↳
Iterate through that array and comparing the current sum to the maximum sum. If the sum becomes negative at some point, reset it to zero since the maximum sum of the forthcoming elements cannot be larger if you include the negative partial sum. That way, you can solve the problem in O(n) time. It can be speeded up by restarting a new partial sum only on a positive element (or the up to that point largest negative element, which captures the case that all elements are smaller than zero). Less
↳
Most of the answers here are wrong (or perhaps the question is wrong, and a subarray is actually wanted instead). In a subsequence, the array elements do not have to be contiguous, hence simply sum up all the positive numbers in the array. Less
↳
Assuming that array contains positive or negative real numbers. (If numbers are only positive, max sum subsequence is obviously the entire array) O(n log n) divide-and-conquer solution outline: 1. Recursively halve the array into array slices of unit 1. 2. Merge array slices, maintaining the totals and start/end indices of 4 types of subsequences: subsq1. The subsequence that contains the greatest sum within the slice subsq2. The subsequence that contains the greatest sum within the slice and that ends at the rightmost cell of the slice subsq3. The subsequence that contains the greatest sum within the slice and starts at the leftmost cell of the slice subsq4. The entire slice While merging 2 slices together update these slices as follows, 1. max(leftSlice.subsq1, rightSlice.subsq1, leftSlice.subsq2 + rightSlice.subsq3) 2. max(rightSlice.subsq2, leftSlice.subsq2 + rightSlice.subsq4) 3. max(leftSlice.subsq3, rightSlice.subsq3 + leftSlice.subsq4) 4. leftSlice.subsq4 + rightSlice.subsq4 When all the array slices are merged, subsq1 will give you the greatest subsequence. We cannot do better than O(n) because we will have to access each element. We probably cannot do better than O(n log n) because we will have to eventually compare subsequence candidates. Less
I have 100 bottles of wine. 1 is poisoned. I have 10 rats. My guests are coming in an hour but the poison takes 45 minutes to kick in and "kill" a rat. How do I test for and find the 1 bottle of poisoned wine?
4 Answers↳
Trivial, for each rat take 10 bottles (rat 1 gets 1-10, 2 gets 11-20....) and feed them a sip from the first bottle, and then the next bottle after a minute, 3rd bottle 2 minutes...etc. If rat n dies after 45+x minutes, bottle 10*n+x is poison Less
↳
label the rats 0 .. 10 label the bottles 0..99 Now, for each bottle: 1) Convert the bottle label to binary number. 2) From the converted number, feed the rats that have their labeled bit set to 1 and leave the rest. (For example: for bottle 2, you will feed rat labeled 1 only) After 45 minutes, check the rats and convert back to decimal. The dead rats are set to 1 and the alive are set to 0. You will get the bottle number. Both this and above solution works for this problem. The above solution works if you have some time freedom and can detect more than one poisoned bottle. This solution can only detect one bottle but works with restricted time. Less
↳
Why open all the wine ! Just open a few bottles and give a bit of each to the first few rats. As long as the rat lives, it's OK. Saves on wine and you'll have more rats for next time. Less
Rotate the letters of a word by k, using only 1 extra byte of storage.
3 Answers↳
If I got it right you should be able to do something like this, having k=2: abcde -> deabc In order to do so you have to repeat k time this loop: swap first letter with last one, swap second letter with the last one etc... so if you run this loop the first time you will have eabcd, since you started with abcde -> ebcda -> eacdb -> eabdc -> eabcd, then if you run the loop for the second time (since k=2) you will have eabcd -> dabce -> debca ->deacb -> deabc Less
↳
Using above example abcde: reverse elements after k: abced reverse elements before k: cbaed reverse entire array: deabc Then that one extra byte you're allowed can be used to store the temporary char while swapping elements. Otherwise everything else is done in place. Less
↳
Convert the string to its binary representation. Repeat k times: store the lowest byte in a temporary variable. Shift the string right by 1 byte ( >> 8). Set the highest byte of the string equal to the temporary value. Less
Title Case the given input. Main goal was to check the memory efficiency.
3 Answers↳
def titleCase(str_): return ' '.join(map(lambda x: chr(ord(x[0]) ^ ord(' '))+x[1:], str_.split(' '))) Less
↳
If strings aren't immutable in your language, the most memory efficient way is to iterate over the string using "indexof(" ",indexOfLastSpace+1)" then replace that exact character by its upper case equivalent. Finding the uppercase equivalent can be done by an helper function like "ToUpper" or is easy to do by yourself if needed (see previous comment with 'A'-'a' which returns by how much you need to increment the char at the position -- also make sure that char is actually a letter by comparing to 'a' and 'z'). Less
↳
public String titleCase(String str){ String[] strar = str.split(" "); StringBuilder strbldr = new StringBuilder(); for (String a : strar) { char [] charArray = a.toCharArray(); charArray[0] = (char)(charArray[0] - ('a' - 'A')); strbldr.append(charArray); strbldr.append(' '); } return strbldr.toString().trim(); } Less
Q: How can you tell if a Linked List is a Palindrome?
3 Answers↳
First ask if this is a double linked list. If double linked list, simply keep two pointer. One at beginning another at end. Iterate both pointer in each direction and compare at each step. If list is a singlely linkedlist. I would use recursion and pass the head node to the end of the recursion stack call. Compare the head node with the end node at the recursion stack. As the recusion call return, continue advancing the head node with the node in the stack. Less
↳
If it's a singly linked list you can divide the list into two halves, and reverse one, compare if they're the same. This would be in O(n) with O(1) space Less
↳
...poorly. Live and learn!
Given an input string, print out the N most common characters in that string.
2 Answers↳
import java.util.*; public class freq { public static void frequency(String str, int N) { Map sortedFreqCount = new TreeMap(); for(int i = 0; i entry : sortedFreqCount.entrySet()) { if(printCount == N) break; Character key = entry.getKey(); Integer value = entry.getValue(); System.out.println(printCount + ".) " + key + " -> " + value); printCount++; } } public static > Map sortByValues(final Map map) { Comparator valueComparator = new Comparator() { public int compare(K k1, K k2) { int compare = map.get(k2).compareTo(map.get(k1)); if (compare == 0) return 1; else return compare; } }; Map sortedByValues = new TreeMap(valueComparator); sortedByValues.putAll(map); return sortedByValues; } public static void main(String[] args) { String test = "aaaaaaaaaaaaaaaaaaakkkkkkkkkkkkkkkkkkkddddddddddddhhhhhhhhhbbbbbbbeeeewqqqer"; frequency(test,10); } } Less
↳
Iterate through the string and save each character inside and hashmap, if the character exists already in the map just increase its number of occurrences. once you're done with registering the occurrences of each char, iterate through the map and while iterating create a linked list ordered in decreasing order. Than take the first N elements of the list. The time total time complexity is O(n) with n being the length of the string. This is because all the other operations have a constant time, since you cannot have more than 256 different chars, independently from the lenght of the string. Less
Given a pointer to an element in a singly linked-list, how can you delete the element from the list?
3 Answers↳
the tricky part in thw questions is that you dont have any pointer to the root of the list. You only have access to the element you want to remove. So you have to copy the data from the next node, element.data=element.next.data and then element.next=element.next.next in doing this you "removed" the element from the list. I hope this is clear Less
↳
Copy the data from the node ahead of the element that has to be deleted and make the current element poi to next->next. Less
↳
Since we have pointer to the element we want to delete and can't go back to it's parent we need to walk the List from the beginning and check current->next == selectedNode once we find a match then all we have to do is current->next = selectedNode->next an example: ROOT > A > B > C > D > E > NULL selectedNode = C while(node != null) { if (node->next == selectedNode) { node->next = selectedNode->next } node = node.next } Less
How would you program a computer to shuffle a deck of cards? (Generate a permutation of the numbers from 1 to 100, uniformly at random)
3 Answers↳
I think you can use some group theory to solve this as well. Pick random number a in [0,51]. Pick another number b in [1,51] such that the gcd(52,b) = 1. The nth card in the permutation is the card at the index given by a+bn % 52, where % means modulus. i.e. nth index = a+bn (mod 52) In addition, this method works for any permutation of any length (assuming random distribution of b values). Less
↳
Easy way : assign a random number to each card (O(n), possibly by using an intermediate object of some kind like a Tuple), sort by this random number (O(n.log(n)) and you're done (final complexity O(n.log(n))). I don't see a more efficient way to do it without breaking the random distribution, but a deck of cards rarely have more than k*52 cards (with k small), so it wouldn't really matter anyway in the real world. Less
↳
Make array of numbers from 1 to 52. Go through each of cards each time removing one number randomly chosen from array and assigning it to the card. Sort the cards by numbers assigned to cards Less
Please write a generic function that performs a specific operation on time series data.
3 Answers↳
On a white board in code format.
↳
Hi Please elaborate the question more like what language and what were they looking for exactly. Thanks Less
↳
Will you kindly suggest some resources for getting past the Technical screening part? I failed the Tech. Screening. But, I have a chance to attempt the interview one other time next month. Any inputs will be extremely helpful for getting past the Tech Screen this time around. Thank you. Less