Microsoft Interview Question SDE1s
Country: United States
Interview Type: Phone Interview
/**
If the size of A is even, partition the array about the lower value that makes up the median (ie the value which occurs at index A.length/2 - 1 if A is sorted in ascending order). If the size of A is odd,
partition the array about the median (ie. the value which occurs at index A.length/2 if A is sorted in ascending order). Call this pivot value mA.
Parititon array A so that values greater than mA are placed towards the right end of the array and elements less than or equal to mA
occurr towards the left half of the array. Parititon array b such that elements in B less than mA are placed towards the right end of B and
elements less than or equal to mA are placed towards the left end of the array. After this partitioning the right half of array A( A[A.length/2 - 1: A.length -1] if A is even size
A[A.length/2: A.length - 1] if A is odd sized) will contain values greater than values in array B at the same positions. The number of elements in this region is 1 + (A.length / 2),
hence countA will be > countB
Time Complexity: Average case: O(N), Worst case O(N^2)
**/
public void shuffle(int[] a, int[] b){
int k = a.length % 2 == 0 ? a.length / 2 - 1: a.length /2;
partitionAsc(a,k);
int i = 0;
int j = b.length - 1;
while(i < j){
if(b[i] < a[k]){
swap(b,i,j);
j--;
}
i++;
}
}
private void partitionAsc(int[] a,int k){
int i = 0;
int j = a.length - 1;
Random rnd = new Random();
while(i < j){
int piv = i + rnd.nextInt(j - i + 1);
piv = partitionHelp(a,piv,i,j);
if(piv == k){
break;
}
if(piv < k){
i = piv + 1;
}else{
j = piv - 1;
}
}
}
private int partitionHelp(int[] a, int piv, int i, int j){
swap(a,piv,j);
piv = j--;
while(i <= j){
if(a[i] > a[piv]){
swap(a,i,j);
j--;
}
i++;
}
swap(a,piv,i);
return i;
}
/*
arrayA = [12, 24, 8, 32]
arrayB = [13, 25, 32, 11]
Push each number into sorted list sequence and mark element
by mask which array it belongs to.
(A, B, both or 0. 0 means element yet used).
For instance:
elements: 32 -> 25 -> 24 -> 13 -> 12 -> 11 -> 8
mask: ab b a b a b a
shuffling goes from left to right.
* if element belongs to B array we can do nothing but connect
most right A element and remove corresponding masks. e.g.(32 - 8)
* if element belongs to A array we take closest right B element e.g.(32 - 25) end mark element as used.
* move to next unused element.
linear time if using double linked list but O(n) aux space.
*/
const int MASK_A = 1;
const int MASK_B = 2;
struct Node
{
Node(int v, unsigned int m)
: value(v)
, mask(m)
, next(nullptr) {}
int value;
unsigned int mask; // array's mask or both. 0- means item not used
Node *next;
};
class List
{
public:
List()
: m_head(nullptr) {}
~List() { clear(); }
void insert_value(int value, unsigned int mask)
{
if (!m_head) {
insert_after(nullptr, value, mask);
}
else
{
Node *iter = m_head;
Node *p = nullptr;
while (iter)
{
if (value > iter->value) {
break;
}
else if (value == iter->value)
{
iter->mask |= mask;
return;
}
p = iter;
iter = iter->next;
}
insert_after(p, value, mask);
}
}
void insert_after(Node *after, int value, unsigned int mask)
{
if (!m_head) {
m_head = new Node(value, mask);
}
else
{
if (!after)
{
Node *new_node = new Node(value, mask);
new_node->next = m_head;
m_head = new_node;
return;
}
Node *iter = m_head;
while (iter)
{
if (iter == after)
{
Node *new_node = new Node(value, mask);
new_node->next = iter->next;
iter->next = new_node;
break;
}
iter = iter->next;
}
}
}
void shuffle(std::vector<int> &outA, std::vector<int> &outB)
{
Node *iter = m_head;
while (iter)
{
if (iter->mask & MASK_B) // B-array
{
outB.push_back(iter->value);
// find most right A object
Node *i = iter->next;
Node *r = nullptr;
while (i)
{
if (i->mask & 1) { // object belongs to A-array
r = i;
}
i = i->next;
}
assert(r);
outA.push_back(r->value);
// clear masks
iter->mask &= ~MASK_B;
r->mask &= ~MASK_A;
}
if (iter->mask & MASK_A) // A-array
{
outA.push_back(iter->value);
// find closest right B-object
Node *i = iter->next;
while (i)
{
if (i->mask & MASK_B) {
break;
}
}
assert(i);
outB.push_back(i->value);
iter->mask &= ~MASK_A;
i->mask &= ~MASK_B;
}
iter = iter->next;
}
}
void clear()
{
Node *iter = m_head;
while (iter)
{
Node *next = iter->next;
delete iter;
iter = next;
}
}
protected:
Node *m_head;
};
TEST(Lists, Build_ArrayA_over_ArrayB)
{
List list;
const int SIZE = 4;
int arrayA[] = { 12, 24, 8, 32 };
int arrayB[] = { 13, 25, 32, 11 };
for (int i = 0; i < SIZE; ++i){
list.insert_value(arrayA[i], MASK_A);
}
for (int i = 0; i < SIZE; ++i) {
list.insert_value(arrayB[i], MASK_B);
}
std::vector<int> A, B;
list.shuffle(A, B);
EXPECT_TRUE(A.size() == SIZE && B.size() == SIZE);
int countA = 0;
int countB = 0;
for (int i = 0; i < SIZE; ++i)
{
if (A[i] == B[i]) {
continue;
}
if (A[i] > B[i]){
countA++;
}
else{
countB++;
}
}
EXPECT_TRUE(countA > countB);
}
1) Sorting array A
2) Place the minimum of A that can be more that B[i]
3) Repeat till you completed B Count
Seems O(N^2)
public List<int> ShuffleArray(List<int> A, List<int> B)
{
int outerLoop = 0;
int innerLoop = 0;
var s = new Sorting();
var min = int.MaxValue;
var result = new List<int>();
var sortedArray = s.SimpleSorting(A);
for (var i = 0; i < B.Count; i++)
{
//Console.WriteLine("Outer Loop : {0}", ++outerLoop);
outerLoop++;
for (var j = 0; j < sortedArray.Count; j++)
{
//Console.WriteLine("Inner Loop : {0}", ++innerLoop);
innerLoop++;
if (sortedArray[j] > B[i])
{
result.Add(sortedArray[j]);
sortedArray.Remove(sortedArray[j]);
break;
}
else if (min > sortedArray[j])
min = sortedArray[j];
if (j == sortedArray.Count - 1)
{
result.Add(min);
sortedArray.Remove(min);
min = int.MaxValue;
}
}
}
Console.WriteLine("Outer Loop : {0} Inner Loop : {1}", outerLoop, innerLoop);
return result;
}
/* Class BSTNode */
class BSTNode
{
BSTNode left, right;
int data, index;
/* Constructor */
public BSTNode()
{
left = null;
right = null;
data = 0;
index = 0;
}
/* Constructor */
public BSTNode(int n, int i)
{
left = null;
right = null;
data = n;
index = i;
}
/* Function to set left node */
public void setLeft(BSTNode n)
{
left = n;
}
/* Function to set right node */
public void setRight(BSTNode n)
{
right = n;
}
/* Function to get left node */
public BSTNode getLeft()
{
return left;
}
/* Function to get right node */
public BSTNode getRight()
{
return right;
}
/* Function to set data to node */
public void setData(int d)
{
data = d;
}
/* Function to get data from node */
public int getData()
{
return data;
}
public void setIndex(int i)
{
index = i;
}
public int getIndex()
{
return index;
}
}
/* Class BST */
class BST
{
private BSTNode root;
/* Constructor */
public BST()
{
root = null;
}
/* Function to check if tree is empty */
public boolean isEmpty()
{
return root == null;
}
/* Function to get the root */
public BSTNode getRoot()
{
return root;
}
/* Functions to insert data */
public void insert(int data, int index)
{
root = insert(root, data, index);
}
/* Function to insert data recursively */
private BSTNode insert(BSTNode node, int data, int index)
{
if (node == null)
node = new BSTNode(data, index);
else
{
if (data <= node.getData())
node.left = insert(node.left, data, index);
else
node.right = insert(node.right, data, index);
}
return node;
}
/* Function to search for an element recursively and find the index for swapping */
public int search(BSTNode r, int val)
{
int index=0;
while ( r != null)
{
int rval = r.getData();
index = r.getIndex();
if (val < rval){
r = r.getLeft();
if((r != null) && (r.getData() < val)) {
index = r.getIndex();
break;
}
else {
index = -1;
}
}
else if (val > rval) {
r = r.getRight();
if((r != null) && (r.getData() > val))
break;
}
}
return index;
}
}
public class ShuffleArray {
public static BST constructBST(BST bst, int[] arr){
for(int k=0; k<arr.length; k++) {
bst.insert(arr[k], k);
}
return bst;
}
public void traverseTree(BSTNode root, int[] arr) {
}
public static void main(String[] args) {
int A[]={12, 24, 8, 32};
int B[]={13, 25, 32, 11};
BST bst = new BST();
constructBST(bst, B);
int temp, ndx;
BSTNode node = bst.getRoot();
for(int k=0; k<A.length; k++) {
ndx = bst.search(node, A[k]);
if(ndx < 0) continue;
temp=A[ndx];
A[ndx]=A[k];
A[k]=temp;
}
System.out.print("A[");
for(int j=0;j<A.length; j++) {
if(j != (A.length -1))
System.out.print(A[j] +",");
else
System.out.println(A[j] +"]");
}
System.out.print("B[");
for(int j=0;j<B.length; j++) {
if(j != (B.length -1))
System.out.print(B[j] +",");
else
System.out.println(B[j] +"]");
}
}
}
There are of course the brute force solution and the random-shuffle-and-check solution but they are not very interesting in the algorithmic sense and the complexity is high.
My idea is to use a greedy approach that takes the maximal number from A and sets it against the maximal value in B that is less than that value. After the maximal value is positioned, continue to the second maximal value and do the same ignoring the position the previous number was set at. The process continues until there are no more numbers left or there is no number in B lower than the current number in A.
The most simple implementation of this algorithm would take O(n^3) time, but we can do better by sorting the arrays and going on A from max to min and doing a binary search on B. This solution would also require keeping the original position of each number in B pre-sort so that we can go back to the right shuffle without sorting. This is O(nlogn).
Approach could be. complexity is O(n^2)
for a given element from ArrayB, find the closest bigger integer value from ArrayA and make it the corresponding element in ArrayA location.
if no bigger value found, take the minimum value from the remaining elements in ArrayA.
here in this case:
ArrayA 12 24 8 32
ArrayB 13 25 32 11
function getClosest
{
this will take input from ArrayB[index i] and find the closest maximum value from ArrayA
if not found any bigger value, return minimum from ArrayA.
}
First Iteration:
consider ArrayB[1]=13 , closest bigger value from ArrayA is 24,
ArrayA 24
ArrayB 13 25 32 11
second iteration
consider ArrayB[2]=25 , closest bigger value from ArrayA is 32,
ArrayA 24 32
ArrayB 13 25 32 11
third iteration
consider ArrayB[3]=32 ,min value from ArrayA is 8, since remaining values in arrayA 8 and 12
ArrayA 24 32 8
ArrayB 13 25 32 11
Fourth iteration
consider ArrayB[4]=11 , closest bigger value from ArrayA is 32,
ArrayA 24 32 8 12
ArrayB 13 25 32 11
int main(){
int A[4] = {12, 24, 8, 32};
int B[4] = {13, 25, 32, 11};
int countA = 0;
int countB = 0;
int maxA = A[0];
for (int i = 0; i < 4; ++i){
if (A[i] > B[i]) ++countA;
else if (B[i] > A[i]) ++countB;
maxA = maxA > A[i] ? maxA : A[i];
}
if (countA < countB){
countA = 0;
countB = 0;
for(int j = 0; j < 4; ++j){
int max = maxA;
int idx = j;
for(int i = j; i < 4; ++i){
if(B[j] < A[i]) {
max = max < A[i] ? max : A[i];
idx = max < A[i] ? idx : i;
}
}
//swap
int temp = A[j];
A[j] = max;
A[idx] = temp;
}
}
for (int i = 0; i < 4; ++i){
cout << A[i] << " " << B[i] << endl;
}
}
void swap(int &x, int &y)
{
int t = x;
x = y;
y = t;
}
int searchForBigger(vector<int> a, int loc, int n)
{
for (int i = loc; i < a.size(); i++)
{
if (a[i] > n)
return i;
}
return loc;
}
void printList(vector<int> l)
{
vector<int>::iterator it;
for (it=l.begin(); it!=l.end(); ++it)
cout << ' ' << *it;
cout << endl;
}
void shuffelArray (vector<int> aArr, vector<int> bArr)
{
for (int i = 0; i < aArr.size(); i++)
{
if (aArr[i] > bArr[i])
continue;
else
{
int tmp = searchForBigger(aArr,i,bArr[i]);
if (i != tmp)
{
swap(aArr[i], aArr[tmp]);
}
}
}
printList(aArr);
printList(bArr);
}
int main() {
vector<int> a = {12,24,8,32};
vector<int> b = {13,25,32,11};
shuffelArray(a,b);
}
void swap(int &x, int &y)
{
int t = x;
x = y;
y = t;
}
int searchForBigger(vector<int> a, int loc, int n)
{
for (int i = loc; i < a.size(); i++)
{
if (a[i] > n)
return i;
}
return loc;
}
void printList(vector<int> l)
{
vector<int>::iterator it;
for (it=l.begin(); it!=l.end(); ++it)
cout << ' ' << *it;
cout << endl;
}
void shuffelArray (vector<int> aArr, vector<int> bArr)
{
for (int i = 0; i < aArr.size(); i++)
{
if (aArr[i] > bArr[i])
continue;
else
{
int tmp = searchForBigger(aArr,i,bArr[i]);
if (i != tmp)
{
swap(aArr[i], aArr[tmp]);
}
}
}
printList(aArr);
printList(bArr);
}
int main() {
vector<int> a = {12,24,8,32};
vector<int> b = {13,25,32,11};
shuffelArray(a,b);
}
The algorithm:
Sort both arrays. Step through B, looking to see if it is a match to the current element of B. If it is, store it in the answers hash. If not, append it to the "junk" array. Don't worry about matching higher elements in B until the lower ones have been matched first.
Complexity: n*log(n) (sort)
#include <vector>
#include <algorithm>
#include <unordered_map>
void ShuffleArray(std::vector<int>& a, const std::vector<int>& b)
{
std::unordered_map<int, int> answers;
std::vector<int> sa = a, sb = b, remainder;
std::sort(sa.begin(), sa.end());
std::sort(sb.begin(), sb.end());
for (int i = 0; i < (int)sa.size(); i++)
if (sa[i] > sb[answers.size()])
answers[sb[answers.size()]] = sa[i];
else
remainder.push_back(sa[i]);
for (int r : remainder)
answers[sb[answers.size()]] = r;
for (int i = 0; i < (int)sa.size(); i++)
a[i] = answers[b[i]];
}
void main()
{
std::vector<int> a = {12,24,8,32};
ShuffleArray(a, {12,25,32,11});
Print(a);
}
output: 24,32,8,12
void ShuffleArray(std::vector<int>& a, const std::vector<int>& b)
{
std::unordered_map<int, int> answers;
std::vector<int> sa = a, sb = b, remainder;
std::sort(sa.begin(), sa.end());
std::sort(sb.begin(), sb.end());
for (int i = 0; i < (int)sa.size(); i++)
if (sa[i] > sb[answers.size()])
answers[sb[answers.size()]] = sa[i];
else
remainder.push_back(sa[i]);
for (int r : remainder)
answers[sb[answers.size()]] = r;
for (int i = 0; i < (int)sa.size(); i++)
a[i] = answers[b[i]];
}
int[] arrayA = { 32, 24, 8, 12 };
int[] arrayB = { 13, 25, 32, 11 };
int[] sortedArrayA = arrayA.OrderBy(a => a).ToArray();
int[] sortedArrayB = arrayB.OrderBy(a => a).ToArray();
int[] answerA = new int[arrayA.Length];
List<int> lesserThanB = new List<int>();
int sortedArrayBStartPosition = 0, count = 0;
bool isGreaterThanAnElementInB = false;
for (int a = 0; a < sortedArrayA.Length; a++)
{
isGreaterThanAnElementInB = false;
for (int b = sortedArrayBStartPosition; b < sortedArrayB.Length; b++)
{
if (sortedArrayA[a] > sortedArrayB[b])
{
answerA[Array.IndexOf(arrayB, sortedArrayB[b])] = sortedArrayA[a];
isGreaterThanAnElementInB = true;
sortedArrayBStartPosition = b + 1;
break;
}
}
if (!isGreaterThanAnElementInB)
{
lesserThanB.Add(sortedArrayA[a]);
}
}
for (int i = 0; i < answerA.Length; i++)
{
if (answerA[i] == 0)
{
answerA[i] = lesserThanB[count];
count++;
}
}
int[] arrayA = { 32, 24, 8, 12 };
int[] arrayB = { 13, 25, 32, 11 };
int[] sortedArrayA = arrayA.OrderBy(a => a).ToArray();
int[] sortedArrayB = arrayB.OrderBy(a => a).ToArray();
int[] answerA = new int[arrayA.Length];
List<int> lesserThanB = new List<int>();
int sortedArrayBStartPosition = 0, count = 0;
bool isGreaterThanAnElementInB = false;
for (int a = 0; a < sortedArrayA.Length; a++)
{
isGreaterThanAnElementInB = false;
for (int b = sortedArrayBStartPosition; b < sortedArrayB.Length; b++)
{
if (sortedArrayA[a] > sortedArrayB[b])
{
answerA[Array.IndexOf(arrayB, sortedArrayB[b])] = sortedArrayA[a];
isGreaterThanAnElementInB = true;
sortedArrayBStartPosition = b + 1;
break;
}
}
if (!isGreaterThanAnElementInB)
{
lesserThanB.Add(sortedArrayA[a]);
}
}
for (int i = 0; i < answerA.Length; i++)
{
if (answerA[i] == 0)
{
answerA[i] = lesserThanB[count];
count++;
}
}
#Python
a = raw_input("Enter array 1: ")
b = raw_input("Enter array 2: ")
a = sorted(map(int, a.split(",")))
b = map(int, b.split(","))
c = sorted(b)
count = 0
temp = []
b_dict = {}
for a1 in a:
if a1 >= c[count]:
if not b_dict.get(c[count]):
b_dict[c[count]] = []
b_dict[c[count]].append(a1)
count += 1
else:
temp.append(a1)
for t in temp:
b_dict[c[count]] = [t]
count += 1
for id, b1 in enumerate(b):
a[id] = b_dict[b1][0]
del(b_dict[b1][0])
print a
print b
I thought about other approaches such as keeping a hashmap with arraylist and then try to eliminate the ones that are not required to be updated. But the implementation seems to be complicated.
Here is my simple approach:
1. Find out how many numbers that need to be adjusted
2. Then for each element, if a[] is less than b[] then find the next one who is potential candidate and swap.
Following is the code for the same in java of O(n*n).
private static void shuffleA(int[]a, int[]b) {
if (a == null || b == null) {
throw new RuntimeException("Either a or b is null");
}
if (a.length != b.length) {
throw new RuntimeException("Array lengths are not equal");
}
int na = 0;
int nb = 0;
for (int i = 0; i < a.length; i++) {
if (a[i] > b[i]) {
na++;
} else if (a[i] < b[i]) {
nb++;
}
}
if (nb < na) return;
int it = nb - na + 1;
for (int i = 0; i < a.length && it > 0; i++, it--) {
int j = i;
while (j < a.length) {
if (a[j] <= b[i])
break;
j++; i++;
}
j++;
while(j < a.length && a[j] < b[i]) j++;
if (j >= a.length) continue;
// swap
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
Using Random Shuffle
public List<int> ShuffleArray(List<int> aArray, List<int> bArray) { int aCount = 0; int bCount = 0; var rand = new Random(); while(aCount <= bCount) { //Random Shuffle var randomNumber = rand.Next(1, aArray.Count); var temp = aArray[0]; aArray[0] = aArray[randomNumber]; aArray[randomNumber] = temp; aCount = 0; bCount = 0; for(var i = 0; i < aArray.Count; i ++) { if (aArray[i] > bArray[i]) aCount++; else if (aArray[i] < bArray[i]) bCount++; } } return aArray;}
- maksymas March 20, 2017