Thanks so much for watching this video, guys! If you're interested in more interview questions like this, I also would recommend my Udemy course, 11 Essential Coding Interview Questions: www.udemy.com/11-essential-coding-interview-questions/?couponCode=HOWTOCRACK
Why cant we make a number of the elements in the array. add 1 to it and then take it apart and put it in a an array. [1,2,3,9]==> 1239 1239+1; 1240 loop to separate the digits num%10 put them in an array
This is literally the first time i understand the code behind a coding interview, that means progress! thank you so much for making it easy to understand
my approach: def add (arr): res = list(arr) last = len(res) - 1 while True: if res[last] < 9: res[last] += 1 break res[last] = 0 last -= 1 if last < 0: res[0] = 1 res.append(0) break return res
Python: Def addOne(set1): Value= (''.join(str(x) for x in set1)*1 Value = int(Value)+1 Value = [int(i) for i in str(value)] Print(Value) addOne([1,2,3,4])
Your solution makes sense, I did this in javascript. However my original JS solution involves taking the array of numbers, joining it into a string, parse inting it, adding the value 1, turning the value ack into a string, splitting it then mapping it running parse int individually on each element. I mean it works, and the reason for mapping at the end is he says they're integers which to me means they'll be number values and not strings or any other type of primitive value.
I think the purpose of the video is "how to solve" a technical question in an interview setup and not solving this particular problem. Several people here have commented about other algorithms. I think they are missing the point.
You can improve the loop by changing if total statement to "if total != 10: carry=0;break;" Cause once the carry is zero it cannot become 1 thus the rest is unnecessary if you copy the original array instead of making a new one
We can derive a different algorithmic approach by observing that all we're basically doing is simply adding a one to the first non-nine digit that we observe (from right to left), and changing it to a zero otherwise. Notice also that this approach would make it much more efficient than the solution presented in this video (on average) if we break out of the loop as soon as we find that first non-nine digit. Here is that approach implemented in python: def addOne(array): i = len(array) - 1 while i >= 0: if array[i] != 9: array[i] += 1 return array array[i] = 0 i -= 1 array.insert(0,1) return array
This is why I watched the whole video, because I though he would mention that in the end to make the code more efficient if the given array is way bigger than these examples.
in such questions [0, 8,7,6] after adding 1 should return [8, 7,7] not [0, 8,7,7] Means one has to remove 0 from front if of no use. Ex in 0 8 7 7 , 0 has no use.
I think it would be easier to reverse the array, then search for the first number that isn't 9. Add one to it and return. If you can't find any number that isn't 9 in the reversed array, just turn all the elements to 0 and add a 1 at the beginning. It's still O(n) on both accounts.
I haven't seen anyone point out yet that in the final instance if carry is 1 and you allocate a new array then you destroy the previous result. Creating a new array doesn't automatically copy the previous contents. Either you need to grow the resultant array if your runtime supports it, then move everything down one, or you need to allocate a new array, copy result[] into it at offset 1 then assign the new array reference or pointer to result (and delete the previous result vector if your language doesn't automatically garbage collect).
Since we only add one, the only case we have to grow the array is when the given array is 999 so we don't need to copy the result because we know the result will be 1 and 0 0 0 (Depending on garbage collector you will need to initialize array with 0s)
The point is that you can't always rely on the new array contents being initialized. He doesn't specify this and it's supposed to be pseudo-code. If you coded this in C you'd get garbage in your newly allocated array.
I guess we could optimize it for large arrays/lists, it may depend on the language we are going to use but for some maybe we might avoid doing too many "if connections" I'm thinking of replacing the for loop by a while with two stop conditions It would looks like this: def add(given_array) carry = 1 result = new int[given_array.length] i = 0 while i
Concatenate each element in the array, turning it into an integer, add one, turn it back into an array. Of course implementing that code is another story, for me at least.
Depends on the max size of the given array, that should be the first question you ask imo. But if the size is small enough to not exceed the integer limit, this would be my go-to solution as well because of it's simplicity, we essentially don't have to do anything that would be error-prone.
don't ask unnecessary question, We like to see coders think for themselves and show initiative. A "good" interviewer will let you know if you are going in the wrong direction anyway. Use words like " I would do this..." if it's the wrong method the interviewer will let you know what they are intent on seeing. project confidence in your solution (even if it's wrong), don't be timid and unsure of yourself if you are stuck say something, speak up! How many times have we hired people who do great on the technical interview but turn out not to be dedicated. Dedication is the most desirable quality, not skill !
What do you expect from that kind of interview. Someone who is dedicated might not solve the problem in the interview, but later because he is dedicated enough to work on it and improve. He might even solve more complicated issues due to his dedication. Someone with enough experience or who have a lot of fun with puzzles, sorting algorithms or math in general will solve this, might even ask the right questions but will not be dedicated and never solve something else. So instead of just changing the quiz often enough until you find something that shows that he is not dedicated, just check if he is dedicated in the first place, no matter if he can solve the issue or not. There are no stupid humans, you can learn and do everything if you are dedicated enough so dont check "can he do it", check "can he learn it"
I've never done a Google interview so don't know specifically what they're looking for, but in another "How to do Google technical interview" video, the person from Google said that the person being interviewed is expected to ask questions for clarification, and not to assume anything. Using a String was my first thought, too, but I don't know if that would be considered "too easy." I'd have to ask the person conducting the interview. Not sure what "dedicated" means. I'd say the most important quality of any engineer or programmer is persistence when you run into a problem.
I fully disagree. Obviously, you don't want to ask pointless questions just for the sake of asking questions. However, If I'm interviewing you and you are A) very confident and B) wrong, I'm going to let you finish your wrong implementation, then start asking some very pointed questions. I would much rather have somebody be unsure and vocal about it, so I can guide him back to the correct path, earlier rather than later. Because that's what I want from an engineer, someone who can say "I don't know", rather that somebody who wastes time coding the wrong solution. Also, confidence is often mistaken for arrogance.
we can also do that taking each element of array in a string buffer by appending it and then convert that string into an integer and add one to that integer value and last putting each value of that integer to the array. This is my idea , If i am thinking in right direction then please inform me its very kind of you. You are doing great job my friend .
4 ปีที่แล้ว +4
Few things 1. I also thought about convert to int, increase, and convert back to array, AFAIK there is no number limit in Python 2. Even if we will do it with arrays, you might use funct divmod in one step 3. I found out your solution something between Java and Python, but more Java because you are using fixed arrays. If you use Python and variable arrays, you can simply pop last element, add it to the end of a new array, and then adding next numbers incremented by possible carry to the beginning, whole logic would be much simpler
This Worked for me In Python: a2=[] a1=[] def magic(a1): s = map(str,a1) s = ''.join(s) s = int(s) return s s = int(input()) for t in range(s): a = int(input()) a1.append(a) res = magic(a1) res1 = res + 1 res2 = str(res1) for t in range(len(res2)): a2.append(res2[t]) print(a2)
A quick python script using the same solution/simplified logic: def addArray(a): carry = 1 for i in range(len(a)-1,-1,-1): n = (a[i] + carry) % 10 carry = (a[i] + carry) // 10 a[i] = n if carry: a.insert(0,1) return a ------------------------------- To Test: print(addArray([1,3,2,4])) print(addArray([9,9,9,9])) print(addArray([1,9,9]))
I thought at the beginning his request was to turn the array of integers into an integer number then add 1 at the end. For example: [1, 2, 3, 4] ---> 1235
I think that would be a good way to approach the problem. Convert to a number, add one, and then convert back. Of course, it would depend on complexity requirements as to whether this was an acceptable solution. It would certainly be simpler than the solution suggested.
If you came up with the idea of converting it into string -> number -> sum 1 -> convert back, then it might work for some cases but you won't definitely get to work at Google
Very nice interview question. I wanted to share my implementation of the problem (Python 3) def add_one(array): if not next(filter(lambda x: x != 9, array), None): # All elements of the array are equal to 9 return [1] + [0] * len(array) for i in range(1, len(array) + 1): if array[-i] != 9: return array[:-i] + [array[-i] + 1] + [0] * (i - 1)
This is how I would approach it in Ruby: def add_one_to_ary(_array) _index = -1 _array.dup.tap do |_result| while _result[_index] == 9 _result[_index] = 0 _index -= 1 end if _result[_index] _result[_index] += 1 else _result.unshift(1) end end end add_one_to_ary([9, 9, 9]) > [1, 0, 0, 0]
In python 3: arr = [1,3,4,5,9] def addOne(arr): newArr = str(arr) for x in newArr: if x == "[" or x =="]" or x == "," or x ==" ": newArr = newArr.replace(x, "") return list(str(int(newArr) + 1)) print(addOne(arr))
I made it int two ways (C#): 1: Loop in the vector and check the number change. 2: Parse the vector into an int32, add 1, then convert back. (CAN GET OVERFLOW. Changing only Int32 to Int64 or UInt64 WILL NOT WORK) The first one ran at approx 2 million times in 5 seconds. The second one ran approx 6 million times in 5 seconds. private static int[] add_one1(int[] given_array) { given_array[given_array.Length - 1] ++; for (int i = given_array.Length-1; i >= 0; i--) { if (given_array[i] == 10) { given_array[i] = 0; if (i > 0) given_array[i - 1]++; else { given_array = new int[given_array.Length + 1]; given_array[0] = 1; } } } return given_array; } private static int[] add_one2(int[] given_array) { Int32 num = 1; for(int i = 0; i
add_one = reverse . toList . (+1) . toInt . reverse where toInt [] = 0 toInt (x:xs) = x + toInt (map (*10) xs) toList i | i < 10 = [i] toList i = i `mod` 10 : toList (i `div` 10) By no means efficient, but fairly straight-forward. (This is in Haskell)
My Solution working with powers of the decimal system: public static void main(String[] args) { int[] number = {1,2,3,4}; int result = 0; for(int i=number.length ;i>0 ; i--) { int multiplier = (int) Math.pow(10, i-1); result += multiplier*number[(i-number.length) * -1]; } result+= 1; System.out.println(result); }
def decomp_array(given_array): index = len(given_array) - 1 new_array = given_array while index != -1: if new_array[index] < 9: new_array[index] += 1 carry = 0 break else: new_array[index] = 0 index -= 1 carry = 1 if carry == 1: print([1]+new_array) else: print(new_array) decomp_array([9,9,9,9]) i dont know but i think this work well
JS: const addArray= (arr => { let newarr = (+arr.join('')) + 1 let finarr = Array.from(String(newarr), Number) return finarr }) addArray([1,2,4,9]) I think this is faster than iterating over the arrray multiple times.
the point is to implement an algorithmic solution at the end it's an interview to test your problem-solving skills not your knowledge of a specific language
This is how I would approach it: def add_one(arr): carry_over = 1 result = [] for element in arr[::-1]: sum = element + carry_over result.append(sum%10) carry_over = sum//10 if carry_over: result.append(1) return result[::-1]
I think converting it to int and adding 1 is NOT what's required here. I am afraid, one must struggle with implementing the addition the way they tech it in school ("the column method" with "carry" etc). Because if not, the "problem" is too simple for a Google interview (and here is my solution which is much shorter and cleaner than your solution): int("".join([str(x) for x in a])) + 1 # given a = [1,2,3] or a =[9,1,9,9] or a = [9,9,9] or whatever ...
Ken, something bad must have happened while you copied Vlad's code. You're right though that it's not correct because it doesn't return the int in "array form".
```python arr = list(map(int, input().split())) a = 1 for ind, ele in enumerate(reversed(arr)): a += ele*10**ind print(list(int(i) for i in str(a))) ``` I don't know if I'm wrong!!! I'm learning from here!
Yeahhh, I'm thinking of starting a career as a web developer, and at the moment, I know absolutely nothing about coding. Watching this has just made me feel like I need to be a rocket scientist to pass an interview.
I know the point of the question is to demonstrate, but i see some comments saying to convert to string. Convert it into number directly will be faster //convert to integer (only works on positive numbers) int number=0; for(int x=0;x=0) { int m = number % 10; newArray[y] = m; number=number/10; y--; } return newArray;
I think i have better solution.The time and space complexity is better.also the ans is in form of list For best case time complexity is 1 and for worst case time complexity is n for i in range(len(list)): If list[-i-1]==9: list[-i-1]=0 else: list[-i-1]=list[-i-1] + 1 break If i==len(list): list.insert(-100000,1) print(list)
My ans in python # convert the int list into str & +1 using eval() # and convert it back to int list q = [1,3,5,4] values = ''.join(map(str, q)) # convert it into list list(map(int,(str(eval(values)+1)))) # output : [1, 3, 5, 5]
This is how I would solve it. I'd take the array and convert it over to a string iteratively concatenating each integer as a char. Then I would take the string representation of the integer and attempt to parse it as an integer (if it fails, it's obviously not a valid integer and will trigger an exception). I would then add one to the integer. I would then use modulo on the integer to break apart each digit iteratively into a new array to be returned. That to me is the simplest solution.. so I'm not sure if they would accept that xD..I wrote an example of how I'd tackle it in c# below. Unsure how performant it is though..hmmm probably would be better off just using a for loop on the original array. public int[] add_one(int[] digits) { string integer = string.Join("", digits).Replace("-",""); //We don't allow negatives try{int result = int.Parse(integer) + 1;} catch(Exception ex) { throw new Exception("Error: Unable to parse integer array");} var resultList = new List(); for (; result != 0; result /= 10) resultList.Add(result % 10); var resultArray = resultList.Reverse().ToArray(); return resultArray; }
it surprises me how people argue over "can't you just cast it to int?" and the counter question is "what if the array is longer than MAX_INT?" - if it actually is, you won't have access to array.len in most languages you might choose. Like a C++ std::size_t limit - which is usually the biggest integer the system can handle. Not to mention that question is unrealistic - even assuming super efficient memory structures that would blow your memory away if it only runs on a single computer - it'd be 2^64 nibbles(smallest possible size for 0-10), which would come down to 6 exibyte just for the data, not even the data structures. So actual question should be what if the the array's size is >20? If it's less, go ahead, cast it to an unsigned int, add one, cast it back to an array. Probably in most high lvl langs much faster doing a check on the array.len and casting it than doing 20 iterations of a loop just to find that you need to create a new object... In the end this is a basic computer science problem for scientific calculations with larger-than-max_int-numbers, where you have to reinvent the wheel unless your language already supports integer types that are large than what your hardware can handle. Python does this and it uses a very similar approach for the data structure with a struct carrying a long and another struct inside that has an array and an integer for length(see PEP 0237).
You are genius man...I wonder how you managed to logically use those array to write code like that. I hope I will be able to logically write code like that one day. I’m still learning Python though. Started 3 days ago. My goal is to invest 2hrs everyday to learn it for 1 year..Hopefully I will good like you one day. I’m 38 years old though😁... so far, I have learnt variables and values, functions.. integer, float, operator string, list, casting, swapping , . The more I’m learning it; the more is getting tough. Lol..
The problem in question (for interviews) is usually to test your analytical algorithm. In this case, the problem isn't actually about how to actually get the result wanted, but to "design" your own mathematical (arithmetical) system and how to approach them from your own coding. TLDR : it's not about the result, it's about how you get there.
I've seen a few of your videos before and I'm learning python for data science(I have math and statistical training) so when I started watching this video I was thinking of your other interview videos and was wondering how hard these questions are supposed to be(to someone with formal CS training and someone without it), but this video explains it in so many words. I've seen the time complexity stuff, which I imagine once you take the time to understand isn't that difficult. I've seen there's quite a lot of problem solving involved, which seems to involve understanding of what the question asks, data structures(?), and perhaps some mathematical things I take for granted. So given that it doesn't seem too bad, to me anyway. I just need to make sure I understand data structures and time complexity first and foremost. Although I may learn other stuff while learning that. Personally it's just a matter of finding the time but I'll be grateful once I do understand it. For a CS major, I imagine this *should* all be a given but the logical look at the high level discussion might cause some problems possibly, hence the reason for these videos.
Do an explode of the array to generate a string, then cast the string to an integer, add one, then cast back to a string and from string to array. 4 line of code max. I would have never hired you with the solution you have shown in this video.
You are using 4 linear functions, so you end up with O(4n) while the original solution, less elegant, is just O(n). As of space complexity, you are converting to a string of n characters and back into an array of n entries which makes it O(3n), against a O(n) solution again.
Nice solution. I think you should convert your answer to be the array of numbers by adding .map(Number) const question = arr => (parseInt(arr.join('')) + 1).toString().split('').map(Number)
My solution in JavaScript: let numArray = [1, 3, 2, 4] let add_one(given_array) => +given_array.join('') + 1 let output_array = add_one(numArray).toString().split('').map(Number) console.log(output_array)
I think you don't understand what they want from you.They obviously want you will manipulate with an array for receive the result.They don't want you to convert it to number by using a built functions.
Answer from the preview of udemy essential coding interview questions ... def fun(arr): for i in arr: for j in arr: if i *j == 20: return i,j arr = [2,3,4,5,6,7,9] print(fun(arr))
In Python it took just 5-10 minutes (without spaghetti code one-liners or list->string->int->list conversion), but later i'm going to try with a lower-level language like C, and i guess it's going to be more difficult, anyway that's my Python code: #!/usr/bin/python3 from sys import argv #parsing array from args res = [int(x) for x in argv[1]] #adding 1 to last element res[-1] += 1 #looping from last element to first i = (len(res) - 1) while i > 0: if res[i] == 10: res[i] = 0 res[i - 1] += 1 i -= 1 #fixing 99, 999 etc. if res[0] == 10: res= [1] + [0 for x in res] #printing result print(res)
With Python i solved this problem in 5 minutes, with C, it took over half an hour, slower to write, but faster to execute, so there is my C version: #include #include //function for printing result void print_result(int res[], int size, char isTen){ int len; if(isTen) len = size / sizeof(int); else len = (size / sizeof(int)) - 1; for(int i = 0; i < len; i++) printf("%d ", res[i]); printf(" "); } int main(int argc, char *argv[]){ //get length of arg int len = strlen(argv[1]); //initialize array (with lenght + 1 to avoid recreating array in case input is 99, 999 etc.) int res[len + 1]; for(int i = 0; i < len; i++){ res[i] = (int) argv[1][i] - '0'; } //adding 1 to last element res[len - 1]++; //looping from last element to first int i = len; while(i > 0){ if(res[i] == 10){ res[i] = 0; res[i - 1]++; } i--; } //fixing 99, 999 etc. (with isTen boolean) char isTen = 0; if(res[0] == 10){ res[0] = 1; for(int i = 1; i < (len + 1); i++) res[i] = 0; isTen = 1; } //printing result print_result(res, sizeof(res), isTen); return 0; }
what do you think of the next approach O(n): def add_one(given_array): if not given_array: return [] if given_array[-1] == 9: if len(given_array) == 1: return [1, 0] return add_one(given_array[:-1]) + [0] else: given_array[-1] += 1 return given_array
Isn't it simpler to concatenate each element to a string, convert to integer, add 1 to it, then into string again, and for each element in the string push a new element into an empty array? This one covers any cases be it 123, 199, or 999.
var arr = [9,9,9,9]; var stage01 = arr.join(""); var stage02 = +stage01; var stage03 = stage02+1; var stage04 = stage03.toString(); var stage05 = stage04.split(""); console.log(stage05);
You can speed things up by exiting the loop when carry == 0 at the end of the loop or at the start of an iteration. This can drastically improve execution time.
Took hours to finally code my strategy - given_array = [1,9,9,9,9] def addFunc(given_array):
x = "" #Converting given list to its sring value form for i in range(len(given_array)): x = x+str(given_array[i]) print(x) #Now converting string to integer value & simply adding 1 y = int(x) z = y+1 print(z) #Finally converting the integer value after addition, into list strz = str(z) result = [] for digit in strz: result.append(int(digit)) print(result)
The solution I came up with is converting it to number by multiplying each array element with corrosponding power of 10 then adding one and they converting it to array by dividing by power of 10
You can solve this problem with three lines as seen bellow. I will assume the list is small enough not to concatenate with str(), otherwise a forloop will be needed to extract the numbers. import re a = [1, 3, 2, 4] r = re.sub(r"\[|\]|,| ", "", str(a)) s = int(r) + 1
I feel, you don't have to create a new array, until entry is like 9999 .. Else you can modify the current array and stop whenever you get carry=0 and return the actual array.
Well my python might be a bit rusty, but if you coded that in Java you would have to copy the array contents of the results array into a new array (reaults2). If you don't, re initializing the array wipes the contents of your original copy of the array and your new result would be [1, 0,0,0]. Having said that, I would probably have just iterated the array to form the integer, added 1 and then exploded a new array on a toString of the int. Thanks for sharing. I hope all google interviews couple be this easy :)
I think while this is probably the most practical solution, I think it violates the spirit of the question. The interviewer wants to see your thought process in developing an algorithm to handle adding the numbers.
arr = 2,3,6,2,9,4 arr_str = '' for i in arr: arr_str = arr_str + str(i) print(f'{arr_str} + 1 = {str(int(arr_str) + 1)}') If the answer to an interview question isn't 'Fibonacci', graduates from the Fibonacci drilling camp have a hard time :)
You have to make sure that a "number" data type can hold that many digits. For example, In Java. You would not be able to use int if the array is larger than an integer's max size.
You might get a laugh out of the interviewer. While effective. I think it breaks what the question was going for. Also beyond the issue posted above. I think that recasting a variable would take up resources. In a small operation its no biggy but an interviewer is probably looking for optimal performance. Simply being able to write code that does an operation is only half the battle.
If the interviewer would laugh at me for that idea, I'd leave the room and go home. Our goal is to solve problems not to look smart. Giving the proposed problem casting is a valid and simple solution. If 1M digits is a thing my first question would be "Why are there 1 million entries in an array that is a poor way to store data". But then again I'm generally no fan of these types of questions. They're too abstract and lose all meaning. They don't reflect how good of a developer you are.
At the beginning of the interview you should ask the guy if he wants to optimize execution speed, elegance, code readability or least time to code it. :-)
let's say you have given array : [1 , 2 , 3 ,4 ] . why not form an integer like int number = 1000*array[0]+100*array[1]+10*array[2] + array[3] ; Afterward you could easily append 1 that that integer number and conversion to array would be the reverse process .
Good old python supports arbitrarily long numbers. In python2 these were called long, python3 even got rid of the distinction between int and long, so you have even less to worry about.(see: www.python.org/dev/peps/pep-0237/). So something like 10**100000 (A number with a 100001 digits) is perfectly acceptable in python and Christian's answer is perfectly legitimate in my opinion. The interviewer could complain about efficiency issues or make the problem harder by saying floats can be in the array, but there are highly efficient big number scientific libraries for python and I think the interviewer would forgive you for not knowing them by heart without a google.
how about this solution in python: def add_one(a): a = [str(i) for i in a] # Convert digits into strings a = list(str(int(''.join(a)) + 1)) # Concatenate strings -> convert into integer -> add +1 -> convert back too string b = [int(i) for i in a] # Split string into list and convert chars into integers return b
One line in Python 3: print(list(str(int("".join(map(str, set)))+1))) # where the variable "set" is the array # it prints a list of string, it can be mapped to int # to be just like the original array but I didn't find it necessary
Yassine Ghariani That is not true. Have you tested it before commenting? Python 3 does not have an int limit size (: Here you go: print(int('893274569823456892374235234523452345456745674565')) If that was true, the INT casting here would have removed part of the number, but when we cast it again to string (print will do that) it has the original number, so it prints: 893274569823456892374235234523452345456745674565
This IS universal. Python runs just about everywhere and this is one of the reasons: It makes many problems tedious to code fairly easy solve and easy to test. As a hiring manager I would expect this answer or similar in just about any language because many have this capability within the language or popular frameworks. And if in the interview I was looking for fluency in a language that did not allow one to solve the problem with string to int to string conversions readily, I would expect a senior eng., before diving into the algorithm, to point out that the problem can be solved by looping over the array elements and tracking the carry but if simplicity and expediency are important we can solve it with strings. When I am interviewing candidates, I am not only looking for the ability to solve problems, but I also want engineers that have the experience and wisdom to pick the right tools (languages) and craft solutions that not only work, but are easy for others to understand and test. For real work on large coding projects, the string solution is what you want because there are no loops or conditionals to check. It just works and is easy to confirm that is works by just looking at the code, no hand tracing required.
In c# it would be (set being the array): (int.Parse(string.Join("", set)) + 1).ToString().Select(x => (int)Char.GetNumericValue(x)).ToArray(); Whether that is the optimal way I don't really know. I just know this one works.
Here is my solution its more simple : main() { int arr[]={1,3,2,4}; //arr.length - 4 int number=arr[arr.length-1]; int one=1; for(int i=arr.length-2;i>=0;i--){ number+=arr[i]*(one*=10); } System.out.println(number+1); }
I think in JavaScript you could do something like: var new_arr = ((given_array.reverse().reduce(function (acc, val, ind){ return acc + val * Math.pow(10, ind); })) + 1).toString().split("");
My answer in python 😅.it will work perfectly, i swear 😂 numbers=[9,9,9] value="" for number in numbers: value+=str(number) result=str(int(value)+1) numbers.clear() for items in result: numbers.append(int(items)) print(numbers)
Thanks so much for watching this video, guys!
If you're interested in more interview questions like this, I also would recommend my Udemy course, 11 Essential Coding Interview Questions: www.udemy.com/11-essential-coding-interview-questions/?couponCode=HOWTOCRACK
Why cant we make a number of the elements in the array. add 1 to it and then take it apart and put it in a an array.
[1,2,3,9]==> 1239
1239+1;
1240
loop to separate the digits num%10
put them in an array
What if the array size is very long, e.g. 1000 ? You won't be able to do that using int/long.
Then switch to Java and use BigInteger.
"former " software developer .
8
This is literally the first time i understand the code behind a coding interview, that means progress! thank you so much for making it easy to understand
I still do not understand very much 🤧
CS Dojo. I never thought about the 0-9 concept. Thank you for giving me some knowledge on questions a condition that I wouldn't be aware of.
Find the length, loop through, multiply by 10^n , 10^n-1 and so on, add one to the number.
my approach:
def add (arr):
res = list(arr)
last = len(res) - 1
while True:
if res[last] < 9:
res[last] += 1
break
res[last] = 0
last -= 1
if last < 0:
res[0] = 1
res.append(0)
break
return res
Python:
Def addOne(set1):
Value= (''.join(str(x) for x in set1)*1
Value = int(Value)+1
Value = [int(i) for i in str(value)]
Print(Value)
addOne([1,2,3,4])
Your solution makes sense, I did this in javascript. However my original JS solution involves taking the array of numbers, joining it into a string, parse inting it, adding the value 1, turning the value ack into a string, splitting it then mapping it running parse int individually on each element. I mean it works, and the reason for mapping at the end is he says they're integers which to me means they'll be number values and not strings or any other type of primitive value.
I think the purpose of the video is "how to solve" a technical question in an interview setup and not solving this particular problem. Several people here have commented about other algorithms. I think they are missing the point.
You can improve the loop by changing if total statement to "if total != 10: carry=0;break;"
Cause once the carry is zero it cannot become 1 thus the rest is unnecessary if you copy the original array instead of making a new one
Interesting suggestion.
Depending on the language you choose, in the case of 999, your new array may return 1 in the [0] position and random things in the rest.
We can derive a different algorithmic approach by observing that all we're basically doing is simply adding a one to the first non-nine digit that we observe (from right to left), and changing it to a zero otherwise. Notice also that this approach would make it much more efficient than the solution presented in this video (on average) if we break out of the loop as soon as we find that first non-nine digit. Here is that approach implemented in python:
def addOne(array):
i = len(array) - 1
while i >= 0:
if array[i] != 9:
array[i] += 1
return array
array[i] = 0
i -= 1
array.insert(0,1)
return array
This is why I watched the whole video, because I though he would mention that in the end to make the code more efficient if the given array is way bigger than these examples.
Perfect solution.
Wow! Thanks a lot. I didn't understand the code given in the Video but after seeing this for some time. I got it. Thanks.
in such questions
[0, 8,7,6] after adding 1 should return [8, 7,7] not [0, 8,7,7]
Means one has to remove 0 from front if of no use. Ex in 0 8 7 7 , 0 has no use.
I think it would be easier to reverse the array, then search for the first number that isn't 9. Add one to it and return.
If you can't find any number that isn't 9 in the reversed array, just turn all the elements to 0 and add a 1 at the beginning.
It's still O(n) on both accounts.
I haven't seen anyone point out yet that in the final instance if carry is 1 and you allocate a new array then you destroy the previous result. Creating a new array doesn't automatically copy the previous contents. Either you need to grow the resultant array if your runtime supports it, then move everything down one, or you need to allocate a new array, copy result[] into it at offset 1 then assign the new array reference or pointer to result (and delete the previous result vector if your language doesn't automatically garbage collect).
Since we only add one, the only case we have to grow the array is when the given array is 999 so we don't need to copy the result because we know the result will be 1 and 0 0 0 (Depending on garbage collector you will need to initialize array with 0s)
The point is that you can't always rely on the new array contents being initialized. He doesn't specify this and it's supposed to be pseudo-code. If you coded this in C you'd get garbage in your newly allocated array.
Trey Quattro good point! But I don’t think he knows C
He says in the video we are assuming the language initializes the array to 0s by default
That would be an assumption you'd tell your interviewer.
I guess we could optimize it for large arrays/lists, it may depend on the language we are going to use but for some maybe we might avoid doing too many "if connections"
I'm thinking of replacing the for loop by a while with two stop conditions
It would looks like this:
def add(given_array)
carry = 1
result = new int[given_array.length]
i = 0
while i
Concatenate each element in the array, turning it into an integer, add one, turn it back into an array.
Of course implementing that code is another story, for me at least.
Time limit exceeded will be the error
Depends on the max size of the given array, that should be the first question you ask imo. But if the size is small enough to not exceed the integer limit, this would be my go-to solution as well because of it's simplicity, we essentially don't have to do anything that would be error-prone.
don't ask unnecessary question, We like to see coders think for themselves and show initiative. A "good" interviewer will let you know if you are going in the wrong direction anyway. Use words like " I would do this..." if it's the wrong method the interviewer will let you know what they are intent on seeing. project confidence in your solution (even if it's wrong), don't be timid and unsure of yourself if you are stuck say something, speak up! How many times have we hired people who do great on the technical interview but turn out not to be dedicated. Dedication is the most desirable quality, not skill !
What do you expect from that kind of interview. Someone who is dedicated might not solve the problem in the interview, but later because he is dedicated enough to work on it and improve. He might even solve more complicated issues due to his dedication.
Someone with enough experience or who have a lot of fun with puzzles, sorting algorithms or math in general will solve this, might even ask the right questions but will not be dedicated and never solve something else.
So instead of just changing the quiz often enough until you find something that shows that he is not dedicated, just check if he is dedicated in the first place, no matter if he can solve the issue or not.
There are no stupid humans, you can learn and do everything if you are dedicated enough so dont check "can he do it", check "can he learn it"
I've never done a Google interview so don't know specifically what they're looking for, but in another "How to do Google technical interview" video, the person from Google said that the person being interviewed is expected to ask questions for clarification, and not to assume anything. Using a String was my first thought, too, but I don't know if that would be considered "too easy." I'd have to ask the person conducting the interview.
Not sure what "dedicated" means. I'd say the most important quality of any engineer or programmer is persistence when you run into a problem.
I fully disagree. Obviously, you don't want to ask pointless questions just for the sake of asking questions. However, If I'm interviewing you and you are A) very confident and B) wrong, I'm going to let you finish your wrong implementation, then start asking some very pointed questions. I would much rather have somebody be unsure and vocal about it, so I can guide him back to the correct path, earlier rather than later. Because that's what I want from an engineer, someone who can say "I don't know", rather that somebody who wastes time coding the wrong solution. Also, confidence is often mistaken for arrogance.
@@BrianKrahmer you are correct.
Asking questions by actually making statement and let them tell you when you're wrong is the best in this kind of interviews.
we can also do that taking each element of array in a string buffer by appending it and then convert that string into an integer and add one to that integer value and last putting each value of that integer to the array.
This is my idea , If i am thinking in right direction then please inform me its very kind of you.
You are doing great job my friend .
Few things
1. I also thought about convert to int, increase, and convert back to array, AFAIK there is no number limit in Python
2. Even if we will do it with arrays, you might use funct divmod in one step
3. I found out your solution something between Java and Python, but more Java because you are using fixed arrays. If you use Python and variable arrays, you can simply pop last element, add it to the end of a new array, and then adding next numbers incremented by possible carry to the beginning, whole logic would be much simpler
He’s more proficient in JAVA looks like
This Worked for me In Python:
a2=[]
a1=[]
def magic(a1):
s = map(str,a1)
s = ''.join(s)
s = int(s)
return s
s = int(input())
for t in range(s):
a = int(input())
a1.append(a)
res = magic(a1)
res1 = res + 1
res2 = str(res1)
for t in range(len(res2)):
a2.append(res2[t])
print(a2)
python w/o converting to string:
def add_one(digits):
n = len(digits) - 1
return reduce(lambda a, b : a + b[1]*10**(n-b[0]), enumerate(digits), 0) + 1
A quick python script using the same solution/simplified logic:
def addArray(a):
carry = 1
for i in range(len(a)-1,-1,-1):
n = (a[i] + carry) % 10
carry = (a[i] + carry) // 10
a[i] = n
if carry:
a.insert(0,1)
return a
-------------------------------
To Test:
print(addArray([1,3,2,4]))
print(addArray([9,9,9,9]))
print(addArray([1,9,9]))
def addArray(a):
return [int(_) for _ in str(int(''.join([str(_) for _ in a]))+1)]
I thought at the beginning his request was to turn the array of integers into an integer number then add 1 at the end. For example: [1, 2, 3, 4] ---> 1235
I think that would be a good way to approach the problem. Convert to a number, add one, and then convert back. Of course, it would depend on complexity requirements as to whether this was an acceptable solution. It would certainly be simpler than the solution suggested.
If you came up with the idea of converting it into string -> number -> sum 1 -> convert back, then it might work for some cases but you won't definitely get to work at Google
def upList(obj):
for a in range(len(obj)-1,-1,-1):
if obj[a] != 9:
obj[a] = obj[a] + 1
break
else:
obj[a] = 0
else:
return [1] + obj
return obj
Very nice interview question.
I wanted to share my implementation of the problem (Python 3)
def add_one(array):
if not next(filter(lambda x: x != 9, array), None): # All elements of the array are equal to 9
return [1] + [0] * len(array)
for i in range(1, len(array) + 1):
if array[-i] != 9:
return array[:-i] + [array[-i] + 1] + [0] * (i - 1)
Ruby solution
def add_one(given_array)
given_array = (given_array.join('').to_i)+1
given_array = given_array.to_s.split('')
given_array
end
puts add_one([1,2,9,9])
I def like how you explain this stuff. You make it VERY clear and it is still very fun to watch. You rock!
This is how I would approach it in Ruby:
def add_one_to_ary(_array)
_index = -1
_array.dup.tap do |_result|
while _result[_index] == 9
_result[_index] = 0
_index -= 1
end
if _result[_index]
_result[_index] += 1
else
_result.unshift(1)
end
end
end
add_one_to_ary([9, 9, 9])
> [1, 0, 0, 0]
In python 3:
arr = [1,3,4,5,9]
def addOne(arr):
newArr = str(arr)
for x in newArr:
if x == "[" or x =="]" or x == "," or x ==" ":
newArr = newArr.replace(x, "")
return list(str(int(newArr) + 1))
print(addOne(arr))
I made it int two ways (C#):
1: Loop in the vector and check the number change.
2: Parse the vector into an int32, add 1, then convert back. (CAN GET OVERFLOW. Changing only Int32 to Int64 or UInt64 WILL NOT WORK)
The first one ran at approx 2 million times in 5 seconds.
The second one ran approx 6 million times in 5 seconds.
private static int[] add_one1(int[] given_array)
{
given_array[given_array.Length - 1] ++;
for (int i = given_array.Length-1; i >= 0; i--)
{
if (given_array[i] == 10)
{
given_array[i] = 0;
if (i > 0) given_array[i - 1]++;
else
{
given_array = new int[given_array.Length + 1];
given_array[0] = 1;
}
}
}
return given_array;
}
private static int[] add_one2(int[] given_array)
{
Int32 num = 1;
for(int i = 0; i
Simple python code
def add(a, add_num):
carry = add_num
result = list()
for digit in reversed(a):
result_num = digit + carry
if int(result_num / 10) >= 1:
carry = int(result_num / 10)
one_digit_num = result_num % 10
result.insert(0, one_digit_num)
else:
carry = 0
result.insert(0, result_num)
if carry > 0:
result.insert(0, carry)
return [digit for digit in result]
add_one = reverse . toList . (+1) . toInt . reverse
where toInt [] = 0
toInt (x:xs) = x + toInt (map (*10) xs)
toList i | i < 10 = [i]
toList i = i `mod` 10 : toList (i `div` 10)
By no means efficient, but fairly straight-forward. (This is in Haskell)
My Solution working with powers of the decimal system:
public static void main(String[] args) {
int[] number = {1,2,3,4};
int result = 0;
for(int i=number.length ;i>0 ; i--) {
int multiplier = (int) Math.pow(10, i-1);
result += multiplier*number[(i-number.length) * -1];
}
result+= 1;
System.out.println(result);
}
Also, you can snoop the first digit, if it's != 9, the array size can be the same.
def decomp_array(given_array):
index = len(given_array) - 1
new_array = given_array
while index != -1:
if new_array[index] < 9:
new_array[index] += 1
carry = 0
break
else:
new_array[index] = 0
index -= 1
carry = 1
if carry == 1:
print([1]+new_array)
else:
print(new_array)
decomp_array([9,9,9,9])
i dont know but i think this work well
JS:
const addArray= (arr => {
let newarr = (+arr.join('')) + 1
let finarr = Array.from(String(newarr), Number)
return finarr
})
addArray([1,2,4,9])
I think this is faster than iterating over the arrray multiple times.
In python 3 we can do this easily by : print(list(str(int("".join(c))+1)))
the point is to implement an algorithmic solution at the end it's an interview to test your problem-solving skills not your knowledge of a specific language
Loop in the video 14:23-14:37 same as 14:38-14:50.
Great tutorial.
I thought I was losing my mind!
This is how I would approach it:
def add_one(arr):
carry_over = 1
result = []
for element in arr[::-1]:
sum = element + carry_over
result.append(sum%10)
carry_over = sum//10
if carry_over:
result.append(1)
return result[::-1]
this is how i would : (lambda a:map(int,str(int(''.join(map(str,a)))+1)))([9,9,9])
I think converting it to int and adding 1 is NOT what's required here.
I am afraid, one must struggle with implementing the addition the way they tech it in school ("the column method" with "carry" etc).
Because if not, the "problem" is too simple for a Google interview (and here is my solution which is much shorter and cleaner than your solution):
int("".join([str(x) for x in a])) + 1
# given a = [1,2,3] or a =[9,1,9,9] or a = [9,9,9] or whatever ...
And the "An Ex-Googler" must be ashamed of himself in any case :
15 (!) minutes of blah-blah-blah for such a trivial task.
Ken, something bad must have happened while you copied Vlad's code. You're right though that it's not correct because it doesn't return the int in "array form".
SpaceChuppy This is the best.
1 solution:
function add(array){
var num = parseInt(array.join(''))+1
return num
}
In JavaScript you can do:
function addOne(arr)
{
var str = arr.join('');
str = (Number.parseInt(str) +1) + "";
arr = str.split('');
return arr;
}
```python
arr = list(map(int, input().split()))
a = 1
for ind, ele in enumerate(reversed(arr)):
a += ele*10**ind
print(list(int(i) for i in str(a)))
```
I don't know if I'm wrong!!! I'm learning from here!
Yeahhh, I'm thinking of starting a career as a web developer, and at the moment, I know absolutely nothing about coding. Watching this has just made me feel like I need to be a rocket scientist to pass an interview.
I know the point of the question is to demonstrate, but i see some comments saying to convert to string. Convert it into number directly will be faster
//convert to integer (only works on positive numbers)
int number=0;
for(int x=0;x=0)
{
int m = number % 10;
newArray[y] = m;
number=number/10;
y--;
}
return newArray;
I think i have better solution.The time and space complexity is better.also the ans is in form of list
For best case time complexity is 1 and for worst case time complexity is n
for i in range(len(list)):
If list[-i-1]==9:
list[-i-1]=0
else:
list[-i-1]=list[-i-1] + 1
break
If i==len(list):
list.insert(-100000,1)
print(list)
My ans in python
# convert the int list into str & +1 using eval()
# and convert it back to int list
q = [1,3,5,4]
values = ''.join(map(str, q))
# convert it into list
list(map(int,(str(eval(values)+1))))
# output : [1, 3, 5, 5]
You could optimize and end the loop when carry = 0
join -> convert to int -> add 1 -> split
This is how I would solve it. I'd take the array and convert it over to a string iteratively concatenating each integer as a char. Then I would take the string representation of the integer and attempt to parse it as an integer (if it fails, it's obviously not a valid integer and will trigger an exception). I would then add one to the integer. I would then use modulo on the integer to break apart each digit iteratively into a new array to be returned. That to me is the simplest solution.. so I'm not sure if they would accept that xD..I wrote an example of how I'd tackle it in c# below. Unsure how performant it is though..hmmm probably would be better off just using a for loop on the original array.
public int[] add_one(int[] digits)
{
string integer = string.Join("", digits).Replace("-",""); //We don't allow negatives
try{int result = int.Parse(integer) + 1;} catch(Exception ex) { throw new Exception("Error: Unable to parse integer array");}
var resultList = new List();
for (; result != 0; result /= 10)
resultList.Add(result % 10);
var resultArray = resultList.Reverse().ToArray();
return resultArray;
}
it surprises me how people argue over "can't you just cast it to int?" and the counter question is "what if the array is longer than MAX_INT?" - if it actually is, you won't have access to array.len in most languages you might choose. Like a C++ std::size_t limit - which is usually the biggest integer the system can handle.
Not to mention that question is unrealistic - even assuming super efficient memory structures that would blow your memory away if it only runs on a single computer - it'd be 2^64 nibbles(smallest possible size for 0-10), which would come down to 6 exibyte just for the data, not even the data structures.
So actual question should be what if the the array's size is >20? If it's less, go ahead, cast it to an unsigned int, add one, cast it back to an array. Probably in most high lvl langs much faster doing a check on the array.len and casting it than doing 20 iterations of a loop just to find that you need to create a new object...
In the end this is a basic computer science problem for scientific calculations with larger-than-max_int-numbers, where you have to reinvent the wheel unless your language already supports integer types that are large than what your hardware can handle. Python does this and it uses a very similar approach for the data structure with a struct carrying a long and another struct inside that has an array and an integer for length(see PEP 0237).
public static void main(String[] args) {
int [] arr = {9,9,9,9};
int exp = 1;
int sum = 0;
int size = arr.length;
for(int i = 0; i < size ; i++) {
sum += arr[size-1] * exp;
exp *= 10;
size -= 1;
System.out.println("sum is "+ sum);
}
char[] ar = Integer.toString(sum+1).toCharArray();
for(char c: ar) {
System.out.println(c);
}
}
You are genius man...I wonder how you managed to logically use those array to write code like that.
I hope I will be able to logically write code like that one day. I’m still learning Python though. Started 3 days ago. My goal is to invest 2hrs everyday to learn it for 1 year..Hopefully I will good like you one day. I’m 38 years old though😁... so far, I have learnt variables and values, functions.. integer, float, operator string, list, casting, swapping , . The more I’m learning it; the more is getting tough. Lol..
Interesting. A JS one liner for the given arr = [1,3,2,4], could be:
((parseInt(arr.join('')) + 1) + '').split('')
but what if the array is 30 digits in length, do you think you can still do parseInt ?
It's Very Easy Question
Here in javascript
const arr = [9,9,9];
function addOne(givenArr) {
let str = givenArr.join('');
const num = Number(str) + 1;
str = String(num);
return str.split('');
}
console.log(addOne(arr));
The problem in question (for interviews) is usually to test your analytical algorithm.
In this case, the problem isn't actually about how to actually get the result wanted, but to "design" your own mathematical (arithmetical) system and how to approach them from your own coding.
TLDR : it's not about the result, it's about how you get there.
I've seen a few of your videos before and I'm learning python for data science(I have math and statistical training) so when I started watching this video I was thinking of your other interview videos and was wondering how hard these questions are supposed to be(to someone with formal CS training and someone without it), but this video explains it in so many words. I've seen the time complexity stuff, which I imagine once you take the time to understand isn't that difficult. I've seen there's quite a lot of problem solving involved, which seems to involve understanding of what the question asks, data structures(?), and perhaps some mathematical things I take for granted. So given that it doesn't seem too bad, to me anyway. I just need to make sure I understand data structures and time complexity first and foremost. Although I may learn other stuff while learning that. Personally it's just a matter of finding the time but I'll be grateful once I do understand it. For a CS major, I imagine this *should* all be a given but the logical look at the high level discussion might cause some problems possibly, hence the reason for these videos.
I would do it with 5 loc in Python in this way:
from functools import reduce
def fn(x, y):
return x * 10 + y
L=[9,9,9]
print((reduce(fn, L))+1)
Do an explode of the array to generate a string, then cast the string to an integer, add one, then cast back to a string and from string to array. 4 line of code max. I would have never hired you with the solution you have shown in this video.
given_array = [1,2,3,4,5]
mynumber = int(''.join(map(str, given_array))) + 1
print(list(str(mynumber)))
JS solution
function addNum(arr) {
return (Math.floor(arr.join('')) + 1).toString().split('').map(Number);
}
addNum([1,2,3,9]); // -> [1, 2, 4, 0]
I think max array size is max integer. So you can convert array into integer with math and add 1. Then conversation integer back to array.
JavaScript:
const question = arr => (parseInt(arr.join('')) + 1).toString().split('');
console.log(question([1,2,3,9]));
You are using 4 linear functions, so you end up with O(4n) while the original solution, less elegant, is just O(n).
As of space complexity, you are converting to a string of n characters and back into an array of n entries which makes it O(3n), against a O(n) solution again.
Nice solution. I think you should convert your answer to be the array of numbers by adding .map(Number)
const question = arr => (parseInt(arr.join('')) + 1).toString().split('').map(Number)
My solution in JavaScript:
let numArray = [1, 3, 2, 4]
let add_one(given_array) => +given_array.join('') + 1
let output_array = add_one(numArray).toString().split('').map(Number)
console.log(output_array)
thats cheating
addOne = (arr) => {
(Number(arr.join("")) + 1).toString().split("");
}
addOne = arr => (+arr.join("")+1+"").split("");
Although its not optimal, but its a one liner ;)
I think you don't understand what they want from you.They obviously want you will manipulate with an array for receive the result.They don't want you to convert it to number by using a built functions.
Answer from the preview of udemy essential coding interview questions ...
def fun(arr):
for i in arr:
for j in arr:
if i *j == 20:
return i,j
arr = [2,3,4,5,6,7,9]
print(fun(arr))
In Python it took just 5-10 minutes (without spaghetti code one-liners or list->string->int->list conversion), but later i'm going to try with a lower-level language like C, and i guess it's going to be more difficult, anyway that's my Python code:
#!/usr/bin/python3
from sys import argv
#parsing array from args
res = [int(x) for x in argv[1]]
#adding 1 to last element
res[-1] += 1
#looping from last element to first
i = (len(res) - 1)
while i > 0:
if res[i] == 10:
res[i] = 0
res[i - 1] += 1
i -= 1
#fixing 99, 999 etc.
if res[0] == 10:
res= [1] + [0 for x in res]
#printing result
print(res)
lol I don't know WHY I sat through this entire video but dude.. applause. u coders live in a whole other world man
What world do you live in? Code is everywhere if you're alive in 2019
With Python i solved this problem in 5 minutes, with C, it took over half an hour, slower to write, but faster to execute, so there is my C version:
#include
#include
//function for printing result
void print_result(int res[], int size, char isTen){
int len;
if(isTen)
len = size / sizeof(int);
else
len = (size / sizeof(int)) - 1;
for(int i = 0; i < len; i++)
printf("%d ", res[i]);
printf("
");
}
int main(int argc, char *argv[]){
//get length of arg
int len = strlen(argv[1]);
//initialize array (with lenght + 1 to avoid recreating array in case input is 99, 999 etc.)
int res[len + 1];
for(int i = 0; i < len; i++){
res[i] = (int) argv[1][i] - '0';
}
//adding 1 to last element
res[len - 1]++;
//looping from last element to first
int i = len;
while(i > 0){
if(res[i] == 10){
res[i] = 0;
res[i - 1]++;
}
i--;
}
//fixing 99, 999 etc. (with isTen boolean)
char isTen = 0;
if(res[0] == 10){
res[0] = 1;
for(int i = 1; i < (len + 1); i++)
res[i] = 0;
isTen = 1;
}
//printing result
print_result(res, sizeof(res), isTen);
return 0;
}
one word for you, pointers..
what do you think of the next approach O(n):
def add_one(given_array):
if not given_array:
return []
if given_array[-1] == 9:
if len(given_array) == 1:
return [1, 0]
return add_one(given_array[:-1]) + [0]
else:
given_array[-1] += 1
return given_array
arr = [9,9,9]
print(add_one(arr))
Isn't it simpler to concatenate each element to a string, convert to integer, add 1 to it, then into string again, and for each element in the string push a new element into an empty array? This one covers any cases be it 123, 199, or 999.
var arr = [9,9,9,9];
var stage01 = arr.join("");
var stage02 = +stage01;
var stage03 = stage02+1;
var stage04 = stage03.toString();
var stage05 = stage04.split("");
console.log(stage05);
Big thanks for you and we are looking for more videos
You are just doing great hope you will recover fast ...
You can speed things up by exiting the loop when carry == 0 at the end of the loop or at the start of an iteration. This can drastically improve execution time.
Took hours to finally code my strategy -
given_array = [1,9,9,9,9]
def addFunc(given_array):
x = ""
#Converting given list to its sring value form
for i in range(len(given_array)):
x = x+str(given_array[i])
print(x)
#Now converting string to integer value & simply adding 1
y = int(x)
z = y+1
print(z)
#Finally converting the integer value after addition, into list
strz = str(z)
result = []
for digit in strz:
result.append(int(digit))
print(result)
The solution I came up with is converting it to number by multiplying each array element with corrosponding power of 10 then adding one and they converting it to array by dividing by power of 10
Same here
I just love that cute little fluffy penguin stuffie ❤️🐧
given_array, given_array, given_array now... RHCP 1991
You can solve this problem with three lines as seen bellow. I will assume the list is small enough not to concatenate with str(), otherwise a forloop will be needed to extract the numbers.
import re
a = [1, 3, 2, 4]
r = re.sub(r"\[|\]|,| ", "", str(a))
s = int(r) + 1
I feel, you don't have to create a new array, until entry is like 9999 .. Else you can modify the current array and stop whenever you get carry=0 and return the actual array.
Jus append new element .. No need of new array
Well my python might be a bit rusty, but if you coded that in Java you would have to copy the array contents of the results array into a new array (reaults2). If you don't, re initializing the array wipes the contents of your original copy of the array and your new result would be [1, 0,0,0]. Having said that, I would probably have just iterated the array to form the integer, added 1 and then exploded a new array on a toString of the int.
Thanks for sharing. I hope all google interviews couple be this easy :)
I think while this is probably the most practical solution, I think it violates the spirit of the question. The interviewer wants to see your thought process in developing an algorithm to handle adding the numbers.
I wrote a one-liner in python 3.
ls=[9,9,9] #input
intls=[int(x) for x in list(str(eval("".join([str(x) for x in ls]))+1))] #output
Good example that one-liners are not always good solutions (in regard of performance and readability).
arr = 2,3,6,2,9,4
arr_str = ''
for i in arr: arr_str = arr_str + str(i)
print(f'{arr_str} + 1 = {str(int(arr_str) + 1)}')
If the answer to an interview question isn't 'Fibonacci', graduates from the Fibonacci drilling camp have a hard time :)
Wouldn't a link list be easier because it easy to traverse the link list and change the data. If it is the 999 case, just add a new node.
Find last number that is not nine and add one to it, zeroing the numbers as you go. If it doesn't exist, add a 1 in front of the list.
Could I convert the list to a string and then in turn to a number😝 add one then convert to a list
Ralph Dias That's exactly what I thought. Seems like it'd be a lot simpler
What about 100000 digits
You have to make sure that a "number" data type can hold that many digits. For example, In Java. You would not be able to use int if the array is larger than an integer's max size.
You might get a laugh out of the interviewer. While effective. I think it breaks what the question was going for. Also beyond the issue posted above. I think that recasting a variable would take up resources. In a small operation its no biggy but an interviewer is probably looking for optimal performance. Simply being able to write code that does an operation is only half the battle.
If the interviewer would laugh at me for that idea, I'd leave the room and go home. Our goal is to solve problems not to look smart. Giving the proposed problem casting is a valid and simple solution. If 1M digits is a thing my first question would be "Why are there 1 million entries in an array that is a poor way to store data". But then again I'm generally no fan of these types of questions. They're too abstract and lose all meaning. They don't reflect how good of a developer you are.
At the beginning of the interview you should ask the guy if he wants to optimize execution speed, elegance, code readability or least time to code it. :-)
let's say you have given array : [1 , 2 , 3 ,4 ] . why not form an integer like int number = 1000*array[0]+100*array[1]+10*array[2] + array[3] ; Afterward you could easily append 1 that that integer number and conversion to array would be the reverse process .
explode the array to String => convert String to Integer => Add 1 (one) => Convert back to string => implode to Array
MaggicBones I came up with the same solution.
you're only thinking in small terms - what if the array is so large it won't fit your "integer" data type
good point. For that reason it's better to agree on array sizes.
l3ertuz I think max array size is the max integer data type.
Good old python supports arbitrarily long numbers.
In python2 these were called long, python3 even got rid of the distinction between int and long, so you have even less to worry about.(see: www.python.org/dev/peps/pep-0237/).
So something like 10**100000 (A number with a 100001 digits) is perfectly acceptable in python and Christian's answer is perfectly legitimate in my opinion.
The interviewer could complain about efficiency issues or make the problem harder by saying floats can be in the array, but there are highly efficient big number scientific libraries for python and I think the interviewer would forgive you for not knowing them by heart without a google.
I love the way you explain programming, thanks so much!
how about this solution in python:
def add_one(a):
a = [str(i) for i in a] # Convert digits into strings
a = list(str(int(''.join(a)) + 1)) # Concatenate strings -> convert into integer -> add +1 -> convert back too string
b = [int(i) for i in a] # Split string into list and convert chars into integers
return b
In scripting languages, array length is not fixed. Therefore, in JavaScript we can do
parseInt(givenArray.join(''))+1
It doesn't return an array but only the total
@@AdamSafadi then make it array after you did this. Correct me if i am wrong. 🙂
@@joshualim8471that's right
((parseInt([9,9,9].join(''))+1).toString()).split("")
I loved it, thanks. Ps: you could've used break in:
Else: carry=0; break ;
One line in Python 3:
print(list(str(int("".join(map(str, set)))+1)))
# where the variable "set" is the array
# it prints a list of string, it can be mapped to int
# to be just like the original array but I didn't find it necessary
This won't work if the number exceeds the integer type limit.
Yassine Ghariani
That is not true. Have you tested it before commenting?
Python 3 does not have an int limit size (:
Here you go: print(int('893274569823456892374235234523452345456745674565'))
If that was true, the INT casting here would have removed part of the number, but when we cast it again to string (print will do that) it has the original number, so it prints: 893274569823456892374235234523452345456745674565
Marcelo Ely Ok, but what about other languages? Your solution should be universal.
This IS universal. Python runs just about everywhere and this is one of the reasons: It makes many problems tedious to code fairly easy solve and easy to test.
As a hiring manager I would expect this answer or similar in just about any language because many have this capability within the language or popular frameworks. And if in the interview I was looking for fluency in a language that did not allow one to solve the problem with string to int to string conversions readily, I would expect a senior eng., before diving into the algorithm, to point out that the problem can be solved by looping over the array elements and tracking the carry but if simplicity and expediency are important we can solve it with strings.
When I am interviewing candidates, I am not only looking for the ability to solve problems, but I also want engineers that have the experience and wisdom to pick the right tools (languages) and craft solutions that not only work, but are easy for others to understand and test.
For real work on large coding projects, the string solution is what you want because there are no loops or conditionals to check. It just works and is easy to confirm that is works by just looking at the code, no hand tracing required.
In c# it would be (set being the array):
(int.Parse(string.Join("", set)) + 1).ToString().Select(x => (int)Char.GetNumericValue(x)).ToArray();
Whether that is the optimal way I don't really know. I just know this one works.
Thanks . Always wanted this type of tutorial :-)
Here is my solution its more simple :
main() {
int arr[]={1,3,2,4}; //arr.length - 4
int number=arr[arr.length-1];
int one=1;
for(int i=arr.length-2;i>=0;i--){
number+=arr[i]*(one*=10);
}
System.out.println(number+1);
}
Scala one-liner -> (array.mkString("").toInt + 1).toString.map(_.asDigit)
Thank you for your contributions.
This helps a lot for my coming interview
I think in JavaScript you could do something like:
var new_arr = ((given_array.reverse().reduce(function (acc, val, ind){
return acc + val * Math.pow(10, ind);
})) + 1).toString().split("");
My answer in python 😅.it will work perfectly, i swear 😂
numbers=[9,9,9]
value=""
for number in numbers:
value+=str(number)
result=str(int(value)+1)
numbers.clear()
for items in result:
numbers.append(int(items))
print(numbers)
Not good solutions. please read Analysis algorithm
function plusOne(n) {
let number = parseInt(n.join("")) + 1;
number = number.split("");
return number.map(n => +n)
}
This should work in JS.
Good video. Thanks for sharing and walk through the interview process.