Fragen im Bewerbungsgespräch: Software engineer in Region New York, Vereinigte Staaten von Amerika | Glassdoor.de

# Fragen im Vorstellungsgespräch: Software engineer in New York, Vereinigte Staaten von Amerika

12,110

Fragen aus Vorstellungsgesprächen für software engineer, von Bewerbern geteilt

## Top Vorstellungsgespräch-Fragen

Sortieren: RelevanzBeliebtheit Datum

17. Mai 2010

15. Feb. 2010

28. Juli 2009

12. Juni 2009

1. Okt. 2010

### Ein Bewerber für eine Stelle als Software Engineer bei Bloomberg L.P. wurde gefragt...

29. Dez. 2016
 1. Phone interview - Sort the characters in string by frequency and then by their alphabetical order. Example - bbaaccc -> cccaabb 2. The question that screwed me - given array is [0,1,1,0,1,1,1] ; output should be [0,1,1,0,1,2,3] ie., for every non-zero element in array, find its distance to the nearest zero in O(n) time. i would definitely encourage the candidates who read this post to share their solution for this question. 3. In order traversal of Binary search tree related (the solution is to start from right sub tree).16 AntwortenSolution to the second problem (sequence processing, with O(N) time and O(N) space complexity): std::vector getZeroDistance(const std::vector &v) { if (v.size() result; uint64_t cnt = 0; bool flag = false; for (auto &i : v) { if (i == 0 && !flag) { flag = true; if (cnt) { while(cnt) result.push_back(cnt--); } result.push_back(0); continue; } if (i != 0) ++cnt; if (i == 0) { if (cnt == 1) { result.push_back(1); } else { uint64_t mid = cnt / 2; for (uint64_t t = 0; t 0; --mid) result.push_back(mid); } result.push_back(0); cnt = 0; } } // If no zeros in input string found, return input string; if (!flag) return v; if (cnt > 0) { if (cnt == 1) result.push_back(1); else { for (uint64_t t = 1; t v = { 0,1,1,0,1,1,1 }; // expected: [0,1,1,0,1,2,3] std::vector v = { 1,1,1,1,1,1,1 }; auto res = getZeroDistance(v); return 0; }std::vector getZeroDistance(const std::vector &v) { if (v.size() result; uint64_t cnt = 0; bool flag = false; for (auto &i : v) { if (i == 0 && !flag) { flag = true; if (cnt) { while(cnt) result.push_back(cnt--); } result.push_back(0); continue; } if (i != 0) ++cnt; if (i == 0) { if (cnt == 1) { result.push_back(1); } else { uint64_t mid = cnt / 2; for (uint64_t t = 0; t 0; --mid) result.push_back(mid); } result.push_back(0); cnt = 0; } } // If no zeros in input string found, return input string; if (!flag) return v; if (cnt > 0) { if (cnt == 1) result.push_back(1); else { for (uint64_t t = 1; t <= cnt; ++t) result.push_back(t); } } return result; }First solution has been posted with wrong format. In the second one, 2 lines should be corrected: instead of this if (v.size() result; should be: if (v.size() result;Mehr Antworten anzeigenFirst solution has been posted with wrong format. In the second one, 2 lines should be corrected: instead of this: if (v.size() result; should be: if (v. size() result; std::vector result;#include #include #include using namespace std; int main() { vector v = {0, 1, 1, 0, 1, 1, 1, 0}; vector dist(8, 0); vector zeros_pos; for(int i = 0; i < v.size(); i++) { if(!v[i]) { zeros_pos.push_back(i); } } int fz = zeros_pos[0]; int sz = zeros_pos[1]; int j = 2; for(int i = 0; i < 8; i++) { dist[i] = min(abs(i - fz), abs(i - sz)); if(i == sz) { fz = sz; if(j < zeros_pos.size()) { sz = zeros_pos[j]; j++; } } } for(auto& iter : dist) cout << iter << " " ; return 0; }std::vector dist(std::vector& value) { std::vector pin; std::vector output(value.size()); bool found = false; int last_zero = -1; for (size_t i = 0; i < value.size(); ++i) { if (value[i] == 0) { int rewind = (last_zero == -1)?i:((i - last_zero) / 2); for (int j = 1; j <= rewind ; ++j) { output[i-j] = j; } last_zero = i; } else { output[i] = (last_zero == -1)?-1:(i-last_zero); } } return output; }Missed the explanation. This is O(n) time complexity with O(1) space complexity. Basically this algorithm iterates through the input vector and records the incremental integers when 0 has been found. When you find 0, trace back to change the distance. If there's no 0 in the input vector, you will see -1 in the distance. This is sort of thing you need to discuss with the interviewer what to do when distance is unknown. std::vector dist(std::vector& value) { std::vector output(value.size()); int last_zero = -1; for (size_t i = 0; i < value.size(); ++i) { if (value[i] == 0) { int rewind = (last_zero == -1)?i:((i - last_zero) / 2); for (int j = 1; j <= rewind ; ++j) { output[i-j] = j; } last_zero = i; } else { output[i] = (last_zero == -1)?-1:(i-last_zero); } } return output; }{{{ vector getMinDistFromZeros(vector A) { int n = A.size(); vector zero_idx(A.size(), INT_MAX); bool atleast_one_zero = false; for (int i = 0; i < n; i++) { if (!A[i]) { zero_idx_map.push_back(i); atleast_one_zero = true; } } if (!atleast_one_zero) { return zero_idx; } for (int i = 0; i < zero_idx.size(); i++) { for (int j = 0; j < n; j++) { if (A[j] != 0) { A[i] = min ( abs ( j - zero_idx[i] ) ); } } return A; } }}} Space Complexity is O(m) where m is num zeros. Run Time: O(n * m)# vector distance calculator: def calc_dist_nearest_zero(vct): curr_zero = -1 curr = 0 dist = [float('inf')]*len(vct) while curr = 0: dist[curr] = abs(curr - curr_zero) curr -= 1 curr = curr_zero + 1 else: if curr_zero != -1: dist[curr] = abs(curr - curr_zero) curr += 1 return distAll of the slutions above are using O(n) space.I believe the correct solution would have 2 indices ( int i1 and int i2 example ) running from each end of the input array and using -1 ( think how ) and as soon as both cross each other ( in the middle , assuming both move one step towatds each other ) then the algorithms gets in action. They start correcting each other. Ofc you will need O(4) or something like that as space complecxity to hold the left and right zero indces and the most recent distance from each of them.O(1) space complexity if we do in-place. Time complexity is O(n) void inplace_dist(std::vector& value) { int last_zero = -1; for (size_t i = 0; i < value.size(); ++i) { if (value[i] == 0) { int rewind = (last_zero == -1)?i:((i - last_zero) / 2); for (int j = 1; j <= rewind ; ++j) { value[i-j] = j; } last_zero = i; } else { value[i] = (last_zero == -1)?-1:(i-last_zero); } } return value; }Here is a O(N) java solution. I use 3 pointers. One for the left zero, one for the right zero, and a main pointer: int leftZero = 0; int rightZero = leftZero; int[] newElements = new int[elements.length]; while(rightZero < elements.length){ if(elements[rightZero] == 0) break; rightZero++; } leftZero = rightZero; for(int i = 0; i < elements.length; i++){ if(rightZero == i){ leftZero = i; newElements[i] = 0; while(true){ if(rightZero == elements.length - 1){ rightZero = Integer.MAX_VALUE; break; } rightZero++; if(elements[rightZero] == 0) break; } } else { newElements[i] = Math.min(Math.abs(i - leftZero), Math.abs(i - rightZero)); } } return newElements;Mehr Antworten anzeigen-> traverse left to right and make a temp1 array -> traverse right to left and make a temp2 array -> pick lower number at every index from temp1 and temp2 array to make result arraydef findAndSetNearestDist(arr): n = len(arr) lastZeroIndex = -1 for index, a in enumerate(arr): if a == 0: if lastZeroIndex == -1: lastZeroIndex = index continue else: twoZeroDistance = index - lastZeroIndex for i in range(int((twoZeroDistance/2) + 1), index): arr[i] = abs(index -i) lastZeroIndex = index continue if a > 0 and lastZeroIndex != -1: dist = index - lastZeroIndex arr[index] = dist return arrdef findAndSetNearestDist(arr): # sliding window approach # from left to right zeroIndex = -1 for index, value in enumerate(arr): if value == 0: zeroIndex = index continue if zeroIndex > -1: arr[index] = index - zeroIndex # from right to left zeroIndex = -1 for index in range(len(arr)-1,-1,-1): value = arr[index] if value == 0: zeroIndex = index continue if zeroIndex > -1: arr[index] = min(abs(index - zeroIndex), arr[index]) return arr

22. Mai 2017

4. Aug. 2010