Data Structure Questions and Answers – Decimal to Binary using Stacks

«
»

This set of Data Structure Interview Questions and Answers for Experienced people focuses on “Decimal to Binary using Stacks”.

1. Express -15 as a 6-bit signed binary number.
a) 001111
b) 101111
c) 101110
d) 001110
View Answer

Answer: b
Explanation: The first 4 1s from the right represent the number 15, 2 more bits are padded to make it 6 digits and the leftmost bit is a 1 to represent that it is -15.

2. Which of the following code snippet is used to convert decimal to binary numbers?
a)

public void convertBinary(int num)
{
     int bin[] = new int[50];
     int index = 0;
     while(num > 0)
     {
       bin[index++] = num%2;
       num = num/2;
     }
     for(int i = index-1;i >= 0;i--)
     {
       System.out.print(bin[i]);
     }
}

b)

advertisement
public void convertBinary(int num)
{
     int bin[] = new int[50];
     int index = 0;
     while(num > 0)
     {
       bin[++index] = num%2;
       num = num/2;
     }
     for(int i = index-1;i >= 0;i--)
     {
       System.out.print(bin[i]);
     }
}

c)

advertisement
advertisement
public void convertBinary(int num)
{
     int bin[] = new int[50];
     int index = 0;
     while(num > 0)
     {
         bin[index++] = num/2;
         num = num%2;
     }
     for(int i = index-1;i >= 0;i--)
     {
         System.out.print(bin[i]);
     }
}

d)

advertisement
public void convertBinary(int num)
 {
     int bin[] = new int[50];
     int index = 0;
     while(num > 0)
     {
         bin[++index] = num/2;
         num = num%2;
     }
     for(int i = index-1;i >= 0;i--)
     {
         System.out.print(bin[i]);
     }
  }
View Answer
Answer: a
Explanation: Take the modulus by 2 of the number and store in an array while halving the number during each iteration and then display the contents of the array.
 
 
3. Which is the predefined method available in Java to convert decimal to binary numbers?
a) toBinaryInteger(int)
b) toBinaryValue(int)
c) toBinaryNumber(int)
d) toBinaryString(int)
View Answer
Answer: d
Explanation: The method toBinaryString() takes an integer argument and is defined in java.lang package. Usage is java.lang.Integer.toBinaryString(int) this returns the string representation of the unsigned integer value.

4. Using stacks, how to obtain the binary representation of the number?
a)

advertisement
public void convertBinary(int num)
{
    Stack<Integer> stack = new Stack<Integer>();
    while (num != 0)
    {
        int digit = num / 2;
        stack.push(digit);
        num = num % 2;
    } 
    System.out.print("\nBinary representation is:");
    while (!(stack.isEmpty() ))
    {
        System.out.print(stack.pop());
    }
 }

b)

advertisement
public void convertBinary(int num)
{
    Stack<Integer> stack = new Stack<Integer>();
    while (num != 0)
    {
        int digit = num % 2;
        stack.push(digit);
    } 
    System.out.print("\nBinary representation is:");
    while (!(stack.isEmpty() ))
    {
        System.out.print(stack.pop());
    }
 }

c)

public void convertBinary(int num)
{
    Stack<Integer> stack = new Stack<Integer>();
    while (num != 0)
    {
        int digit = num % 2;
        stack.push(digit);
        num = num / 2;
    } 
    System.out.print("\nBinary representation is:");
    while (!(stack.isEmpty() ))
    {
        System.out.print(stack.pop());
    }
 }

d)

public void convertBinary(int num)
{
    Stack<Integer> stack = new Stack<Integer>();
    while (num != 0)
    {
        int digit = num % 2;
        stack.push(digit%2);
        num = num / 2;
    } 
    System.out.print("\nBinary representation is:");
    while (!(stack.isEmpty() ))
    {
        System.out.print(stack.pop());
    }
 }
View Answer
Answer: c
Explanation: Here instead of adding the digits to an array, you push it into a stack and while printing, pop it from the stack.
 
 
5. What is the time complexity for converting decimal to binary numbers?
a) O(1)
b) O(n)
c) O(logn)
d) O(nlogn)
View Answer
Answer: c
Explanation: Since each time you are halving the number, it can be related to that of a binary search algorithm, hence the complexity is O(logn).

6. Write a piece of code which returns true if the string contains balanced parenthesis, false otherwise.
a)

public boolean isBalanced(String exp)
{
	int len = exp.length();
	Stack<Integer> stk = new Stack<Integer>();
	for(int i = 0; i < len; i++)
        {
		char ch = exp.charAt(i);
                if (ch == '(')
                stk.push(i);
                else if (ch == ')')
                {
			if(stk.peek() == null)
                        {
				return false;
			}
			stk.pop();
		}
	}
	return true;
}

b)

public boolean isBalanced(String exp)
{
	int len = exp.length();
	Stack<Integer> stk = new Stack<Integer>();
	for(int i = 0; i < len; i++)
            {
		char ch = exp.charAt(i);
                if (ch == '(')
                stk.push(i);
                else if (ch == ')')
                {
			if(stk.peek() != null)
                        {
				return true;
			}
			stk.pop();
		}
	}
	return false;
  }

c)

public boolean isBalanced(String exp)
{
	int len = exp.length();
	Stack<Integer> stk = new Stack<Integer>();
	for(int i = 0; i < len; i++)
        {
	       char ch = exp.charAt(i);
               if (ch == ')')
               stk.push(i);
               else if (ch == '(')
               {
			if(stk.peek() == null)
                        {
				return false;
			}
			stk.pop();
		}
	}
	return true;
}

d)

public boolean isBalanced(String exp)
{
	int len = exp.length();
	Stack<Integer> stk = new Stack<Integer>();
	for(int i = 0; i < len; i++)
        {
		char ch = exp.charAt(i);
                if (ch == '(')
                stk.push(i);
                else if (ch == ')')
                {
			if(stk.peek() != null)
                        {
				return false;
			}
			stk.pop();
		}
	}
	return true;
  }
View Answer
Answer: a
Explanation: Whenever a ‘(‘ is encountered, push it into the stack, and when a ‘)’ is encountered check the top of the stack to see if there is a matching ‘(‘, if not return false, continue this till the entire string is processed and then return true.
 
 
7. What is the time complexity of the following code?

public boolean isBalanced(String exp)
{
	int len = exp.length();
	Stack<Integer> stk = new Stack<Integer>();
	for(int i = 0; i < len; i++)
        {
		char ch = exp.charAt(i);
                if (ch == '(')
                stk.push(i);
                else if (ch == ')')
                {
			if(stk.peek() == null)
                        {
				return false;
			}
			stk.pop();
		}
	}
	return true;
}

a) O(logn)
b) O(n)
c) O(1)
d) O(nlogn)
View Answer

Answer: b
Explanation: All the characters in the string have to be processed, hence the complexity is O(n).

8. Which of the following program prints the index of every matching parenthesis?
a)

public void dispIndex(String exp)
{
    Stack<Integer> stk = new Stack<Integer>();
    for (int i = 0; i < len; i++)
    {    
        char ch = exp.charAt(i);
        if (ch == '(')
        stk.push(i);
        else if (ch == ')')
        {
          try
          {
            int p = stk.pop() + 1;
            System.out.println("')' at index "+(i+1)+" matched with ')' at index "+p);
          }
          catch(Exception e)
          {
             System.out.println("')' at index "+(i+1)+" is unmatched");
          }
        }            
    }
    while (!stk.isEmpty() )
    System.out.println("'(' at index "+(stk.pop() +1)+" is unmatched");
}

b)

public void dispIndex(String exp)
{
    Stack<Integer> stk = new Stack<Integer>();
    for (int i = 0; i < len; i++)
    {    
        char ch = exp.charAt(i);
        if (ch == '(')
        stk.push(i);
        else if (ch == ')')
        {
           try
           {
             int p = stk.pop() + 1;
             System.out.println("')' at index "+(i)+" matched with ')' at index "+p);
           }
           catch(Exception e)
           {
              System.out.println("')' at index "+(i)+" is unmatched");
           }
        }            
    }
    while (!stk.isEmpty() )
    System.out.println("'(' at index "+(stk.pop() +1)+" is unmatched");
}

c)

public void dispIndex(String exp)
{
    Stack<Integer> stk = new Stack<Integer>();
    for (int i = 0; i < len; i++)
    {    
        char ch = exp.charAt(i);
        if (ch == ')')
        stk.push(i);
        else if (ch == '(')
        {
          try
          {
            int p = stk.pop() +1;
            System.out.println("')' at index "+(i+1)+" matched with ')' at index "+p);
          }
          catch(Exception e)
          {
             System.out.println("')' at index "+(i+1)+" is unmatched");
          }
        }            
    }
    while (!stk.isEmpty() )
    System.out.println("'(' at index "+(stk.pop() +1)+" is unmatched");
}

d)

public void dispIndex(String exp)
{
    Stack<Integer> stk = new Stack<Integer>();
    for (int i = 0; i < len; i++)
    {    
        char ch = exp.charAt(i);
        if (ch == ')')
        stk.push(i);
        else if (ch == '(')
        {
          try
          {
            int p = stk.pop();
            System.out.println("')' at index "+(i+1)+" matched with ')' at index "+p);
          }
          catch(Exception e)
          {
            System.out.println("')' at index "+(i+1)+" is unmatched");
          }
        }            
    }
    while (!stk.isEmpty() )
    System.out.println("'(' at index "+(stk.pop() +1)+" is unmatched");
}
View Answer
Answer: a
Explanation: Whenever a ‘(‘ is encountered, push the index of that character into the stack, so that whenever a corresponding ‘)’ is encountered, you can pop and print it.
 
 
Sanfoundry Global Education & Learning Series – Data Structure.

To practice all areas of Data Structure for Interviews, here is complete set of 1000+ Multiple Choice Questions and Answers.

Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!
advertisement
advertisement
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn | Youtube | Instagram | Facebook | Twitter