Microsoft Interview Question for SDE-2s


Country: United States
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void main(String args[]) throws Exception {
		int K = 3;
		System.out.println(isDivisibleByKInBase("1010100011", K, 2));
	}

	private static int isDivisibleByKInBase(String str, int K, int base) {
		char c[] = new StringBuilder(str).reverse().toString().toCharArray();
		int rem = 0;
		for (int i = 0; i < c.length; i++) {
			rem = ((((int) Math.pow(base, i) * Integer.parseInt("" + c[i])) % K) + rem) % K;
		}
		return rem;
	}

- koustav.adorable September 04, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Hi Koustav

Can you explain your algo?

- samwise.gamjee September 11, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think this should work.

Go over all the digits of the binary number and keep a count of the number of 1's in the even place and the number of 1;'s in the odd space.

Finally the difference between the even place 1's and the odd place 1's is the remainder..

Please correct me if you have a valid situation where the logic fails

- Sayantan Chowdhury September 12, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think this should work.

Go over all the digits one by one in the binary number given. As you scan the number, keep track of the count of even place 1's and odd place 1's.

Finally remainder will be odd count - even count. If -ve, remained is 3+ (-ve remainder)

- sayantanc85 September 12, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Time Complexity is O(n) where n is the length of input string.
	static boolean isDivisible(String input) {
                
                int noOfOnesAtOddPlace = 0;
                for(int index=0; index < input.length(); index++) {
                        if(index%2 == 0 && input.charAt(index) == '1') {
                                noOfOnesAtOddPlace--;
                        } else if(index%2 != 0 && input.charAt(index) == '1') {
                                noOfOnesAtOddPlace++;
                        }
                }
                
                return (noOfOnesAtOddPlace%3==0);
        }

- Kapil September 12, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

boolean isDivisible(String input, int n) {
	
	int remainder = 0;
	int size = input.length();
	for(int index = size-1; index >=0; index--) {
		if(input.charAt(index) == '1') {
			remainder = (2*remainder + 1) %n;
		} else {
			remainder = (2*remainder) %n;
		}
	}

	if(remainder%n==0) {
		return true;
	} else {
		return false;
	}

}

- Kapil September 17, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

geeksforgeeks.org/dfa-based-division/

- Kapil September 17, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<bits/stdc++.h>
using namespace std;
int main(){
	
string s;
 cin>>s;
 int len=s.length();
 // consider s[0] as msb and s[len-1] as lsb 
 
 int rem=0;
 for(int i=0;i<len;i++){
 	 if(s[i]=='0'){
 	 	rem=rem*2;
	  }else{
	  	rem=rem*2+1;
	  }
	  rem%=3;
	  
 }
  cout<<rem<<endl;
}

- deepdoc333 February 25, 2018 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More