# Sollicitatievragen voor een engineer

# 620K

Sollicitatievragen voor een engineer gedeeld door sollicitanten## Meest gestelde sollicitatievragen

### want you to write me a simple spell checking engine. The query language is a very simple regular expression-like language, with one special character: . (the dot character), which means EXACTLY ONE character (it can be any character). So, for example, 'c.t' would match 'cat' as the dot matches any character. There may be any number of dot characters in the query (or none). Your spell checker will have to be optimized for speed, so you will have to write it in the required way. There would be a one-time setUp() function that does any pre-processing you require, and then there will be an isMatch() function that should run as fast as possible, utilizing that pre-processing. There are some examples below, feel free to ask for clarification. Word List: [cat, bat, rat, drat, dart, drab] Queries: cat -> true c.t -> true .at -> true ..t -> true d..t -> true dr.. -> true ... -> true .... -> true ..... -> false h.t -> false c. -> false */ // write a function // Struct setup(List<String> list_of_words) // Do whatever processing you want here // with reasonable efficiency. // Return whatever data structures you want. // This function will only run once // write a function // bool isMatch(Struct struct, String query) // Returns whether the query is a match in the // dictionary (True/False) // Should be optimized for speed

22 antwoorden↳

Here is the Python Code (inspired by someone's code on this page): def setUp(word, input_list): word = word.strip() temp_list = [] Ismatch = False if word in input_list: Ismatch = True elif word is None or len(word) == 0: Ismatch = False else: for w in input_list: if len(w) == len(word): temp_list.append(w) for j in range(len(temp_list)): count=0 for i in range(len(word)): if word[i] == temp_list[j][i] or word[i] == '.': count += 1 else: break if count == len(word): Ismatch = True print(Ismatch) def isMatch(word, input_list): return setUp(word, input_list) isMatch('c.t', ['cat', 'bte', 'art', 'drat', 'dart', 'drab']) Minder

↳

bear in mind for your solution, checking the lengths of words in the dictionary is very fast. That's what you can use your setup for. There's no need to iterate through the whole loop of checks if the word fails the length already. See my solution above Minder

↳

This was the fastest I could do without regex: def func(wrd,lst): if len(wrd) not in [len(x) for x in lst]: return False elif wrd in lst: return True else: lst1 = [x for x in lst if len(x)==len(wrd)] for z in lst1: c=0 for i in range(len(wrd)): if wrd[i] != '.' and wrd[i] == z[i]: c=c+1 if len(wrd)-wrd.count('.') == c: return True return False Minder

### Given input: // could be potentially more than 3 keys in the object above items = [ {color: 'red', type: 'tv', age: 18}, {color: 'silver', type: 'phone', age: 20} ... ] excludes = [ {k: 'color', v: 'silver'}, {k: 'type', v: 'tv'}, .... ] function excludeItems(items, excludes) { excludes.forEach(pair => { items = items.filter(item => item[pair.k] === item[pair.v]); }); return items; } 1. Describe what this function is doing... 2. What is wrong with that function ? 3. How would you optimize it ?

22 antwoorden↳

I agree with converting the excludes to an object, but in order to get linear performance that doesn't depend on the number of excluded things, you have to concatenate the k and v into one value to be used as the key in the object: let excludesObject = {}; excludes.forEach(pair => excludesObject[`${pair.k}_${pair.v}`] = true); Then you can check if an item should be excluded in O(k) time where k is the number of keys in an item. And the whole thing will run in O(nk) where n is the number of items. // if there is some key which is found in the excludesObject, the filter will return false items = items.filter(item => !Object.keys(item).some(key => excludesObject[`${key}_${item[key]}`]); ); Facebook, hire me! lol Minder

↳

I guess there's a typo in the question? I don't really get the purpose of "item[pair.k] === item[pair.v]" Minder

↳

If the objetive is exclude the elements using the excludes filters the function should be: function excludeItems(items, excludes) { excludes.forEach(pair => { items = items.filter(item => item[pair.k] !== pair.v); }); return items; } Minder

### A dwarf-killing giant lines up 10 dwarfs from shortest to tallest. Each dwarf can see all the shortest dwarfs in front of him, but cannot see the dwarfs behind himself. The giant randomly puts a white or black hat on each dwarf. No dwarf can see their own hat. The giant tells all the dwarfs that he will ask each dwarf, starting with the tallest, for the color of his hat. If the dwarf answers incorrectly, the giant will kill the dwarf. Each dwarf can hear the previous answers, but cannot hear when a dwarf is killed. What strategy should be used to kill the fewest dwarfs, and what is the minimum number of dwarfs that can be saved with this strategy?

21 antwoorden↳

Think broadband communication. Exploit the capabilities of the communications medium. A minimum of nine dwarves can be saved based on the information provided in the original post I viewed. The strategy is for each dwarf to employ the expected language to communicate the color of their own hat to the giant, while simultaneously employing a vocal pitch protocol to indicate the color of the hat of the dwarf in front of him, high pitch for white and low pitch for black. The original post, indicates the dwarves may collude prior to the distribution of hats, so there is opportunity to negotiate such a simple broadband communication protocol. The tallest dwarf only has a 50/50 chance since the number of black and white hats in play is not known (rhetorical question, what are the odds the tallest dwarf's hat is black if he turns to find that all nine hats in front of him are white? I don't know, but odds are high that the giant is a sadistic bloke). The original post I viewed is here. http://www.businessinsider.com/toughest-job-interview-questions-2013-7#a-dwarf-killing-giant-lines-up-10-dwarfs-from-shortest-to-tallest-each-dwarf-can-see-all-the-shortest-dwarfs-in-front-of-him-but-cannot-see-the-dwarfs-behind-himself-the-giant-randomly-puts-a-white-or-black-hat-on-each-dwarf-no-dwarf-can-see-their-own-hat-the-giant-tells-all-the-dwarfs-that-he-will-ask-each-dwarf-starting-with-the-tallest-for-the-color-of-his-hat-if-the-dwarf-answers-incorrectly-the-giant-will-kill-the-dwarf-each-dwarf-can-hear-the-previous-answers-but-cannot-hear-when-a-dwarf-is-killed-the-dwarves-are-given-an-opportunity-to-collude-before-the-hats-are-distributed-what-strategy-should-be-used-to-kill-the-fewest-dwarfs-and-what-is-the-minimum-number-of-dwarfs-that-can-be-saved-with-this-strategy-11 Minder

↳

What is the minimum number of dwarfs that can be saved with this strategy? 9 First of all, let's numerate the dwarfs as N1, N2, N3, etc. with N10 being the tallest. Now, N10 will state the color of N9 as his own answer, "My hat is WHITE". Based on this answer, N9 will state his color with a positive statement if the color of N8 is the same as his, "My hat is WHITE". Based on N8's answer, N8 knows that his color is WHITE, now, he will state his color depending on N7. Let's say N7 is black, so N8 will state, "My hat is NOT BLACK". N7 knows that his color is BLACK, but N6 is white, so he will use a negative statement, "My hat is NOT WHITE" and so on. Full example: N10 = BLACK N9 = WHITE N8 = WHITE N7 = BLACK N6 = WHITE N5 = WHITE N4 = WHITE N3 = BLACK N2 = BLACK N1 = WHITE N10: My hat is WHITE (Dies) N9 = My hat is WHITE N8 = My hat is NOT BLACK N7 = My hat is NOT WHITE N6 = My hat is WHITE N5 = My hat is WHITE N4 = My hat is NOT BLACK N3 = My hat is BLACK N2 = My hat is NOT WHITE N1 = My hat is WHITE N10 will have a 50/50 chances of survival... I'm sorry N10, I couldn't save you :'( Minder

↳

the question does not mention that there will be equal number of white and black hats ! Minder

### An array of 99 elements contains integers from 1 to 100 with one missing element. Find the missing element.

20 antwoorden↳

1. calculate the sum of elements in array say SUM 2. sum of numbers 1 to 100 is(n* (n+1))/2 = 5050 when n==100 3. missing element is (5050-SUM) Minder

↳

Sum them and then subtract them from 5050. In general, if an array of size n - 1 elements has unique elements from 1 to n, then the missing element can be found by subtracting the sum of the elements in the array from sum(1 ... n) = n * (n + 1) / 2. Alternately, one could use a boolean array of length n with all values set to false and then for each value, set array[val - 1] to true. To find the missing value, scan through the array and find the index which is set to false. Return index + 1. This requires O(n) memory and two passes over an O(n) array (instead of constant memory and one pass), but has the advantage of actually allowing you to verify whether or not the input was well formed. Minder

↳

Read the question. Here are the steps to solve it: 1) find the sum of integers 1 to 100 2) subtract the sum of the 99 members of your set 3) the result is your missing element! Very satisfying! Minder

### The final round of interview was challenging in terms of how you pick scenarios from your career.

21 antwoorden↳

Out of the 4 scenarios - I realized its better to show both sides of the coin and treaded one positive experience followed by negative experience. It was fulfilling to mention that a mistake was made due to XYZ reasons and was corrected in future assignments. Minder

↳

Hi could you please share your contact number

↳

Hi ABC can u share what kind of techincal question they have asked, r they asked to write program or only oral with usecases? as i am having my interview on next week for java developer. Minder

### Given an array of ints = [6, 4, 0, 5, 0, 0, 0, 1, 0] move all non zero numbers to the left and zeros to the right. How can you now improve your answer to O(n)?

21 antwoorden↳

Just keep pointers to the first and last elements of a new array. private static int[] moveZerosToLeft(int[] arr) { int first = 0; int last = arr.length - 1; int[] newArr = new int[arr.length]; for (int i = 0; i < arr.length; i++) { if (arr[i] == 0) { newArr[last--] = arr[i]; } else { newArr[first++] = arr[i]; } } return newArr; } Minder

↳

Since the order doesn't matter. Keep a separate pointer for your array. iterate through the array, for every 0 you find, swap it with the value at array[k], then increment k. This would be O(n) Otherwise, just sort it and return that. Which is O(nlogn) Minder

↳

O(n) is the best conceivable time for this type of sort Here's one way to solve it: private static void moveZerosToRight(int[] a) { int rightIndex = a.length - 1; int leftIndex = 0; while (leftIndex < rightIndex) { if (a[rightIndex] == 0) rightIndex--; else { if (a[leftIndex] == 0) { swap(a, leftIndex, rightIndex); rightIndex--; } leftIndex++; } } } private static void swap(int[] a, int i, int j) { int temp = a[i]; a[i] = a[j]; a[j] = temp; } Minder

### How long do you plan to work here?

21 antwoorden↳

4 years

↳

As long as possible

↳

I will like to work with you as long as the term of the contract are respected

### Write an algorithm to determine whether a given number is of the form (2^n)+1, where n is an integer.

20 antwoorden↳

return (n == 1) || ((n-1)&(n-2) == 0);

↳

boolean isapower(int pow, int num); int main(){ int num = 2; int pow = 2; if(isapower(pow, num-1)) { printf("%d is power of %d + 1", num, pow); } else { printf("%d is not power of %d + 1", num, pow); } return 0; } boolean isapower(int pow, int num) { while((num > pow) && (num % pow == 0)) { num /= pow; }; return num == pow; } Minder

↳

Sorry. That answer is for checking odd or even. Not power of 2 + 1.

### What is polymorphism?

20 antwoorden↳

Polymorphism means having many forms. In object-oriented programming paradigm, polymorphism is often expressed as 'one interface, multiple functions'. Minder

↳

Polymorphism means having many forms. In object-oriented programming paradigm, polymorphism is often expressed as 'one interface, multiple functions'. Minder

↳

Polymorphism means having many forms. In object-oriented programming paradigm, polymorphism is often expressed as 'one interface, multiple functions'. Minder

### Given the list of points of the skyline of a city in order (from East to West) Find the maximal rectangle contained in this skyline. I was asked to write the code. I managed to find the algorithm but was not sufficient.

20 antwoorden↳

For others' reference: http://www.topcoder.com/stat?c=problem_statement&pm=7473&rd=10661 http://www.topcoder.com/tc?module=Static&d1=match_editorials&d2=srm337 https://www.spoj.pl/problems/HISTOGRA/ http://www.informatik.uni-ulm.de/acm/Locals/2003/html/judge.html Minder

↳

O(n) solution: /* * Basic idea: use a stack to store the buildings. Look at * the buildings in left-to-right order (west to east). If a * building is taller than the building on the top of the stack * (the tallest building to its left), push it onto * the stack. If a building is equal in height to the building on the * top, skip it. If a building is shorter than the building on the top, * it is not part of the maximum rectangle that is topped by the tallest * building to its left. Pop that tallest building, calculate its area and * compare it to the current main area, then repeat the comparison * procedure with the new tallest building. * * Along the way, track the number of buildings to the left and right of a * given building that would participate in that building's maximum * rectangle. The number to the left is equal to the number of buildings * that are popped off the stack before this building is pushed - that is * the number of buildings to the left of this building that are taller. * We do not need to worry about the buildings that are equal in height * since they are discarded (they are accounted for in the topBuilding's * rightWidth count). * * The number of buildings to the right of this building that participate * in this building's maximum rectangle is equal to the number of buildings * that are discarded because they are equal to this building's height * plus the number of buildings that are pushed onto the stack because they * are taller than this building while this building is on the top of the * stack. * * In this input array a, the ith building has height a[i], which means * its lower left corner is at (i,0) and its upper right corner is at * (i+1,a[i]). All buildings have width 1. The total width of the skyline * is n. */ public long getMax_useStack(long[] a){ Stack stack = new Stack(); int n = a.length; long maxArea = 1; // Process the buildings in left-to-right order. for (int i= 0; i < n; i++){ Building nextBuilding = new Building(a[i]); // Keep track of the number of buildings that we pop before we // push nextBuilding. That number will be equal to the number // of buildings to the immediate left of nextBuilding that are // taller in size. int popCount = 0; // If the stack is empty, push the next building onto the stack. // There are no buildings to its left, so we do not need to // update nextBuilding.leftWidth. if (stack.empty()) { stack.push(nextBuilding); continue; } Minder

↳

(cont'd) // Otherwise, compare the new building's height to the building on // the top of the stack until the new building is either // discarded (if it is equal in size) or pushed (if it is taller). while (! stack.empty()){ Building topBuilding = stack.peek(); long heightDiff= nextBuilding.height - topBuilding.height; // If the new building is equal in height, skip it. Increment // the rightWidths count of topBuilding as its largest // rectangle goes through the new building. if (heightDiff == 0) { topBuilding.rightWidth++; break; } // If the new building is greater in height, push it onto the // stack. The number of buildings to the immediate left of it // that are taller is equal to the number of buildings that // were popped before this point, its popCount. Set its // leftWidth equal to its popCount. Increment the rightWidths // count of the top building as its largest rectangle goes // through the new building. if (heightDiff > 0) { nextBuilding.leftWidth = popCount; topBuilding.rightWidth++; stack.push(nextBuilding); break; } // If the new building is less in height, update the maximum area // with regards to the element at the top of the stack. long topArea = topBuilding.getArea(); if (topArea > maxArea){ maxArea = topArea; } // Then discard the top element and repeat the comparison // procedure with the current next building. stack.pop(); popCount++; } } // If all buildings have been processed and the stack is not yet empty, // finish the remaining subproblems by updating the maximum area // with regards to the building at the top of the stack. while (! stack.empty()){ Building topBuilding = stack.pop(); long topArea = topBuilding.getArea(); if (topArea > maxArea){ maxArea = topArea; } } return maxArea; } class Building { long height; int leftWidth; int rightWidth; Building(long y){ this.height = y; leftWidth = 0; rightWidth = 0; } long getArea(){ return height * (1 + leftWidth + rightWidth); } } Minder