Interview Question


Country: South Africa




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

int main()
{
    int firstK = 0, secondK = 0, thirdK= 0, fourthK = 0, tryNo = 0;
    clock_t start = clock();
    for(int h = 0 ; h < 10 ; h++)
    {
        for(int t = 0 ; t < 10 ; t++)
        {
            if(t==h || ((2*h + 2*t) % 10) != h)
                continue;
            firstK = (2*h + 2*t) / 10;
            for(int s = 0 ; s < 10 ; s++)
            {
                if(s==t || s==h)
                    continue;
                if(((2*s + 2*t + firstK) % 10) != t)
                    continue;
                secondK = (2*s + 2*t + firstK) / 10;
                for(int r = 0 ; r < 10 ; r++)
                {
                    if(r==t || r==h || r==s)
                        continue;
                    for(int u = 0 ; u < 10 ; u++)
                    {
                        if(u==t || u==h || u==s || u==r)
                            continue;
                        for(int a = 0 ; a < 10 ; a++)
                        {
                            if(a==t || a==h || a==s || a==r || a==u)
                                continue;
                            for(int e = 0 ; e < 10 ; e++)
                            {
                                if(e==t || e==h || e==s || e==r || e==u || e==a)
                                    continue;
                                if(((r+u+a+e+secondK) % 10) != r)
                                    continue;
                                thirdK = (r+u+a+e+secondK) / 10;
                                for(int o = 0 ; o < 10 ; o++)
                                {
                                    if(o==t || o==h || o==s || o==r || o==u || o==a || o==e)
                                        continue;
                                    for(int w = 0 ; w < 10 ; w++)
                                    {
                                        if(w==t || w==h || w==s || w==r || w==u || w==a || w==e || w==o)
                                            continue;
                                        if(((2*o + e + w + thirdK) % 10) != a)
                                            continue;
                                        fourthK = (2*o + e + w + thirdK) / 10;
                                        for(int n = 0 ; n < 10 ; n++)
                                        {
                                            if(n==t || n==h || n==s || n==r || n==u || n==a || n==e || n==o || n==w)
                                                continue;
                                            if((n+s+fourthK)!= e)
                                                continue;
                                            cout << "Solution: " << tryNo++ << endl;
                                            cout << n << o << r << t <<  h << endl;
                                            cout << s << o << u << t <<  h << endl;
                                            cout << " " << e << a << s << t << endl;
                                            cout << " " << w << e << s << t << endl;
                                            cout << e << a << r << t <<  h << endl << endl;
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }

    clock_t end = clock();
    cout << "time: " << double(end-start)/CLOCKS_PER_SEC;
    return 0;
}

- md.etemad September 21, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <time.h>

#if 0

Logic

N O R T H  	+
  E A S T   +
S O U T H 	+
  W E S T 	=

E A R T H

n1 = 2*(H + T)

n1%10 = H

n2 = 2*(T + S) + n1/10

n2%10 = T

n3 = (R + A + U + E) + n2/10

n3%10 = R

n4 = (2*O + E + W) + n3/10

n4%10 = A

n5 = N + S + n4/10

n5 = E

#endif

bool
choose_ow(int *O, int *W, int *N, int S, int A, int E, int n3, uint8_t used[])
{
	int o, w, n;
	int n4, n5;

	for (o=*O; o<10; o++) {

		if (used[o]) continue;

		used[o] = 1;
		*O = o;
		for (w=*W; w<10; w++) {

			if (used[w]) continue;

			n4 = (o * 2) + E + w + n3/10;

			if (n4%10 != A) continue;

			used[w] = 1;
			*W = w;

			for (n=*N; n<10; n++) {

				if (used[n]) continue;

				n5 = n + S + n4/10;

				if (n5 != E) {
					continue;
				}

				used[n] = 1;
				*N = n;
				return TRUE;

			} // N
			if (n==10) {
				used[w] = 0;
			}
		} // W
		if (w==10) {
			used[o] = 0;
		}
	} // O
	return FALSE;
}


bool
choose_raue (int *R, int *A, int *U, int *E, int n2, uint8_t used[])
{
	int r, a, u, e;
	int n3;

	for (r=*R; r<10; r++) {
		if (used[r]) continue;

		used[r] = 1;
		*R = r;
		for (a=*A; a<10; a++) {
			if (used[a]) continue;

			used[a] = 1;
			*A = a;
			for (u=*U; u<10; u++) {
				if (used[u])  continue;

				used[u] = 1;
				*U = u;
				for (e=*E; e<10; e++) {
					if (used[e]) continue;

					n3 = (r + a + e + u) + n2/10;

					if (n3%10 == r) {
						used[e] = 1;
						*E = e;
						return TRUE;
					}
				} // E
				if (e==10) {
					used[u] = 0;
				}
			} // U
			if (u==10) {
				used[a] = 0;
			}
		} // A
		if (a==10) {
			used[r] = 0;
		}
	}
	return FALSE;
}


int
main ()
{
	uint8_t used[10];
	int n1, n2, n3, n4, n5;
	int H, T, S, R, A, W, E, O, N, U;
	bool found = FALSE;
	clock_t start, end;
	double cpu_time_used;

	start = clock();

	H = T = S = R = A = W = E = O = N = U = 0;

	for (H=0; H<10; H++) {

		memset(used, 0, sizeof(used));
		used[H] = 1;

		for (T = 0; T<10; T++) {

			if (used[T]) continue;

			n1 = 2 * (H + T) ;
			if ((n1%10) != H) {
				continue;
			}
			used[T] = 1;

			for (S=0; S<10; S++) {
				if (used[S]) continue;

				n2 = (2 * (T + S)) + n1/10;

				if (n2%10 != T) continue;

				used[S] = 1;
				R = A = U = E = 0;

raue:
				if (choose_raue(&R, &A, &U, &E, n2, used) == FALSE) {
					used[S] = 0;
					continue;
				}

				n3 = (R + A + U + E) + n2/10;

				O = W = N = 0;

				if (choose_ow(&O, &W, &N, S, A, E, n3, used) == FALSE) {
					used[R] = used[A] = used[U] = used[E] = 0;
					E++;
					goto raue;
				} else { // choose_owns
					printf("Found the values: H %d, T %d, S %d, R %d, A %d, W %d, E %d, O %d, N %d, U %d\n",
						H, T, S, R, A, W, E, O, N, U);
					S = T = 10;
				}

			} // S

			if (S == 10) {
				used[T] = 0;
			}
		} // T

		if (T == 10) {
			used[H] = 0;
		}

	} // H

	end = clock();


	cpu_time_used = ((double) (end - start) * 1000) / CLOCKS_PER_SEC;

	printf("%lfmsec count %d\n", cpu_time_used);

	return 0;
}

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

/*
 */

 #include "basic.h"

#include <time.h>

#if 0

N O R T H  	+
  E A S T   +
S O U T H 	+
  W E S T 	=

E A R T H

n1 = 2*(H + T)

n1%10 = H

n2 = 2*(T + S) + n1/10

n2%10 = T

n3 = (R + A + U + E) + n2/10

n3%10 = R

n4 = (2*O + E + W) + n3/10

n4%10 = A

n5 = N + S + n4/10

n5 = E

#endif

bool
choose_ow(int *O, int *W, int *N, int S, int A, int E, int n3, uint8_t used[])
{
	int o, w, n;
	int n4, n5;

	for (o=*O; o<10; o++) {

		if (used[o]) continue;

		used[o] = 1;
		*O = o;
		for (w=*W; w<10; w++) {

			if (used[w]) continue;

			n4 = (o * 2) + E + w + n3/10;

			if (n4%10 != A) continue;

			used[w] = 1;
			*W = w;

			for (n=*N; n<10; n++) {

				if (used[n]) continue;

				n5 = n + S + n4/10;

				if (n5 != E) {
					continue;
				}

				used[n] = 1;
				*N = n;
				return TRUE;

			} // N
			if (n==10) {
				used[w] = 0;
			}
		} // W
		if (w==10) {
			used[o] = 0;
		}
	} // O
	return FALSE;
}


bool
choose_raue (int *R, int *A, int *U, int *E, int n2, uint8_t used[])
{
	int r, a, u, e;
	int n3;

	for (r=*R; r<10; r++) {
		if (used[r]) continue;

		used[r] = 1;
		*R = r;
		for (a=*A; a<10; a++) {
			if (used[a]) continue;

			used[a] = 1;
			*A = a;
			for (u=*U; u<10; u++) {
				if (used[u])  continue;

				used[u] = 1;
				*U = u;
				for (e=*E; e<10; e++) {
					if (used[e]) continue;

					n3 = (r + a + e + u) + n2/10;

					if (n3%10 == r) {
						used[e] = 1;
						*E = e;
						return TRUE;
					}
				} // E
				if (e==10) {
					used[u] = 0;
				}
			} // U
			if (u==10) {
				used[a] = 0;
			}
		} // A
		if (a==10) {
			used[r] = 0;
		}
	}
	return FALSE;
}


int
main ()
{
	uint8_t used[10];
	int n1, n2, n3, n4, n5;
	int H, T, S, R, A, W, E, O, N, U;
	bool found = FALSE;
	clock_t start, end;
	double cpu_time_used;

	start = clock();

	H = T = S = R = A = W = E = O = N = U = 0;

	for (H=0; H<10; H++) {

		memset(used, 0, sizeof(used));
		used[H] = 1;

		for (T = 0; T<10; T++) {

			if (used[T]) continue;

			n1 = 2 * (H + T) ;
			if ((n1%10) != H) {
				continue;
			}
			used[T] = 1;

			for (S=0; S<10; S++) {
				if (used[S]) continue;

				n2 = (2 * (T + S)) + n1/10;

				if (n2%10 != T) continue;

				used[S] = 1;
				R = A = U = E = 0;

raue:
				if (choose_raue(&R, &A, &U, &E, n2, used) == FALSE) {
					used[S] = 0;
					continue;
				}

				n3 = (R + A + U + E) + n2/10;

				O = W = N = 0;

				if (choose_ow(&O, &W, &N, S, A, E, n3, used) == FALSE) {
					used[R] = used[A] = used[U] = used[E] = 0;
					E++;
					goto raue;
				} else { // choose_owns
					printf("Found the values: H %d, T %d, S %d, R %d, A %d, W %d, E %d, O %d, N %d, U %d\n",
						H, T, S, R, A, W, E, O, N, U);
					S = T = 10;
				}

			} // S

			if (S == 10) {
				used[T] = 0;
			}
		} // T

		if (T == 10) {
			used[H] = 0;
		}

	} // H

	end = clock();


	cpu_time_used = ((double) (end - start) * 1000) / CLOCKS_PER_SEC;

	printf("%lfmsec count %d\n", cpu_time_used);

	return 0;
}

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

/*
'NORTH' + 
'0EAST' + 
'0WEST' + 
'SOUTH' 
===========
'EARTH'
2(H + T) % 10 = H // constraint 1 
(2(T + S) + 2(H+T)/5) % 10 = T constraint 2 
Solving these two reduces the problem from 10! into 7! Baam.
That is heavily reduced.
Now let's see how H, T, S are there.
*/
def is_valid( map ){
  north = map.h + 10 * ( map.t  + 10 * ( map.r  + 10* ( map.o + 10 * map.n )))
   east = map.t + 10 * ( map.s  + 10 * ( map.a  + 10* ( map.e ) ) )
   west = map.t + 10 * ( map.s  + 10 * ( map.e  + 10* ( map.w ) ) )
  south = map.h + 10 * ( map.t  + 10 * ( map.u  + 10* ( map.o + 10 * map.s ) ) )
  earth = map.h + 10 * ( map.t  + 10 * ( map.r  + 10* ( map.a + 10 * map.e ) ) )
  earth == ( north + east + west + south )
}

digits = [0:10].asList
// find constraint 1 
c1_pairs = join(digits,digits) where { ($.l != $.r) && ( $.l == 2 * sum($.o) % 10 )  }
// get next set of constrant 2 ?
c2_tuples = join(digits,c1_pairs) where { 
   #(H,T) = $.r 
   S = $.l 
   S !@ $.r && ( ( 2 *( T + S ) + 2*(H+T)/10 ) % 10 == T )
} as { d = { 'h' : $.r.0 , 's' : $.l , 't' : $.r.1 }  }
rest_of_lettrers = [ 'a' , 'e' , 'n', 'o', 'r', 'u' ,'w' ]
// now that we have established the 3 items, 
// rest 7 has to be chosen who are not ... in the group
for ( t : c2_tuples ) {
  other_digits = digits - t.values 
  // now permuatate the other_digits 
  for ( p : perm( other_digits ) ){
    // assign into map 
    d = dict( rest_of_lettrers ) as { [ $.o, p[$.i] ] }
    d |= t // the whole map 
    if ( is_valid( d ) ){
        println( d )
    }
  }
}

Producing...

{a=1, r=6, s=0, t=8, e=5, u=3, w=7, h=4, n=2, o=9}
{a=2, r=5, s=0, t=8, e=6, u=1, w=7, h=4, n=3, o=9}
{a=3, r=1, s=0, t=8, e=7, u=9, w=2, h=4, n=5, o=6}
{a=3, r=5, s=0, t=8, e=7, u=9, w=2, h=4, n=6, o=1}
{a=0, r=5, s=1, t=6, e=7, u=2, w=4, h=8, n=3, o=9}
{a=3, r=2, s=1, t=6, e=7, u=9, w=4, h=8, n=5, o=0}
{a=3, r=4, s=1, t=6, e=7, u=9, w=0, h=8, n=5, o=2}
{a=9, r=5, s=1, t=6, e=3, u=7, w=4, h=8, n=2, o=0}
{a=9, r=0, s=1, t=6, e=7, u=3, w=2, h=8, n=5, o=4}
{a=3, r=1, s=2, t=5, e=9, u=7, w=6, h=0, n=4, o=8}
{a=4, r=1, s=2, t=5, e=8, u=7, w=6, h=0, n=3, o=9}
{a=7, r=8, s=2, t=5, e=9, u=3, w=4, h=0, n=6, o=1}
{a=8, r=9, s=2, t=5, e=4, u=7, w=6, h=0, n=1, o=3}
{a=8, r=6, s=2, t=5, e=7, u=4, w=1, h=0, n=3, o=9}
{a=9, r=8, s=2, t=5, e=4, u=6, w=7, h=0, n=1, o=3}
{a=9, r=6, s=2, t=5, e=7, u=3, w=8, h=0, n=4, o=1}
{a=9, r=6, s=4, t=1, e=7, u=3, w=0, h=8, n=2, o=5}
{a=2, r=3, s=5, t=8, e=7, u=9, w=1, h=4, n=0, o=6}
{a=2, r=6, s=5, t=8, e=7, u=9, w=3, h=4, n=1, o=0}
{a=2, r=6, s=5, t=8, e=9, u=7, w=1, h=4, n=3, o=0}
{a=3, r=7, s=5, t=8, e=6, u=9, w=1, h=4, n=0, o=2}
{a=6, r=0, s=5, t=8, e=9, u=3, w=1, h=4, n=2, o=7}
{a=7, r=1, s=5, t=8, e=9, u=2, w=6, h=4, n=3, o=0}
{a=9, r=1, s=5, t=8, e=6, u=3, w=7, h=4, n=0, o=2}

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

require 'ostruct'
require 'benchmark'
k = Benchmark.measure do
  ps = []
  (0..9).each do |h|
    (0..9).each do |t|
      if (temp = h + (2 * t)) % 10 == 0
        k = (temp / 10)
        ot = OpenStruct.new
        ot.h = h
        ot.t = t
        ot.k = k
        ps << ot
      end
    end
  end
  
  new_ps = []
  ps.each do |ps_n|
    (0..9).each do |s|
      if (temp = ps_n.t + (2 * s) + ps_n.k) % 10 == 0
        l = (temp / 10)
        ot = ps_n.clone
        ot.s = s
        ot.l = l
        new_ps << ot
      end
    end
  end
  ps = new_ps
  new_ps = []
  ps.each do |ps_n|
    (0..9).each do |a|
      (0..9).each do |u|
        (0..9).each do |e|
          if (temp = a + u + e + ps_n.l) % 10 == 0
            m = temp / 10
            ot = ps_n.clone
            ot.a = a
            ot.u = u
            ot.e = e
            ot.m = m
            new_ps << ot
          end
        end
      end
    end
  end
  ps = new_ps
  new_ps = []
  
  
  ps.each do |ps_n|
    (0..9).each do |o|
      (0..9).each do |w|
        if (temp =  (2 * o) + ps_n.e + w + ps_n.m - ps_n.a ) % 10 == 0
          q = temp / 10
          ot = ps_n.clone
          ot.o = o
          ot.w = w
          ot.q = q
          new_ps << ot
        end
      end
    end
  end
  ps = new_ps
  new_ps = []
  
  ps.each do |ps_n|
    (0..9).each do |n|
      if (temp = n + ps_n.s + ps_n.q) == ps_n.e
        ot = ps_n.clone
        ot.n = n
        new_ps << ot
      end
    end
  end
  ps = new_ps
  puts ps.size * 10 # multiplied by 10 as for each 0 <= R <= 9, the problem condition satisfies.
end

- naresh.dwivedi1987 September 20, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote
Solution using C#: {{{ private void Calculate() { for (int ih = 0; ih < 10; ih++) { for (int it = 0; it < 10; it++) { int r1 = 2 * ih + 2 * it; if (r1 % 10 != ih) continue; for (int i_s = 0; i_s < 10; i_s++) { int r2 = 2 * it + 2 * i_s + r1 / 10; if (r2 % 10 != it) continue; for (int ir = 0; ir < 10; ir++) for (int ia = 0; ia < 10; ia++) for (int iu = 0; iu < 10; iu++) for (int ie = 0; ie < 10; ie++) { int r3 = ir + ia + iu + ie + r2 / 10; if (r3 % 10 != ir) continue; for (int io = 0; io < 10; io++) for (int iw = 0; iw < 10; iw++) { int r4 = 2 * io + ie + iw + r3 / 10; if (r4 % 10 != ia) continue; for (int i_n = 0; i_n < 10; i_n++) { int r5 = i_n + i_s + r4 / 10; if (r5 % 10 == ie) { //store value nums.Add(new NumberSet(ih, it, i_s, ir, ia, iu, ie, io, iw, i_n)); } } } } } } } } - Daniel September 21, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void main(String[] args) {
		String s1 = "north";
		String s2 = "east";
		String s3 = "west";
		String s4 = "south";
		String result = "earth";

		long s = System.currentTimeMillis();
		solve(s1, s2, s3, s4, result);
		System.out.println("Time: " + (System.currentTimeMillis()-s));
	}

	public static void solve(String s1, String s2, String s3, String s4, String result) {
		Map<Integer, Map<Character, Integer>> map = new HashMap<Integer, Map<Character, Integer>>();

		s1 = reverse(s1);
		s2 = reverse(s2);
		s3 = reverse(s3);
		s4 = reverse(s4);
		result = reverse(result);

		for (int i = 0; i < 5; i++) {
			Map<Character, Integer> t = new HashMap<Character, Integer>();
			if (i < s1.length() && t.get((Character) s1.charAt(i)) != null) {
				int c = t.get((Character) s1.charAt(i));
				t.put((Character) s1.charAt(i), c + 1);
			} else if(i < s1.length()){
				t.put((Character) s1.charAt(i), 1);
			}
			
			if (i < s2.length() && t.get((Character) s2.charAt(i)) != null) {
				int c = t.get((Character) s2.charAt(i));
				t.put((Character) s2.charAt(i), c + 1);
			} else if(i < s2.length()){
				t.put((Character) s2.charAt(i), 1);
			}
			
			if (i < s3.length() && t.get((Character) s3.charAt(i)) != null) {
				int c = t.get((Character) s3.charAt(i));
				t.put((Character) s3.charAt(i), c + 1);
			} else if(i < s3.length()) {
				t.put((Character) s3.charAt(i), 1);
			}
			
			if (i < s4.length() && t.get((Character) s4.charAt(i)) != null) {
				int c = t.get((Character) s4.charAt(i));
				t.put((Character) s4.charAt(i), c + 1);
			} else if(i < s4.length()) {
				t.put((Character) s4.charAt(i), 1);
			}
			map.put(i, t);
		}

		int[] nos = new int[10];
		for (int i = 0; i < 10; i++)
			nos[i] = -1;

		int[] alph = new int[26];
		for (int i = 0; i < 26; i++)
			alph[i] = Integer.MAX_VALUE;

		int n = solutions(map, result.toCharArray(), 0, nos, alph, 0, 0, new ArrayList<String>());
		System.out.println("Total = " + n);
	}

	public static int solutions(Map<Integer, Map<Character, Integer>> map, char[] res, int i, int[] nos, int[] alph,
			int carry, int count, List<String> list) {
	
		if (i == map.size()) {
			if(carry == 0){
				String str = ""; 
				for(int l = 0; l < 26; l++){
					if(alph[l] != Integer.MAX_VALUE){
						str += ((char)('a'+l)) + ":" + alph[l] + " ";
					}
				}
				if(!list.contains(str)){
					list.add(str);
					//System.out.println(str);
					return count + 1;
				}
				return count;
			}else{
				return count;
			}
		}

		Map<Character, Integer> m = map.get(i);
		int p = 0;
		for (Map.Entry<Character, Integer> en : m.entrySet()) {
			char c = en.getKey();
			int mul = en.getValue();
			
			if (alph[c - 'a'] != Integer.MAX_VALUE) {
				p += mul * alph[c - 'a'];
			} else {
				for (int g = 0; g < nos.length; g++) {
					if (nos[g] == -1) {
						nos[g] = g;
						alph[c - 'a'] = g;
						count = solutions(map, res, i, nos, alph, carry, count, list);
						alph[c - 'a'] =  Integer.MAX_VALUE;
						nos[g] = -1;
					}
				}
			}
		}

		for(int q = 0; q <= i; q++){
			Map<Character, Integer> mh = map.get(q);
			for (Map.Entry<Character, Integer> en : mh.entrySet()) {
				char c = en.getKey();
				if(alph[c -'a'] == Integer.MAX_VALUE)
					return count;
			}
		}
			
			
		p += carry;
		
		if (alph[res[i] - 'a'] != Integer.MAX_VALUE && (p % 10) == alph[res[i] - 'a']) {
			count = solutions(map, res, i + 1, nos, alph, (p / 10), count, list);
		} else if (alph[res[i] - 'a'] != Integer.MAX_VALUE && (p % 10) != alph[res[i] - 'a']) {
			return count;
		} else if (alph[res[i] - 'a'] == Integer.MAX_VALUE && nos[p % 10] == -1) {
			alph[res[i] - 'a'] = (p % 10);
			nos[p % 10] = (p % 10);
			count = solutions(map, res, i + 1, nos, alph, (p / 10), count, list);
			alph[res[i] - 'a'] = Integer.MAX_VALUE;
			nos[p % 10] = -1;
		} else if (alph[res[i] - 'a'] == Integer.MAX_VALUE && nos[p % 10] != -1) {
			return count;
		}
		return count;
	}

	public static String reverse(String str) {
		char[] arr = str.toCharArray();
		String rev = "";

		for (int i = arr.length - 1; i >= 0; i--)
			rev += arr[i];

		return rev;
	}

- sudip.innovates September 22, 2017 | 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