Microsoft Interview Question Software Developers
Team: Cloud + Enterprise
Country: United States
Interview Type: Written Test
string lowNum = GenerateLowestNumber("124538945", 3); // Returns "124345".
public static string GenerateLowestNumber(string str, int n)
{
if(n == 0) return str;
string newStr = str; //str "124538945"
for(int i=0;i< n; i++) {
int k = getLargestIndex(newStr, i);
newStr = String.Concat(newStr.Substring(0, k), newStr.Substring(k + 1, newStr.Length - k - 1));
}
return newStr;
}
static int getLargestIndex(String str, int index)
{
for (int i = 0; i < str.Length - 1; i++)
if (str[i] - '0' > str[i+1] - '0')
index = i;
return index;
}
a) does not return anything except null
b) displays "0123" for GenerateLowestNumber("4205123",4)
package com.cnu.ds.hash.test;
public class Microsoft {
public static String generateLowestNumber(String number, int n) {
if (number == null || number.length() < n) {
return null;
} else if (number.length() > n) {
int removed = 0;
for (int i = 0, j = 1; removed != n && j != number.length();) {
if (number.charAt(i) > number.charAt(j)) {
number = number.substring(0, i)
+ number.substring(j, number.length());
System.out.println(number);
i = 0;
j = 1;
removed++;
} else {
i++;
j++;
}
}
}
return null;
}
public static void main(String[] args) {
generateLowestNumber("2200010300", 4);
}
}
public static string Find(string number, int n)
{
var maxReturnLength = number.Length - n;
var returnNumber = "";
for (int i = 0; i < number.Length; i++)
{
var minNumberCounter = 0;
for (int j = 0; j < number.Length; j++)
{
if (i != j)
{
if (number[i] >= number[j])
{
minNumberCounter++;
}
}
}
if (minNumberCounter < maxReturnLength)
{
returnNumber = returnNumber + number[i].ToString();
number = number.Substring(i);
i = 0;
}
}
if (returnNumber.Length > maxReturnLength)
{
for (int k = 0; k < returnNumber.Length-1; k++)
{
if (returnNumber[k] > returnNumber[k + 1])
{
if (k > 0)
{
returnNumber = returnNumber.Substring(0, k) + returnNumber.Substring(k + 1);
}
else {
returnNumber = returnNumber.Substring(k + 1);
}
}
}
}
return returnNumber;
}
public static string Find(string number, int n)
{
var maxReturnLength = number.Length - n;
var returnNumber = "";
for (int i = 0; i < number.Length; i++)
{
var minNumberCounter = 0;
for (int j = 0; j < number.Length; j++)
{
if (i != j)
{
if (number[i] >= number[j])
{
minNumberCounter++;
}
}
}
if (minNumberCounter <= maxReturnLength)
{
returnNumber = returnNumber + number[i].ToString();
}
number = number.Substring(i);
i = 0;
}
if (returnNumber.Length > maxReturnLength)
{
for (int k = 0; returnNumber.Length > maxReturnLength; k++)
{
if (returnNumber[k] >= returnNumber[k + 1])
{
if (k > 0)
{
returnNumber = returnNumber.Substring(0, k) + returnNumber.Substring(k + 1);
}
else
{
returnNumber = returnNumber.Substring(k + 1);
}
k = 0;
}
}
}
return returnNumber;
}
This is a O(n^2) solution. Algorithm goes as follows -
1. find the length of number we want to obtain i.e. count = length(string) - n
2. since, relative order of characters in string is not to be changed, we iterate from start (initially set to 0) to length(string) - (count-1) to find minimum value character(or the index of minimum value character in char array).
3. update the start to (min) index+1 for next iteration and reduce count by 1.
4. keep iterating till we have not found the number of characters required i.e. till count is not reduced to 0.
public static String GenerateLowestNumber(String number, int n) {
if(number == null || number .length() == 0 || n >= number.length())
return null;
int count = number.length() - n;
char[] num = number.toCharArray();
StringBuilder st = new StringBuilder();
int start = 0;
while(count > 0) {
int end = number.length() - count + 1;
int index = findMin(start, end, num);
start = index+1;
st.append(num[index]);
count--;
}
return st.toString();
}
public static int findMin(int start, int end, char[] number) {
if(start > end || number == null || number.length == 0)
return Integer.MIN_VALUE;
if(start == end)
return start;
int min = start;
for(int i = start; i <end; i++) {
if(number[min] > number[i])
min = i;
}
return min;
}
string GenerateLowestNumber(string number, int n){
int start, end;
int len, min;
string lowest = "";
len = number.size();
if (len <= n)
return lowest;
start = 0;
end = n;
for (int i=0; i<len-n; i++){
min = number[start]-'0';
for (int j=start+1; j<=end; j++){
if (number[j]-'0' < min){
min = number[j]-'0';
start = j;
}
}
start++;
end++;
lowest.push_back(min+'0');
}
return lowest;
}
public class GenerateLowestNumber {
public static void main(String[] args) {
System.out.println(generateLowestNumber("4205123",4));
System.out.println(generateLowestNumber("216504",3));
}
static String generateLowestNumber(String str, int num) {
if(num == 0) {
return str;
}
int index = str.length() -1;
for(int i=0;i< str.length() -1; i++) {
if(getNum(str,i) > getNum(str, i+1)) {
index = i;
break;
}
}
String newStr = str.substring(0, index);
if(index < str.length() - 2) {
newStr += str.substring(index+1);
}
return generateLowestNumber(newStr, num -1);
}
static int getNum(final String str, final int index) {
return Character.getNumericValue(str.charAt(index));
}
}
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
public class Microsoft {
public static String generateLowestNumber(String number, int n) {
// "8791234" => 8 7 9 1 2 3 4
String res = "";
char[] numbers = number.toCharArray();
StringBuilder s;
int length = numbers.length;
int count = n;
if (n == number.length()) {
return number;
} else if (n > number.length()) {
return null;
} else {
// for the length of the numbers
for (int x = 9; x > 1; x--) {
for (int i = 0; i < length; i++) {
if (numbers[i] != ' ' && count > 0) {
if (Integer.parseInt(numbers[i] + "") == x) {
numbers[i] = ' ';
count--;
}
}
}
}
}
for (int i = 0; i < numbers.length; i++) {
if (numbers[i] != ' ') {
res += numbers[i];
}
}
return res;
}
public static void main(String[] args) {
Microsoft t = new Microsoft();
System.out.println(t.generateLowestNumber("9234945999", 5));
}
}
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
public class Microsoft {
public static String generateLowestNumber(String number, int n) {
// "8791234" => 8 7 9 1 2 3 4
String res = "";
char[] numbers = number.toCharArray();
StringBuilder s;
int length = numbers.length;
int count = n;
if (n == number.length()) {
return number;
} else if (n > number.length()) {
return null;
} else {
// for the length of the numbers
for (int x = 9; x > 1; x--) {
for (int i = 0; i < length; i++) {
if (numbers[i] != ' ' && count > 0) {
if (Integer.parseInt(numbers[i] + "") == x) {
numbers[i] = ' ';
count--;
}
}
}
}
}
for (int i = 0; i < numbers.length; i++) {
if (numbers[i] != ' ') {
res += numbers[i];
}
}
return res;
}
public static void main(String[] args) {
Microsoft t = new Microsoft();
System.out.println(t.generateLowestNumber("99999", 1));
}
}
public class GenerateLowestNumber {
public static void main(String[] args) {
System.out.println(generateLowestNumber("4205123",4));
System.out.println(generateLowestNumber("216504",3));
}
static String generateLowestNumber(String str, int num) {
if(num == 0) {
return str;
}
int index = str.length() -1;
for(int i=0;i< str.length() -1; i++) {
if(getNum(str,i) > getNum(str, i+1)) {
index = i;
break;
}
}
String newStr = str.substring(0, index);
if(index < str.length() - 2) {
newStr += str.substring(index+1);
}
return generateLowestNumber(newStr, num -1);
}
static int getNum(final String str, final int index) {
return Character.getNumericValue(str.charAt(index));
}
}
public static String GenerateLowestNumber(String number, int n){
StringBuilder lowestNum = new StringBuilder(number);
for(int i=9; i>=0 && n >0 ;i--){
for(int j=0; j<lowestNum.length() && n >0; j++){
if (Character.getNumericValue(lowestNum.charAt(j))==i){
lowestNum.deleteCharAt(j);
n--;
}
}
}
System.out.println(lowestNum);
return lowestNum.toString();
}
public static String GenerateLowestNumber(String number, int n){
StringBuilder lowestNum = new StringBuilder(number);
for(int i=9; i>=0 && n >0 ;i--){
for(int j=0; j<lowestNum.length() && n >0; j++){
if (Character.getNumericValue(lowestNum.charAt(j))==i){
lowestNum.deleteCharAt(j);
n--;
}
}
}
System.out.println(lowestNum);
return lowestNum.toString();
}
{
class Program
{
static void Main(string[] args)
{
var generator = new LowestNumberGenerator();
string result1 = generator.Generate("4205123", 4);
string result2 = generator.Generate("216504", 3);
}
}
public class LowestNumberGenerator
{
public string Generate(string number, int n)
{
var digitsMap = new SortedDictionary<int, SortedSet<int>>();
for (int i = 0; i < number.Length; i++)
{
char c = number[i];
var digit = (int)char.GetNumericValue(c);
if (digitsMap.ContainsKey(digit))
{
var sortedList = digitsMap[digit];
sortedList.Add(i);
}
else
{
var sortedSet = new SortedSet<int>();
sortedSet.Add(i);
digitsMap.Add(digit, sortedSet);
}
}
int targetCount = number.Length - n;
foreach (KeyValuePair<int, SortedSet<int>> uniqueDigits in digitsMap)
{
int currentDigitMinIndex = uniqueDigits.Value.Min;
var resultSet = new SortedSet<int>();
foreach (KeyValuePair<int, SortedSet<int>> digits in digitsMap)
{
var viewBetween = digits.Value.GetViewBetween(currentDigitMinIndex, number.Length);
resultSet.UnionWith(viewBetween);
if (resultSet.Count >= targetCount)
{
break;
}
}
if (resultSet.Count >= targetCount)
{
string result = string.Empty;
foreach (var index in resultSet)
{
result += number[index];
}
return result;
}
}
return string.Empty;
}
}
}
private static string FindTheSmallestSequece(string str, int n)
{
if (n == 0)
return str;
int largest = FindIndexOfTheLargest(str);
string nextIterationStr = Substring(str, largest);
return FindTheSmallestSequece(nextIterationStr, n - 1);
}
private static int FindIndexOfTheLargest(string str)
{
int indexOfMaxValue = 0;
for (int i = 1; i < str.Length; i++)
{
if (str[i] > str[indexOfMaxValue])
indexOfMaxValue = i;
}
return indexOfMaxValue;
}
private static string Substring(string str, int indexToRemove)
{
return str.Substring(0, indexToRemove) + str.Substring(indexToRemove + 1, str.Length-indexToRemove - 1);
}
Basically we need to follow a growing sequence until the next digit is lower than the current value in the sequence.
using System;
using System.Collections.Generic;
namespace buskila.Careercup
{
class MainClass
{
private static string ClimbCliff(string number)
{
for (var i = 1; i < number.Length; i++)
if (char.GetNumericValue(number [i - 1]) > char.GetNumericValue(number[i]))
return number.Remove (i - 1, 1);
return number.Substring (0, number.Length - 1);
}
public static string GenerateLowestNumber(string number, int n)
{
for (var i = 0; i < n; i++)
number = ClimbCliff (number);
return number;
}
public static void Main(string[] args)
{
var tests =new List<Tuple<string, int>> {
Tuple.Create("4205123", 4),
Tuple.Create("216504", 3)
};
foreach (var test in tests)
System.Console.Out.WriteLine("GenerateLowestNumber({0}, {1}) -> {2}",
test.Item1, test.Item2,
GenerateLowestNumber(test.Item1, test.Item2));
}
}
}
public static String findLowestPossibleNumberFromNumericString(String s, int n) {
if (n <= 0 || s == null || s.length() == 0 || n > s.length()) {
return null;
}
if (s.length() == n) {
return s;
}
int[] indexKeep = new int[s.length()];
int[] numbers = new int[s.length()];
for (int i = 0; i < s.length(); i++) {
numbers[i] = Integer.parseInt(s.substring(i,i+1));
indexKeep[i] = 0;
}
int localMin = Integer.MAX_VALUE;
int localMinIndex = 0;
int indexStart = 0;
int totalCharsToKeep = s.length() - n;
int indexEnd = s.length() - totalCharsToKeep;
while (totalCharsToKeep > 0 && indexStart < s.length()) {
for (int i = indexStart; i < indexEnd; i++) {
if (localMin > numbers[i]) {
localMin = numbers[i];
localMinIndex = i;
}
}
indexKeep[localMinIndex] = 1;
totalCharsToKeep--;
indexStart = localMinIndex + 1;
indexEnd = s.length() - totalCharsToKeep + 1;
localMin = Integer.MAX_VALUE;
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < indexKeep.length; i++) {
if (indexKeep[i] == 1) {
sb.append(numbers[i]);
}
}
return sb.toString();
}
public static String generateLowestNumber(String s, int n) {
if (n <= 0 || s == null || s.length() == 0 || n > s.length()) {
return null;
}
if (s.length() == n) {
return s;
}
int[] indexKeep = new int[s.length()];
int[] numbers = new int[s.length()];
for (int i = 0; i < s.length(); i++) {
numbers[i] = Integer.parseInt(s.substring(i,i+1));
indexKeep[i] = 0;
}
int localMin = Integer.MAX_VALUE;
int localMinIndex = 0;
int indexStart = 0;
int totalCharsToKeep = s.length() - n;
int indexEnd = s.length() - totalCharsToKeep;
while (totalCharsToKeep > 0 && indexStart < s.length()) {
for (int i = indexStart; i <= indexEnd; i++) {
if (localMin > numbers[i]) {
localMin = numbers[i];
localMinIndex = i;
}
}
int totalNoOfCharsRemoved=localMinIndex-indexStart;
int yetToBeRemoved=n-totalNoOfCharsRemoved;
n=yetToBeRemoved;
indexKeep[localMinIndex] = 1;
totalCharsToKeep--;
indexStart = localMinIndex + 1;
indexEnd = indexStart+yetToBeRemoved;
localMin = Integer.MAX_VALUE;
}
/*if(n==totalNoOfCharsRemoved){
for(int j=indexStart;j<s.length();j++){
indexKeep[j]=1;
}
}*/
StringBuilder sb = new StringBuilder();
for (int i = 0; i < indexKeep.length; i++) {
if (indexKeep[i] == 1) {
sb.append(numbers[i]);
}
}
return sb.toString();
}
public static String generateLowestNumber(String s, int n) {
if (n <= 0 || s == null || s.length() == 0 || n > s.length()) {
return null;
}
if (s.length() == n) {
return s;
}
int[] indexKeep = new int[s.length()];
int[] numbers = new int[s.length()];
for (int i = 0; i < s.length(); i++) {
numbers[i] = Integer.parseInt(s.substring(i,i+1));
indexKeep[i] = 0;
}
int localMin = Integer.MAX_VALUE;
int localMinIndex = 0;
int indexStart = 0;
int totalCharsToKeep = s.length() - n;
int indexEnd = s.length() - totalCharsToKeep;
while (totalCharsToKeep > 0 && indexStart < s.length()) {
for (int i = indexStart; i <= indexEnd; i++) {
if (localMin > numbers[i]) {
localMin = numbers[i];
localMinIndex = i;
}
}
int totalNoOfCharsRemoved=localMinIndex-indexStart;
int yetToBeRemoved=n-totalNoOfCharsRemoved;
n=yetToBeRemoved;
indexKeep[localMinIndex] = 1;
totalCharsToKeep--;
indexStart = localMinIndex + 1;
indexEnd = indexStart+yetToBeRemoved;
localMin = Integer.MAX_VALUE;
}
/*if(n==totalNoOfCharsRemoved){
for(int j=indexStart;j<s.length();j++){
indexKeep[j]=1;
}
}*/
StringBuilder sb = new StringBuilder();
for (int i = 0; i < indexKeep.length; i++) {
if (indexKeep[i] == 1) {
sb.append(numbers[i]);
}
}
return sb.toString();
}
public class GenerateLowestNumber {
int[] srcArr = new int[]{2,1,6,5,0,4};
boolean[] used = new boolean[srcArr.length];
StringBuffer number = new StringBuffer();
int min = 999999999;
int toBeRemoved = 4;
public static void main(String args[]){
GenerateLowestNumber permute = new GenerateLowestNumber();
permute.permute(0,0);
System.out.println("Minimum Number "+permute.min);
}
private void permute(int idx,int level){
if(level == (srcArr.length-toBeRemoved)){
System.out.println(number.toString());
int intNumber = Integer.parseInt(number.toString());
if(intNumber < min){
min = intNumber;
}
return;
}
for(int i=idx;i<srcArr.length;i++){
if(used[i]){
continue;
}
used[i] = true;
number.append(srcArr[i]);
permute(i+1,level+1);
used[i]=false;
number.setLength(number.length()-1);
}
}
}
public class GenerateLowestNumber {
int[] srcArr = new int[]{2,1,6,5,0,4};
boolean[] used = new boolean[srcArr.length];
StringBuffer number = new StringBuffer();
int min = 999999999;
int toBeRemoved = 4;
public static void main(String args[]){
GenerateLowestNumber permute = new GenerateLowestNumber();
permute.permute(0,0);
System.out.println("Minimum Number "+permute.min);
}
private void permute(int idx,int level){
if(level == (srcArr.length-toBeRemoved)){
System.out.println(number.toString());
int intNumber = Integer.parseInt(number.toString());
if(intNumber < min){
min = intNumber;
}
return;
}
for(int i=idx;i<srcArr.length;i++){
if(used[i]){
continue;
}
used[i] = true;
number.append(srcArr[i]);
permute(i+1,level+1);
used[i]=false;
number.setLength(number.length()-1);
}
}
}
Permuting the integers in the array(srcArr), by maintaining the order. Order is maintained by passing the "idx" so that we don't pick the previous characters.
public class GenerateLowestNumber {
int[] srcArr = new int[]{2,1,6,5,0,4};
boolean[] used = new boolean[srcArr.length];
StringBuffer number = new StringBuffer();
int min = 999999999;
int toBeRemoved = 4;
public static void main(String args[]){
GenerateLowestNumber permute = new GenerateLowestNumber();
permute.permute(0,0);
System.out.println("Minimum Number "+permute.min);
}
private void permute(int idx,int level){
if(level == (srcArr.length-toBeRemoved)){
System.out.println(number.toString());
int intNumber = Integer.parseInt(number.toString());
if(intNumber < min){
min = intNumber;
}
return;
}
for(int i=idx;i<srcArr.length;i++){
if(used[i]){
continue;
}
used[i] = true;
number.append(srcArr[i]);
permute(i+1,level+1);
used[i]=false;
number.setLength(number.length()-1);
}
}
}
string lowNum = GenerateLowestNumber("124538945", 3); // Returns "124345".
public static string GenerateLowestNumber(string str, int n)
{
if(n == 0) return str;
string newStr = str; //str "124538945"
for(int i=0;i< n; i++) {
int k = getLargestIndex(newStr, i);
newStr = String.Concat(newStr.Substring(0, k), newStr.Substring(k + 1, newStr.Length - k - 1));
}
return newStr;
}
static int getLargestIndex(String str, int index)
{
for (int i = 0; i < str.Length - 1; i++)
if (str[i] - '0' > str[i+1] - '0')
index = i;
return index;
}
They wrote that the number could be generated when n characters were removed,
so why to remove anything. just simulate the situation.
My proposal is like the following :
/**
* @brief Find minimal number in the subset,
* which is not closer to the end than cnt
*
* @param subset [in] A subset on which the min number should be found
* @param ioff [in] Index offset from the end
* @param idx [out] Index of the found minimum value (returend by ref)
* @return Character that represents the min number
*/
char findMinChar(const string& subset, const int ioff, int& idx)
{
int len = subset.length();
int maxIdx = len-ioff;
// initialize search
idx = 0;
char minC = subset[idx];
if(len == 0) return '\0'; // safety
if(len == ioff) return minC; // return the first one
// don't look in the subset above the certain index
// only up to maxIdx
for(int i=0; i<=maxIdx; i++)
{
char c = subset[i];
if(c < minC){
minC = c;
idx = i;
}
}
return minC;
}
/**
* @brief GenerateLowestNumber
*
* @param number A string of digits
* @param n A numbers of characters to remove
* @return
*/
string GenerateLowestNumber(string number, int n)
{
cout<< endl << std::setw(10) <<" GLM(\""<<number.c_str()<<"\","<<n <<") "<<std::setw(3)<<" ";
string temp = "";
int len = number.length();
int count = len -n; // how many characters wil remain
int idx = -1; // position of the last found number
string subStr = number; // start with the whole string
for(int i=count; i>0; i--)
{
int pos = idx+1; // idx is relative to begining of the subString
subStr = subStr.substr(pos, len-pos); // prepare a subset on the right from the last fount index
temp+= findMinChar(subStr,i,idx); // search a subset on the range <0 , (len-i)>
}
return temp;
}
The idea is we need to have minimum possible value at most significant digit
so get the minimum of first n most significant digits, print it out.
then get the minimum of next n digits, print the it out.
and so on keep sliding the window of size n and keep printing the minimum till the end.
1. For 1 to n
a.insert in the list if current element greater than head of the list.
b.otherwise keep popping the head unless list empty or head is smaller and then insert.
2. For each subsequent element.
a. pop and print the tail of list.
b. insert current element as descirbed in step 1b.
Sort the given array and while traversing start from the last and remove all the n characters.
void findSmallestNo(char* numStr,int noOfCharToDel)
{
int n = strlen(numStr);
int resStrlen = n-noOfCharToDel;
char resArr[250];
int j=0,i=0,minIndex=0;
char min = numStr[i];
while(i<n-1 && j<=resStrlen-1)
{
min = numStr[i];
for(;i<noOfCharToDel+j;i++)
{
if(min > numStr[i+1])
{
min = numStr[i+1];
minIndex = i+1;
}
}
i= minIndex+1;
resArr[j] = min;
j++;
}
if(noOfCharToDel+j==n-1)
{
if(i<(n-1))
resArr[j] =numStr[++i] ;
else
resArr[j] =numStr[i] ;
resArr[++j] = '\0';
}
resArr[j] = '\0';
}
an o(N) solution:
#include <string>
#include <vector>
#include <iostream>
using namespace std;
#define TONUM(C) (C - '0')
#define TOCHAR(I) (I + '0')
string CreateLowestNumber(
const string &Digits,
const size_t ToErase)
{
if (ToErase >= Digits.size())
{
return "";
}
string Res;
int Min = TONUM(Digits[0]);
int MinIdx = 0;
for (int i = 1; i < ToErase + 1; ++i)
{
if (TONUM(Digits[i]) < Min)
{
Min = TONUM(Digits[i]);
MinIdx = i;
}
}
Res.push_back(TOCHAR(Min));
int IndexPassedMin = MinIdx + 1;
int ErasedToRight = MinIdx;
for (int i = ToErase + 1; i < Digits.size(); ++i)
{
if (ErasedToRight < ToErase)
{
if (TONUM(Digits[i]) < TONUM(Digits[IndexPassedMin]))
{
IndexPassedMin++;
ErasedToRight++;
i--;
}
else
{
Res.push_back(Digits[IndexPassedMin]);
IndexPassedMin++;
}
}
else
{
Res.push_back(Digits[i]);
}
}
return (Res);
}
int main()
{
string Digits;
int Erase = 0;
cin >> Digits >> Erase;
cout << CreateLowestNumber(Digits, Erase) << endl;
return (0);
}
here is my code
string getMinNumberRemoveK(const string & num, int k)
{
string result;
int digits[10] = {0};
int i;
//store the digit frequencies
for( i = 0; i < num.size(); i++ )
{
digits[num[i]-'0']++;
}
//decrement top K digits from the frequency table
for( i = 9; i >= 0 && k > 0; )
{
while( digits[i] > 0 )
{
k--;
digits[i]--;
}
i--;
}
//reconstruct the result from modified frequency table
for( i = 0; i < num.size(); i++ )
{
if( digits[num[i]-'0'] > 0 )
{
result += num[i];
digits[num[i]-'0']--;
}
}
return result;
}
for explanation, look at my blogspost comproguide[dot].blogspot[dot]in/2015/03/
here is my code
string getMinNumberRemoveK(const string & num, int k)
{
string result;
int digits[10] = {0};
int i;
//store the digit frequencies
for( i = 0; i < num.size(); i++ )
{
digits[num[i]-'0']++;
}
//decrement top K digits from the frequency table
for( i = 9; i >= 0 && k > 0; )
{
while( digits[i] > 0 )
{
k--;
digits[i]--;
}
i--;
}
//reconstruct the result from modified frequency table
for( i = 0; i < num.size(); i++ )
{
if( digits[num[i]-'0'] > 0 )
{
result += num[i];
digits[num[i]-'0']--;
}
}
return result;
}
for explanation, look at my blogspost comproguide[dot].blogspot[dot]in
here is my code
string getMinNumberRemoveK(const string & num, int k)
{
string result;
int digits[10] = {0};
int i;
//store the digit frequencies
for( i = 0; i < num.size(); i++ )
{
digits[num[i]-'0']++;
}
//decrement top K digits from the frequency table
for( i = 9; i >= 0 && k > 0; )
{
while( digits[i] > 0 )
{
k--;
digits[i]--;
}
i--;
}
//reconstruct the result from modified frequency table
for( i = 0; i < num.size(); i++ )
{
if( digits[num[i]-'0'] > 0 )
{
result += num[i];
digits[num[i]-'0']--;
}
}
return result;
}
for explanation, look at my blogspost comproguide[dot]blogspot[dot]in/2015/03/
here is my code
string getMinNumberRemoveK(const string & num, int k)
{
string result;
int digits[10] = {0};
int i;
//store the digit frequencies
for( i = 0; i < num.size(); i++ )
{
digits[num[i]-'0']++;
}
//decrement top K digits from the frequency table
for( i = 9; i >= 0 && k > 0; )
{
while( digits[i] > 0 )
{
k--;
digits[i]--;
}
i--;
}
//reconstruct the result from modified frequency table
for( i = 0; i < num.size(); i++ )
{
if( digits[num[i]-'0'] > 0 )
{
result += num[i];
digits[num[i]-'0']--;
}
}
return result;
}
for explanation, look at my blogspost comproguide[dot]blogspot[dot]in/2015/03/
public static String findSmallestInteger(String number, int n)
{
int beginPos=0,min,index=0;
int count=number.length()-n;
String op="";
System.out.println("Count of numbers required:"+count);
if(count<0 || number==null)
return op;
while(count>0)
{
min=number.charAt(beginPos)-'0';
for(int i=beginPos;i<number.length()-count;i++)
{
if(min>(number.charAt(i)-'0'))
{
min=number.charAt(i)-'0';
index = i;
}
}
beginPos=index+1;
count--;
op=op+Integer.toString(min);
}
System.out.println("Output is:"+op);
return op;
}
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
void findloweststr(char *input, unsigned int n);
int main()
{
findloweststr("4205123", 4);
}
void findloweststr(char *input, unsigned int n)
{
unsigned int i = 0, index = 0, len = 0, temp;
char *small;
len = strlen(input);
small = (char *)malloc( sizeof(char) * n + 1);
for (i = 0; i < n; i++)
{
small[i] = input[index];
while (index <= (len - n) - 1 + i)
{
if (small[i] >= input[index + 1])
{
small[i] = input[index + 1];
temp = index + 1;
}
index++;
}
index = temp + 1;
}
small[n] = '\0';
printf("small %s\n", small);
free(small);
}
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
void findloweststr(char *input, unsigned int n);
int main()
{
findloweststr("4205122403", 4);
}
void findloweststr(char *input, unsigned int n)
{
unsigned int i = 0, index = 0, len = 0, temp;
char *small;
len = strlen(input);
small = (char *)malloc( sizeof(char) * n + 1);
for (i = 0; i < n; i++)
{
small[i] = input[index];
while (index <= (len - n) + i)
{
if (small[i] >= input[index])
{
small[i] = input[index];
temp = index;
}
index++;
}
index = temp + 1;
}
small[n] = '\0';
printf("small %s\n", small);
free(small);
}
This is my version of solution:
public static string GenerateLowestNumber(string number, int n) {
StringBuilder lowest_number_str = new StringBuilder();
StringBuilder tmp_str = new StringBuilder ();
SortedSet<int> lowest_number_combination = new SortedSet<int> ();
int lowest_number = int.MaxValue;
foreach(SortedSet<int> combination in combination_to_test(0, number.Length, number.Length - n)) {
tmp_str.Clear ();
foreach (int element in combination) {
tmp_str.Append (number [element]);
}
if (lowest_number > int.Parse (tmp_str.ToString ())) {
lowest_number = int.Parse (tmp_str.ToString ());
lowest_number_str.Clear ();
lowest_number_str.Append (tmp_str.ToString ());
lowest_number_combination.Clear ();
lowest_number_combination.UnionWith (combination);
}
}
return lowest_number_str.ToString ();
}
private static IEnumerable<SortedSet<int>> combination_to_test(int start, int end, int requested_amount){
if (requested_amount == 1) {
for (int i = start; i < end; i++) {
yield return new SortedSet<int> (new int[]{ i });
}
} else {
for (int j = start; j + requested_amount <= end; j++) {
foreach (SortedSet<int> combination in combination_to_test(j + 1, end, requested_amount - 1)) {
SortedSet<int> combination_to_return = new SortedSet<int> (combination);
combination_to_return.UnionWith (new int[]{ j });
yield return combination_to_return;
}
}
}
}
public static String generateLowestNumber(StringBuilder str, int num) {
if (num == 0) {
return str.toString();
}
for (int i = 0; i < str.length()-1; i++) {
if (getNumValue(str.charAt(i)) >= getNumValue(str.charAt(i + 1))) {
str.deleteCharAt(i);
i--;
num--;
}
if (num == 0) {
break;
}
}
return str.toString();
}
public static int getNumValue(Character c) {
return Character.getNumericValue(c);
}
This can be solved with recursive function call.
First analyze that if string size is a and we have to remove b number of elements, So the first digit must be minimum of from first (a-b+1) digit.
Suppose we got the index i.
Next digit cannot be before the index of element selected, and now we have to find the minimum number of length (a-b-1) from the in remaining array.
string generateLowestNumber(String str,n)
{
//get lowest number between index 0 and strlen(str)-n+1 suppose i
generateLowestNumber(&str[i+1],n-1);
}
My version C#
public static string GenerateLowestNumber(string number, int n)
{
string current_string;
string outcome = "";
current_string = number;
for (int count = 1; count <= n; count++)
{
int StringLength = current_string.Length - (n - count);
char min_char = '9';
int min_index = 0;
for (int char_num = 0; char_num < StringLength; char_num++)
{
if (min_char > current_string[char_num])
{
min_char = current_string[char_num];
min_index = char_num;
}
}
outcome = outcome + min_char;
current_string = current_string.Substring(min_index + 1);
}
return outcome;
}
O(N) time
1: /**
2: *
3: * @param S
4: * @param K the number of characters to remove
5: * @return
6: */
7: public String generateLowestNumber(String S, int K) {
8: if (S == null || K > S.length()) {
9: return "";
10: }
11: // removing K digits is the same as keeping N - K digits
12: int add = S.length() - K; // the number of characters to add.
13: char[] lowest = new char[add];
14: // convert the input into an array of digits
15: int[] digits = new int[S.length()];
16: for (int i = 0; i < digits.length; i++) {
17: digits[i] = S.charAt(i) - '0';
18: }
19: int index = 0;
20: int[] closest = new int[S.length()];
21: closest[digits.length - 1] = -1;
22: for (int i = digits.length - 2; i >= 0; i--) {
23: int j = i + 1;
24: while (j != -1 && digits[i] <= digits[j]) {
25: j = closest[j];
26: }
27: closest[i] = j;
28: }
29: for (int i = 0; i < add; i++) {
30: int j = index;
31: while (j != -1 && j <= (digits.length - (add - i))) {
32: lowest[i] = (char) (digits[j] + (int) '0');
33: index = j;
34: j = closest[j];
35: }
36: index++;
37: }
38: return String.valueOf(lowest);
39: }
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace DataStructures
{
public class GetLowestNumber
{
private static DoubleLinkedListNode root;
public DoubleLinkedListNode GetHead(DoubleLinkedListNode node)
{
if (node == null)
{
return null;
}
while (node.prev != null)
{
node = node.prev;
}
return node;
}
public DoubleLinkedListNode GetTail(DoubleLinkedListNode node)
{
if (node == null)
{
return null;
}
while (node.next != null)
{
node = node.next;
}
return node;
}
public string GetLowNumber(string input, int n)
{
DoubleLinkedListNode temp;
for (int i = 0; i < input.Count(); i++)
{
temp = new DoubleLinkedListNode();
temp.data = Convert.ToInt32(input[i].ToString());
if (root == null)
{
root = temp;
}
else
{
root.next = temp;
root.next.prev = root;
}
if (root.next != null)
{
root = root.next;
}
}
root = GetHead(root);
int cut = 0;
temp = root;
while (cut < n)
{
while (root.next != null)
{
if (temp.data > root.next.data)
{
if (cut < n)
{
root.next.prev = temp.prev;
if (root.next.prev != null)
{
root.next.prev.next = root.next;
}
cut += 1;
root = root.next;
break;
}
else
{
break;
}
}
else
{
root = root.next;
break;
}
}
bool isListSorted = false;
if (root.next == null && cut < n)
{
isListSorted = true;
root = GetHead(root);
temp = root;
int prev = 0;
while (root.next != null)
{
if(prev > root.data)
{
isListSorted = false;
root = GetHead(root);
temp = root;
break;
}
prev = root.data;
root = root.next;
}
}
else
{
temp = temp.next;
}
if(isListSorted && cut < n)
{
root = GetTail(root);
for(int i = 1; i <= (n - cut);i++)
{
root.prev.next = null;
cut += 1;
root = root.prev;
}
}
}
root = GetHead(root);
string number = root.data.ToString();
while (root.next != null)
{
number = number + root.next.data.ToString();
root = root.next;
}
root = null; //free linked list
return number;
}
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace DataStructures
{
public class GetLowestNumber
{
private static DoubleLinkedListNode root;
public DoubleLinkedListNode GetHead(DoubleLinkedListNode node)
{
if (node == null)
{
return null;
}
while (node.prev != null)
{
node = node.prev;
}
return node;
}
public DoubleLinkedListNode GetTail(DoubleLinkedListNode node)
{
if (node == null)
{
return null;
}
while (node.next != null)
{
node = node.next;
}
return node;
}
public string GetLowNumber(string input, int n)
{
DoubleLinkedListNode temp;
for (int i = 0; i < input.Count(); i++)
{
temp = new DoubleLinkedListNode();
temp.data = Convert.ToInt32(input[i].ToString());
if (root == null)
{
root = temp;
}
else
{
root.next = temp;
root.next.prev = root;
}
if (root.next != null)
{
root = root.next;
}
}
root = GetHead(root);
int cut = 0;
temp = root;
while (cut < n)
{
while (root.next != null)
{
if (temp.data > root.next.data)
{
if (cut < n)
{
root.next.prev = temp.prev;
if (root.next.prev != null)
{
root.next.prev.next = root.next;
}
cut += 1;
root = root.next;
break;
}
else
{
break;
}
}
else
{
root = root.next;
break;
}
}
bool isListSorted = false;
if (root.next == null && cut < n)
{
isListSorted = true;
root = GetHead(root);
temp = root;
int prev = 0;
while (root.next != null)
{
if(prev > root.data)
{
isListSorted = false;
root = GetHead(root);
temp = root;
break;
}
prev = root.data;
root = root.next;
}
}
else
{
temp = temp.next;
}
if(isListSorted && cut < n)
{
root = GetTail(root);
for(int i = 1; i <= (n - cut);i++)
{
root.prev.next = null;
cut += 1;
root = root.prev;
}
}
}
root = GetHead(root);
string number = root.data.ToString();
while (root.next != null)
{
number = number + root.next.data.ToString();
root = root.next;
}
root = null; //free linked list
return number;
}
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace DataStructures
{
public class GetLowestNumber
{
private static DoubleLinkedListNode root;
public DoubleLinkedListNode GetHead(DoubleLinkedListNode node)
{
if (node == null)
{
return null;
}
while (node.prev != null)
{
node = node.prev;
}
return node;
}
public DoubleLinkedListNode GetTail(DoubleLinkedListNode node)
{
if (node == null)
{
return null;
}
while (node.next != null)
{
node = node.next;
}
return node;
}
public string GetLowNumber(string input, int n)
{
DoubleLinkedListNode temp;
for (int i = 0; i < input.Count(); i++)
{
temp = new DoubleLinkedListNode();
temp.data = Convert.ToInt32(input[i].ToString());
if (root == null)
{
root = temp;
}
else
{
root.next = temp;
root.next.prev = root;
}
if (root.next != null)
{
root = root.next;
}
}
root = GetHead(root);
int cut = 0;
temp = root;
while (cut < n)
{
while (root.next != null)
{
if (temp.data > root.next.data)
{
if (cut < n)
{
root.next.prev = temp.prev;
if (root.next.prev != null)
{
root.next.prev.next = root.next;
}
cut += 1;
root = root.next;
break;
}
else
{
break;
}
}
else
{
root = root.next;
break;
}
}
bool isListSorted = false;
if (root.next == null && cut < n)
{
isListSorted = true;
root = GetHead(root);
temp = root;
int prev = 0;
while (root.next != null)
{
if(prev > root.data)
{
isListSorted = false;
root = GetHead(root);
temp = root;
break;
}
prev = root.data;
root = root.next;
}
}
else
{
temp = temp.next;
}
if(isListSorted && cut < n)
{
root = GetTail(root);
for(int i = 1; i <= (n - cut);i++)
{
root.prev.next = null;
cut += 1;
root = root.prev;
}
}
}
root = GetHead(root);
string number = root.data.ToString();
while (root.next != null)
{
number = number + root.next.data.ToString();
root = root.next;
}
root = null; //free linked list
return number;
}
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace DataStructures
{
public class GetLowestNumber
{
private static DoubleLinkedListNode root;
public DoubleLinkedListNode GetHead(DoubleLinkedListNode node)
{
if (node == null)
{
return null;
}
while (node.prev != null)
{
node = node.prev;
}
return node;
}
public DoubleLinkedListNode GetTail(DoubleLinkedListNode node)
{
if (node == null)
{
return null;
}
while (node.next != null)
{
node = node.next;
}
return node;
}
public string GetLowNumber(string input, int n)
{
DoubleLinkedListNode temp;
for (int i = 0; i < input.Count(); i++)
{
temp = new DoubleLinkedListNode();
temp.data = Convert.ToInt32(input[i].ToString());
if (root == null)
{
root = temp;
}
else
{
root.next = temp;
root.next.prev = root;
}
if (root.next != null)
{
root = root.next;
}
}
root = GetHead(root);
int cut = 0;
temp = root;
while (cut < n)
{
while (root.next != null)
{
if (temp.data > root.next.data)
{
if (cut < n)
{
root.next.prev = temp.prev;
if (root.next.prev != null)
{
root.next.prev.next = root.next;
}
cut += 1;
root = root.next;
break;
}
else
{
break;
}
}
else
{
root = root.next;
break;
}
}
bool isListSorted = false;
if (root.next == null && cut < n)
{
isListSorted = true;
root = GetHead(root);
temp = root;
int prev = 0;
while (root.next != null)
{
if(prev > root.data)
{
isListSorted = false;
root = GetHead(root);
temp = root;
break;
}
prev = root.data;
root = root.next;
}
}
else
{
temp = temp.next;
}
if(isListSorted && cut < n)
{
root = GetTail(root);
for(int i = 1; i <= (n - cut);i++)
{
root.prev.next = null;
cut += 1;
root = root.prev;
}
}
}
root = GetHead(root);
string number = root.data.ToString();
while (root.next != null)
{
number = number + root.next.data.ToString();
root = root.next;
}
root = null; //free linked list
return number;
}
}
}
C# code:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace DataStructures
{
public class DoubleLinkedListNode
{
public int data { get; set; }
public DoubleLinkedListNode prev { get; set; }
public DoubleLinkedListNode next { get; set; }
}
public class GetLowestNumber
{
private static DoubleLinkedListNode root;
public DoubleLinkedListNode GetHead(DoubleLinkedListNode node)
{
if (node == null)
{
return null;
}
while (node.prev != null)
{
node = node.prev;
}
return node;
}
public DoubleLinkedListNode GetTail(DoubleLinkedListNode node)
{
if (node == null)
{
return null;
}
while (node.next != null)
{
node = node.next;
}
return node;
}
public string GetLowNumber(string input, int n)
{
DoubleLinkedListNode temp;
for (int i = 0; i < input.Count(); i++)
{
temp = new DoubleLinkedListNode();
temp.data = Convert.ToInt32(input[i].ToString());
if (root == null)
{
root = temp;
}
else
{
root.next = temp;
root.next.prev = root;
}
if (root.next != null)
{
root = root.next;
}
}
root = GetHead(root);
int cut = 0;
temp = root;
while (cut < n)
{
while (root.next != null)
{
if (temp.data > root.next.data)
{
if (cut < n)
{
root.next.prev = temp.prev;
if (root.next.prev != null)
{
root.next.prev.next = root.next;
}
cut += 1;
root = root.next;
break;
}
else
{
break;
}
}
else
{
root = root.next;
break;
}
}
bool isListSorted = false;
if (root.next == null && cut < n)
{
isListSorted = true;
root = GetHead(root);
temp = root;
int prev = 0;
while (root.next != null)
{
if(prev > root.data)
{
isListSorted = false;
root = GetHead(root);
temp = root;
break;
}
prev = root.data;
root = root.next;
}
}
else
{
temp = temp.next;
}
if(isListSorted && cut < n)
{
root = GetTail(root);
for(int i = 1; i <= (n - cut);i++)
{
root.prev.next = null;
cut += 1;
root = root.prev;
}
}
}
root = GetHead(root);
string number = root.data.ToString();
while (root.next != null)
{
number = number + root.next.data.ToString();
root = root.next;
}
root = null; //free linked list
return number;
}
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace DataStructures
{
public class DoubleLinkedListNode
{
public int data { get; set; }
public DoubleLinkedListNode prev { get; set; }
public DoubleLinkedListNode next { get; set; }
}
public class GetLowestNumber
{
private static DoubleLinkedListNode root;
public DoubleLinkedListNode GetHead(DoubleLinkedListNode node)
{
if (node == null)
{
return null;
}
while (node.prev != null)
{
node = node.prev;
}
return node;
}
public DoubleLinkedListNode GetTail(DoubleLinkedListNode node)
{
if (node == null)
{
return null;
}
while (node.next != null)
{
node = node.next;
}
return node;
}
public string GetLowNumber(string input, int n)
{
DoubleLinkedListNode temp;
for (int i = 0; i < input.Count(); i++)
{
temp = new DoubleLinkedListNode();
temp.data = Convert.ToInt32(input[i].ToString());
if (root == null)
{
root = temp;
}
else
{
root.next = temp;
root.next.prev = root;
}
if (root.next != null)
{
root = root.next;
}
}
root = GetHead(root);
int cut = 0;
temp = root;
while (cut < n)
{
while (root.next != null)
{
if (temp.data > root.next.data)
{
if (cut < n)
{
root.next.prev = temp.prev;
if (root.next.prev != null)
{
root.next.prev.next = root.next;
}
cut += 1;
root = root.next;
break;
}
else
{
break;
}
}
else
{
root = root.next;
break;
}
}
bool isListSorted = false;
if (root.next == null && cut < n)
{
isListSorted = true;
root = GetHead(root);
temp = root;
int prev = 0;
while (root.next != null)
{
if(prev > root.data)
{
isListSorted = false;
root = GetHead(root);
temp = root;
break;
}
prev = root.data;
root = root.next;
}
}
else
{
temp = temp.next;
}
if(isListSorted && cut < n)
{
root = GetTail(root);
for(int i = 1; i <= (n - cut);i++)
{
root.prev.next = null;
cut += 1;
root = root.prev;
}
}
}
root = GetHead(root);
string number = root.data.ToString();
while (root.next != null)
{
number = number + root.next.data.ToString();
root = root.next;
}
root = null; //free linked list
return number;
}
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace DataStructures
{
public class DoubleLinkedListNode
{
public int data { get; set; }
public DoubleLinkedListNode prev { get; set; }
public DoubleLinkedListNode next { get; set; }
}
public class GetLowestNumber
{
private static DoubleLinkedListNode root;
public DoubleLinkedListNode GetHead(DoubleLinkedListNode node)
{
if (node == null)
{
return null;
}
while (node.prev != null)
{
node = node.prev;
}
return node;
}
public DoubleLinkedListNode GetTail(DoubleLinkedListNode node)
{
if (node == null)
{
return null;
}
while (node.next != null)
{
node = node.next;
}
return node;
}
public string GetLowNumber(string input, int n)
{
DoubleLinkedListNode temp;
for (int i = 0; i < input.Count(); i++)
{
temp = new DoubleLinkedListNode();
temp.data = Convert.ToInt32(input[i].ToString());
if (root == null)
{
root = temp;
}
else
{
root.next = temp;
root.next.prev = root;
}
if (root.next != null)
{
root = root.next;
}
}
root = GetHead(root);
int cut = 0;
temp = root;
while (cut < n)
{
while (root.next != null)
{
if (temp.data > root.next.data)
{
if (cut < n)
{
root.next.prev = temp.prev;
if (root.next.prev != null)
{
root.next.prev.next = root.next;
}
cut += 1;
root = root.next;
break;
}
else
{
break;
}
}
else
{
root = root.next;
break;
}
}
bool isListSorted = false;
if (root.next == null && cut < n)
{
isListSorted = true;
root = GetHead(root);
temp = root;
int prev = 0;
while (root.next != null)
{
if(prev > root.data)
{
isListSorted = false;
root = GetHead(root);
temp = root;
break;
}
prev = root.data;
root = root.next;
}
}
else
{
temp = temp.next;
}
if(isListSorted && cut < n)
{
root = GetTail(root);
for(int i = 1; i <= (n - cut);i++)
{
root.prev.next = null;
cut += 1;
root = root.prev;
}
}
}
root = GetHead(root);
string number = root.data.ToString();
while (root.next != null)
{
number = number + root.next.data.ToString();
root = root.next;
}
root = null; //free linked list
return number;
}
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace DataStructures
{
public class DoubleLinkedListNode
{
public int data { get; set; }
public DoubleLinkedListNode prev { get; set; }
public DoubleLinkedListNode next { get; set; }
}
public class GetLowestNumber
{
private static DoubleLinkedListNode root;
public DoubleLinkedListNode GetHead(DoubleLinkedListNode node)
{
if (node == null)
{
return null;
}
while (node.prev != null)
{
node = node.prev;
}
return node;
}
public DoubleLinkedListNode GetTail(DoubleLinkedListNode node)
{
if (node == null)
{
return null;
}
while (node.next != null)
{
node = node.next;
}
return node;
}
public string GetLowNumber(string input, int n)
{
DoubleLinkedListNode temp;
for (int i = 0; i < input.Count(); i++)
{
temp = new DoubleLinkedListNode();
temp.data = Convert.ToInt32(input[i].ToString());
if (root == null)
{
root = temp;
}
else
{
root.next = temp;
root.next.prev = root;
}
if (root.next != null)
{
root = root.next;
}
}
root = GetHead(root);
int cut = 0;
temp = root;
while (cut < n)
{
while (root.next != null)
{
if (temp.data > root.next.data)
{
if (cut < n)
{
root.next.prev = temp.prev;
if (root.next.prev != null)
{
root.next.prev.next = root.next;
}
cut += 1;
root = root.next;
break;
}
else
{
break;
}
}
else
{
root = root.next;
break;
}
}
bool isListSorted = false;
if (root.next == null && cut < n)
{
isListSorted = true;
root = GetHead(root);
temp = root;
int prev = 0;
while (root.next != null)
{
if(prev > root.data)
{
isListSorted = false;
root = GetHead(root);
temp = root;
break;
}
prev = root.data;
root = root.next;
}
}
else
{
temp = temp.next;
}
if(isListSorted && cut < n)
{
root = GetTail(root);
for(int i = 1; i <= (n - cut);i++)
{
root.prev.next = null;
cut += 1;
root = root.prev;
}
}
}
root = GetHead(root);
string number = root.data.ToString();
while (root.next != null)
{
number = number + root.next.data.ToString();
root = root.next;
}
root = null; //free linked list
return number;
}
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace DataStructures
{
public class DoubleLinkedListNode
{
public int data { get; set; }
public DoubleLinkedListNode prev { get; set; }
public DoubleLinkedListNode next { get; set; }
}
public class GetLowestNumber
{
private static DoubleLinkedListNode root;
public DoubleLinkedListNode GetHead(DoubleLinkedListNode node)
{
if (node == null)
{
return null;
}
while (node.prev != null)
{
node = node.prev;
}
return node;
}
public DoubleLinkedListNode GetTail(DoubleLinkedListNode node)
{
if (node == null)
{
return null;
}
while (node.next != null)
{
node = node.next;
}
return node;
}
public string GetLowNumber(string input, int n)
{
DoubleLinkedListNode temp;
for (int i = 0; i < input.Count(); i++)
{
temp = new DoubleLinkedListNode();
temp.data = Convert.ToInt32(input[i].ToString());
if (root == null)
{
root = temp;
}
else
{
root.next = temp;
root.next.prev = root;
}
if (root.next != null)
{
root = root.next;
}
}
root = GetHead(root);
int cut = 0;
temp = root;
while (cut < n)
{
while (root.next != null)
{
if (temp.data > root.next.data)
{
if (cut < n)
{
root.next.prev = temp.prev;
if (root.next.prev != null)
{
root.next.prev.next = root.next;
}
cut += 1;
root = root.next;
break;
}
else
{
break;
}
}
else
{
root = root.next;
break;
}
}
bool isListSorted = false;
if (root.next == null && cut < n)
{
isListSorted = true;
root = GetHead(root);
temp = root;
int prev = 0;
while (root.next != null)
{
if(prev > root.data)
{
isListSorted = false;
root = GetHead(root);
temp = root;
break;
}
prev = root.data;
root = root.next;
}
}
else
{
temp = temp.next;
}
if(isListSorted && cut < n)
{
root = GetTail(root);
for(int i = 1; i <= (n - cut);i++)
{
root.prev.next = null;
cut += 1;
root = root.prev;
}
}
}
root = GetHead(root);
string number = root.data.ToString();
while (root.next != null)
{
number = number + root.next.data.ToString();
root = root.next;
}
root = null; //free linked list
return number;
}
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace DataStructures
{
public class DoubleLinkedListNode
{
public int data { get; set; }
public DoubleLinkedListNode prev { get; set; }
public DoubleLinkedListNode next { get; set; }
}
public class GetLowestNumber
{
private static DoubleLinkedListNode root;
public DoubleLinkedListNode GetHead(DoubleLinkedListNode node)
{
if (node == null)
{
return null;
}
while (node.prev != null)
{
node = node.prev;
}
return node;
}
public DoubleLinkedListNode GetTail(DoubleLinkedListNode node)
{
if (node == null)
{
return null;
}
while (node.next != null)
{
node = node.next;
}
return node;
}
public string GetLowNumber(string input, int n)
{
DoubleLinkedListNode temp;
for (int i = 0; i < input.Count(); i++)
{
temp = new DoubleLinkedListNode();
temp.data = Convert.ToInt32(input[i].ToString());
if (root == null)
{
root = temp;
}
else
{
root.next = temp;
root.next.prev = root;
}
if (root.next != null)
{
root = root.next;
}
}
root = GetHead(root);
int cut = 0;
temp = root;
while (cut < n)
{
while (root.next != null)
{
if (temp.data > root.next.data)
{
if (cut < n)
{
root.next.prev = temp.prev;
if (root.next.prev != null)
{
root.next.prev.next = root.next;
}
cut += 1;
root = root.next;
break;
}
else
{
break;
}
}
else
{
root = root.next;
break;
}
}
bool isListSorted = false;
if (root.next == null && cut < n)
{
isListSorted = true;
root = GetHead(root);
temp = root;
int prev = 0;
while (root.next != null)
{
if(prev > root.data)
{
isListSorted = false;
root = GetHead(root);
temp = root;
break;
}
prev = root.data;
root = root.next;
}
}
else
{
temp = temp.next;
}
if(isListSorted && cut < n)
{
root = GetTail(root);
for(int i = 1; i <= (n - cut);i++)
{
root.prev.next = null;
cut += 1;
root = root.prev;
}
}
}
root = GetHead(root);
string number = root.data.ToString();
while (root.next != null)
{
number = number + root.next.data.ToString();
root = root.next;
}
root = null; //free linked list
return number;
}
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace DataStructures
{
public class DoubleLinkedListNode
{
public int data { get; set; }
public DoubleLinkedListNode prev { get; set; }
public DoubleLinkedListNode next { get; set; }
}
public class GetLowestNumber
{
private static DoubleLinkedListNode root;
public DoubleLinkedListNode GetHead(DoubleLinkedListNode node)
{
if (node == null)
{
return null;
}
while (node.prev != null)
{
node = node.prev;
}
return node;
}
public DoubleLinkedListNode GetTail(DoubleLinkedListNode node)
{
if (node == null)
{
return null;
}
while (node.next != null)
{
node = node.next;
}
return node;
}
public string GenerateLowestNumber(string input, int n)
{
DoubleLinkedListNode temp;
for (int i = 0; i < input.Count(); i++)
{
temp = new DoubleLinkedListNode();
temp.data = Convert.ToInt32(input[i].ToString());
if (root == null)
{
root = temp;
}
else
{
root.next = temp;
root.next.prev = root;
}
if (root.next != null)
{
root = root.next;
}
}
root = GetHead(root);
int cut = 0;
temp = root;
while (cut < n)
{
while (root.next != null)
{
if (temp.data > root.next.data)
{
if (cut < n)
{
root.next.prev = temp.prev;
if (root.next.prev != null)
{
root.next.prev.next = root.next;
}
cut += 1;
root = root.next;
break;
}
else
{
break;
}
}
else
{
root = root.next;
break;
}
}
bool isListSorted = false;
if (root.next == null && cut < n)
{
isListSorted = true;
root = GetHead(root);
temp = root;
int prev = 0;
while (root.next != null)
{
if(prev > root.data)
{
isListSorted = false;
root = GetHead(root);
temp = root;
break;
}
prev = root.data;
root = root.next;
}
}
else
{
temp = temp.next;
}
if(isListSorted && cut < n)
{
root = GetTail(root);
for(int i = 1; i <= (n - cut);i++)
{
root.prev.next = null;
cut += 1;
root = root.prev;
}
}
}
root = GetHead(root);
string number = root.data.ToString();
while (root.next != null)
{
number = number + root.next.data.ToString();
root = root.next;
}
root = null; //free linked list
return number;
}
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Sort
{
class Program
{
static void Main(string[] args)
{
string s = "1279143";
generateLowestNumber(s, 4);
Console.WriteLine();
}
private static void generateLowestNumber(string s, int n)
{
int index = 0;
for (int i = 0; i < s.Length - n; i++)
{
index = getMinimumNumber(s, index, n + 1 - index + i);
}
}
private static int getMinimumNumber(string s, int start, int end)
{
int index = 0;
string temp = s.Substring(start, end);
int number = int.Parse(s);
int minimum = int.MaxValue;
int len = temp.Length;
for (int i = 0; i < len; i++)
{
number = int.Parse(temp);
int n = number / (int)Math.Pow(10, temp.Length - 1);
if (n < minimum)
{
minimum = n;
index = i;
}
temp = temp.Substring(1);
}
Console.Write(minimum);
return start + index + 1;
}
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Sort
{
class Program
{
static void Main(string[] args)
{
string s = "4205123";
generateLowestNumber(s, 4);
Console.WriteLine();
}
private static void generateLowestNumber(string s, int n)
{
int index = 0;
for (int i = 0; i < s.Length - n; i++)
{
index = getMinimumNumber(s, index, n + 1 - index + i);
}
}
private static int getMinimumNumber(string s, int start, int end)
{
int index = 0;
string temp = s.Substring(start, end);
int number = int.Parse(s);
int minimum = int.MaxValue;
int len = temp.Length;
for (int i = 0; i < len; i++)
{
number = int.Parse(temp);
int n = number / (int)Math.Pow(10, temp.Length - 1);
if (n < minimum)
{
minimum = n;
index = i;
}
temp = temp.Substring(1);
}
Console.Write(minimum);
return start + index + 1;
}
}
}
public static String generateLowestNumber2(String number, int n) {
char[] num = number.toCharArray();
Arrays.sort(num);
int len = number.length();
for (int j = n; j < len; j++) {
int i = number.indexOf(num[j]);
number = number.substring(0, i) + number.substring(i + 1,number.length());
}
return number;
}
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;
/**
*
* @author sonali gupta
*/
class GenSmallestNumber {
public static void main(String[] args) throws IOException{
InputStreamReader isr=new InputStreamReader(System.in);
BufferedReader br=new BufferedReader(isr);
System.out.println("enter the string");
String Input=br.readLine();
Scanner in=new Scanner(System.in);
System.out.println("enter the number to remove to get the smallest number");
int n= in.nextInt();
String smallNum = genLowestNum(Input,n);
System.out.println(" Smallest string after removing is " + smallNum);
}
public static String genLowestNum(String number,int p ){
if(p==0){
return number;
}
String newNumber=number;
StringBuilder sb= new StringBuilder(newNumber);
for(int i=0;i<p-1;i++){
int j= getLargestIndex(newNumber,i);
sb.deleteCharAt(j);
String resultString= sb.toString();
newNumber=resultString;
}
List<String> comboNumbers;
comboNumbers = new ArrayList<String>();
for(int i=0,j=1;i<newNumber.length()&&j<newNumber.length();i++,j++){
String str= newNumber.substring(0,i)+newNumber.substring(j,newNumber.length());
comboNumbers.add(str);
}
comboNumbers.add(newNumber.substring(0,newNumber.length()-1));
Collections.sort(comboNumbers);
System.out.println(" combinations " + comboNumbers);
String smallestNumber=comboNumbers.get(0);
return smallestNumber;
}
static int getLargestIndex(String str, int index){
for(int i=1;i<str.length();i++){
if(str.charAt(i)>str.charAt(index)){
index=i;
}
}
return index;
}
}
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;
/**
*
* @author sonali gupta
*/
class GenSmallestNumber {
public static void main(String[] args) throws IOException{
InputStreamReader isr=new InputStreamReader(System.in);
BufferedReader br=new BufferedReader(isr);
System.out.println("enter the string");
String Input=br.readLine();
Scanner in=new Scanner(System.in);
System.out.println("enter the number to remove to get the smallest number");
int n= in.nextInt();
String smallNum = genLowestNum(Input,n);
System.out.println(" Smallest string after removing is " + smallNum);
}
public static String genLowestNum(String number,int p ){
if(p==0){
return number;
}
String newNumber=number;
StringBuilder sb= new StringBuilder(newNumber);
for(int i=0;i<p-1;i++){
int j= getLargestIndex(newNumber,i);
sb.deleteCharAt(j);
String resultString= sb.toString();
newNumber=resultString;
}
List<String> comboNumbers;
comboNumbers = new ArrayList<String>();
for(int i=0,j=1;i<newNumber.length()&&j<newNumber.length();i++,j++){
String str= newNumber.substring(0,i)+newNumber.substring(j,newNumber.length());
comboNumbers.add(str);
}
comboNumbers.add(newNumber.substring(0,newNumber.length()-1));
Collections.sort(comboNumbers);
System.out.println(" combinations " + comboNumbers);
String smallestNumber=comboNumbers.get(0);
return smallestNumber;
}
static int getLargestIndex(String str, int index){
for(int i=1;i<str.length();i++){
if(str.charAt(i)>str.charAt(index)){
index=i;
}
}
return index;
}
}
Here is the solution for this problem
LowestNumb(InputStr, n)
if n > InputStr.Length
output = 0;
else
CountArray = Integer array of size 9, each having value 0, indexing from 0 to 9
for index j from 0 to InputStr.Length-1
CountArray[InputStr[j].ToInt()]++;
for index j from 9 to 0
if n > CountArray[j]
n = n-CountArray[j];
CountArray[j] = 0;
else
CountArray[j] = CountArray[j] - n;
n = 0;
break;
Multiplier = 1;
output = 0;
for index j from 0 to InputStr.Length-1
if(CountArray[InputStr[j].ToInt()] > 0)
output = output + InputStr[j].ToInt()*Multiplier;
CountArray[InputStr[j].ToInt()] --;
Multiplier = Multiplier * 10;
print output
private static class Pair
{
private int num;
private int index;
public Pair(int num, int index)
{
this.num = num;
this.index = index;
}
@Override
public String toString()
{
return "num = " + num + ", index = " + index;
}
}
private static int findIndex(ArrayList<Pair> A, int L, int N, int i, int num)
{
for (int k = 0; k < A.size(); k++)
if (N - i >= L - k && A.get(k).num > num)
return k;
return -1;
}
public static String solution1(String A, int M)
{
int N = A.length();
int L = N - M;
if (L == 0) return "";
if (L == N || L < 0) return A;
else if (L == 1)
{
char[] Achar = A.toCharArray();
Arrays.sort(Achar);
return Character.toString(Achar[0]);
}
ArrayList<Pair> result = new ArrayList<>();
result.add(new Pair(A.charAt(0) - '0', 0));
for (int k = 1; k < N; k++)
{
int num = (int)(A.charAt(k) - '0');
if (result.size() + N - k <= L)
result.add(new Pair(num, k));
else
{
int index = findIndex(result, L, N, k, num);
Pair newPair = new Pair(num, k);
if (index == -1)
result.add(newPair);
else
{
result.set(index, new Pair(num, k));
Pair removed = result.get(result.size()-1);
while (k != removed.index)
{
result.remove(removed);
removed = result.get(result.size()-1);
}
}
}
}
if (result.size() > L) result.remove(result.size()-1);
StringBuilder temp = new StringBuilder();
for (Pair x : result) temp.append(x.num);
return temp.toString();
}
private static String shuffle(String A)
{
char[] Achar = A.toCharArray();
Random randGen = new Random();
for (int k = 0; k < Achar.length; k++)
{
int i = randGen.nextInt(k+1);
char temp = Achar[k];
Achar[k] = Achar[i];
Achar[i] = temp;
}
return new String(Achar);
}
public static void main(String[] args)
{
String[] A1 = {"4205123", "216504"};
int M1 = 4;
int M2 = 3;
for (String x : A1)
{
System.out.println("Input number = " + x + ", L = " + x.length());
System.out.println("Smallest number for: ");
System.out.printf("M = %5d: %20s\n", M1, solution1(x, M1));
System.out.printf("M = %5d: %20s\n", M2, solution1(x, M2));
System.out.println();
}
Random randGen = new Random();
for (int k = 1; k <= 15; k++)
{
int data = randGen.nextInt(Integer.MAX_VALUE - 200) + 100;
String dataStr = shuffle(Integer.toString(data));
int M = randGen.nextInt(5) + 1;
System.out.println("Input string = " + dataStr + ", L = " + dataStr.length());
System.out.printf("Smallest number when M = %5d: %30s\n", M, solution1(dataStr, M));
System.out.println();
}
String[] A2 = {"1354427625", "1865979234"};
for (String x : A2)
{
System.out.println("Input string = " + x + ", L = " + x.length());
System.out.printf("Smallest number when M = %5d: %30s\n", 5,
solution1(x, 5));
System.out.println();
}
}
{ int FindLowest(const char *ptr, int k)
10 {
11 if(ptr == NULL || k < 1 || k >= sizeof(ptr)){
12 cout<<"Invalid Input"<<endl;
13 return 0;
14 }
15 int arr[10];
16 int index = -1;
17 //for(int count = 0; count < k; count++){
18 while(true){
19 if(k == 0){
20 while(*ptr != '\0'){
21 arr[++index] = *ptr;
22 ++ptr;
23 }
24 break;
25 }
26 if(*ptr == '\0'){
27 index = index - k;
28 break;
29 }
30 if(index >= 0){
31 while(arr[index] > *ptr){
32 index--;
33 k--;
34 if(index == -1 || k == 0){
35 break;
36 }
37 }
38 arr[++index] = *ptr;
39 } else {
40 arr[++index] = *ptr;
41 }
42 ++ptr;
43 }
44 for(int count = 0; count <= index; ++count){
45 cout<<arr[count] - 48;
46 }
47 cout<<endl;
48 }
Actually there is a simpler way to doing this. We will need to two maxheaps
1) find the lowest index. let's say number is aaaaXbbbb where X is lowest index
2) create maxheap1 for upper part (aaaa).
3) create maxheap2 for lower part (bbbb)
now, get max from maxheap1, if it is greater than x, then remove the value from heap and the string. if max from heap1 is lower than or equal to X then remove the value from maxHeap2. the value from maxHeap2 should be greater than the max value from maxHeap1
- Srinivas March 14, 2015package com.cnu.ds.hash.test; public class Microsoft { public static String generateLowestNumber(String number, int n) { if (number == null || number.length() < n) { return null; } else if (number.length() > n) { int removed = 0; for (int i = 0, j = 1; removed != n && j != number.length();) { if (number.charAt(i) > number.charAt(j)) { number = number.substring(0, i) + number.substring(j, number.length()); System.out.println(number); i = 0; j = 1; removed++; } else { i++; j++; } } } return null; } public static void main(String[] args) { generateLowestNumber("2200010300", 4); } }