Questions d'entretiens - Software engineer

365 k

Questions d'entretien pour Software Engineer partagées par les candidats

Principales questions d'entretien

Trier: Pertinence|Populaires|Date
Snapsheet
On a demandé à Backend Developer...14 août 2015

What is polymorphism?

20 réponses

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

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

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

Afficher Plus de réponses
Google

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 réponses

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 Moins

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; } Moins

(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); } } Moins

Afficher Plus de réponses
Meta

Given an array of positive integers and a target integer, find if there is a consecutive subarray that sums to the target. E.g, given {5,6,4,12}, findsum(10)=true, findsum(11)=false.

19 réponses

Why does findSUm(11) return false? Isn't {5,6} a consecutive subarray?

Java Solution: public static boolean contiguousSubSequenceWithSum(int [] a, int sum) { for(int i = 0 ; i sum) continue; for(int j = i+1; j sum) break; } } return false; } Moins

static boolean process(Integer[] a, Integer target) { for (int i=0; i < a.length; i++) { int j = i+1; int sum = a[i]; while((j Moins

Afficher Plus de réponses
Goldman Sachs

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

19 réponses

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[0])) { Average avg = map.get(x[0]); int val = avg.num + Integer.parseInt(x[1]); int count = ++avg.count; int average = val/count; map.put(x[0], new Average(count, val , average)); } else { if(x[0] != null) { int val = Integer.parseInt(x[1]); map.put(x[0], new Average(1, val, val )); } } } avera = map.entrySet() .stream() .max(comparingInt(e -> e.getValue().average)).get().getValue().average; } catch(Exception e) { } System.out.println(avera); } } Moins

Can anybody please tell, If anything is wrong with this simple approach : public class StudentWithMax { private static class Student { public String name; public Double avg; Student(String n, Double a) { name = n; avg = a; } } public static void main(String[] args) { String[][] s = { { "Jerry", "65" }, { "Bob", "92" }, { "Jerry", "33" }, { "Eric", "83" }, }; Student maxStudent= new Student("", (double)Integer.MIN_VALUE); for (String[] strings : s) { //System.out.println(strings[0]); if(Double.parseDouble(strings[1]) > maxStudent.avg) { maxStudent.name=strings[0]; maxStudent.avg=Double.parseDouble(strings[1]); } } System.out.println("name: "+maxStudent.name + ", avg: " + maxStudent.avg); } } Moins

Solving same problem using Java 8: import java.util.Arrays; import java.util.Comparator; import java.util.List; import java.util.Optional; import java.util.stream.Collectors; public class MaxScore { public static String s[][] = {{"jerry","65"}, {"bob","91"}, {"jerry","23"}, {"Eric","83"}}; public static void main(String[] args) { List arrayOfLists = Arrays.asList(s); List students = arrayOfLists.stream().map(s->new Student(s)).collect(Collectors.toList()); Optional studentWithMaxScore = students.stream().max(Comparator.comparing(Student::getScore)); System.out.println(studentWithMaxScore.get().getScore()); } } class Student{ private final String name; private final int score; public Student(String[] s) { String name = s[0]; String score = s[1]; this.name = name; if(score.matches("-?\\d+(\\.\\d+)?")) { this.score = Integer.parseInt(score); } else { this.score = 0; } } public String getName() { return name; } public int getScore() { return score; } } Moins

Afficher Plus de réponses
Google

Given an array of integers where each element points to the index of the next element how would you detect if there is a cycle in this array?

18 réponses

The problem is imprecisely stated. If every element a[i] contains a value that is an index into a (i.e. a value in the range 0..length(a)), then there *must* be at least 1 cycle, assuming a is of finite size. On the other hand, if a is allowed to contain values that are not valid indexes (negative, or >= length(a)), then it indeed takes some work to determine if a has cycles. So let's assume the latter. If a is allowed to contain negative values to start with, then the negate-as-you-see-it solution doesn't work. To determine if there is a cycle starting at any given element (isCycle(elemindex)) in O(1) space and O(n) time, you could walk 2 pointers starting at elemindex. One would go at normal speed (nextelem = a[thiselem]) and one would go at double speed (nextelem=a[a[thiselem]]). If the 2 pointers meet, isCycle() returns true. However, since you'd have to run isCycle(index) on every index to ask if there is a cycle *anywhere* in the array, this algorithm is O(n**2) in time. I'd have to ponder if there's an O(1) space / O(n) time algorithm for this... Moins

Define two pointers One pointer move one step each time, The other pointer move two steps each time. If the pointers ever meet together (besides the start point) before one of the pointer reaches the end, then there is a loop. Otherwise, there isn't. This takes O(n) time and O(1) space. Moins

use the contents of a position as an index into array and while traversing the contents, negate the contents after you visit it. if at any time you find the contents of a position as negative (given that every element points to the next element in array, you cannot have -ve numbers in array) this will run in o(n) with constant space e.g. array = [1,2,3,4,5,2] (zero based index) a[0]=1 go to a[1] and negate a[0] to -1 a[1]=2 go to a[2] and negate a[1] to -2 like this when you hit a[5] =2 and then you see a[2] = -3, which is already visited so there is a loop/cycle Moins

Afficher Plus de réponses
Meta

If your are given an Integer Singly linked list. Print it backwards. Constraints: 1. Do not manipulate the list. (example: do not make it a doubly linked list, do not add or delete elements, do not change any memory location of any element) 2. O(n) < time < O(n^2) 3. O(1) < space < O(n)

18 réponses

Couldn't you either just: a) Use a stack (O(n) time, O(n) space) b) Do it recursively? (if end of list, print element, else, recurse on next node then print element (O(n) space, O(n) time) Is there something I missed? Moins

void printList(List list) { if (list == null) { return; } printList(list.next); System.out.print(list.elem + " "); } Moins

//This will recursively print all nodes backwards by going to the last node and then printing on its way out. // O(N) complexity and O(1) space void main() { printNodesBackwards(myFirstNode); } void printNodesBackwards(Node) { if (Node.Next != null) printNodeBackwards(Node.Next); Print(Node.Value); } Moins

Afficher Plus de réponses
Jimmy John's

My experience and availability to relocate

18 réponses

I said I couldn't relocate.

"&gt;

"&gt;

Afficher Plus de réponses
Google

Wie findet man den Mittelwert einer Zahlenmenge?

18 réponses

For Anonymous, build a BST takes O(nlogn) time, so it is not a linear time method. Moins

@sai, are you sure? The array is not sorted. In that case, your best hope is an O(n) expected time. Moins

Given an unsorted array of values, you can use a partitioning method. You can start from using the n/2th value as the initial pivot and depending on where it ends up, you pick the next pivot in the area around the center of the array until the processed pivot ends up in the n/2th spot. This will be your median. Moins

Afficher Plus de réponses
Pratian Technologies

Print the series 1,3,7,13,21,43,57,73,91,111,157,183,211...

17 réponses

int i=1; for(int j=1;j&lt;=19;j++){ System.out.print(i+","); i+=2*j; } System.out.print(i); Moins

#include int main() { int i=1,j,k=5; printf("%d,",i); for(j=1;j&lt;=19;j++) { if(j%k==0) { i=i+2*j; k=k*2+1; } else { i=i+2*j; printf("%d,",i); } } } Moins

#include int main() { int i=1; for(int j=1;j&lt;=19;j++) { printf("%d,\n",i); if((j%5)==0) { i=i+2*j; } i=i+2*j; } } Moins

Afficher Plus de réponses
Cerner

The only unexpected question was to design a employee database because it wasnt in the previous thread :) but it was easy

17 réponses

please reply... Are they expect coding or UML diagrams for chess game ?

sorry, i don't understand.could you please explain it,programming design means UML.am i right.? what is high level design here.. Thank you in advance. Moins

Thanks,

Afficher Plus de réponses
31 - 40 sur 364 960 Questions d'entretien