# 72K

Sollicitatievragen voor Senior Developer gedeeld door sollicitanten

## Meest gestelde sollicitatievragen

Sorteren: Relevantie|Populair|Datum
Er werd een Senior Software Engineer gevraagd...14 juli 2009

### Given an array of numbers, replace each number with the product of all the numbers in the array except the number itself *without* using division.

34 antwoorden

It seems to me that for any number array[i], you're looking for PRODUCT(all array[j] where j i]) we can simply precompute these "running products" first from left-to-right, then right-to-left, storing the results in arrays. So, leftProduct = array; for j=1; j = 0; j-- rightProduct[j] = rightProduct[j+1]*array[j]; then to get our answer we just overwrite the original array with the desired product array = rightProduct; array[n-1] = leftProduct[n-2]; for j=1; j &lt; n-1; j++ array[j] = leftProduct[j-1] * rightProduct[j+1] and clearly this solution is O(n) since we just traversed the data 3 times and did a constant amount of work for each cell. Minder

betterStill, I think you have the answer the interviewer wanted.. But... if the array is google sized, don't we have to worry about overflows? Minder

narya trick is good but really useful as it might take more iterations depending on values... eg. 2,3,1000000000000000 so if you have 3 numbers and if you are trying for the first one it will go for 500000000000000 iterations, hence as the overall product value wrt to the value matters a lot... try something else.... Minder

Meer reacties weergeven

### Coderpad: given an array scores[][] = {“jerry”,”65”},{“bob”,”91”}, {“jerry”,”23”}, {“Eric”,”83”}} Find the student with highest average score

19 antwoorden

package Hello; import java.util.Comparator; import java.util.HashMap; import java.util.Map; import java.util.Map.Entry; import java.util.Optional; import static java.util.Comparator.comparingInt; public class hello { public static class Average { public int count; public int num; public int average; public Average(int count, int num, int average) { super(); this.count = count; this.num = num; this.average = average; } public Average() { super(); } } public static void main(String[] args) { String s[][] = {{"jerry","65"}, {"bob","91"}, {"jerry","23"}, {"Eric","83"}, {"bob","10"}}; Map map = new HashMap(); int avera = 0; try { for(String x[]:s) { if(map.containsKey(x)) { Average avg = map.get(x); int val = avg.num + Integer.parseInt(x); int count = ++avg.count; int average = val/count; map.put(x, new Average(count, val , average)); } else { if(x != null) { int val = Integer.parseInt(x); map.put(x, new Average(1, val, val )); } } } avera = map.entrySet() .stream() .max(comparingInt(e -&gt; e.getValue().average)).get().getValue().average; } catch(Exception e) { } System.out.println(avera); } } Minder

public class BestGrade { public static void main(String[] args) { String student[][] = {{"jerry","65"}, {"bob","1"}, {"jerry","23"},{"jerry","23"}, {"jerry","100"},{"Eric","83"}}; //Map counter = new HashMap(); List score = new ArrayList(); Map&gt; map = new HashMap(); for(int i = 0;i(); score.add(Integer.parseInt(student[i])); map.put(student[i], score); } } List grade = new ArrayList(); for(String key:map.keySet()) { score = map.get(key); int sum = 0; for(int num : score) { sum+=num; } int average = sum/score.size(); grade.add(average); } Collections.sort(grade); System.out.println(grade.get(grade.size()-1)); } } Minder

import java.util.*; import java.util.stream.Collectors; class Student{ private String name; private Float averageMark = 0.0f; private int numberOfSubjects = 0; public Student(String name){ this.name = name; } public void addMark(Float mark ){ averageMark += mark; numberOfSubjects += 1; averageMark = averageMark/numberOfSubjects; } public Float getAverageMark(){ return averageMark; } public String getName(){ return name; } public Student(Float mark, String n){ name = n; averageMark = mark; } } public class MaxScore { public static String s[][] = {{"jerry","65"}, {"bob","91"}, {"jerry","23"}, {"Eric","83"},{"Eric","99"}}; public static void main(String args[]){ Map studentMap = new HashMap(); for(int i=0; i studentList = studentMap.values().stream().collect(Collectors.toList()); Collections.sort(studentList, Comparator.comparing(Student::getAverageMark).reversed()); System.out.println(studentList.get(0).getName()); } } Minder

Meer reacties weergeven

### Consider an X x Y array of 1's and 0s. The X axis represents "influences" meaning that X influences Y. So, for example, if \$array[3,7] is 1 that means that 3 influences 7. An "influencer" is someone who influences every other person, but is not influenced by any other member. Given such an array, write a function to determine whether or not an "influencer" exists in the array.

12 antwoorden

public static int influencer(final int[][] jobs, final int r, final int c) { int[] degree_in = new int[jobs.length]; int[] degree_out = new int[jobs.length]; for (int i = 0; i &lt; r; ++i) { for (int j = 0; j &lt; c; ++j) { if(jobs[i][j] == 1) { // i influences j degree_out[i]++; degree_in[j]++; } } } for (int i = 0; i &lt; r; ++i) { if (degree_out[i] == r - 1 &amp;&amp; degree_in[i] == 0) { return i; } } return -1; } Minder

//if vec[i][j] == 0 then i is not an influence //if vec[i][j] == 1 then j is not an influence //so time complexity is O(n) bool find_influences(vector &gt; &amp;vec) { int n = vec.size(); vector not_influence(n); for (int i = 0; i = 0; --j) { if (!vec[i][j]) { break; } not_influence[j] = 1; } if (j &lt; 0) { return true; } } not_influence[i] = 1; } return false; } Minder

X should be equal to Y, right?

Meer reacties weergeven

### Write a probability formula to tell how many bits will be changed when 1 is added to a 32 bit binary number.

11 antwoorden

The probability of N bits being changed is (1/2)^N. The reason: the number of bits that will change depends on the position of the first zero that appears in the number. If the first zero is at the LSB, only one bit changes; if it is in the third position, the three bits upto the first zero change. Now, it boils down to the probability of finding the first zero. Assuming that the zeros and ones appear with equal probability in a given number, the probability of finding the first 0 in the Nth position is (1/2)^N. For more, look up the Geometric Random Variable. Minder

I think that you need to take into account that if you want to toggle 2 bits, you can only do if you flip bits from position 0..30. Toggling bit 31 is only going to toggle this bit no matter what. Therefore, you need to multiply (33-N)/32 to your proposed result, to keep this into account. Minder

@Mythreya's analysis is correct but incomplete. To get the expected value, you have to multiply the number of bits by their probability. Answer is Sigma{k/(2^k)} for k = 1 to 32. Minder

Meer reacties weergeven

### Write some pseudo code to raise a number to a power.

11 antwoorden

int raise(num, power){ if(power==0) return 1; if(power==1) return num; return(raise(num, power-1)*num); } Minder

small mistake function power(x, n) { if n == 1 return x; // Even numbers else if (n%2 == 0) return square( power (x, n/2)); // Odd numbers else return power(x, n-1) * x; } Minder

double Power(int x, int y) { double ret = 1; double power = x; while (y &gt; 0) { if (y &amp; 1) { ret *= power; } power *= power; y &gt;&gt;= 1; } return ret; } Minder

Meer reacties weergeven

### In a stream of integers from 1 to n, only one number will be repeated. How can you tell what that number is?

11 antwoorden

You know n. S = n*(n+1)/2 is the sum of 1st n numbers. P = sum of the n+1 numbers you are provided with. Finding P given an array of n+1 integers can be done in O(n). P - S is the repeated integer. Minder

If you're writing it in ruby def find_repeat(numbers) numbers.length.times{|n| return numbers[n] if numbers[n] != n } end Minder

Mat, try 1,2,2,3: 1+2+2+3= 8 1^2^2^3= 2 (8-2)/2=3?2

Meer reacties weergeven

### Create a stack of numbers where the maximum number is always known.

10 antwoorden

To Job Seeker: The basic idea is that when a new number is being pushed onto the stack, you need to see if that number is greater than or equal to the current top of the maximums-stack. If it is, you push the number onto maximums-stack as well. Also, when pop is called, you look to see if the number being popped is equal to the number on the top of the maximums-stack. If it it, pop that stack as well. Minder

sorry, typo while(top&gt;p)

I was asked of this question as well. I not sure how to implment a second stack in a way that the max number is always on top. Minder

Meer reacties weergeven

### Traverse nodes in a binary tree

11 antwoorden

What is taught in compsci, and even what's in Knuth, isn't entirely right on modern out-of-order execution core CPUs Minder

void traverse(Node node){ if(node == null) return null; System.out.println(node.data); traverse(node.left); traverse(node.right); } Minder

It can't be that this candidate really serves on a language committee. I find it difficult to believe that someone who serves on a language standards committee doesn't care about the difference between an O(N^2) and an O(logN) solution, for that would be horrifying indeed. And in defense of the employee conducting the interview, if I did see a candidate that didn't care about the difference between the two, I really wouldn't care what they have on their resume. They could be a Turing award winner for all I would care. There's a valid point about spatial locality, etc, but for something like N = 10^6 (for example), I'll take even O(logN) disk reads (*gasp*), over N^2 quick register operations any day.. Minder

Meer reacties weergeven

### There will be a meeting at New York and San Francisco offices. We will have to fly the participants to either one of these two offices. Let's say each office can accommodate half of the participants. Our goal is to assign each participant to an office in a way that the total travel cost for the company is minimized. What is this minimal cost? SF NY A 500 700 B 200 600 C 400 500 D 600 200 Output : 1400 (A:500 + B:200 + C:500 +D: 200)

10 antwoorden

Can you give an high level solution which you arrived at the end? I am curious to know the solution 😊 Minder

The solution was something like: Look for the candidates that have a bigger difference in cost first (in this case B and D since the difference for the price to each office are 400), choose the cheaper option for those. After one of the offices is full then just choose whatever spot is left. Minder

I would use a Min Heap for SF of size = no. of candidates / 2 . k = no. of candidates / 2 ; for(int i : SFcosts){ minHeap.offer(i); if(minHeap.size() &gt; k){ minHeap.poll(); } } // so at the end we have half candiates with minimum cost for SF then remaining will go ti NY Minder

Meer reacties weergeven

### How many golf balls can fit in a school bus?

10 antwoorden

Depends how big the school bus is, for simplicity, lets say its the small bus that can fit 20 + 1 people. You have to take account of the empty space as well, therefore a person could be sitting in the middle line and three more in the front so we have around 30 people making a full squished bus. The average size of a golf ball is around 3 cm in diameter. The height of the bus is usually 200 cm, the width of an average person is usually 50 cm. The depth of the seat is about 70 cm You can calculate the volume of that cubic form to be 50 x 70 x 200 x 3 x 30 = the number of golf balls in average. Minder

Nobody need to actually put golf balls in a school buss , nobody care if the number is 61,000,000 or whatever .Nobody in Google cares how good are you in giving estimates to the size of a buss. The answer is bussWidth*bussHight*bussLength / (ball/Diameter ^ 3 * sin (60) * sin(60) ^2 ) . This answer depends on the size of the school buss, different busses yield different answer. The sin(60) are since its gold balls and not cubics. Minder