# Software Developer Interview Questions

Software developer interview questions shared by candidates

## Top Interview Questions

Given a string "aaabbbcc", compress it, = "a3b3c2" . Given that output string's length is always smaller than input string, you have do it inplace. No extra space 28 Answerspublic static String cstr(String a){ if(a.length()<2){return a;} if(a.length()==2){if(a.charAt(0)==a.charAt(1)){return a.charAt(0)+"2";}else{return a;}} for(int i=0;i #include #include #include #define STR_SIZE 26 int main() { /* Current char sequence tracker */ char *c = NULL; char *b = NULL; char *str = (char*)malloc(STR_SIZE * sizeof(char)); if(NULL == str) return -1; memcpy(str, "aaaabbbcceeeeefffffff", 26); b = c = str; printf("Input: %s\n", b); while(*str) { if(*(str+1) != *str) // Repeat sequence ends { // Add 48 so the count gets printed as a char *(c+1) = ((str-c+1)+48); // Updated count, copy rest of the string starting after the count position memcpy(c+2, str+1, strlen(str)); // Update c to point to the new char repeat sequence c = c+2; } str++; } /* b was initialized to point to str up top, proving it was done in place */ printf("Output:%s\n", b); free(b); b = NULL; return 0; } String test="aavvvqwqaa"; int count=0,start=0,end=0; int length=test.length(); for(int i=0;i Show more responses Rohan: What if I give you the string "aaaaaaaaaa"? Your solution will print "a:", not "a10". in java, if you give me a String str="aaabbbcc"; you can't modify the str as all, then how can you do it in place? I assume I can go through the str, and store the new string such as "a3b3c2" anyone can explain to me? java inplace public void compress(char[] str) { if (str != null && str.length > 1) { for (int last = 0, curr = 1, count = 1, tail = 0; curr 1) { str[tail++] = str[last]; str[tail++] = (char) count; count = 1; } last = curr; curr++; } } } Need to delimit the array public void compress(char[] str) { if (str != null && str.length > 1) { int tail = 0; for (int last = 0, curr = 1, count = 1; curr 1) { str[tail++] = str[last]; str[tail++] = (char) count; count = 1; } last = curr; curr++; } str[tail] = '\0'; } } small correction - public void compress(char[] str) { if (str != null && str.length > 1) { int tail = 0; for (int last = 0, curr = 1, count = 1; curr 1) { str[tail++] = str[last]; str[tail++] = (char) (count + '0'); count = 1; } last = curr; curr++; } str[tail] = '\0'; } } This solution covers all cases.. http://justprogrammng.blogspot.in/2012/06/amazon-interview-string-compression-c.html Here is a recursive code which considers all cases... http://justprogrammng.blogspot.com/2012/06/amazon-interview-string-compression-c.html Try this.. it generates the desired output in Java /** * * @author Sourabh Mishra * Class which handles compression of a string replacing the occurrences of characters * with the character followed by its count in the input string * */ public class StringCompressor { /** * Method takes input as a string and replacing the occurrences of characters * with the character followed by its count in the input string * @param data String * @return */ public String compressString(String data){ StringBuilder outBuilder = new StringBuilder(); char prevChar = data.charAt(0); int counter = 0; char currChar; int length = data.length(); for(int i=0; i< length; i++){ currChar = data.charAt(i); if(currChar == prevChar){ counter++; // For the last unique characters if(i == length-1){ outBuilder.append(currChar); outBuilder.append(counter); } continue; } else { outBuilder.append(prevChar); outBuilder.append(counter); prevChar = currChar; counter=1; } } return outBuilder.toString(); } /** * @param args */ public static void main(String[] args) { StringCompressor sc = new StringCompressor(); System.out.println(sc.compressString("aaabbbcc")); } } An additional check and write inside in the else class is required to print the final unique character for inputs like "aaabbbh" public class Stringcompress { /** * Method takes input as a string and replacing the occurrences of * characters with the character followed by its count in the input string */ public String compressString(String data) { StringBuilder outBuilder = new StringBuilder(); char prevChar = data.charAt(0); int counter = 0; char currChar; int length = data.length(); for (int i = 0; i < length; i++) { currChar = data.charAt(i); System.out.println("Curr character is :" + currChar); System.out.println("Prev character is :" + prevChar); if (currChar == prevChar) { counter++; // For the last unique characters if (i == length - 1) { outBuilder.append(currChar); outBuilder.append(counter); } continue; } else { System.out.println("Prev character in else is :" + prevChar); outBuilder.append(prevChar); outBuilder.append(counter); prevChar = currChar; counter = 1; if(i==length-1) { outBuilder.append(currChar); outBuilder.append(counter); } } } return outBuilder.toString(); } public static void main(String[] args) { Stringcompress sc = new Stringcompress(); System.out.println(sc.compressString("aaaaaaadfgdfu")); } } public class Example1 { static String S1="aaabbbccc"; static String comstring=""; public static void main(String[] args) { System.out.println(" Actual string is "+S1); S1=S1+"#"; String oldString=S1; int count=1; for(int i=0;i Show more responses import java.io.*; import java.util.*; import java.text.*; import java.math.*; class amzone { public static void main(String [] args) throws Exception { BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); String line=br.readLine(); int n=line.length(); int count=1; for(int i=0;i Using Ruby methods, ans = "" s.split("").group_by{|x| x}.each{|k,v| ans += "#{k}#{v.count}"} puts ans But this code snippet will produce "a4b3c2" for the input string "aaabbbcca" import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map; public class StringCharCount { public static void main(String args[]) { String inputString="aaabbbccdddddddddddd"; List charUniqueList=new ArrayList(); Map charCountMap=new HashMap(); for(int i=0;i What about the input "abc"? I assume that should compress to "a1b1c1" which is NOT shorter than the input, so you cannot compress in place. string CombineWithNoExtraSpace(string S) { int n=S.size(),count=1,i=0; if(i==n) return "\0"; while(i+1<=n && S[i]==S[i+1] ) { count++; i++; } S = S[i] + to_string(count) + combine(S.substr(i+1,n-count)); return S; } def compress(in_string): final_string = "" init_char = "" ch_val = 1 for (i,ch) in enumerate(in_string): if ch is not init_char: init_char = ch if ch_val > 1: final_string += str(ch_val) ch_val = 1 final_string += ch continue ch_val += 1 try: out = in_string[i+1] except IndexError: final_string += str(ch_val) return final_string print compress("aaaaab") public String compress(String in) { if (in.length() 1 ? right-left : ""); right++; left = right-1; } return out.toString(); } public String compress(String in) { if (in.length() 1 ? right-left : ""); right++; left = right-1; } return out.toString(); } Answer: public class StringCompression { public static void main(String[] args) { String inputString = "abcabcaaaaaaaaaaaaabc";//"aabcccccaaa"; System.out.println(getCompressedString(inputString)); } private static String getCompressedString(String originalString) { StringBuilder compressedStr = new StringBuilder(); if(originalString != null && originalString.length() = originalString.length()){ return originalString; } else{ return compressedStr.toString(); } } } public static String returnCount (String values) { HashMap getHash = new HashMap(); StringBuilder sb = new StringBuilder(); // char[] charsInString = values.toCharArray(); for(char characters : values.toCharArray()){ if(!(getHash.containsKey(characters))){ getHash.put(characters,1); } else getHash.put(characters,getHash.get(characters) + 1); } // for() for(char keys : getHash.keySet()){ sb.append(keys); sb.append(getHash.get(keys)); } System.out.println(getHash); return sb.toString(); } Show more responses #include #include int main(void) { char ch; char accept[100]; char output_string[100]; int count=0,i,j,pos=0; scanf("%s",&accept); printf("%s",accept); for(i=0;i dfdsf #include int main() { char c[30]; int i,count=0; printf("Enter a String : "); scanf("%s",c); for(i=0;s[i]!='\0';i++) { count=1; while(s[i]==s[i+1]) { i++; count++; } printf("%s,%d",s[i],count); } return 0; } x="aaabbbcc" for i in range(len(x)): if i==x.index(x[i])+x.count(x[i])-1: print(x[i],end="") print(x.count(x[i]),end="") public class CompressUtil { public static void main(String[] args) { char[] str = "aaabbbccs".toCharArray(); StringBuilder strcompress = compressString(str); System.out.println(strcompress.toString()); } private static StringBuilder compressString(char[] str) { StringBuilder strcompress = new StringBuilder(); int counter = 1; if (str.length == 1) strcompress.append(str[0]); for (int i = 0; i < str.length - 1; i++) { if (str[i] == str[i + 1]) { counter++; //check if it's the last position if (i + 1 == str.length - 1) { strcompress.append(str[i] + "" + counter); } } else { if (counter == 1) { strcompress.append(str[i]); } else { strcompress.append(str[i] + "" + counter); } counter = 1; //check if it's the last position if (i + 1 == str.length - 1) { strcompress.append(str[i + 1]); } } } return strcompress; } } |

Why do you want to join Wipro ? and please don't give me crap answers ! 12 AnswersDon't say, this is the best company and all the regular stuff Its just for the fame,good salary,n happy life as i heard it s one of the best company too......:-) because, its good company and attractive salary,... Show more responses because its starting of my carrier and i have interest in this field and this is the better platform to boost up my carrier and its true that it gives better salary also ..................thanks and regards 2 fullfill my dreams its good , and I interest in this field To provide better service at the same time to increase the fame of wipro company....bcoz wipro is best company ever. because,they trust freshers and satisfy their needs.. its good company Wipro is one of the top most company and providing well equipments and standard products for society. Job security It’s my dream job and I do anything for this job as well as company it’s always be my first priority i want to be a CEO of Wipro I do very hard work for this position because it’s my dearm |

Given an array of numbers, nums, return an array of numbers products, where products[i] is the product of all nums[j], j != i. Input : [1, 2, 3, 4, 5] Output: [(2*3*4*5), (1*3*4*5), (1*2*4*5), (1*2*3*5), (1*2*3*4)] = [120, 60, 40, 30, 24] You must do this in O(N) without using division. 13 AnswersWell my answer was to divide the array in 2 different parts perform some logic and in end multiply both the arrays One solution would probably be to go through entire array once, keep a track of total product, and then in another loop populate result array by setting each index as totalProduct / (value at index in argument array) oh.. but without division. Didn't see that part with my tiny browser Show more responses If you were not supposed to divide the array into two, for processing.... import java.util.*; class aNum2{ public static void main(String[] args){ int[] a= new int[5]; int[] b= new int[5]; a[0]=1; a[1]=2; a[2]=3; a[3]=4; a[4]=5; int j; for(j=0;j<5;j++){ int i; int p=1; for(i=0; i<5; i++){ p=a[i]*p; } b[j]=p/j; } System.out.println(Arrays.toString(b)); } } if you werent supposed to use the division operator : import java.util.*; class aNum{ public static void main(String[] args){ int[] a= new int[5]; int[] b= new int[5]; a[0]=1; a[1]=2; a[2]=3; a[3]=4; a[4]=5; int j; for(j=0;j<5;j++){ int i; int p=1; for(i=0; i Please ignore the very first response .. there is a correction on line 20 If you were not supposed to divide the array into two, for processing.... import java.util.*; class aNum2{ public static void main(String[] args){ int[] a= new int[5]; int[] b= new int[5]; a[0]=1; a[1]=2; a[2]=3; a[3]=4; a[4]=5; int j; for(j=0;j<5;j++){ int i; int p=1; for(i=0; i<5; i++){ p=a[i]*p; } b[j]=p/a[j]; } System.out.println(Arrays.toString(b)); } } trick is to construct the arrays (in the case for 4 elements) for example { 1, a[0], a[0]*a[1], a[0]*a[1]*a[2], } // productsBelow { a[1]*a[2]*a[3], a[2]*a[3], a[3], 1, } // productsAbove then multiply productsBelow and productsAbove http://stackoverflow.com/questions/2680548/interview-q-given-an-array-of-numbers-return-array-of-products-of-all-other-nu #include using namespace std; int main(){ int a[4] = {1,2,3,4}; int b[4] = {1,1,1,1}; for(int i = 1 ; i =0; i--){ prod *= a[i+1]; b[i] *= prod; } for(int i = 0; i < 4; i++){ cout << b[i] << " " << endl; } } public class Example2 { static int[] Numarray={1,2,3,4,5}; public static void main(String[] args) { ArrayList arr1=new ArrayList(); int first=0; int count=1; for(int j=0;j<=Numarray.length-1;j++) { for(int i=0;i There should be no divsion of array not even numbers so the solution goes like this //SIMPLIFIED APPROACH class amazon2 { public static void main(String rags[]) { int []a={1,2,3,4,5};//any digits as per approach int []b=new int[10]; int []c=new int[10];//dummy integer array for(int i=0;i public void printProduct(int[] a) { int[] b= new int[a.length]; for(int j=0;j public void printProduct(int[] a) { int[] b= new int[a.length]; for(int j=0;j prodSum = function (arr, memo, index) { if(index >= arr.length){ return; } for(var i=0; i |

out of 25 horses select the fastest three in minimum number of races where in each race there would be exactly five horses. 10 Answers6 races i think it could be 6 races... first five races taking 5 horses each,and then the 6th ace taking the 1st horse of each of the previous race,den select the fastest three among them. would be 5 races if a stop watch is given..... however solutions given before are wrong since the horse coming 2nd in the first race might be faster than the horses that come first in the subsequent race :) hence we have to assume that a timer is provided Show more responses umesh no timer has been provided and it would be 7 races :) 11 races First 5 races taking 5 horses in each race. Next 5 races taking in each race horses which have come first, horses which have come second, third, fourth and fifth....... Final 11th race out of 5 which have won in second set of races to find fastest 3 6 Race would be wrong answer. What if in one group all the 5 horses are fastest of all others. Then from first round of 5 races we might lose those 2nd and 3rd ones. My answer is also 11 Races. Round one - 5 Races -------------------- Including all 25 horses. 5 each race. Left with -> 15 horses [Take 1st,2nd & 3rd from each race. Which would be total of 5*3=15 horses.] Round two - 3 Races [ Grouping any 5 of 15 horses left] ------------------- Left with -> 9 horses [Take 1st,2nd & 3rd from each race. which would be total of 3*3=9 horses.] Round three - 1 Race. ---------------- Take any 5 horses of 9 horses left Left with -> 7 horses 3 (1st 2nd and 3rd) + 4 (remaining ones) = 7 horses Round four - 1 Race. ---------------- Take any 5 out of 7 Left with -> 5 Round Five - 1 Race ---------- Race of 5 horses left 7 races: Split the 25 into 5 groups and make them race, this would be 5 races. Take the fastest horse of each group and make them race (6th race). Let's label the initial group of the top 3 horses of the 6th as a, b, c. The possible candidate for the 3 fastest are: a[1], a[2], a[3], b[1], b[2], c[1] We just need one last race to determine the top, the race would be between a[2], a[3], b[1], b[2], c[1]. The final result is a[1] then the top 2 of the 7th race. Easy: Correct answer is 11 but much easier method: 1. One race among 5 horses to find the fastest 3. 20 horses left not raced yet. 2. Now keep the 3 fastest horses you found and add two other horses out of 20 horses left to the race, again select the fastest 3. 3. Keep doing this for all 20 horses by selecting 2 of the horses left to race against the fastest 3 always. 1 race (to find the fastest 3) + 10 races (20/2 races to test all other 20 horses) = 11 races Constant Time - 7 Races 5 Races among 5 each. 6th Race for all third place holders 7th Race for Winner of sixth race +two people who defeated him in 1st race + two people who defeated the second place winner in 6th race. Best Case - 6 Races (3 place winner of 1st race against other 20 and he wins all the time) Worst Case - 11 Races( Make the fastest 3 of each race run against the other 2 each time) |

Find all anagrams in a file. Improve the running time to O(n). 7 Answersfor each work in the file, sort the letters in the work and add the result into a stack, if there is a collision, the original word is part of set whose words in that set is an anagram. Since adding to a stack only take O(1) and you must visit each word once, the complexity is O(n). The way I approach anagrams is that I assign a prime number to each letter and then multiply the letters. In theory, ABC gives you say 3 * 5 * 7 = 105 Any anagram will have letters that when multiplied give you 105. In the solution above, it's far more than O(n) because of the sort step which depending on how you're trying to sort could wind up nlogn or n2 or something like that. I should note that this is generally good to about 9 characters, at which point overflowing becomes an issue and you'll probably want to go to some construct such as BigInteger in Java or go with what Anonymous presented. Show more responses @SeanB: Instead of multiplying number just add them. Adding won't cause a big value for stack overflow or something.(e.g A=1, a=1: b=2, B=2...so on.) Rule of Association in maths. That would do. However even for multiplying or adding we have to split the string which will involve some complexity, therefore that might not make the whole operation o(n). @SeanB, thats good idea, adding to that: we can map a prime number for each alphabet. if any string has same multiplied product then both should be anagram. For example: Map the first 26 prime numbers to "abcd....xyz" "1, 3, 5, 7, 9, 11, 13, 17, 19, 23, 25, 29, 31, 37, 41, 43, 47, 49, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97" now consider the anagram: "cinema" and "iceman" the product of the two numbers will be same. Since we use prime numbers, the factors should be same. so its proved that both are anagrams. To check overflow: 97 is for the char "z", and usual word size is 10. So, Math.pow(9, 10) is 73742412689492830000 and which still finite. @Jimmy: There is a small flaw in your assumption. Let's say we take the prime number sequence as 1, 2, 3, 5, 7,,, assigned to A, B, C, D, E etc Your assumption would give out the same answer for "BC" and "D". But these two are two not anagrams. So i guess i better approach would be to multiply the numbers. 1 is not prime man |

Puzzle: There are 25 horses and 5 lanes for conducting a race among them. In a minimum of how many races, would be able to find out the 3 fastest horses among them? Assumption: Speed of horses are consistent enough across races. 9 AnswersAnswer: 7 6 because 5 races req to find 5 fastest and 1 race to determine the top 3 out of the 5 fastest 7 Show more responses 6 5, just because its speed is consistent between races, so we need note down time taken by all the horses, for this 5 races needed ( 5 lanes and 25 horses ). From the list identify top 3, thats simple! 1 race with of 3 horses 10 6 5 |

### Software Developer at Commvault was asked...

The coding problem in 2nd round. 5 Answerscan u plz explain how to solve the 2nd round question . like on which platform/IDE we have to code. can u please send me commVault papers please can u plz gimme ur email id or ph. no. itz visiting my campus n i need sm info? Show more responses Check out the section "Address arithmetic" in K & R C under the chapter "Pointers and Arrays" for a crude implementation of malloc and free. This is almost similar to the poster's 2nd round interview question. sry fr late reply, i registered it on sum other id. The 2nd round question was to be developed on VisualStudio as far as i remember.. it cud be done in dev c++ also.. i used array of records to keep track of all allocated blocks. nd fr each new blk addition in array, i sorted the recor array. The record wud consist of starting add nd length of record |

Consider a stack of N number of cards which are piled up and in facing down. Each card has a unique number from the range 1 to N. The card is stacked in such a way that it exhibits the following behavior: Take the first card and put it under the stack without revealing. Now the next card on the top will have the number 1 on it. Next take 2 cards one after the other and put is under the stack without revealing. Yes you guessed it right - the next card on the top will reveal a value of 2. This goes on. Eg. for such a series : 9,1,8,5,2,4,7,6,3,10 [for N=10] Write a program to generate such a series for a given N number of cards so that this behavior can be exercised. 8 AnswersPossible implementation in C++ -------------------------------------------------- int CounterStep(int counter,int N); int LocatePosition(int *cards,int N, int startPointer,int value); using namespace std; void main() { int cards[20]; int N=20; int POS = 0,TOP = 0; // Initializing everything to zero for(int i=0;i Written in Python although it can be re-written in C/C++ if required. def generateSpecialSeries(numberOfCards): specialSeries = [] if numberOfCards > 0: for i in range(numberOfCards, 0, -1): specialSeries.append(i) currentSpecialElement = 1 currentIndex = 1 while currentIndex < numberOfCards: indexOfCurrentSpecialElement = numberOfCards - currentSpecialElement specialSeries[currentIndex], specialSeries[indexOfCurrentSpecialElement] = specialSeries[indexOfCurrentSpecialElement], specialSeries[currentIndex] currentSpecialElement += 1 currentIndex += currentSpecialElement + 1 return specialSeries specialSeries = generateSpecialSeries(50) print specialSeries specialElement = 1 specialElementSum = 1 currentIndex = 1 while currentIndex < 50: print specialSeries[currentIndex] == specialElement specialElement += 1 specialElementSum += specialElement currentIndex += specialElement + 1 // Short and simple C++ algorithm #define N 10 void compute(int stack[]) // Make sure N elements are allocated { int j=0; for(int i=0; i Show more responses #include using namespace std; int main(int argc,char **argv){ int count=20; int array[20]; for(int i=0;i>a; return 0; } Java implementation public class App { public static void main(String[] args) { String arr[] = new String[10]; int pointer = 0; for (int valueToPlace = 1; valueToPlace <= arr.length; valueToPlace++) { for (int x = 1; x <= valueToPlace; x++) { if (pointer == arr.length - 1) pointer = 0; else pointer++; if (arr[pointer] != null) x--; } System.out.println("Placing " + valueToPlace + " at index " + pointer); arr[pointer] = valueToPlace + ""; while (arr[pointer] != null && valueToPlace != arr.length) { if (pointer == arr.length - 1) pointer = 0; else pointer++; } } for (String str : arr) { System.out.print(str + ", "); } } } The algorithm used is: For each number n (ranging from 1 to 10), we have to skip n places in the array. And then put number n at that position. The catch in the program is that we can skip only, not occupied places (the array places where value is 0 by default). Also, when we reach the end of the array, we have to move back to beginning of array (similar to cards being kept at the bottom of the pile of cards.) Here, a variable 'pos' is used to store the final position of any element. Initially, pos is at 0. The skip() takes the array, the current value of pos and the number of skips to be made. For example, for n=1, the values passed to skip() would be: pos=0, n=1. This means that we have to skip 1 place starting from index 0. Similarly, for n=2, pos=1. This means we have to skip 2 places starting from index 1. Java Implementation: public class StackOfCards { /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub int[] arr = new int[10]; int pos=0; for(int n=1;n0){ if(arr[pos]==0){ //reduce the number of skips to be made n--; } pos++; //if end of array is reached, take pos back to beginning if(pos==10){ pos=0; } } // keep incrementing pos until a not occupied index is reached. while(arr[pos]!=0){ pos++; } return pos; } } Here is C# Code... namespace ConsoleApplication1 { class Program { static void Main(string[] args) { int n = 36; int[] series = new int[n]; int LargestNumber = n; int SmallestNumber = 1, temp = 1, i; bool putLargeNumber = true; for (i= 0; i 0)) { series[i] = LargestNumber; Console.Write("{0} ", series[i]); LargestNumber = LargestNumber - 1; putLargeNumber = false; temp--; } else { series[i] = SmallestNumber; Console.Write("{0} ", series[i]); SmallestNumber += 1; putLargeNumber = true; temp = SmallestNumber; } } } } } import java.util.HashMap; import java.util.HashSet; import java.util.Scanner; import java.util.Stack; public class MSQuestion1 { static int counter =1; public static void main(String[] args) { // TODO Auto-generated method stub Scanner in = new Scanner(System.in); int n =in.nextInt(); // x 1 x1 x2 2 x3 x4 x5 3 x6 int[] arr = new int[n]; int f = 0; while(f0)) { arr[f]=counter; counter++; } f++; } for(int i=0;i |

Find count of unique characters in a given string 4 AnswersWhat kind of characters in the string? Assuming ASCII characters, total 256. Array should be a good choose. int uniqueCount(string str){ if(str.size()<2) return str.size(); int charNum[256]={0}; // initialized to zero //counting concurrency for(int i=0; i here are two ways of attacking this: (1) sort the chars, then walk the list incrementing a count any time you hit a different char (2) take advantage of the fact that there are at most 256 ASCII characters, with values 0 to 255, so build a 256 sized array to hold all possible chars, then as you walk the list, increment the corresponding array entry holding a matching char. first approach: /* sort the string */ for (int i=0; i public void counter(String g) { int count; for (int i = 'a' ; i<='z' ; i++){ count = 0; for (int a = 0; a Show more responses Using single iteration :) ..... int map[256]={0}; //initialise map to 0 int count=0; string a="abcabnaabcabaccacbbbqf"; for(int i=0;i |

Given an integer array which consists of numbers from 1 to N with 1 number missing find the missing number. What will you do if 2 numbers are missing? 4 AnswersGiven that the summation from 1 -> N = N(N+1)/2, we can use simple math to get a solution in O(n) time. We know that our array is "missing" a number, so it's length "L", is N-1. So we know that the summation for our array if it were not missing the value X could be calculated as N(N+1)/2, or (L+1)(L+2)/2. For a given array with length L, all we need to do is calculate what the expected summation is, iterate over the array and find the actual summation, then calculate the difference. public int findMissingValue(int[] sequence) { int length = sequence.length(); int expectedSum = ((length + 1) * (length + 2)) / 2; int actualSum = 0; for (int i = 0; i < length; i++) { actualSum += sequence[i]; } return expectedSum - actualSum; } You have an array of length N filled with numbers 1 through N+1 with one number missing. 1. bitwise xor all numbers 1 to N+1 2. bitwise xor all numbers in the array 3. bitwise xor the above two numbers to get the missing number, as duplicates will cancel out If two numbers are missing this approach and the sum approach fail. In this case I can't think of a faster way than sorting the list. For 2 number missing.. First split up the array into half from first half find the first missing number and second half find the second missing number. If 2 missing numbers are in first half then again divide the first half into 2 half and find it. Show more responses Use a bitmap: keys are 1 to N and values are true/false. Iterate over the array and populate the bitmap. Iterate over the bitmap and the missing numbers are those that have the value == false. |

**1**–

**10**of

**16,839**Interview Questions

## See Interview Questions for Similar Jobs

- Software Engineer
- Senior Software Engineer
- Software Developer
- Software Development Engineer II
- Software Development Engineer I
- Java Developer
- Senior Software Development Engineer
- Associate Software Engineer
- Software Engineer II
- Intern
- Business Analyst
- Member of Technical Staff
- Technical Lead
- Applications Developer
- Analyst
- Senior Software Developer
- Software Development Engineer In Test
- Consultant
- Senior Consultant