Google Interview Question Developer Program Engineers
Country: United States
I completely agree. Pure random data would not be losslessly compressible. However, I hadn't thought the data was random because that was never mentioned in the subject. But, if it were perfectly random then I'm not sure someone would really want to send it. I could only think of a few things that pure random data could be- a 1 time pad or some observed natural phenonemon... ?
///
//////////////////////////////////////////////////////////////
///
/// Time : O(n) n = number of elements.
/// Space: O(n).
//
//////////////////////////////////////////////////////////////
//
#define MAX(a,b) (a>b ? a: b)
/// go over the array from left to right and from right to left.
/// take the maximum of the computed array. This is necessary as
/// the maximum is needed to accomdate the longest increasing or
/// decreasing sequence.
///
/// if current element is bigger than the next element. restart from
/// 1. the reverse order will catch what the next element should be.
int get_min_candy(int *a, int size) {
int lr[size], rl[size];
int sum = 0;
for (int i=0;i<size;++i) {
lr[i] = rl[i] = 1;
}
for (int i=0;i<size-1;++i) {
if (a[i] < a[i+1])
lr[i+1] = lr[i]+1;
}
for (int i=size-1;i>0;--i) {
if (a[i] < a[i-1])
rl[i-1] = rl[i]+1;
}
for (int i=0;i<size;++i) {
sum += MAX(lr[i], rl[i]);
}
return sum;
}
//////////////////////////////////////////////////////////////
// main.
//////////////////////////////////////////////////////////////
int main() {
int a[] = {2,6,1,2,9,1,1,4,9,6,3,5,1};
printf("%d\n", get_min_candy(a, sizeof(a)/sizeof(a[0])));
return 0;
}
\\\
Sounds great so far.
can we optimize it to avoid lr lookup O(n) + rl lookup O(n) + find higher O(n)
into single lookup and thats it. that array can be final answer
hint: both time we traverse through same length of array
The original question is about a stream of 1 and 0 and when you say stream i guess we are not talking about the classic compression algorithm here.
Also the program you have written, first you should provide subjective description of the solution rather jumping directly into the coding which most of the interviewer don't like
//////////////////////////////////////////////////////////////
/// solution 1.
///
/// Time : O(n) n = number of elements.
/// Space: O(n).
//
//////////////////////////////////////////////////////////////
//
#define MAX(a,b) (a>b ? a: b)
/// go over the array from left to right and from right to left.
/// take the maximum of the computed array. This is necessary as
/// the maximum is needed to accomdate the longest increasing or
/// decreasing sequence.
///
/// if current element is bigger than the next element. restart from
/// 1. the reverse order will catch what the next element should be.
int get_min_candy(int *a, int size) {
int lr[size], rl[size];
int sum = 0;
for (int i=0;i<size;++i) {
lr[i] = rl[i] = 1;
}
for (int i=0;i<size-1;++i) {
if (a[i] < a[i+1])
lr[i+1] = lr[i]+1;
}
for (int i=size-1;i>0;--i) {
if (a[i] < a[i-1])
rl[i-1] = rl[i]+1;
}
for (int i=0;i<size;++i) {
sum += MAX(lr[i], rl[i]);
}
return sum;
}
//////////////////////////////////////////////////////////////
// main.
//////////////////////////////////////////////////////////////
int main() {
int a[] = {2,6,1,2,9,1,1,4,9,6,3,5,1};
printf("%d\n", get_min_candy(a, sizeof(a)/sizeof(a[0])));
return 0;
}
//////////////////////////////////////////////////////////////
/// solution 1.
///
/// Time : O(n) n = number of elements.
/// Space: O(n).
//
//////////////////////////////////////////////////////////////
//
#define MAX(a,b) (a>b ? a: b)
/// go over the array from left to right and from right to left.
/// take the maximum of the computed array. This is necessary as
/// the maximum is needed to accomdate the longest increasing or
/// decreasing sequence.
///
/// if current element is bigger than the next element. restart from
/// 1. the reverse order will catch what the next element should be.
int get_min_candy(int *a, int size) {
int lr[size], rl[size];
int sum = 0;
for (int i=0;i<size;++i) {
lr[i] = rl[i] = 1;
}
for (int i=0;i<size-1;++i) {
if (a[i] < a[i+1])
lr[i+1] = lr[i]+1;
}
for (int i=size-1;i>0;--i) {
if (a[i] < a[i-1])
rl[i-1] = rl[i]+1;
}
for (int i=0;i<size;++i) {
sum += MAX(lr[i], rl[i]);
}
return sum;
}
//////////////////////////////////////////////////////////////
// main.
//////////////////////////////////////////////////////////////
int main() {
int a[] = {2,6,1,2,9,1,1,4,9,6,3,5,1};
printf("%d\n", get_min_candy(a, sizeof(a)/sizeof(a[0])));
return 0;
}
public class AssignChocolates {
public int[] assignChocolates(int[] ages) {
int[] assign = new int[ages.length];
for (int i = 0; i < ages.length; i++) {
assign[i] = 1;
}
for (int i = 1; i < ages.length; i++) {
if (ages[i] > ages[i-1]) {
assign[i] = assign[i-1] + 1;
}
}
for (int i = ages.length-2; i >= 0; i--) {
if (ages[i] > ages[i+1]) {
assign[i] = assign[i+1] + 1;
}
}
return assign;
}
/**
* @param args
*/
public static void main(String[] args) {
int[] ages = new int[]{2, 6, 1, 3, 2, 1, 9};
AssignChocolates c = new AssignChocolates();
int[] assign = c.assignChocolates(ages);
for (int i = 0; i < assign.length; i++) {
System.out.print(assign[i] + " ");
}
}
}
public class AssignChocolates {
public int[] assignChocolates(int[] ages) {
int[] assign = new int[ages.length];
for (int i = 0; i < ages.length; i++) {
assign[i] = 1;
}
for (int i = 1; i < ages.length; i++) {
if (ages[i] > ages[i-1]) {
assign[i] = assign[i-1] + 1;
}
}
for (int i = ages.length-2; i >= 0; i--) {
if (ages[i] > ages[i+1]) {
assign[i] = assign[i+1] + 1;
}
}
return assign;
}
/**
* @param args
*/
public static void main(String[] args) {
int[] ages = new int[]{2, 6, 1, 3, 2, 1, 9};
AssignChocolates c = new AssignChocolates();
int[] assign = c.assignChocolates(ages);
for (int i = 0; i < assign.length; i++) {
System.out.print(assign[i] + " ");
}
}
}
It takes 2 hours, is it ok?
int[] age = new int[13] { 2, 6, 1, 2, 9, 1, 1, 4, 9, 6, 3, 5, 1 };
int[] choco = new int[13];
int descendingLength;
for (int i = 0; i < age.Length; i++)
{
if (i < age.Length - 1)
{
if (age[i] > age[i + 1])
{
descendingLength = 1;
int j;
for (j = i; (j + 1) < age.Length && age[j] > age[j + 1]; j++)
descendingLength++;
if(i != 0 && choco[i-1] >= descendingLength)
{
if (age[i-1] == age[i])
choco[i] = choco[i - 1];
else
choco[i] = choco[i - 1] + 1;
i++;
descendingLength--;
}
while (descendingLength > 0)
{
choco[i] = descendingLength--;
i++;
}
i--;
}
else
if (i != 0 && age[i] > age[i - 1])
choco[i] = choco[i - 1] + 1;
else
choco[i] = 1;
}
else
{
if (age[i] > age[i - 1])
choco[i] = choco[i - 1] + 1;
else
choco[i] = 1;
}
}
foreach (int col in choco)
Console.Write(col + " ");
It was a wrong way to do it, here is the proper:
static void Main(string[] args)
{
int[] age = new int[13] { 2, 6, 1, 2, 9, 1, 1, 4, 9, 6, 3, 5, 1 };
int[] choco = new int[13];
int descendingLength;
for (int i = 0; i < age.Length; i++)
{
if (i < age.Length - 1)
{
if (age[i] > age[i + 1])
{
descendingLength = 1;
int j;
for (j = i; (j + 1) < age.Length && age[j] > age[j + 1]; j++)
descendingLength++;
if (i != 0 && choco[i - 1] >= descendingLength)
{
if (age[i - 1] == age[i])
choco[i] = choco[i - 1];
else
choco[i] = choco[i - 1] + 1;
i++;
descendingLength--;
}
while (descendingLength > 0)
{
choco[i] = descendingLength--;
i++;
}
i--;
}
else
if (i != 0 && age[i] > age[i - 1])
choco[i] = choco[i - 1] + 1;
else
choco[i] = 1;
}
else
{
if (age[i] > age[i - 1])
choco[i] = choco[i - 1] + 1;
else
choco[i] = 1;
}
}
foreach (int col in choco)
Console.Write(col + " ");
}
How's about implementing a series of compression algorithms (huffman, chunking, etc), each prefixing the encoding header information in a parseable way (IE: encrypting 'Message' with chunking -> [header:chunking]+chunking('Message') ) Using each of these algorithms, you could effectively search the space of all possible encoding applications to optimize the size of the message regardless the computational complexity. Convert the problem into a search problem. True, it would be EXTREMELY computationally expensive, but it would probably optimize the size of the message.
This would work great if you were not sending totally random data. But if you were sending totally random data you would not be able to compress it.
Let's say you had an algorithm that could compress totally random data into something smaller all the time. The resulting stream of bits would be totally random. So you would be able to compress it and so on until you only had 1 bit left.
Or think about in another way say I could send you one of 8 messages but they were 8 bytes long. We could agree on a code and I could send you 3 bits and then you could decode them. This would be great. But now say I could send you 2^(8*8) messages or all possible values of the 8 bytes well we would be out of luck. As there would need log2(2^(8*8)) = 8*8 bits required to specify which code I wanted to send.
This idea comes out of the field of information theory.
I have heard it postulated that alien civilizations that are reasonably advanced will send everything in a compressed from and as a result you won't be able to spot the pattern as the data will be totally random to those that don’t have the right codec. It is a bit more complex then that but basically once you compress it enough it becomes a totally random all patterns are possible and all are equally likely.
It is a nice concept and can help you think about it I wish I could explain it better it has helped me greatly.
import java.util.Stack;
class test{
public class InorderIterator {
Stack<Node> st = new Stack<Node>();
Node root;
Node nextNode = null;
public InorderIterator(Node root) {
this.root = root;
}
public boolean hasnext(){
if(nextNode != null) return true;
Node cur = null;
if(st == null) return false;
if(!st.empty())
cur = st.pop();
else{
cur = root;
}
while(true){
if(cur != null){
st.push(cur);
cur = cur.left;
}else{
if(!st.isEmpty()){
Node tmp = st.pop();
if(nextNode == null){
nextNode = tmp;
}
st.push(tmp.right);
tmp = tmp.right;
return true;
}else{
st= null;
return false;
}
}
}
}
public Node next(){
if(nextNode != null){
Node tmp = nextNode;
nextNode = null;
return tmp;
}
if(hasnext()){
Node tmp = nextNode;
nextNode = null;
return tmp;
}else{
new Exception("Element not found");
}
return nextNode;
}
}
class Node{
Node right;
Node left;
char value;
Node(){
this.left=null;
this.right=null;
}
}
public boolean sameInorder(Node root1,Node root2){
InorderIterator itr1 = new InorderIterator(root1);
InorderIterator itr2 = new InorderIterator(root2);
System.out.println(itr1.next());
while(itr1.hasnext() && itr2.hasnext()){
if(itr1.next().value != itr2.next().value){
return false;
}
}
if((!itr1.hasnext() && itr2.hasnext()) || (itr1.hasnext() && !itr2.hasnext())){
return false;
}
return true;
}
public static void main(String[] args){
test t=new test();
Node firstroot=t.new Node();
Node secondroot=t.new Node();
Node left=t.new Node();
Node right=t.new Node();
left.value='A';
right.value='C';
firstroot.value='B';
firstroot.left=left;
firstroot.right=right;
secondroot.value='A';
secondroot.left=null;
Node right1=t.new Node();
secondroot.right=right1;
right1.value='B';
Node right2=t.new Node();
right1.right=right2;
right2.value='C';
System.out.println(t.sameInorder(firstroot,secondroot));
}
}
import java.util.Stack;
class test{
public class InorderIterator {
Stack<Node> st = new Stack<Node>();
Node root;
Node nextNode = null;
public InorderIterator(Node root) {
this.root = root;
}
public boolean hasnext(){
if(nextNode != null) return true;
Node cur = null;
if(st == null) return false;
if(!st.empty())
cur = st.pop();
else{
cur = root;
}
while(true){
if(cur != null){
st.push(cur);
cur = cur.left;
}else{
if(!st.isEmpty()){
Node tmp = st.pop();
if(nextNode == null){
nextNode = tmp;
}
st.push(tmp.right);
tmp = tmp.right;
return true;
}else{
st= null;
return false;
}
}
}
}
public Node next(){
if(nextNode != null){
Node tmp = nextNode;
nextNode = null;
return tmp;
}
if(hasnext()){
Node tmp = nextNode;
nextNode = null;
return tmp;
}else{
new Exception("Element not found");
}
return nextNode;
}
}
class Node{
Node right;
Node left;
char value;
Node(){
this.left=null;
this.right=null;
}
}
public boolean sameInorder(Node root1,Node root2){
InorderIterator itr1 = new InorderIterator(root1);
InorderIterator itr2 = new InorderIterator(root2);
System.out.println(itr1.next());
while(itr1.hasnext() && itr2.hasnext()){
if(itr1.next().value != itr2.next().value){
return false;
}
}
if((!itr1.hasnext() && itr2.hasnext()) || (itr1.hasnext() && !itr2.hasnext())){
return false;
}
return true;
}
public static void main(String[] args){
test t=new test();
Node firstroot=t.new Node();
Node secondroot=t.new Node();
Node left=t.new Node();
Node right=t.new Node();
left.value='A';
right.value='C';
firstroot.value='B';
firstroot.left=left;
firstroot.right=right;
secondroot.value='A';
secondroot.left=null;
Node right1=t.new Node();
secondroot.right=right1;
right1.value='B';
Node right2=t.new Node();
right1.right=right2;
right2.value='C';
System.out.println(t.sameInorder(firstroot,secondroot));
}
}
Following is my solution in O(n):
/**
* Created by sky on 5/11/15.
*/
public class DistributeChocolate {
public static void main(String[] args) {
int[] kids = new int[] {2, 6, 1, 2, 9, 1, 1, 4, 9, 6, 3, 5, 1};
int[] choco = new int[kids.length];
int saved = 1;
for (int i = 0; i < kids.length; i++) {
if (i == 0) {
choco[i] = saved;
continue;
}
if (kids[i] <= kids[i - 1]) {
saved = 1;
choco[i] = saved;
} else {
choco[i] = ++saved;
}
}
for (int i = 0; i < choco.length; i++) {
if (i > 0) System.out.print(" ");
System.out.print(choco[i]);
}
System.out.println();
}
}
Appreciate your effort BUT,
please try with below input which is violating law.
kids : 2, 6, 1, 3, 2, 1, 9
choc: 1, 2, 1, 2, 1, 1, 2
2nd kid of age 2 years should get more than younger(1 year) next to him
please try
Either they wanted an open ended discussion or you omitted something. If the task is to compress a completely random string of bits there is no loss less algorithm possible.
- Dr ADM May 12, 2015if all combinations of 1s a and 0s are possible and all are equally likely then you are stuck. You have 2^n possible states so you need log2(2^n) to store it.
If less than 2^(n-1) states are possible you can send enough bits to reconstruct the n bits in less than n bits.
If some states are common and others are uncommon you can compress to a variable length string. Say 2^(n-m) states happen x fraction of the time then you can put one bit at the front if it is one you sent the compressed version taking 1 + log2(2^(n-m) x of the time.
If it is an unusual sequence in the (1-x) portion of the probability space you set the first bit the other way and send 1+log2(2^n) bits.
You only need a few bits to send the common sequences and the same number to send the uncommon ones but you need 1 bit extra to specify which regime you are in.
On average you will send 1 + log2(2^(n-m) x + 1+log2(2^n)(x-1) bits or
1+(n-m) * x + n * (x-1) if x is close to 1 you are in luck.
Generally compression algorithms look at small portions of the file at a time and different combinations of bits have a wide variety of distributions. If you were compressing English on a letter by letter basis you would find that for most texts e and a is more common than x and q. You could compress on the word basis or even compress phrases. You might compress the file by turning it into a list of numbers referring to a dictionary of English words. You could throw all letters into the dictionary so that you can spell out words when you run into words you can’t find in your dictionary. Obviously if you were using 16 or 24 bit numbers to index into your word dictionary, when you hit words you have to spell out you would use more space when if you had just spelled everything out with 8 bit letters. But you would save space when compressing longer words.
Huffman coding is a similar algorithm that is much more general and generally more efficient but harder to explain here.
Depending on the type of data you are compressing both the compressor and decompressor will need a dictionary of some kind. Often the advantages of coming up with a custom dictionary for the particular file are so great it makes sense to append the dictionary as part of the compressed file rather than using a dictionary you store in the programs themselves though.
Other documents and messages have other patterns.
Bit map images of line drawings for instance can be compressed using essentially an algorithmic dictionary. An algorithm called run length encoding describes the document in terms of how many pixels are black and then how many pixels are white as you raster across the image.
Computer languages of course will often have very limited vocabularies and grammars that can permit other specialized compression techniques.
I believe general purpose compressors will try a number of approaches and then go with the best one. I think some algorithms may try a lossy algorithm and then compute the errors and try to compress them though I am not certain if this is actually used for lossless compression.