String
1) How to Print duplicate characters from String?
To start with, we have a simple String related coding question frequently asked in programming interviews. You need to write a program in C, C++, Java or Python to print duplicate characters from a given String, for example if String is "Java" then program should print "a". Bonus points if your program is robust and handle different kinds of input e.g. String without duplicate, null or empty String etc. Bonus points if you also write unit tests for normal and edge cases.
Solution:
packageswain.codding.String;
Solution:
packageswain.codding.String;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
public class FindDuplicateCharacters {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.println("Enter any value: ");
printDuplicateCharacters(scanner.nextLine());
printDuplicateCharacters(scanner.next());
}
public static voidprintDuplicateCharacters(String word) {
char[] charecters = word.toCharArray();
Map<Character, Integer> map = new HashMap<Character, Integer>();
for (Character ch : charecters) {
if (map.containsKey(ch)) {
map.put(ch, map.get(ch) + 1);
} else {
map.put(ch, 1);
}
}
System.out.printf("list of duplicate charecter of string '%s'%n", word);
for(Map.Entry<Character, Integer> entry : map.entrySet()) {
if (entry.getValue() > 1) {
System.out.printf("%s : %d %n", entry.getKey(), entry.getValue());
}
}
}
}
Output:
Enter any value:
sitansu
list of duplicate charecter of string 'sitansu'
s : 2
himanshu
list of duplicate charecter of string 'himanshu'
h : 2
2) How to check if two Strings are anagrams of each other?
A simple coding problem based upon String, but could also be asked with numbers. You need to write a Java program to check if two given strings are anagrams of Each other. Two strings are anagrams if they are written using the same exact letters, ignoring space, punctuation and capitalization. Each letter should have the same count in both strings. For example, Army and Mary are anagram of each other.
Solution:
packageswain.codding.String;
import java.util.Arrays;
public class StringAnagramTest {
public static void main(String[] args) {
isAnagram("word", "wrdo");
isAnagram("swain", "sitansu");
}
public static void isAnagram(String word, String anagram) {
char[] wordArray = word.toCharArray();
char[] anagramArray = anagram.toCharArray();
Arrays.sort(wordArray);
Arrays.sort(anagramArray);
if (Arrays.equals(wordArray, anagramArray)) {
System.out.println("Two string are anagram");
} else {
System.out.println("Two string are not anagram");
}
}
}
Output:
Two string are anagram
Two string are not anagram
3) How to program to print first non repeated character from String?
One of the most common string interview questions: Find the first non-repeated (unique) character in a given string. for Example if given String is "Morning" then it should print "M". This question demonstrates efficient use of Hashtable. We scan the string from left to right counting the number occurrences of each character in a Hashtable. Then we perform a second pass and check the counts of every character. Whenever we hit a count of 1 we return that character, that’s the first unique letter. Be prepared for follow-up question for improving memory efficiency, solving it without hash table as well.
Solution:
packageswain.codding.String;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
public class FirstNonRepeatedChar {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.println("Enter any String value ");
System.out.println("First Non Repeat character is " + getFirstNonRepeatedChar(scanner.nextLine()));
System.out.println("First Non Repeat character is " + getFirstNonRepeatedChar(scanner.next()));
}
public static chargetFirstNonRepeatedChar(String word) {
char[] character = word.toCharArray();
Map<Character, Integer> map = new HashMap<Character, Integer>();
for (Character ch : character) {
if (map.containsKey(ch)) {
map.put(ch, map.get(ch) + 1);
} else {
map.put(ch, 1);
}
}
for(Map.Entry<Character, Integer> entry : map.entrySet()) {
if (entry.getValue() == 1) {
return entry.getKey();
}
}
throw new RuntimeException("didn't find any non repeated Character");
}
}
Output:
Enter any String value
sitansu
First Non Repeat character is a
swain
First Non Repeat character is a
4) How to reverse String in Java using Iteration and Recursion?
Your task is to write a program to reverse String in Java without using StringBuffer class. You also need to provide both iterative and recursive algorithm for String reversal. You can use other String utility methods e.g. charAt(), toCharArray() or substring() from java.lang.String class.
Solutions:
Solutions:
packageswain.javainterviewhub.blogspot.in;
public class StringReverseExample {
public static void main(String[] args) {
String str = "This is sitansu";
System.out.println(newStringBuffer(str).reverse().toString());
// using iterative
System.out.println(reverse(str));
// using recursion
System.out.println(reverseRecursively(str));
}
public static String reverse(String str) {
StringBuffer sb = new StringBuffer();
char[] charArray = str.toCharArray();
for (int i = charArray.length - 1; i >= 0; i--) {
sb.append(charArray[i]);
}
return sb.toString();
}
public static String reverseRecursively(String str) {
if (str.length() < 2) {
return str;
}
return reverseRecursively(str.substring(1)) + str.charAt(0);
}
}
Output:
usnatis si sihT
usnatis si sihT
usnatis si sihT
5) How to check if a String contains only digits?
You need to write a program to check a String contains only numbers by using Regular expression in Java. You can use Java API but a solution without using Java API will be better because that is what interviewer can always ask.
Solutions:
packageswain.javainterviewhub.blogspot.in;
importjava.util.regex.Pattern;
public classCheckStringContainsOnlyDigit {
public static void main(String[] args) {
// Regular expression in Java to check if String is number or not
Pattern pattern = Pattern.compile(".*[^0-9].*");
// Pattern pattern = Pattern.compile(".*\\D.*");
String[] inputs = { "123", "-123", "123.12", "abcd123" };
for (String input : inputs) {
System.out.println("does " + input + " is number : " + !pattern.matcher(input).matches());
}
// Regular expression in java to check if String is 6 digit number or not
String[] numbers = { "123", "1234", "123.12", "abcd123", "123456" };
Pattern digitPattern = Pattern.compile("\\d{6}");
// Pattern digitPattern = Pattern.compile("\\d\\d\\d\\d\\d\\d");
for (String number : numbers) {
System.out.println("does " + number + " is 6 digit number : " + digitPattern.matcher(number).matches());
}
}
}
Output:
does 123 is number : true
does -123 is number : false
does 123.12 is number : false
does abcd123 is number : false
does 123 is 6 digit number : false
does 1234 is 6 digit number : false
does 123.12 is 6 digit number : false
does abcd123 is 6 digit number : false
does 123456 is 6 digit number : true
6) How to find duplicate characters in a String?
You need to write a program to print all duplicate character and their count in Java. For example if given String is "Programming" then your program should print
g : 2
r : 2
m : 2
Solution:
g : 2
r : 2
m : 2
Solution:
package swain.coding;
import java.util.Arrays;
public class RepeatingNumber {
public static void main(String[] args) {
int[] numbers = { 1, 5, 23, 23, 13, 5, 3, 7, 7, 9, 10, 12, 10, 4 };
findRepeatingNumber(numbers);
}
public static void findRepeatingNumber(int[] numbers) {
try {
Arrays.sort(numbers);
int count = 1;
for (int i = 1; i < numbers.length; i++) {
if (numbers[i] == numbers[i - 1]) {
++count;
} else {
if (count > 1) {
System.out.println("Duplicate : " + numbers[i - 1]
+ " Repeating : " + count);
}
count = 1;
}
if ((numbers.length - 1) == i) {
if (count > 1) {
System.out.println("Duplicate : " + numbers[i - 1]
+ " Repeating : " + count);
}
}
}
} catch (Throwable e) {
throw new RuntimeException();
}
}
}
Output:
Duplicate : 5 Repeating : 2
Duplicate : 7 Repeating : 2
Duplicate : 10 Repeating : 2
Duplicate : 23 Repeating : 2
Output:
Duplicate : 5 Repeating : 2
Duplicate : 7 Repeating : 2
Duplicate : 10 Repeating : 2
Duplicate : 23 Repeating : 2
7) How to count number of vowels and consonants in a String?
One of easiest String question you will ever see. You have to write a Java program which will take a String input and print out number of vowels and consonants on that String. For example if input is "Java" then your program should print "2 vowels and 2 consonants". If you get this question on Interview, you should clarify that whether String can contain numbers, special characters or not e.g. anything other than vowels and consonants.
Solution:
Solution:
packageswain.codding.String;
import java.util.Scanner;
public class CountVowelNConsonant {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.println("Enter any string.");
System.out.println();
countVowel(scanner.nextLine());
}
public static void countVowel(String str) {
char[] chArray = str.toCharArray();
int totalCount = 0;
int countVowel = 0;
int countConsonant;
for (char ch : chArray) {
if (ch != ' ') {
totalCount++;
}
switch (ch) {
case 'a':
;
case 'e':
;
case 'i':
;
case 'o':
;
case 'u':
;
countVowel++;
break;
}
}
System.out.println("Total count " + totalCount + " vowel count " + countVowel + " consonant count " + (totalCount - countVowel));
}
}
Output:
Enter any string.
this is sitansu
Total count 13 vowel count 5 consonant count 8
this is sitansu
Total count 13 vowel count 5 consonant count 8
8) How to count occurrence of a given character in String?
If interviewer ask you to count occurrence of more than one character than you can either use an array, hash table or any additional data structure. In order to solve this problem, you are not allowed to do so. Your method must return count of given character, for example if input String is "Java" and given character is 'a' then it should return 2. Bonus point if you handle case, null and empty String and come up with unit tests.
Solution:
Solution:
packageswain.coding;
public classCountCharacters {
public static voidmain(String[] args) {
String str = "Today is monday";
intcountOccurance = 0;
// counting occurrence of character with loop
for (int i = 0; i < str.length(); i++) {
if(str.charAt(i) == 'a') {
countOccurance++;
}
}
System.out
.println("count of character 'a' on String: 'Today is Monday' using for loop "
+ countOccurance);
// a more elegant way of counting occurrence of character in String
// using foreach loop
countOccurance = 0;
for (char ch : str.toCharArray()) {
if (ch == 'a') {
countOccurance++;
}
}
System.out
.println("count of character 'a' on String: 'Today is Monday' using for loop "
+ countOccurance);
}
}
Output:
count of character 'a' on String: 'Today is Monday' using for loop 2
count of character 'a' on String: 'Today is Monday' using for loop 2
9) How to convert numeric String to int?
A classical coding interview question based upon String. You need to write a method like atoi() from C/C++, which takes a numeric String and return its int equivalent. For example, if you pass "67263" to the program then it should return 67263. Make sure your solution is robust i.e. it should be able to handle + and - character, null and empty String, integer overflow and other corner cases. Bonus points if you come up with good unit test cases. By the way, if your interviewer doesn't mention to you about atoi() then you can also use Java API's parseInt() or valueOf() method to solve this problem.
10) How to replace each given character to other e.g. blank with %20?
10) How to replace each given character to other e.g. blank with %20?
Write a Java program to replace a given character in a String to other provided character, for example if you are asked to replace each blank in a String with %20, similar to URL encoding done by browser, so that Server can read all request parameters. For example if input is "Java is Great" and asked to replace space with %20 then it should be "Java%20is%20Great".
11) How to find all permutations of String?
I have seen this String interview question on many interviews. It has a easy recursive solution but thinks get really tricky when Interviewer ask you to solve this question without using recursion. You can use Stack though. Write a program to print all permutations of a String in Java, for example if input is "xyz" then it should print "xyz", "yzx", "zxy", "xzy", "yxz", "zyx".
12) How to reverse words in a sentence without using library method?
Write a function, which takes a String word and return sentence on which words are reversed in order e.g. if input is "Java is best programming language", output should be "language programming best is Java".
13) How to check if String is Palindrome?
Another easy coding question based upon String, I am sure you must have done this numerous time. Your program should return true if String is Palindrome, otherwise false. For example, if the input is "radar", the output should be true, if input is "madam" output will be true, and if input is "Java" output should be false.
14) How to remove duplicate characters from String?
This is one of the interesting String question, which also has lots of variants. You need to remove duplicate characters from a given string keeping only the first occurrences. For example, if the input is ‘bananas’ the output will be ‘bans’. Pay attention to what output could be, because if you look closely original order of characters are retained in output. This is where many developer make mistake of shorting character array of String and removing duplicates, similar to how you remove duplicates from array. That destroys original order of characters and will not be correct solution in this case.
15) How to check if a String is valid shuffle of two String?
One more difficult String algorithm based coding question for senior developers. You are given 3 strings: first, second, and third. third String is said to be a shuffle of first and second if it can be formed by interleaving the characters of first and second String in a way that maintains the left to right ordering of the characters from each string. For example, given first = "abc" and second = "def", third = "dabecf" is a valid shuffle since it preserves the character ordering of the two strings. So, given these 3 strings write a function that detects whether third String is a valid shuffle of first and second String.
16) Write a program to check if a String contains another String e.g. indexOf()?
You need to write a function to search for the existence of a string (target) in another string (source). The function takes two strings as the input and returns the index where the second string is found. If the target string cannot be found, then return -1. If you are a Java developer, then you can related its behavior to indexOf() method from java.lang.String class. This question is also asked as Code and algorithm to check if a given short string is a substring of a main string. Can you get a linear solution (O(n)) if possible?
17) How to return highest occurred character in a String?
You need to write a function to implement algorithm which will accept a string of characters and should find the highest occurrence of the character and display it. For example if input is "aaaaaaaaaaaaaaaaabbbbcddddeeeeee" it should return "a".
18) Write a program to remove a given characters from String?
One of my favorite coding question, when I interview Java developers. You need to write a Java method which will accept a String and a character to be removed and return a String, which doesn't has that character e.g remove(String word, char ch). You need to provide both iterative and recursive solution of this method and also has to write JUnit tests to cover cases like null and empty String, input which only contains letter to be removed, String which doesn't contain given character etc.
19) Write a program to find longest palindrome in a string?
This is one of the tough coding question based upon String. It's hard to think about an algorithm to solve this problem until you have practiced good. What makes it more difficult is the constraint that your solution has O(n) time complexity and O(1) space complexity.
20) How to sort String on their length in Java?
Write a Program to sort String on their length in Java? Your method should accept an array of String and return a sorted array based upon length of String. Don't forget to write unit tests for your solution.
Arrays
1. How to find missing number in integer array of 1 to 100?
This is one of the most simple array problem you will see, mostly asked in telephonic round of Interview. You have given an integer array which contains numbers from 1 to 100 but one number is missing, you need to write a Java program to find that missing number in array. You cannot use any open source library or Java API method which solves this problem. One trick to solve this problem is calculate sum of all numbers in array and compare with expected sum, the difference would be the missing number.
2. How to find duplicate number on Integer array in Java?
An array contains n numbers ranging from 0 to n-2. There is exactly one number is repeated in the array. You need to write a program to find that duplicate number. For example, if an array with length 6 contains numbers {0, 3, 1, 2, 3}, then duplicated number is 3. Actually this problem is very similar to previous one and you can apply the same trick of comparing actual sum of array to expected sum of series to find out that duplicate. This is generally asked as follow-up question of previous problem.
3. How to check if array contains a number in Java?
Another interesting array problem, because array doesn't provide any builtin method to check if any number exists or not. This problem is essentially how to search an element in array. There are two options sequential search or binary search. You should ask interviewer about whether array is sorted or not, if array is sorted then you can use binary search to check if given number is present in array or not. Complexity of binary search is O(logN). BTW, if interviewer say that array is not sorted then you can still sort and perform binary search otherwise you can use sequential search. Time complexity of sequential search in array is O(n).
4. How to find largest and smallest number in unsorted array?
This is a rather simple array interview question. You have given an unsorted integer array and you need to find the largest and smallest element in the array. Of course you can sort the array and then pick the top and bottom element but that would cost you O(NLogN) because of sorting, getting element in array with index is O(1) operation.
5. How to find all pairs on integer array whose sum is equal to given number?
This is an intermediate level of array coding question, its neither too easy nor too difficult. You have given an integer array and a number, you need to write a program to find all elements in array whose sum is equal to the given number. Remember, array may contain both positive and negative numbers, so your solution should consider that. Don't forget to write unit test though, even if interviewer is not asked for it, that would separate you from lot of developers. Unit testing is always expected from a professional developer.
6. How to find repeated numbers in an array if it contains multiple duplicate?
This is actually the follow-up question of problem 2, how to find duplicate number on integer array. In that case, array contains only one duplicate but what if it contains multiple duplicates? Suppose, an array contains n numbers ranging from 0 to n-1 and there are 5 duplicates on it, how do you find it? You can use the approach, we have learned in similar String based problem of finding repeated characters in given String.
7. Write a program to remove duplicates from array in Java?
This is another follow-up question from problem 2 and 6. You have given an array which contains duplicates, could be one or more. You need to write a program to remove all duplicates from array in Java. For example if given array is {1, 2, 1, 2, 3, 4, 5} then your program should return an array which contains just {1, 2, 3, 4, 5}. This array question is also comes at intermediate category because there is no way to delete an element from array. If substituting with another value is not an option then you need to create another array to mimic deletion.
8. How to sort an array in place using QuickSort algorithm?
You will often see sorting problems on array related questions, because sorting mostly happen on array data structure. You need to write a program to implement in place quick sort algorithm in Java. You can implement either recursive or iterative quick sort, its your choice but you cannot use additional buffer, array or list, you must sort array in place.
9. Write a program to find intersection of two sorted array in Java?
1. How to find missing number in integer array of 1 to 100?
This is one of the most simple array problem you will see, mostly asked in telephonic round of Interview. You have given an integer array which contains numbers from 1 to 100 but one number is missing, you need to write a Java program to find that missing number in array. You cannot use any open source library or Java API method which solves this problem. One trick to solve this problem is calculate sum of all numbers in array and compare with expected sum, the difference would be the missing number.
2. How to find duplicate number on Integer array in Java?
An array contains n numbers ranging from 0 to n-2. There is exactly one number is repeated in the array. You need to write a program to find that duplicate number. For example, if an array with length 6 contains numbers {0, 3, 1, 2, 3}, then duplicated number is 3. Actually this problem is very similar to previous one and you can apply the same trick of comparing actual sum of array to expected sum of series to find out that duplicate. This is generally asked as follow-up question of previous problem.
3. How to check if array contains a number in Java?
Another interesting array problem, because array doesn't provide any builtin method to check if any number exists or not. This problem is essentially how to search an element in array. There are two options sequential search or binary search. You should ask interviewer about whether array is sorted or not, if array is sorted then you can use binary search to check if given number is present in array or not. Complexity of binary search is O(logN). BTW, if interviewer say that array is not sorted then you can still sort and perform binary search otherwise you can use sequential search. Time complexity of sequential search in array is O(n).
4. How to find largest and smallest number in unsorted array?
This is a rather simple array interview question. You have given an unsorted integer array and you need to find the largest and smallest element in the array. Of course you can sort the array and then pick the top and bottom element but that would cost you O(NLogN) because of sorting, getting element in array with index is O(1) operation.
5. How to find all pairs on integer array whose sum is equal to given number?
This is an intermediate level of array coding question, its neither too easy nor too difficult. You have given an integer array and a number, you need to write a program to find all elements in array whose sum is equal to the given number. Remember, array may contain both positive and negative numbers, so your solution should consider that. Don't forget to write unit test though, even if interviewer is not asked for it, that would separate you from lot of developers. Unit testing is always expected from a professional developer.
6. How to find repeated numbers in an array if it contains multiple duplicate?
This is actually the follow-up question of problem 2, how to find duplicate number on integer array. In that case, array contains only one duplicate but what if it contains multiple duplicates? Suppose, an array contains n numbers ranging from 0 to n-1 and there are 5 duplicates on it, how do you find it? You can use the approach, we have learned in similar String based problem of finding repeated characters in given String.
7. Write a program to remove duplicates from array in Java?
This is another follow-up question from problem 2 and 6. You have given an array which contains duplicates, could be one or more. You need to write a program to remove all duplicates from array in Java. For example if given array is {1, 2, 1, 2, 3, 4, 5} then your program should return an array which contains just {1, 2, 3, 4, 5}. This array question is also comes at intermediate category because there is no way to delete an element from array. If substituting with another value is not an option then you need to create another array to mimic deletion.
8. How to sort an array in place using QuickSort algorithm?
You will often see sorting problems on array related questions, because sorting mostly happen on array data structure. You need to write a program to implement in place quick sort algorithm in Java. You can implement either recursive or iterative quick sort, its your choice but you cannot use additional buffer, array or list, you must sort array in place.
9. Write a program to find intersection of two sorted array in Java?
Another interesting array interview question, where you need to treat array as Set. Your task is to write a function in your favorite language e.g. Java, Python, C or C++ to return intersection of two sorted array. For example, if the two sorted arrays as input are {21, 34, 41, 22, 35} and {61, 34, 45, 21, 11}, it should return an intersection array with numbers {34, 21}, For the sake of this problem you can assume that numbers in each integer array are unique.
10. There is an array with every element repeated twice except one. Find that element?
This is an interesting array coding problem, just opposite of question related to finding duplicates in array. Here you need to find the unique number which is not repeated twice. For example if given array is {1, 1, 2, 2, 3, 4, 4, 5, 5} then your program should return 3. Also, don't forget to write couple of unit test for your solution.
This is an interesting array coding problem, just opposite of question related to finding duplicates in array. Here you need to find the unique number which is not repeated twice. For example if given array is {1, 1, 2, 2, 3, 4, 4, 5, 5} then your program should return 3. Also, don't forget to write couple of unit test for your solution.
11. How to find kth smallest element in unsorted array?
You are given an unsorted array of numbers and k, you need to find the kth smallest number in the array. For example if given array is {1, 2, 3, 9, 4} and k=2 then you need to find the 2nd smallest number in the array, which is 2. One way to solve this problem is to sort the array in ascending order then pick the k-1th element, that would be your kth smallest number in array because array index starts at zero, but can you do better? Once you are able to solve this array coding question, you can solve many similar questions easily e.g. our next question.
12. How to find kth largest element in unsorted array?
This problem is exactly same as previous question with only difference being finding kth largest element instead of kth smallest number. For example if given array is {10, 20, 30, 50, 40} and k = 3 then your program should return 30 because 30 is the 3rd largest number in array. You can also solve this problem by sorting the array in decreasing order and picking k-1th element. I often seen this array question on Java interviews with 2 to 3 years experienced guys.
This problem is exactly same as previous question with only difference being finding kth largest element instead of kth smallest number. For example if given array is {10, 20, 30, 50, 40} and k = 3 then your program should return 30 because 30 is the 3rd largest number in array. You can also solve this problem by sorting the array in decreasing order and picking k-1th element. I often seen this array question on Java interviews with 2 to 3 years experienced guys.
13 How to find common elements in three sorted array?
Now we are coming on territory of tough array questions. Given three arrays sorted in non-decreasing order, print all common elements in these arrays.
Examples:
input1 = {1, 5, 10, 20, 40, 80}
input2 = {6, 7, 20, 80, 100}
input3 = {3, 4, 15, 20, 30, 70, 80, 120}
Output: 20, 80
14. How find the first repeating element in an array of integers?
Given an array of integers, find the first repeating element in it. We need to find the element that occurs more than once and whose index of first occurrence is smallest.
Examples:
Input: input [] = {10, 5, 3, 4, 3, 5, 6}
Output: 5 [5 is the first element that repeats]
15. How to find first non-repeating element in array of integers?
This array interview question is exactly opposite of previous problem, In that you need to find first repeating element while in this you need to find first non-repeating element. I am sure you can use similar approach to solve this problem, just need to consider non repeating element though.
16. How to find top two numbers from an integer array?
This is another one of the easy array questions you will find on telephonic round of Interviews, but its also little bit tricky. You are asked to find top two numbers not just the top or highest numbers? Can you think of how you would do it without sorting? before looking at solution.
17. How to find the smallest positive integer value that cannot be represented as sum of any subset of a given array?
This is another tough array question you will see on Amazon, Microsoft or Google. You have given a sorted array (sorted in non-decreasing order) of positive numbers, find the smallest positive integer value that cannot be represented as sum of elements of any subset of given set. What makes it more challenging is expected time complexity of O(n).
Examples:
Input: {1, 3, 6, 10, 11, 15};
Output: 2
18. How to rearrange array in alternating positive and negative number?
Given an array of positive and negative numbers, arrange them in an alternate fashion such that every positive number is followed by negative and vice-versa maintaining the order of appearance.
Number of positive and negative numbers need not be equal. If there are more positive numbers they appear at the end of the array. If there are more negative numbers, they too appear in the end of the array. This is also a difficult array problem to solve and you need lot of practice to solve this kind of problems in real interviews, especially when you see it first time. If you have time constraint then always attempt these kind of questions once you are done with easier ones.
Example:
Input: {1, 2, 3, -4, -1, 4}
Output: {-4, 1, -1, 2, 3, 4}
Input: {-5, -2, 5, 2, 4, 7, 1, 8, 0, -8}
output: {-5, 5, -2, 2, -8, 4, 7, 1, 8, 0}
19. How to find if there is a sub array with sum equal to zero?
There is whole set of array related questions which are based upon sub-array or only selective elements of array e.g. from some range, this is one of such problem. Here you are given an array of positive and negative numbers, find if there is a sub-array with 0 sum.
Examples:
Input: {4, 2, -3, 1, 6}
Output: true
There is a sub-array with zero sum from index 1 to 3.
20. How to remove duplicates from array in place?
Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.
Do not allocate extra space for another array, you must do this in place with constant memory.
For example,
Given input array A = [1,1,2],
Your function should return length = 2, and A is now [1,2].
When you see a questions which asked you do to sorting or task in place, it means you cannot use additional array or buffer, but using couple of variables is fine.
21. How to remove a given element from array in Java?
This is another array coding questions similar to previous one. Here you don't have to find and remove duplicates but a given number. In this problem you are given an array and a value, remove all instances of that value in place and return the new length. The order of elements can be changed. It doesn't matter what you leave beyond the new length.
22. How to merge sorted array?
Given two sorted integer arrays A and B, merge B into A as one sorted array. You may assume that A has enough space (size that is greater or equal to m + n) to hold additional elements from B. The number of elements initialized in A and B are m and n respectively. This is another intermediate array coding question, its not as simple as previous one but neither very difficult.
23. How to find sub array with maximum sum in an array of positive and negative number?
Another array coding question based upon sub-array. Here you have to find the contiguous sub-array within an array (containing at least one number) which has the largest sum.
For example, given the array [−2,1,−3,4,−1,2,1,−5,4],
the contiguous subarray [4,−1,2,1] has the largest sum = 6.
24. How to find sub array with largest product in array of both positive and negative number?
In this problem, your task is to write a program in Java or C++ to find the contiguous sub-array within an array (containing at least one number) which has the largest product.
For example, given the array [2,3,-2,4],
the contiguous subarray [2,3] has the largest product = 6.
25. Write a program to find length of longest consecutive sequence in array of integers?
Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.
Challenging part of this question is that your algorithm should run in O(n) complexity.
26. How to find minimum value in a rotated sorted array?
This is another advanced level array coding question and you should only attempt this one, once you have solved the easier ones. Suppose a sorted array is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
Find the minimum element.
You may assume no duplicate exists in the array. One follow-up question of this question is What if duplicates are allowed? Would this affect the run-time complexity? How and why?
27. Given an array of of size n and a number k, find all elements that appear more than n/k times?
Another tough array based coding questions from Interviews. You are given an array of size n, find all elements in array that appear more than n/k times. For example, if the input arrays is {3, 1, 2, 2, 1, 2, 3, 3} and k is 4, then the output should be [2, 3]. Note that size of array is 8 (or n = 8), so we need to find all elements that appear more than 2 (or 8/4) times. There are two elements that appear more than two times, 2 and 3.
1. Returns the largest sum of contiguous integers in the array
Example: if the input is (-10, 2, 3, -2, 0, 5, -15), the largest sum is 8
2. Return the sum two largest integers in an array
3. Given an array of integers write a program that will determine if any two numbers add up to a specified number N. Do this without using hash tables
1. Returns the largest sum of contiguous integers in the array
Example: if the input is (-10, 2, 3, -2, 0, 5, -15), the largest sum is 8
2. Return the sum two largest integers in an array
3. Given an array of integers write a program that will determine if any two numbers add up to a specified number N. Do this without using hash tables
28. How to reverse array in place in Java?
Now let's see one of the most frequently asked array interview question. You need to write a program which accepts an integer array and your program needs to reverse that array in place, which means you cannot use additional buffer or array, but one or two variables will be fine. Of course you cannot use any open source library or Java API method to directly solve this problem, you need to create your own logic. Here is one such logic to solve this problem :
29. Difference between array and linked list data structure?
This is a theoretical questions from phone interviews. There are several differences between array and linked list e.g. array stores element in contiguous memory location while linked list stores at random places, this means linked list better utilizes the places. Consequently, its possible to have large linked list in limited memory environment compare to array of same size. Advantage of using array is random access it provides if you know the index, while in linked list you need to search an element by traversing which is O(n) operation.
30. How to check if array contains a duplicate number?
This may look a repeated question because we have already done similar question, but in this question, most from Java interviews, you need to write a contains() like method from Collections, which returns true or false if you pass an element and it is repeated or not.
Nice algo . sharing for sharing this visit String program example
ReplyDelete