fayezelfar
BAN USERMy on-paper solution is almost identical, however, if you simply use an int array as the input, and convert the 1 to a 2 (for example), then you can just maintain the 'visited' property that way. You don't need the extra visited array O(nxm) space saving.
Your if statement would simply become
if(arr[i][j] == 1) { //do work; }
Just for an explanation as to why we should use a LinkedHashMap instead of a regular HashMap:
LinkedHashMap maintains the insertion order, whereas a regular hashmap cannot guarantee the insertion order. Since the question specifies the 'first' non-duplicate, order matters. Just a tidbit.
Also, I'm not sure if LinkedHashMap is available in all modern languages; this is a Java implementation.
A simple hashmap will do the trick.
public class RemoveDupesFromString
{
HashMap<Character, List<Integer>> characters = null;
public String removeDupes(String input)
{
//Error and edges
if(input == null || input.isEmpty()) {throw new IllegalArgumentException();}
if(input.length() == 1) { return input;}
characters = new HashMap<>();
int index = 0;
List<Integer> indeces = new ArrayList<>();
for(char current : input.toCharArray())
{
if(characters.containsKey(current))
indeces = characters.get(current);
else
indeces = new ArrayList<>();
indeces.add(index);
characters.put(current, indeces); //first occurrence
index++;
indeces = new ArrayList<>();
}
for(Entry<Character, List<Integer>> entry : characters.entrySet())
{
if(entry.getValue().size() > 1)
{
input = input.replace(entry.getKey().toString(), "");
}
}
return input;
}
}
I don't think there's a 'clever' or algorithmic way to solve this (happy to be corrected), but brute force would work well here.
Following is the code
public class Find2dPattern
{
private int[][] input;
private int[][] pattern;
public boolean patternExists(final int[][] input, final int[][] pattern)
{
//Errors and edge conditions.
if(input == null || pattern == null || input.length == 0 || input[0].length == 0 || pattern.length==0 || pattern[0].length == 0) { throw new IllegalArgumentException();}
if(input.length < pattern.length) { return false; }
if(input[0].length < pattern[0].length) { return false; }
if(input.length == pattern.length && input[0].length == pattern[0].length && input[0][0] != pattern[0][0]) { return false;}
else
{
this.input = input;
this.pattern = pattern;
for(int i = 0; i < input.length; i++)
for(int j = 0; j < input[i].length; j++)
{
if(input[i][j] == pattern[0][0]) //found potential
{
if(isMatch(i,j))
return true;
}
}
}
return false;
}
private boolean isMatch(int row, int column)
{
//Check for boundary
if(row + pattern.length-1 > input.length)
return false;
if(column + pattern[0].length-1 > input[0].length)
return false;
int k = 0 ; int l = 0;
while(k < pattern.length)
{
while(l < pattern[k].length)
{
if(input[row][column] != pattern[k][l]) //done
return false;
else
{
column++;
l++;
}
}
row++;
k++;
}
return true;
}
}
An answer that uses LinkedHashMap (to maintain insertion order). Overall O(n) time
public static Character firstNonRepeating(String s)
{
if(s == null || s.isEmpty()) { throw new IllegalArgumentException();}
if(s.length() == 1) { return s.charAt(0);}
//strip white space
s = s.replace(" ", "");
s = s.toLowerCase();
char[] split = s.toCharArray();
LinkedHashMap<Character, Integer> map = new LinkedHashMap<>();
for(char c : split)
{
if(map.containsKey(c))
map.put(c, map.get(c) + 1);
else
map.put(c, 1);
}
for(Entry<Character,Integer> entry : map.entrySet())
{
if(entry.getValue()==1)
return entry.getKey();
}
return null;
}
@coolhaitechie, that's a good observation - thank you! The array index should be Ceil(n/2) not Ceil(n/2) -1
- fayezelfar January 26, 2016Amazon uses Collabedit (collabedit.com). You can go there and practice before your interview (You should).
- fayezelfar January 24, 2016This is a minimum spanning tree starting at each node.
- fayezelfar January 19, 2016Center - 1 :)
Check out my solution.
However it gets interesting when the ceiling factor is 4.
Since the array is sorted, and we have a guarantee that such an element exists, then the answer is always
input[Math.ceil(n/2)]
Examples: (Realize that the repeated element always takes up >= n/2 elements.)
Input: {1,2,3,3,3,3,3,3,4,5,6}
Input: {3,3,3,3,3,3,4,5,6,7,8}
Input: {1,2,3,4,5,6,6,6,6,6,6}
Ceil(n/2) = Ceil(11/2) = 6
input[6-1] = repeated elements in all cases. There are some edge cases depending on the array length (0, 1, 2)
I'll update with the n/4 solution.
I could not find a way to resolve this question with the info provided without sorting the array/list first, and then finding the missing values from 1 - k-1 (assume MergeSort O(nLogn) followed by a scan of O(n)
Simply put, you cannot have an array of size K and the elements are 1-K-1
Example: K=5
Array {3,2,1,4, ??? } <-- It can't be 0 (>1), and it can't be 5 (<= k-1), and size of array = 4 not 5
Also, let's say that the OP did not write the question properly, and K is not the size of the array but the max value in the array
For example: {3,2,5,7}
Then K = 7 and the missing values are {1,4,6}. In this case, the array has to be scanned to get K, then processed to find missing values. 2*O(n)
Or let's say K is provided as input, then a valid input with K = 100 is array = {1}...
98 missing numbers.
Regardless, here's my solution that runs in 2*O(n). The assumptions I made:
1. K is provided is part of the input.
2. Missing elements are only one-apart from existing elements. For example
K = 13
Input is { 1,8,3,5,7,6,2,11,12}
Output would be {9,4,10}
I didn't test for edge cases by the way...
Code
public class FindMissing {
private HashMap<Integer, Boolean> tracker;
public List<Integer> findMissing(List<Integer> input, int K)
{
if(input == null) { throw new IllegalArgumentException();}
this.tracker = new HashMap<>();
//O(n)
for(int i = 0; i < input.size();i++)
{
Integer current, previous, next;
current = input.get(i);
//Make sure we stay within the bounds of 1 - K-1
if(current > 1)
previous = current-1;
else
previous = null;
if(current < K-1)
next = current+1;
else
next = null;
//Algorithm:
//When inspecting an entry in the input list, if the entry doesn't exist, insert it with value true (found)
//Check if the previous (-1) and next (+1) elements exist and insert with false, otherwise do nothing.
if(tracker.containsKey(current) == false) //New entry.
{
tracker.put(current,true);
if(previous != null)
{
if(tracker.containsKey(previous) ==false)
tracker.put(previous, false);
}
if(next != null)
{
if(tracker.containsKey(next) == false)
tracker.put(next, false);
}
}
else //we have encountered this key before
{
tracker.put(current, true); //Update to 'found'
if(previous != null)
{
if(tracker.containsKey(previous)==false)
tracker.put(previous, false);
}
if(next != null)
{
if(tracker.containsKey(next)==false)
tracker.put(next, false);
}
}
}
//Another O(n) to find the missing elements
List<Integer> missing = new ArrayList<>();
Iterator iter = tracker.entrySet().iterator();
Map.Entry<Integer, Boolean> entry = null;
while(iter.hasNext())
{
entry = (Entry<Integer, Boolean>) iter.next();
if(entry.getValue() == false)
missing.add(entry.getKey());
}
return missing;
}
}
And the driver code
List<Integer> input = new ArrayList();
input.add(1);
input.add(8);
input.add(3);
input.add(5);
input.add(7);
input.add(6);
input.add(2);
input.add(11);
input.add(12);
FindMissing find = new FindMissing();
List<Integer> missing = find.findMissing(input, 13); //K = 13, so elements are expected to be 1-12
System.out.println(missing.toString());
The solution is clever, but it's not O(n); you have multiple iterations. The trick here is to make a decision as you're traversing through the list.
A HashMap where you increment the value on collision is O(n), but then you have to iterate through the HashMap to see which values are >1, which has a worst case of O(N).
I don't think it's possible to do in O(N) because any algorithm will require two steps:
1. Parsing the data
2. Examining the data.
Any comments?
Also, I think you can repeat a particular number as long as it's >= 1 steps away from itself. For example:
1->2->5->1
That's a question I would ask the interviewer.
This is not O(n)..
- fayezelfar January 05, 2016@hnatsu is correct. Use a LinkedHashMap (to guarantee insertion order) and you should be good to go.
- fayezelfar January 05, 2016This is a variation on the Sliding Window algorithm without a fixed window size. Code is a bit messy but works. Appreciate comments and feedback
PS: This will print the consecutive sums (not the pair a,k)
Doesn't take into account the -ve numbers or real numbers scenarios.
public class SumOfConsecutives {
private static List<String> result = new ArrayList<>();
public static List<String> process(int n)
{
//Corner cases, assumes n is +ve
if(n < 0)
result.add("Invalid input");
if(n == 0)
result.add("No sums");
else if(n == 1)
result.add("0 + 1");
else if(n == 2)
result.add("No sums");
else // >1
{
String consecutive = "";
int sum = 0;
int start = 0;
int nextStart = 0;
//Naive approach
while(start <= Math.floor(n/2)) //for example: n = 20, start = 10.
{
while(sum < n)
{
sum += nextStart;
consecutive += nextStart + " + ";
nextStart++;
}
if(sum == n)
{
result.add(consecutive);
}
//reset
start = start+1;
nextStart = start;
consecutive = "";
sum = 0;
}
}
return result;
}
}
Mergesort would be better than quicksort because the worst case run-time is still O(nLogn), and in quicksort, the pivot choice using findMedium may be a bad choice.
- fayezelfar August 22, 2015I think using a HashSet (java) will do the trick. It implements the Set interface so uniqueness is guaranteed.
The code below will run in worst case O(i*j) time, but I THINK this is a mandatory step anyway to read the matrix. All other functions are O(1) time.
Note: no -ve K or other error condition checks.
public boolean findDuplicateWithinIndex(int[][] input, int k)
{
int currentK = 0;
for(int i = 0; i < input.length-1; i++)
{
for(int j=0; j < input[i].length-1; j++)
{
Integer cell = input[i][j];
System.out.println(cell.hashCode());
if(!hs.add(cell)) //collision
{
if(currentK < k) //found collision within k indices
return true;
}
if(currentK < k)
currentK++;
else
currentK = 0; //reset if we've surpassed K
}
}
return false; //no collision within K indices.
Sample input:
int[][] findDuplicateInput = new int[][] { { 1,2,3,4} , { 5, 6, 3, 8 }, {9, 2, 11, 12 } };
DuplicateEntriesWithinIndex duplicate = new DuplicateEntriesWithinIndex();
int k = 9;
boolean found = duplicate.findDuplicateWithinIndex(findDuplicateInput, k);//no collision
if(found)
System.out.println("Find duplicate: " + k);
else
System.out.println("No dupes.");
Output:
Dupe found at 9
The question is phrased very strangely; I have no idea what input 2 does and where 2MHz came from, but let's assume we have an array of integers and we want to find the max positive difference across two selections. The easiest way is to sort then
((last - first)) + ((last-1) - (first+1))
int selection1 = -1;
int selection2 = -2;
//Since the array is sorted, we don't need to check if the subtraction operation is +ve (incase of -ve values being allowed)
selection1 = A[A.length-1] - A[0];
selection2 = A[A.length-2] - A[1];
maxDifference = selection1 + selection2;
Insertion sort if the array is very small, mergesort otherwise = O(nlgn)
Comparison operation twice 2 * C
O(nlogn) + 2C
Didn't read other responses; apologies for duplicate
Two important things here:
1. Dictionary usage makes it easy
2. Rule: If (A[i] < A[i+1] ) and both A[i] and A[i+1] are markers (always true actually), then this is a subtraction operation, otherwise, addition
Code
import java.util.Dictionary;
import java.util.Hashtable;
public class ConvertRomanToDecimal
{
private Dictionary<Character, Integer> markers;
public ConvertRomanToDecimal()
{
markers = new Hashtable<Character, Integer>();
markers.put('I', 1);
markers.put('V', 5);
markers.put('X', 10);
markers.put('L', 50);
markers.put('C', 100);
markers.put('D', 500);
markers.put('M', 1000);
}
public int doConvert(String numeral)
{
int conversion = 0;
if(numeral == null || numeral.isEmpty())
{
conversion = 0;
}
else if(numeral.length() == 1)
{
Character single = Character.valueOf(numeral.charAt(0));
conversion = markers.get(single);
}
else
{
//RULE: If two markers are consecutive, and marker1 is less than marker2, this is a subtraction operation
//example IV = -1 + 5 = 4
//CM = -100 + 1000 = 900
//Input II
char[] components = numeral.toCharArray();
int i = 0;
for(i = 0; i < components.length; i++)
{
Integer current = markers.get(Character.valueOf(components[i]));
Integer next = 0;
if(i+1 < components.length)
next = markers.get(Character.valueOf(components[i+1]));
if(current < next) //subtraction
{
conversion -= current;
}
else
{
conversion += current;
}
}
}
return conversion;
}
}
To call:
ConvertRomanToDecimal conversion = new ConvertRomanToDecimal();
int decimalResult = conversion.doConvert("XXIV");
System.out.println(decimalResult);
Runtime: O(n) * O(1) ; where n is #of characters in the Roman numeral, and O(1) is cost of lookup from the dictionary.
I/O
XXX = 30
I = 1
MD = 1500
CM = 900
MIX = 1009
This code will run in O(n) and space complexity O(k) where K = max(arr1.length, arr2.length)
- fayezelfar February 17, 2016