Data Structure Questions and Answers – Decimal to Binary using Stacks

Uncategorized Computer Science & Engineering Data Structures & Algorithms

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

1. 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;
  }


Explanation: If a ‘(‘ is encountered, push it into the stack; if a ‘)’ is encountered, search the top of the stack for a corresponding ‘(‘; if not, return false; repeat until the entire string is processed; then return true.

2. 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)

Explanation: The complexity is O since all of the characters in the string must be processed (n).

3. 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");
}


Explanation: Push the index of that character into the stack whenever a ‘(‘ is encountered, so that you can pop and print it whenever a corresponding ‘)’ is encountered.

4. Express -15 as a 6-bit signed binary number.
A) 001111
B) 101111
C) 101110
D) 001110

Explanation: The number 15 is represented by the first four 1s from the right, two more bits are padded to make it six digits, and the leftmost bit is a 1 to indicate that it is -15.

5. 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)

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)

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)

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]);
     }
  }


Explanation: Take the number’s modulus by two and store it in an array, halving the number with each iteration, before displaying the contents of the array.
6. 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)

Explanation: The java.lang package specifies the method toBinaryString(), which takes an integer argument. The method java.lang.Integer.toBinaryString(int) returns the unsigned integer value’s string representation.

7. 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)

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());
    }
 }


Explanation: Instead of adding the digits to an array, you put them into a stack and then pop them out while printing.

8. What is the time complexity for converting decimal to binary numbers?

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

Explanation: Since you’re halving the number each time, it can be compared to a binary search algorithm, so the complexity is O. (logn).

The Stack’s push and pop operation can be used to convert a decimal number to a binary number. Now, Java has an inbuilt Stack class that can be used for our needs. Using stacks to convert a decimal number to a binary number: Using a stack that has been pre-defined. Start with the sum of 0 to convert a binary fraction to a decimal. Attach the next digit to the current total and divide the result by two. Continue until no more digits are left. The fraction 0.1011 is used as an example of such a conversion.

Leave a Reply

Your email address will not be published. Required fields are marked *