Raj
BAN USER- 2of 2 votes
Answersfind first not-repeating character by iterating through the length of the string only once and by using constant space.
- Raj in United States| Report Duplicate | Flag | PURGE
Amazon SDET Algorithm
Time : O(n)
1. initialize leftSum, rightSum to 0
2.find sum of all elements - rightSum
3. for each element in array
a) reduce cur element from rightSum
b) compare rightSum with Left sum, if same return
c) add cur element to leftSum
int findPivot(int a[]){
int leftSum=0,rightSum=0;
for(int i=0;i<a.length;i++){
rightSum+=a[i];
}
for(int i=0;i<a.length;i++){
rightSum-=a[i];
if(leftSum == rightSum)
return i;
leftSum+=a[i];
}
}
1. Create max heap of size k
2. iterate through first list
if no. of elements in heap is less than k
insert in heap
else
check if cur element is less than max value in heap
extract max from heap and insert cur value
3. repeat step 2 for second list
4. extract all elements of heap and print
// Time : O((m+n)*logk), Space : O(logk)
public static void findKSmallestElementsFromTwoLists(List<Integer> list1, List<Integer> list2, final int k){
final PriorityQueue<Integer> pq = new PriorityQueue<>(k, new Comparator<Integer>() {
@Override
public int compare(Integer i1, Integer i2) {
return i2-i1;
}
});
for(int i:list1){
if(pq.size() < k){
pq.offer(i);
}
else{
if(i < pq.peek()){
pq.poll();
pq.offer(i);
}
}
}
for(int i:list2){
if(pq.size() < k){
pq.offer(i);
}
else{
if(i < pq.peek()){
pq.poll();
pq.offer(i);
}
}
}
System.out.println(pq);
}
void rotateMatrixByClockwise(int matrix[][], int m, int n) {
int r = 0, c = 0;
int pre, cur;
while (r < m && c < n) {
if (r + 1 == m || c + 1 == n)
break;
pre = matrix[r + 1][c];
for (int i = c; i < n; i++) {
cur = matrix[r][i];
matrix[r][i] = pre;
pre = cur;
}
r++;
for (int i = r; i < m; i++) {
cur = matrix[i][n - 1];
matrix[i][n - 1] = pre;
pre = cur;
}
n--;
if (r < m) {
for (int i = n - 1; i >= c; i--) {
cur = matrix[m - 1][i];
matrix[m - 1][i] = pre;
pre = cur;
}
}
m--;
if (c < n) {
for (int i = m - 1; i >= r; i--) {
cur = matrix[i][c];
matrix[i][c] = pre;
pre = cur;
}
}
c++;
}
}
Using hashmap
firstly, if we use list related api Running time will be O(mn). Because, contains() in list is O(n)
Secondly, if we use set related api it maintains only unique elements but not how many times it repeated
To solve these two things we use hash map. It contains unique elements and maintains as value how many times each element is repeated. Also, we are using linkedhashmap to preserve the order in which elements occurred
Importantly, add/contains/remove methods are O(1)
// Time : O(m+n), Space : O(max(m,n))
public static List<Integer> findUncommonElements(Integer a1[], Integer a2[]) {
if (null == a1 && null == a2) {
return null;
}
if (null == a1 || a1.length == 0)
return Arrays.asList(a2);
if (null == a2 || a2.length == 0)
return Arrays.asList(a1);
List<Integer> result = new ArrayList<>();
Map<Integer, Integer> countMap = new LinkedHashMap<>();
for (int i : a2) {
countMap.compute(i, (key, value) -> {
if (null == value)
return 1;
return value + 1;
});
}
for (int i : a1) {
if (countMap.containsKey(i)) {
countMap.remove(i);
} else {
result.add(i);
}
}
for (int key : countMap.keySet()) {
for (int i = 0; i < countMap.get(key); i++) {
result.add(key);
}
}
return result;
}
Here is the efficient version, Time : O(n). Also similar approach as we do regularly find height of a tree In regular tree, we assume when hit null it's a leaf. But, in this case leaf is Circular DLL. So, if my cur node's left's right is pointing to cur node then it's a leaf.
public int height(BinaryTreeNode<Integer> root) {
if (null == root) {
return 0;
}
if (isLeaf(root)) {
return 1;
}
return 1 + Math.max(height(root.left), height(root.right));
}
private boolean isLeaf(BinaryTreeNode<Integer> root) {
BinaryTreeNode<Integer> left = root.left;
if (null == left)
return false;
return left.right == root;
}
Even, I got O(mn) solution. I would like to see if some one have better solution than this.
public static void replace() {
String[] symbols = { "I", "Am", "cro", "Na", "le", "abc" };
String[] arr = { "Amazon", "Microsoft", "Google" };
for (int i = 0; i < arr.length; i++) {
String name = arr[i];
String selectedSymbol = "";
for (String symbol : symbols) {
if (name.contains(symbol)) {
if (symbol.length() > selectedSymbol.length())
selectedSymbol = symbol;
}
}
if (selectedSymbol.length() > 0) {
arr[i] = name.replace(selectedSymbol, "[" + selectedSymbol + "]");
}
}
System.out.println(Arrays.toString(arr));
}
// Time :O(n2) , Space :O(n2)
public int longestPalindromeSubString(String str) {
if (null == str || str.length() == 0)
return 0;
if (str.equals(new StringBuilder(str).reverse().toString()))
return str.length();
int t[][] = new int[str.length()][str.length()];
for (int i = 0; i < str.length(); i++) {
t[i][i] = 1;
}
for (int l = 2; l <= str.length(); l++) {
for (int i = 0; i < str.length() - l + 1; i++) {
int j = i + l - 1;
if (str.charAt(i) == str.charAt(j)) {
if (l == 2) {
t[i][j] = 2;
} else {
t[i][j] = 2 + t[i + 1][j - 1];
}
} else {
t[i][j] = Math.max(t[i + 1][j], t[i][j - 1]);
}
}
}
System.out.println(t[0][str.length() - 1]);
return t[0][str.length() - 1];
}
I agree with smallchallenges upto certain extent, however my answer goes like this.
If we know what kind of input is we are receiving and if that input is in given range, then we can use counting sort/bucket sort depending on input. - Time : O(n)
If we know the (1) what kind of input, (2)numbers are random(but not in range), (3) numbers are not already sorted(ascending/descending) , then choose quick sort
- Time : O(nlogn)
If we don't know anything about input - heap sort/Merge Sort - Time : O(nlogn)
// Time : O(n), Space : O(n)
// In java, string manipulations cannot be done in constant space
public static String reverseSetence(String str) {
StringBuilder sb = new StringBuilder(str);
Pattern p = Pattern.compile("[a-zA-Z0-9]+");
Matcher m = p.matcher(str);
while (m.find()) {
reverse(sb, m.start(), m.end() - 1);
}
return sb.toString();
}
public static void reverse(StringBuilder sb, int l, int r) {
while (l < r) {
swap(sb, l++, r--);
}
}
public static void swap(StringBuilder sb, int i, int j) {
char temp = sb.charAt(i);
sb.setCharAt(i, sb.charAt(j));
sb.setCharAt(j, temp);
}
Easiest way using arthimatic sequence properties
Time : O(n), Space : O(1)
public boolean checkArrayIsArthimaticSequence(int[] a, int n) {
int min = findMin(a,n);
int max = findMax(a,n);
int common_diff = (max - min) / (n - 1);
// check for allowed maximum
// for nth term
int possible_max = min + (n - 1) * common_diff;
if (possible_max != max)
return false;
// check for difference between any elements
for (int i = 0; i < n - 1; i++) {
if (Math.abs(a[i] - a[i + 1]) % common_diff != 0)
return false;
}
return true;
}
public int findKthSmallest(BinaryTreeNode<Integer> root, int k) {
if (null == root)
return -1;
int n = BinaryTree.size(root);
int a[] = new int[n];
inorder(root, a);
Arrays.sort(a);
return a[k - 1];
}
int i = 0;
public void inorder(BinaryTreeNode<Integer> root, int[] a) {
if (root != null) {
inorder(root.left, a);
a[i++] = root.data;
inorder(root.right, a);
}
}
- Raj January 23, 2017