# 5K

Software Engineer Summer Intern interview questions shared by candidates

## Top Interview Questions

Sort: Relevance|Popular|Date
Software Engineer Intern was asked...28 July 2009

### Suppose you had eight identical balls. One of them is slightly heavier and you are given a balance scale . What's the fewest number of times you have to use the scale to find the heavier ball?

Two. Split into three groups of three, three, and two. weigh the two groups of three against each other. If equal, weigh the group of two to find the heavier. If one group of three is heavier pick two of the three and compare them to find the heaviest. Less

2 3a+3b+2 = 8 if wt(3a)==wt(3b) then compare the remaining 2 to find the heaviest if wt(3a) !== wt(3b) then ignore group of 2 discard lighter group of 3 divide the remaining group of 3 into 2+1 weigh those 2 If == the remaing 1 is the heaviest if !== the heaviest will be on the scale Less

2 weighings to find the slightly heavier ball. Step 1. compare 2 groups of three balls. Case 1. if they are both equal in weight, compare the last 2 balls - one will be heavier. case 2. If either group of 3 balls is heavier, take 2 balls from the heavier side. compare 1 ball against the 2nd from the heavy group result 1. if one ball is heavier than the other, you have found the slightly heavier ball. result 2. if both balls are equal weight, the 3rd ball is the slightly heavier ball. Easy Shmeezi Less

### Given two strings representing integer numbers ("123" , "30") return a string representing the sum of the two numbers ("153")

public static String sumStrings(String a, String b){ char[] num1 = a.toCharArray(); char[] num2 = b.toCharArray(); int i = num1.length - 1; int j = num2.length - 1; StringBuilder sumString = new StringBuilder(); int carry = 0; while(i &gt;= 0 || j &gt;= 0){ int d1 = 0; int d2 = 0; if (i &gt;= 0) d1 = num1[i--] - '0'; if (j &gt;= 0) d2 = num2[j--] - '0'; int sum = d1 + d2 + carry; if (sum &gt;= 10){ carry = sum / 10; sum = sum % 10; }else carry = 0; sumString.insert(0, sum); } return sumString.toString(); } Less

The interviewer wanted a loop through the digits starting form right to left, adding them one by one, and keeping track of the carriage. Less

public static String addTwoStrings(String s1, String s2) { int len1 = s1.length(); int len2 = s2.length(); char[] s1Chars = s1.toCharArray(); char[] s2Chars = s2.toCharArray(); StringBuilder sb = new StringBuilder(); int pointerA = len1 -1; int pointerB = len2 -1; int carry = 0; while (pointerA &gt;= 0 || pointerB &gt;= 0){ int a = pointerA 10) { carry = sumTemp / 10; sumTemp = sumTemp % 10; } else { carry = 0; } sb.insert(0, sumTemp); } if(carry &gt;0) sb.insert(0, carry); return sb.toString(); } Less

### Suppose we can translate numbers into characters: 1-&gt;a, 2-&gt;b, ...26-&gt;z given an integer, for example, 11223, output every translation of the number.

Well I think the first answer in totally wrong except the first one, Here is what I have: aabbc kvc alw kbw aavc aabw kbbc albc Less

In Java, a recursive solution is: public static void main(String[] args) { String s = "11223"; char[] N = s.toCharArray(); char[] S = new char[N.length]; m(0,0,N,S); } public static void m(int i, int j, char N[], char[] S){ if (i==N.length){ System.out.println(new String(S, 0, j) ); return; } S[j]=(char)('a'+Integer.parseInt(""+N[i])-1); m(i+1, j+1, N, S); if (N[i]=='1' || (N[i]=='2' &amp;&amp; N[i+1]&lt;'7')) { S[j]=(char)('a'+Integer.parseInt(""+N[i]+N[i+1])-1); m(i+2, j+1, N, S); } } Less

no body use dp?

### There are 20 floors in a building. If you're on an elevator and you're trying to get to the 20th floor, what is the probability that 4 people ahead of you click the 20th floor before you do? Assuming you click last.

The above two are close, but wrong.. There are 20 buttons, thus 20 choices, sure. But you are getting on at one of the floor. No body will press the button for the floor they get on.. Thus, there is really only 19 choices. P = (1/19)^3 (Independent events mean (1/19)(1/19)(1/19)). Less

1/19 + 1/18 + 1/17 + 1/16 assuming that there were no repeated destinations.

based on question: P(all 4 ahead of you want to get off on 20th fl) = (1/19)^4 real life(all 4 want to get off on 20th fl, and one of them is the first person press the button to 20th fl, and that leave all others, including you, stay still): (1/19) * (1/4) Less

### Write a function in language of your choice that takes in two strings, and returns true if they match. Constraints are as follows: String 1, the text to match to, will be alphabets and digits. String 2, the pattern, will be alphabets, digits, '.' and '*'. '.' means either alphabet or digit will be considered as a "match". "*" means the previous character is repeat 0 or more # of times. For example: Text: Facebook Pattern: F.cebo*k returns true

#include using namespace std; bool regex_match(string s1, string s2); int main() { if(regex_match("facebook", ".*.")) { cout &lt;&lt; "Pattern Matched!" &lt;&lt; endl; } else { cout &lt;&lt; "Pattern Not Matched!" &lt;&lt; endl; } return 0; } bool regex_match(string s1, string s2) { char c1, c2; int s2i = 0; for(int i = 0; i &lt; s1.length(); i++) { c1 = s1[i]; c2 = s2[s2i]; if(c2 == '.') { s2i++; continue; } if(c2 == '*') { c2 = s2[s2i - 1]; bool done = true; c1 = s1[i - 1]; for(int j = i; j &lt; s1.length(); j++) { c1 = s1[j]; if(c2 != '.' &amp;&amp; c1 != c2) { done = false; i = j - 1; break; } } if(done) { break; } } else if(c1 != c2) { return false; } s2i++; } if(s2i &lt; s2.length()) { for(int j = s2i + 1; j &lt; s2.length(); j++) { if(s2[j] != '*') { return false; } } } else { return true; } return true; } Less

boolean accepts(char* pattern, char* s) { if (!pattern || !s) return 0; if (0 == *pattern) return (0 == *s); if ((strlen(pattern) &gt; 1) &amp;&amp; (pattern == '*')) { return (match(pattern, s) &amp;&amp; accepts(pattern, s+1)) || accepts(pattern+2,s); } else { return (match(pattern, s) &amp;&amp; accepts(pattern+1, s+1)); } } boolean match(char* pattern, char* s) { return ((*pattern == '*') || (*pattern == *s)); } Less

@Rahul: a small bug there (matching the '*' rather than the '.'): boolean match(char* pattern, char* s) { return ((*pattern == '*') || (*pattern == *s)); } should be: boolean match(char* pattern, char* s) { return ((*pattern == '.') || (*pattern == *s)); } Other thoughts: -- "if ((strlen(pattern) &gt; 1)" is redundant since "if (!pattern =='*')" takes care of it. (and I'd generally avoid a strlen in either a loop or recursive call) -- This solution ends up with a stack depth that is equal to the length of the target string -- far from ideal. Less

### You are climbing a stair case. Each time you can either make 1 step or 2 steps. The staircase has n steps. In how many distinct ways can you climb the staircase ?

Let c(i-1) = the total for a staircase with i-1 steps. Now add one step to the beginning. You have two choices: start with one step and then do c(i-1), or start with two steps and then do c(i-2). In other words, c(i) = c(i-1) + c(i-2). The basis for the recurrence is c(0) = c(1) = 1. This is exactly the Fibonacci sequence. I submit that the solution to this problem of n steps is Fib(n+1). Let's verify for small values of n: 1 steps: There's only one way to take one step. (1) 2 steps: There are 2 ways (1+1) or (2) 3 steps: 3 ways (1+1+1), (1+2), (2+1) 4 steps: 5 ways (1+1+1+1), (1+1+2), (1+2+1), (2+1+1), (2+2) Less

int getways(int n) { int i,j; int sumways=0; for(i=0;i&lt;=n-i;i++) { if(i==0) sumways++; else { int subways=1; for(j=1;j&lt;=i;j++) subways*=((n-j)/j); sumways+=subways; } } } Less

this is fibonacci your first step can be either 1 or 2 step. if first step is 1 step, remaining is an N-1 problem. if first step is 2 steps, remaining is an N-2 problem. N problem = N-1 problem + N-2 problem Less

### Find the integer pairs in an integer array, so that they sum up to a specific number n.

Complexity O(N): void findSum(int sum, int[] vec) { Set set= new HashSet(vec.length); for (int i : set) { int j = sum - i; if (set.contains(j)) { printf("%i + %i = %i \n", i, j, sum); } set.add(i); } Less

typo: the "for" loop is for (int i : vec) {

To elaborate on vsp's solution. I believe they are looking for the matching pairs in the array that sum to n. Ex: 5,0 4,1 2,3 6,-1 I'd suggest dumping the vector into a hash O(n). Then walk the vector getting i and check the hash for the j where j = sum - i;. When j is in the hash, then you have an ij pair. Less

### n= 20 for (i=0;i&lt;n; i--) print i the question was to change or replace a only one character in for loop to print 20 times.

changing i-- to n-- is a correct answer. adding 4 in front of i=0 would work, but does not satisfy the condition "change or replace a character" as it adds a character instead. Less

n= 20 for (i=0;i

&lt; stands for '&lt;' and replace '-' with '+' for i in the increment part of for loop. Less

### Questions related to data structures like "What data structure would you use for a browser's BACK & FORWARD ability"

I would use doubly link list

Use two stacks. Every time you visit a site, push its address in stack1. When you press back, pop from stack1 and also push in stack2. When user presses forward, pop from stack2 and also push in stack1. Less

May be Stack , any one please correct me if I am wrong.