Google Interview Question Software Engineer / Developers
0of 0 votesHow would you implement an infinite counter?
Country: United States
Interview Type: Phone Interview
Let us say in the language, the range of integers is from 0-65535.
Use only the nearest 10-powered value - 1. In this case, 10^4 - 1 = 9999.
Keep a counter and increment it until 9999 (say Node-1).
When this value is reached, on next increment, set this counter to 0. Add a node and set the counter to 1 (say Node-2).
Again, count from 0-9999 in Node-1 and on next increment, set Node-1 to 0 and Node-2 to 2.
Continue this way and add extra node whenever required.
Store all these nodes in a doubly linked list for easy access.
Hi, thanks for this logic can you please explain this part --->Again, count from 0-9999 in Node-1 and on next increment, set Node-1 to 0 and Node-2 to 2.
For example,
Initially the linked list is
----------
| 1 |
It will be incremented until 9999
----------
| 9999 |
Now after the next increment, the linked list will add a new node as shown below:
---------- ----------
| 1| <---> | 0 |
This will happen until 19999. After this, again the 9999 is set to 0 and 1 will be added to other node's value. Thus, the linked list would be:
---------- --------
| 2 | <------->|0000|
This way, if we want to print the counter it is to print the values in the nodes together, which is 20000.
This way we can add nodes dynamically infinitely (until the system is out of memory ;) )
l=[1,9,9,0,8]
def inc():
if l==[]:
l.append(1)
else:
for i in range(len(l)-1,-1,-1):
if l[i]==9:
l[i]=0
if l[i]==l[0]:
l.insert(0,1)
else:
l[i]+=1
break
return int(''.join(map(str,l)))
use two variable, one is string and another is int64 M, we start with M = 0, use M till maximum value is hit, then we copy half of it to the string and start start again, if M becoming negative we bring max(M)/2 from string and add it to M, and start again,
for example Max(M) is 1000;
then we start from M = 0; when M is 1000 and one more add come, then we make M to 500 and add 500 to string, when M is 0 and one sub come then we make M to 500 and reduce 500 from string,
so by this way after at least 500 operation we perform one string add/sub. so on an avg we are just doing one add or one sub to integer per operation.
Hello, I am having a hard time understanding what we accomplish by adding max(M)/2 to the string rather than max(M). Could you kindly explain the rational behind this.
def inc():
l=[0,9,9,0,9]
stack=[];
if l==[]:
l.append(1);
else:
carry=0;
sum=l[len(l)-1]+1;
if(sum<=9):
l[len(l)-1]=sum;
return int(''.join(map(str,l)));
else:
carry=1;
stack.append(0);
for i in range(len(l)-2,-1,-1):
sum=carry+l[i];
if(sum>9):
stack.append(0);
carry=1;
else:
stack.append(sum);
carry=0;
stack.reverse();
return int(''.join(map(str,stack)))
res=inc();
print "%s"%res;
No, for most c based languages this will only be meaningful for 2^31 increments. After 2^31+1 increments we can no longer tell whether we overflowed once, twice or a trillion^2 times.
What the question asks is having a meaningful counter beyond this limitation and beyond unsigned long ints. So that's where the psuedo-infinite counter implementation comes in.
public incrementedCount() {
int carry = 1;
Node currentNode = head;
while(true) {
if (currentNode == null) {
currentNode = new Node();
currentNode.data = carry;
head = currentNode;
}
else {
int num = currentNode.data;
int sum = num+carry;
currentNode.data = sum%10;
carry = sum/10;
if (currentNode.next == null && carry > 0) {
Node next = new Node();
next.data = carry;
currentNode.next = next;
break;
}
}
}
}
Use Linked List concept. Let us say that the maximum limit of an integer in the language is 65,536. Let us limit it to 9999.
- Kishan January 22, 2013The counter will increase from 0-9999. After that, add another node, with value 1 and change the first node value to 0. Do this infinitely by adding nodes whenever needed.
Thus, we can easily print the counter value.