Google Interview Question Software Engineer / Developers
Country: United States
Interview Type: Phone Interview
Because all digits are in [0, 9], so instead of sorting, counting each of them might be faster, down from O(n*log(n)) to O(n). The remaining is the same. Finding a target digit needs O(1) time, so the total is still O(n).
What happens in this case where set1={2,4,1,0} and set2={2,4,1,9}
Here you will need to notify backwards to choose from a number which is greater at a previous level.
yea, that's why I sort set1 first. in this way, the next we select is greater than the previous one.
This is O(x^2) in the worst-case.
Consider if Y is already as big as it can be, or sorted in descending order. Now you will traverse to the end of x at each iteration, resulting in a quadratic algorithm.
@steve. yes, you are right. one opt that i can think of is to use binary search to find a right digit in x that is greater than or equal to the corresponding digit in y, which reduce the time to O(nlogn).
I think linear time can be achieved. Assume the length of x and y are equal.
The naive idea is counting the number but not sorting, so that constant time needed to find a suitable candidate.
def arrange( ypos )
ydigit = y[ypos]
if ypos == last position of y
if there is nonzero element in count whose index is larger than ydigit # constant time
result[ypos] = the index of the nonzero element
return true
else return false
if count[ydigit] > 0
count[ydigit]--
if arrange(ypos + 1)
result[ypos] = ydigit
return true
else
if there is i such that i > ypos and count[i] > 0 # constant time
result[ypos] = the smallest i
result[ypos + 1, ..., ylast] = the smallest number can be formed by the rest in count # linear time
return true
else
return false
else
if there is i such that i > ypos and count[i] > 0 # constant time
result[ypos] = the smallest i
result[ypos + 1, ..., ylast] = the smallest number can be formed by the rest in count # linear time
return true
else
return false
def main()
for i in x
count[i]++
if arrange(left-most index)
print result
else
no arrange satisfying the requirement.
Since scanning the count array require constant time, the alg. would be linear time.
Don't know whether it will work :)
This solution is partially incorrect. It will work optimally with following modifications:
1. Sort the X so that we can do binary search every time.
2. When you look for an element in X and there is no element in X that is equal to the digit we are looking for, then you also need to consider the case when unused digit is smaller than the digit we are looking for
3. While doing binary search, if you find the desired digit multiple times, process it just once.
Optimum time complexity would be O(n*logn)
You don't need to backtrack if you are out of digits that are higher then the one in y.
Why not just generate the largest possible number with the remaining digits (even though it will be lower then y) and then run next permutation algorithm on the result?
Why consider smaller one?
Consider the situation that we are in position i and all j < i s.t. result[j]==y[j], and there remains no digit equivalent to y[i]. If we choose a smaller one, since it's the most significant digit different with y, no matter how we permute remaining digit, the result wouldn't larger than y. On the other hand, if we choose a digit larger than y[i], we are guaranteed that the result > y. So we just need to find the smallest permutation for the digit left and ignore what remains in y. That's why I think only larger digit should be considered. May I know why this is wrong? Thx
Later edit: @warrior: in case your last reply was not referring to my comment then just ignore what I just wrote :)
I didn't say that your solution is incorrect (it is actually correct), but i don't like the fact that it uses backtracking.
Regarding to what I proposed you misunderstood one thing: it doesn't permute the remaining digits, it finds the next permutation for the whole number.
Here is an example:
X = [1, 6, 7, 3, 2], Y = [6, 7, 8, 9, 1]
Algorithm:
[6 ?] --> [6, 7, ? ] -- no remaining larger digits? ---> [6, 7, 3, 2, 1] -- next permutation --> [7, 1, 2, 3, 6]
You can sort A first, using count sort O(N)
public static int[] getLowest(int[] A, int[] B){
if(A== null || B == null || A.length != B.length){
return null;
}
int length = A.length;
if(length < 2){
if (A[0] < B[0])
return null; // no solution
else return A;
}
// Assume A is sorted.
int i = 0; int j = 1; int k = 0;
while(i<length && j< length && k< length){
if(A[i] < B[k]){
swap(A, i, j);
j++;
}
else if(A[i] == B[k]){
i++; k++;
}
else{
break;
}
}
return A;
}
This looks really close but consider the input
A=[1,3,3,4] and B=[4,3,2,1]
I think if you set j=i+1 (after the i++ statement) your algorithm should be good.
No that wont work because the value of 'j' crossing the 'length'.
But good example to check the algorithm!
//before calling this function check if the greatest possible number from x is greater then y or not , if it is gthen a hovernum exist.
// has the numbers of x in sorted form
//compv is a function which compares digits of vectors one by one till digitlevel and if it finds any digit of v1 > v2 it returns 1 , if v1<v2 returns -1 , if all equal then returns 0
bool nextNum(set<int> &sx , vector<int> &y , vector<int> &result){
static int digitlevel = 0;
set<int>::iterator it;
if(digitlevel+1 == y.size()){
result.push_back(*it);
if(compv(result , y , digitlevel) <=0){ //returns 0 if vectors are equal from 0 to digitlevel
result.pop_back();
return -1;
}else{
return 0;
}
}
if(compv(result , y , digitlevel) == 0){
it = sx.lowerbound(y[digitlevel]);
}
for(;it!=sx.end();){
result.push_back(*it);
sx.erase(it++);
digitlevel++;
if(!nextNum(sx,y,result)) return true;
digitlevel--;
sx.insert(result.back());
result.pop_back();
}
return -1;
}
1) Sort the Xs
2) For each y value find the x that is equal to or greater than the y using binary search and this integer in x is part of your rearrangement x.
Time: O(log x * (x+y))
Note: I assume x and y have the same number of digits
This is an O(N) algorithm:
Here is pseudocode with explanations:
1. create digits histogram for x in order to be able to efficiently extract a given digit from it
for (int i = 0; i < x.size(); ++i)
++histogram[x[i]];
2. start from most significant digit (assuming its index is 0) and basically use the same digit from y on the same position in result. If at some point you don't have that digit, you select the smallest digit higher than the digit you're looking for and then put the remaining digits in increasing order and you have your answer. If there is no larger digit then put the remaining digits in decreasing order.
In this case you've got yourself the closest number to Y, but lower. So you need to generate the next lexicographic permutation - see step 3 (in C++ there is std::next_permutation that just does that).
for (i = 0; i < y.size(); ++i)
{
try to extract digit y[i] from histogram
if (y[i] found in histogram) then { result[i] = y[i] }
else if (there is a digit d in histogram s.t. d > y[i])
{
result[i] = the smallest digit d from histogram st d>y[i]
// put remaining digits in increasing order
result[(i+1)..y.size()] = histogram.sortIncreasing();
// found the number, woohoo!!
break for loop;
}
else /* there are only digits lower than y[i] */
{
// put remaining digits in decreasing order
result[i..y.size()] = histogram.sortDecreasing();
// found closest number smaller then y
break for loop;
}
}
3. Now the variable result is either:
- the result we're looking for, i.e.: the closest number greater or equal to y
- the closest number less than y, case in which we need to generate the next lexicographic permutation of digits
So we need to do this check:
if (result < y)
result = nextPermutation(result);
Forgot to mention that there is no solution in case nextArrangment() method fails (i.e. this is the highest arrangement for x digits and yet still lower than y).
private static void nextHighest(){
Set<Integer> y = new HashSet<Integer>();
y.add(new Integer(1));
y.add(new Integer(2));
y.add(new Integer(3));
y.add(new Integer(4));
Set<Integer> x = new HashSet<Integer>();
x.add(new Integer(1));
x.add(new Integer(2));
x.add(new Integer(3));
x.add(new Integer(4));
String num = "";
for(int i: y){
Integer remove = getDigit(x, i);
num += remove.toString();
x.remove(remove);
}
System.out.println(num);
}
private static Integer getDigit(Set<Integer> x, int close){
Integer currentLowest = -1;
for(int i: x){
if(currentLowest < 1){
currentLowest = i;
continue;
}
if(currentLowest<=close || i>close && (i+close)<(currentLowest+close)){
currentLowest = i;
}
}
return currentLowest;
}
use a hash table to store digits and their occurrences instead of performing the binary search on the sorted array
first to choose the same digit for every position and recursively choose the next position with remaining digits
if it failed to yield a valid combination or the same digit doesn't exist, choose the next larger digit and arrange the position on left with remaining digits in the ascending order
if no lager digit, return false
Time: O(n)
ideone.com/8pDJIG
Test Cases
2 1 4 5
2 1 4 6
[2, 1, 5, 4]
1 6 7 3 2
6 7 8 9 1
[7, 1, 2, 3, 6]
1 2 3 4
2 4 3 9
[3, 1, 2, 4]
1 2 3 4
2 4 1 0
[2, 4, 1, 3]
4
1 3 3 4
4 3 2 1
[4, 3, 3, 1]
public void findClosestPermuntation(int[] x, int[] y)
{
int[] z = new int[x.length];
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for(int i = 0; i < 10; i++) map.put(i, 0);
for(int i: x) map.put(i, map.get(i) + 1);
r(y, z, 0, map);
System.out.println(Arrays.toString(z));
}
private boolean r(int[] y, int[] z, int i, Map<Integer, Integer> map)
{
if(i == z.length) return true;
int j;
for(j = y[i]; j < 10 && map.get(j) == 0; j++);
if(j == y[i]) {
z[i] = y[i];
map.put(j, map.get(j) - 1);
if(r(y, z, i + 1, map)) return true;
map.put(j, map.get(j) + 1);
z[i] = 0;
for(j = y[i] + 1; j < 10 && map.get(j) == 0; j++);
}
if(j > 9) return false;
z[i] = j;
map.put(j, map.get(j) - 1);
int k = i + 1;
for(int p = 0; p < 10; p++) {
for(int q = 0; q < map.get(p); q++) {
z[k] = p;
k++;
}
}
return true;
}
Am I the only one that think this is a DFS algo? Any reason why that's not used?
int rearrange (const int & x, const int & y)
{
std::string xStr;
{
std::stringstream ss;
ss << x;
xStr = ss.str ();
}
std::string yStr;
{
std::stringstream ss;
ss << y;
yStr = ss.str ();
}
std::sort (xStr.begin (), xStr.end ());
std::reverse (xStr.begin (), xStr.end ());
std::stack<std::string> newX;
for (int i = 0; i < xStr.size (); ++i)
{
newX.push (xStr.substr (i, 1));
}
while (! newX.empty ())
{
std::string current = newX.top ();
newX.pop ();
std::cout << "\nConsidering [" << current << "]." << std::endl;
if (current < yStr.substr (0, current.size ()))
{
continue;
}
if (current.size () == yStr.size () && current > yStr)
{
std::stringstream ss;
ss << current;
int retVal (0);
ss >> retVal;
return retVal;
}
std::string mark; // Handle duplicates
{
for (int i = 0; i < xStr.size (); ++i)
{
mark.append ("F");
}
for (int i = 0; i < current.size (); ++i)
{
std::size_t tmp = xStr.find (current.at (i));
if (std::string::npos == tmp)
{
// This should never happen in tis algo ...
}
else
{
mark.at (tmp) = 'T';
}
}
}
for (int i = 0; i < xStr.size (); ++i)
{
if (mark.at (i) == 'F')
{
newX.push (current + xStr.substr (i, 1));
}
}
}
return -1; // Impossible to get such an int
}
//sort the array X in ascending order before calling this method.
bool rearrangeX(int*x, int* y, int size)
{
if (size == 0)
return true;
for (int i = 0; i < size; i++)
{
bool found = false;
if (x[0] >= y[0])
{
found = rearrangeX(x+1,y+1, size-1);
if (found)
return true;
}
if (i < size-1)
swap(x[i+1], x[0]);
}
return false;
}
sort the array x in ascending order before calling this method
bool rearrangeX(int*x, int* y, int size)
{
if (size == 0)
return true;
for (int i = 0; i < size; i++)
{
bool found = false;
if (x[0] >= y[0])
{
found = rearrangeX(x+1,y+1, size-1);
if (found)
return true;
}
if (i < size-1)
swap(x[i+1], x[0]);
}
return false;
}
this is my solution in java
static int getClosestNumber(int[] x, int[] y) {
int[] count = new int[10];
for (int aX : x) {
count[aX] += 1;
}
StringBuilder result = new StringBuilder();
for (int aY : y) {
// find maximum num
for (int k = aY; k >= 0; k--) {
if (count[k] > 0) {
result.append(k);
count[k] -= 1;
break;
}
}
}
for (int k = 9; k >= 0; k--) {
if (count[k] > 0) {
result.append(k);
count[k] -= 1;
}
}
return Integer.parseInt(result.toString());
}
What about the case x ={9,8,7,6,5,4,3,3,1}, y={2,2,2,2,2,2,2,2,2} ? Count Sort for x will be O(n) which is fine; however Binary Search for each element of y will be logn, logn + 1, logn + 2...logn + n-1, since at every occurrence of not finding 2 in x we will be traversing array x by one step to the right(i.e. ascending order). This gives a total time complexity of O(n) + (nlogn + n^2) which is O(n^2).
public boolean arrange(int[] x, int[] y)
{
if(x.length != y.length)
return false;
else if(x.length == 0)
return true;
return arrHelper(x, y, 0);
}
public boolean arrHelper(int[] x, int[] y, int p)
{
if(p == x.length-1)
{
if(x[p] > y[p])
return true;
else
return false;
}
if(getEqual(x, y[p])
return arrHelper(x, y, p+1);
if(!getNext(x, y[p]))
return false;
Arrays.sort(p+1, x);
return true;
}
public boolean getEqual(int[] x, int[] y, int p)
{
for(int i = p; i < x.length; i++)
{
if(x[i] == y[p])
{
int h = x[i];
x[i] = x[p];
x[p] = h;
return true;
}
}
return false
}
public boolean getNext(int[] x, int[] y, int p)
{
int min = Integer.MAX_VALUE;
int j = p;
int i = p;
for(; i < x.length; i++)
{
if(x[i] > y[p] && x[i] < min)
{
j = i;
min = x[i];
}
}
if(i == x.length) return false;
int h = x[p];
x[p] = x[j];
x[j] = h;
return true;
}
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int main() {
char num[]="19999";
char digits[]="12999";
int dc[10];
int n=5;
char res[6];
int i,j,k;
memset(dc,0,sizeof(dc));
for(i=0;i<n;i++) {
dc[digits[i]-'0']++;
}
for(i=0;i<n;i++) {
for(j=num[i]-'0';j<=9;j++) {
if(dc[j]>0) {
dc[j]--;
res[i]=j+'0';
break;
}
}
if(j!=num[i]-'0')
break;
}
if(j==10) {
for(i--;i>=0;i--) {
dc[res[i]-'0']++;
for(j=res[i]-'0'+1;j<=9;j++) {
if(dc[j]>0) {
dc[j]--;
res[i]=j+'0';
break;
}
}
if(j<=9)
break;
}
}
if(i==-1 || i==n) {
printf("no such number\n");
return 0;
}
for(k=0;k<=9 && i<n;k++) {
for(j=0;j<dc[k];j++) {
res[++i]=k+'0';
}
}
res[n]='\0';
printf("%s\n",res);
return 0;
}
Store x in an array and sort it. for each bit or element of y from right side find the bit or element in the array using binary search. if the element is present move it to the desired position in the array, now the length of the array will get reduced every time .If the element not present stop the algorithm, if the next element is grater than the bit which we are comparing then output the array it will give the number greater than y.
backtracing.
1. sort x first.
2. iterate through x, find a unused digit that is greater than or equal to the target digit in y.
2.a if we can find a digit that is strictly greater than that in y, we find a solution, add all unused digits in x into the result in ascending order
2.b if we can only find a digit in x that is equal to the target digit in y, we continue this execution path.
- gnahzy October 31, 2012