hellohello
BAN USER@blckembr you are right. Here is properly indented code with the bug you pointed out fixed.
{{
def compare(str1, str2):
i = 0;
n = len(str1)
m = len(str2)
c1 = ''
c2 = ''
while i < max(n,m):
if i < n: c1 = str1[i]
if i < m: c2 = str2[i]
if(c1 == c2) continue;
return c1 > c2
return n < m
}}
def compare(str1, str2):
i = 0;
n = len(str1)
m = len(str2)
c1 = ''
c2 = ''
while i < max(n,m):
if i < n: c1 = str1[i]
if i < m: c2 = str2[i]
if(c1 == c2) continue;
return c1 > c2
return true;
Convert the int's to string's. Then sort them using this function and concatenate.
To compare, find the first character by which they differ and compare them.
def compare(str1, str2):
i = 0;
n = len(str1)
m = len(str2)
c1 = ''
c2 = ''
while i < max(n,m):
if i < n: c1 = str1[i]
if i < m: c2 = str2[i]
if(c1 == c2) continue;
return c1 > c2
return true;
Concise solution in Scala
def gen(elems:List[Int], n:Int): List[List[Int]] = {
if(n == 0) List(List())
else if(elems.isEmpty) Nil
else {
gen(elems.tail, n) :::
gen(elems, n - 1).map(elems.head :: _)
}
}
Scala
object Solve extends App {
def gen(elems:List[Int], n:Int): List[List[Int]] = {
println( s"$elems $n" )
if(n == 0) List(List())
else if(elems.isEmpty) Nil
else {
gen(elems.tail, n) :::
gen(elems, n - 1).map(elems.head :: _)
}
}
println(gen(List(2,3,4), 2))
}
This is hard to solve in 30 mins. Took me about 2 hours or so.
The key insight here is that there is no "zero" value in this representation.
Otherwise, it is similar to a binary representation.
A = 1 and B = 2
And value (0 counted from right) is 2^i times the value of A or B at that location.
Now, in order to deal with there being no zeros, first find the largest number represented with only A's that is smaller than the given number.
Example: for 13 that value is "AAA".
After than take the remaining value 13 - AAA = 13 - 7 = 6.
Now, take the binary representation of 6 which is "110" and for each occurance of 1, replace A with B. i.e "AAA" becomes "BBA".
class Solution {
public static String reverse(String str){
return new StringBuilder(str).reverse().toString();
}
public static String sequence(int num){
//baseNum is just a value corresponding to series of A's
int baseNum = 1;
int length = 1;
while((baseNum << 1) + 1 <= num){
baseNum = (baseNum << 1) + 1;
length += 1;
}
int remaining = num - baseNum;
String remainingStr = Integer.toString(remaining,2);
String remRev = reverse(remainingStr);
String res = "";
for(int i = 0; i < length; i++){
boolean second = (i < remRev.length()
&& remRev.charAt(i) == '1');
res += (second ? "B" : "A");
}
return reverse(res);
}
public static void main(String[] args) {
System.out.println( sequence(12) );
}
}
Man, this problem is hard. Do they really ask this in the interviews ?
- hellohello October 30, 2015Here is very efficient linear time solution.
They key insight to note is that all solutions is a substring of "123456789".
Given this insight, all you have to do is generate all substrings of size k, where k is the length of the input number string. Then return the first substring that is greater then the input string's numeric value.
static String ref = "123456789";
static int max = 123456789;
public static String nextSequence(String str){
int num = Integer.parseInt(str);
if(num > max) return "";
int k = str.length();
for(int i = 0; i <= ref.length() - k; i++){
int candidate = Integer.parseInt(ref.substring(i,i+k));
if(candidate > num){
return ""+candidate;
}
}
if(k+1 <= ref.length()) return ref.substring(0,k+1);
return "";
}
- hellohello November 21, 2015