King@Work
BAN USER- 8of 8 votes
AnswersYou are given an array that contains integers. The integers content is such that every integer occurs 3 times in that array leaving one integer that appears only once.
- King@Work
Fastest way to find that single integer
-- using memory.
-- not using any external memory.
eg: [2,1,4,5,1,4,2,2,4,1]| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm
We can do it in O(n).
If input string is all lower case english alphabets then we can create a 1-D array
public static char findNonRepeating(String str){
if(null == str || str.length() == 0) return '';
int[] arr = new int[26];
Arrays.fill(arr, 0);
for(int i=0; i<str.length(); i++){
arr[str.charAt(i) - 'a'] = arr[str.charAt(i) - 'a'] + 1;
}
for(int i=0; i<str.length(); i++){
if(arr[str.charAt(i) - 'a'] == 1)
return str.charAt(i);
}
return '';
}
This will do it in constant memory. We are using the source array to mark if we have visited the number before or not.
package algorithms;
public class FindRepeatingNums {
public static void main(String[] args) {
int[] arr = {1,3,0,2,1,4,5,3,3,0};
findRepeatingNums(arr);
}
public static void findRepeatingNums(int[] arr){
if(arr == null || arr.length <2) return;
for(int i=0; i<arr.length; i++){
if( arr[Math.abs(arr[i])] >= 0) arr[Math.abs(arr[i])] = -1 * arr[Math.abs(arr[i])] ;
else System.out.println(Math.abs(arr[i]));
}
}
}
Its just like coin change problem.
package dp;
import java.util.Arrays;
public class NSteps {
public static void main(String[] args) {
int[] possibleSteps = {1,2,3};
long startTime = System.nanoTime();
System.out.println(getNumberForSteps(possibleSteps, 30));
long stopTime = System.nanoTime();
System.out.println("Time taken: " + (stopTime - startTime));
startTime = System.nanoTime();
dpSolution(possibleSteps, 30);
stopTime = System.nanoTime();
System.out.println("Time taken2: " + (stopTime - startTime));
}
public static int getNumberForSteps(int[] steps, int n){
if (n == 0) return 1;
if (n < 0) return 0;
return getNumberForSteps(steps, n-steps[0]) + getNumberForSteps(steps, n-steps[1]) + getNumberForSteps(steps, n-steps[2]);
}
public static void dpSolution(int[] steps, int n){
int[] arr = new int[n+1];
arr[0] = 0;
for(int i=1; i <arr.length; i++){
for(int step: steps){
if(i-step == 0){
arr[i] += 1;
}else if(i-step < 0){
continue;
}else{
// i - step > 0
arr[i] += arr[i-step];
}
}
}
System.out.println(Arrays.toString(arr));
System.out.println(arr[n]);
}
}
*Java Solution* with test cases
Runs like a charm! Easy Problem though
import java.util.Arrays;
public class ArrayProblems{
public static void print(String str){
System.out.println(str);
}
public static void main(String[] args){
int[] arr = {-1,-2,1,2,-100};
int[] arr2 = {1,-1,2,-2,3,-3};
int[] arr3 = {-1,-2,-3,-4,-5};
print(Arrays.toString(arr));
movePositiveToEndMinSwaps(arr);
print(Arrays.toString(arr));
print(Arrays.toString(arr2));
movePositiveToEndMinSwaps(arr2);
print(Arrays.toString(arr2));
print(Arrays.toString(arr3));
movePositiveToEndMinSwaps(arr3);
print(Arrays.toString(arr3));
}
public static void movePositiveToEndMinSwaps(int[] arr){
if(arr == null || arr.length <= 1) return;
int i =0, j= arr.length-1;
int swaps = 0;
while(i<j){
while(j>0 && arr[j]>0 ) j--;
while(i < arr.length && arr[i]<0) i++;
//swap i and j values
if (i >= j) break;
int tmp = arr[j];
arr[j] = arr[i];
arr[i] = tmp;
swaps++;
}
System.out.println("Moved all +ve nums to end in " + swaps + " swaps.");
}
}
short[] charCount = new short[26]; // assuming all chars are same case
short[] needleCount = new short[26];
so for needle = "abbdd" we will have needleCount = [1,2,0,2,....0,0,0]
we calculate charCount in same way for every string in haysack whose length is same.
Not sure if a better solution is there. If no duplicates are allowed then we can use BitSet and can xor them to check if both are same or not.
There are multiple ways to do it. One is to sort the strings and then compare them.
Complexity will be m * n log(n) where haysack contains m strings. Some optimizations can be made as to first check the length of the string in haysack before sorting it.
Another is to use use an array of 26 and then marking the chars with 1 if in needle. Use it like a hash map and also maintain another array of 26 chars for duplicates.
Its Simple.. all month days are fixed. Leap year calculation is single line. O(1)
int leapyear (int yr)
{
if ((yr % 4 == 0) && !(yr % 100 == 0))
cout<<yr;
else if (yr % 400 == 0) // year divisible by 4 but not by 100
cout<<yr;
return yr;
}
I agree that if we need number of milli-seconds and support different time zones then writing calendar is complex but in this case none of that is required.
- King@Work April 11, 2013if(sameYearDates){
long daysNum = |CountDaysFromJan1(d1)-CountDaysFromJan1(d2)|;
if(daysNum<30) // less a month
else if (daysNum > 30) // greater than a month
else // excatly a month
}
else if(Y1-Y2==1) { // assuming y1 is before y2 put some more code to arrange y1 y2
if(Y1IsLeap)
int days1 = 366-CountDaysFromJan1(d1);
else
days1 = 365-CountDaysFromJan1(d1);
int days2 = CountDaysFromJan1(d1);
int daysNum = days1 +days2 ; // apply same logic like above for finding (>,<,==)month
}
else
// more than a month
A lot of code reuse can be done on this.. on doing it right now coz in hurry.
-- Second approach is if API is available get the long milliseconds and then do the math.
At start keep teh count of number of zero till you encounter first '1' bit. At this time calculate the decimal number.
Now keep updating it using the left shift concept.
Left shift with 0 doubles the number.
Left shift with 1 2*number+1
Once you have the number it is easy to check that it is divisible by three or nor.
When you use synchronized method for static method you get lock on the class and not on class object. So in the above example you have two separate locks. On the the class and other on its object. No one blocks the other one and hence the race condition can happen.
Solution: Either use 2 variables or change static method to non-static.
right. wat abt hash map? :) it solves the problem. Good thing about hashmap is that it is not ordered. Though I doubt that everytime you get a number it is same or not. But the hashmap design says that there is no gurantee that the order is same every time iterate.
I think there should be some better solution of this.
Repcharlesndouglass, Employee at VANS
I am Michael from Nantucket USA. I am working as a Power plant dispatcher in Matrix Design company. I am ...
Repsylviarashtons, Accountant at ASAPInfosystemsPvtLtd
I am a journalist. Outside the office, I enjoy additional writing time in a different genre of historical fiction. I ...
Repsusanaminick, Research Scientist at CapitalIQ
I am Susan from Dallas, I am working as a Property manager in Kohl's Food Stores company. I love ...
Use recursion for simplicity
- King@Work June 05, 2017